Размещение прямоугольников на поле

[Фенёк]

Привет. Тут такая задача: есть прямоугольное поле и в него надо суметь сложить некоторое количество прямоугольников так, чтобы они друг на друга не накладывались и а края не вылезали. Посмотрел тут алгоритмы упаковки, задачу о ранце и пр. - не похоже на то что нужно.

Мое предположение: при каждой постановке прямоугольника в области создавать список свободных прямоугольных областей. При постановке следующего, перебирать список полученных областей, в поисках той, чья площадь больше, либо равна площади устанавливаемого прямоугольника и переразбивать на области еще раз.

Надо велосипед изобретать или есть уже готовые алгоритмы?

[faraday]

да, идея правильная. алгоритмов упаковки атласов много гуглится, вот первый http://gamedevblogs.ru/blog/actionscript/906.html
это самый простой, есть и более продвинутые

[Фенёк]

Но мне не атласы паковать ) мне надо на рандом натыкать домиков на карту ) Ну, то есть мне нет необходимости оптимально их ужать, нужно чтобы они просто поместились друг друга не перекрывая

[Alex Lexcuk]

Тут описан интересный способ расположить прямоугольники на карте.
https://habrahabr.ru/post/275727/

[Фенёк]

Похоже плохо выразил мысль (

В общем, смотрите, есть какая-то ограниченная прямоугольная область. Есть прямоугольные домики, различных соотношений сторон. Задача в том, чтобы случайным образом расположить эти домики, но так, чтобы они не вылезли за пределы и не пересекали друг друга.

По моему алгоритму у меня появились еще пара дополнений (пока не знаю насколько соответствующих реальной жизни).

Я предполагаю, что каждый прямоугольник разбивает пространство вокруг не более чем на четыре прямоугольные области (слева, справа, сверху, снизу), ограниченные близлежащими прямоугольниками. На 1000 прямоугольников это будет уже 4000 областей, многие из которых вероятно будут дублировать друг друга. Поиски ближайших скорее всего потребуют работы по написанию двоичного дерева (чего мне хотелось бы избежать), плюс, мне кажется, что должен существовать какой-то механизм вставки, чтобы не перерасчитывать все-все области по новой, но у меня абсолютно 0 идей о том как это воплотить.

Мне кажется это задача лежащая где-то в области графов, но я очень плохо с ними знаком и даже не знаю в какую сторону посмотреть.

[Tails]

Попробуйте погуглить по запросу "Texture atlas algorithm".
Вот например: http://gamedev.stackexchange.com/questions/2829/texture-packing-algorithm

[Фенёк]

Господа, еще раз, задача НЕ на упаковку. Я вот даже иллюстрацию прикрепил.

1) Пустое поле
2) Поставили прямоугольник в ПРОИЗВОЛЬНОЕ место

Области A, B, C, D (да, они ПЕРЕСЕКАЮТСЯ) обозначают места, в которые можно поставить новый прямоугольник площадью меньшей чем площадь этой области.

Так вот, вопрос о том, как найти эти области наименьшими затратами. НЕ О ТОМ как упаковать сами прямоугольники таким образом, чтобы они занимали наименьшую площадь.

[Фенёк]

Еще раз привет, в этот раз я пришел к вам с более продуманным планом и более аккуратными картинками.

Вот как я вижу выполнение алгоритма (пока руками)

1) пустое поле
2) поставили новый прямоугольник
3) рассчитали 4 такие области в которых можно расположить новые прямоугольники в любом свободном месте
4) поставили новый прямоугольник
5) определили с какими уже существующими областями он пересекается и удалили эти области
6) рассчитали 5 новых областей в которых можно расположить новые прямоугольники в любом свободном месте

Собственно у меня вызывают вопросы пункты 3 и 6, потому что я не знаю КАК рассчитать эти области. То есть я не могу пока придумать алгоритм, который рассчитывал бы эти цветные области.

[Tails]

Вообщем, что то такое я набросал, вариант правда далёк от завершения.
Думаю, сперва лучше забить всё поле квадратами, а затем для каждой из сторон искать свободную площадь. В примере ищется площадь для верхней стороны квадратов.

Клик мышки - обновить:
Test.swf

Код:

package
{
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Rectangle;


/**
* Тест.
* @author Tails
*/
public class Main extends Sprite {

// Приват
private var _quadsTotal:uint; // Количество квадратов.
private var _space:Rectangle; // Размер мира.
private var _sprite:Sprite; // Рисунок результата.
private var _quads:Vector.<Rectangle>; // Рассекающие квадраты.
private var _result:Vector.<Rectangle>; // Полученные области.


public function Main() {
if (stage === null)
addEventListener(Event.ADDED_TO_STAGE, init);
else
init();
}
private function init(e:Event = null):void {
removeEventListener(Event.ADDED_TO_STAGE, init);

_sprite = new Sprite;
addChild(_sprite);


stage.addEventListener(MouseEvent.MOUSE_DOWN, onMouseDown);
onMouseDown();
}
private function onMouseDown(e:MouseEvent = null):void {
var i:uint;
var quad:Rectangle;


// ГЕНЕРАЦИЯ МИРА
// Общие параметры и свойства:
_quadsTotal = 5;
_space = new Rectangle(100, 100, 400, 300);
_quads = new Vector.<Rectangle>;
_result = new Vector.<Rectangle>;

// Создаём рассекающие квадраты:
i = 0;
while (i < _quadsTotal) {
_quads[i] = createRandomQuad();
i ++;
}

//_quads.push(new Rectangle(200, 10, 10, 200));
//_quads.push(new Rectangle(300, 150, 50, 30));

// АЛГОРИТМ
// Обходим каждую сторону получившегося квадрата,
// формируя прямоугольник свободного пространства:
i = _quadsTotal;
while (i--) {

// Получаем область для каждой стороны. (Может быть null, если области не существует)
// Верхняя сторона:
quad = getFreeSpaceForTop(_quads[i]);
if (quad !== null)
_result.push(quad);
}


// РЕНДЕР.
// Рисунок:
_sprite.graphics.clear();
_sprite.x = _space.x;
_sprite.y = _space.y;
addChild(_sprite);

// Мир:
_sprite.graphics.lineStyle(1, 0x999999);
_sprite.graphics.drawRect(0, 0, _space.width, _space.height);

// Результат:
i = _result.length;
while (i--) {
quad = _result[i];
_sprite.graphics.lineStyle(1, Math.random() * 0xcccccc);
_sprite.graphics.drawRect(quad.x, quad.y, quad.width, quad.height);
}

// Квадраты:
i = _quadsTotal;
_sprite.graphics.lineStyle(1, 0x0);
_sprite.graphics.beginFill(0, 1);
while (i--) {
quad = _quads[i];
_sprite.graphics.drawRect(quad.x, quad.y, quad.width, quad.height);
}
}


// ПРИВАТ
private function createRandomQuad():Rectangle {
const minSize:uint = 10; // Минимальный размер стороны квадрата.
const maxSize:uint = 50; // Максимальный.
const quad:Rectangle = new Rectangle();

quad.width = Math.round(Math.random() * (maxSize - minSize) + minSize);
quad.height = Math.round(Math.random() * (maxSize - minSize) + minSize);
quad.x = Math.round(Math.random() * (_space.width - quad.width));
quad.y = Math.round(Math.random() * (_space.height - quad.height));

return quad;
}
private function getFreeSpaceForTop(currentQuad:Rectangle):Rectangle {
var i:uint;
var quad:Rectangle;
var free:Rectangle;
var value:Number;
var dx:Number;
var dy:Number;


// Получаем свободную область для верхней стороны.
// Получаем будущий прямоугольник области:
free = new Rectangle(0, 0, _space.width, _space.height - (_space.height - currentQuad.y));

// Обходим все имеющиеся прямоугольники:
i = _quadsTotal;
while (i--) {
quad = _quads[i];

// Проверка сама с собою пропускается:
if (quad === currentQuad)
continue;

// Пересечение свободной области с квадратом.
// Глубина пересечения по X:
if (quad.x > free.x)
dx = free.x - quad.x + free.width;
else
dx = quad.x - free.x + quad.width;

// Глубина пересечения по Y:
if (quad.y > free.y)
dy = free.y - quad.y + free.height;
else
dy = quad.y - free.y + quad.height;

// Обрезание по Y:
if (dy > 0) {
if (dx > 0) {

// Есть пересечение.
// Проверка типа пересечения, оно может быть частичным или сквозным:
if (dy < free.height) {

// Частичное пересечение.
// Выбираем способ обрезания:
if (quad.y > free.y) {

// Блок ниже нас.
// В зависимости от его расположения, обрезаемся справа или cлева:
if (quad.x > currentQuad.x) {
free.width -= dx;
}
else {
value = quad.x + quad.width;
if (value > free.x) {
free.x = value;
free.width = dx - quad.width;
}
}
}
else {

// Блок выше нас.
// Просто обрезаемся на величину пересечения:
free.y += dy;
free.height -= dy;
}
}
else {

// Сквозное пересечение.
continue;
}
}

// Нет пересечения по X.
continue;
}

// Нет пересечения по Y.
continue;
}

return free;
}
/*
private function hitTest(a:Rectangle, b:Rectangle):Boolean {
var value:Number;


// Проверка пересечеения двух прямоугольников.
// Приводим обоих в одну точку отсчёта, добавляя разницу к ширине и высоте.

// Проверка пересечения по X:
if (a.x > b.x)
value = b.x - a.x + b.width;
else
value = a.x - b.x + a.width;

if (value < 0)
return false;

// Проверка пересечения по Y:
if (a.y > b.y)
value = b.y - a.y + b.height;
else
value = a.y - b.y + a.height;

if (value < 0)
return false;

// Блоки пересекаются:
return true;
}
*/
}
}

[Фенёк]

Ого! Вам было не влом поковыряться с вопросом! Да, пожалуй пока не совсем то, но похоже на движение в правильную строну. Спасибо! Попробую покопать в эту сторону

[GBee]

А нельзя взять самый крупный дом Х на У. Взять квадрат с максимальной стороной самого крупного дома, например Y на Y. Разбить на такие квадраты все поле. Остатки поля разделить на кол-во влезших квадратов и добавить в квадраты (Y+offsetX, Y+offsetY). В получившиеся квадраты напихать домики из расчета 1 домик - 1 квадрат. Ну и домики в рамках их квадратов можно подвигать получив некий хаос.

Добавлено через 1 минуту
Ну и мелкие домики можно пихать в один квадрат.

[Фенёк]

GBee
Задачу поставили в таком ключе, что в рантайме надо уметь добавлять домик в произвольное свободное место (то есть если использовать сетку, то появляется ограничение, не позволяющее разместить домик на стыке) + сами домики могут быть произвольного размера, так что выбрать шаг сетки неудастся

Короч, я написал МОНСТРА, который ПОЧТИ выполняет свою задачу (пока еще отлаживаю, но хочу поделиться)
По клику добавляется новый прямоугольник (иногда неправильно рассчитываются области, выясняю почему)
Slicing.swf

Вот код

package
{
import flash.display.Sprite;
import flash.display.StageAlign;
import flash.display.StageScaleMode;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Rectangle;

[SWF(width = "800", height = "600", backgroundColor = "#FFFFFF", frameRate = "60")]
public class Slicing extends Sprite
{
private var canvas:Sprite = new Sprite();
private var rectsCanvas:Sprite = new Sprite();
private var areasCanvas:Sprite = new Sprite();
private var baseArea:Rectangle = new Rectangle(0, 0, 700, 500);
private var freeAreas:Vector.<Rectangle> = new <Rectangle>[];
private var rects:Vector.<Rectangle> = new <Rectangle>[];

public function Slicing()
{
addEventListener(Event.ADDED_TO_STAGE, onAddedToStage);

}

private function onAddedToStage(event:Event):void
{
removeEventListener(Event.ADDED_TO_STAGE, onAddedToStage);

stage.scaleMode = StageScaleMode.NO_SCALE;
stage.align = StageAlign.TOP_LEFT;

canvas.x = (stage.stageWidth - baseArea.width) >> 1;
canvas.y = (stage.stageHeight - baseArea.height) >> 1;
addChild(canvas);

canvas.addChild(rectsCanvas);
canvas.addChild(areasCanvas);

init();

}

private function init():void
{
freeAreas.push(baseArea);

drawAreas();

stage.addEventListener(MouseEvent.CLICK, onClick);
}

private function drawAreas():void
{
for (var i:int = 0, length:int = freeAreas.length; i < length; i++)
{
drawArea(freeAreas[i]);
}
}

private function drawArea(area:Rectangle):void
{
areasCanvas.graphics.lineStyle(1, Math.round(Math.random() * 0xFFFFFF));
areasCanvas.graphics.drawRect(area.x, area.y, area.width, area.height);
}

private function createRandomRect():Rectangle
{
var rect:Rectangle = new Rectangle();
rect.width = 30 + Math.round(Math.random() * 50);
rect.height = 30 + Math.round(Math.random() * 50);

return rect;
}

private function drawRect(rect:Rectangle):void
{
rectsCanvas.graphics.beginFill(0);
rectsCanvas.graphics.drawRect(rect.x, rect.y, rect.width, rect.height);
rectsCanvas.graphics.endFill();
}

private function onClick(event:MouseEvent):void
{
putRectIntoFreeArea();
recalculateFreeAreas();
drawAreas();
}

private function putRectIntoFreeArea():void
{
var rect:Rectangle = createRandomRect();
var suitableAreas:Vector.<Rectangle> = new <Rectangle>[];

for (var i:int = 0, length:int = freeAreas.length; i < length; i++)
{
var area:Rectangle = freeAreas[i];

if (area.width >= rect.width && area.height >= rect.height)
{
suitableAreas.push(area);
}
}

if (suitableAreas.length == 0)
return;

rects.push(rect);

var randomSuitableArea:Rectangle = suitableAreas[Math.floor(Math.random() * suitableAreas.length)];
rect.x = randomSuitableArea.x + Math.round(Math.random() * (randomSuitableArea.width - rect.width));
rect.y = randomSuitableArea.y + Math.round(Math.random() * (randomSuitableArea.height - rect.height));

drawRect(rect);
}

private function recalculateFreeAreas():void
{
areasCanvas.graphics.clear();
freeAreas.length = 0;

for (var i:int = 0, length:int = rects.length; i < length; i++)
{
var rect:Rectangle = rects[i];

var topArea:Rectangle = new Rectangle();
topArea.copyFrom(baseArea);
topArea.bottom = rect.top;

var bottomArea:Rectangle = new Rectangle();
bottomArea.copyFrom(baseArea);
bottomArea.top = rect.bottom;

var leftArea:Rectangle = new Rectangle();
leftArea.copyFrom(baseArea);
leftArea.right = rect.left;

var rightArea:Rectangle = new Rectangle();
rightArea.copyFrom(baseArea);
rightArea.left = rect.right;

checkForTopIntersections(rect, topArea);
checkForBottomIntersections(rect, bottomArea);
checkForLeftIntersections(rect, leftArea);
checkForRightIntersections(rect, rightArea);

if (topArea.width * topArea.height > 0)
{
freeAreas.push(topArea);
}

if (bottomArea.width * bottomArea.height > 0)
{
freeAreas.push(bottomArea);
}

if (leftArea.width * leftArea.height > 0)
{
freeAreas.push(leftArea);
}

if (rightArea.width * rightArea.height > 0)
{
freeAreas.push(rightArea);
}
}
}

private function checkForTopIntersections(targetRect:Rectangle, area:Rectangle):void
{
var sideCompareRects:Vector.<Rectangle> = new <Rectangle>[];
var i:int = 0;
var length:int = 0;
var currentRect:Rectangle = null;

for (i = 0, length = rects.length; i < length; i++)
{
currentRect = rects[i];

if (currentRect === targetRect)
continue;

if (area.intersects(currentRect))
{
sideCompareRects.push(currentRect);
}
}

var nearestLeft:Rectangle = null;
var nearestRight:Rectangle = null;

for (i = 0, length = sideCompareRects.length; i < length; i++)
{
currentRect = sideCompareRects[i]

if (currentRect.right <= targetRect.left)
{
if (nearestLeft)
{
nearestLeft = nearestLeft.right < currentRect.right ? currentRect : nearestLeft;
}
else
{
nearestLeft = currentRect;
}
}

if (currentRect.left >= targetRect.right)
{
if (nearestRight)
{
nearestRight = nearestRight.left > currentRect.left ? currentRect : nearestRight;
}
else
{
nearestRight = currentRect;
}
}
}

area.left = nearestLeft ? nearestLeft.right : area.left;
area.right = nearestRight ? nearestRight.left : area.right;

var topCompareRects:Vector.<Rectangle> = new <Rectangle>[];

for (i = 0, length = sideCompareRects.length; i < length; i++)
{
currentRect = sideCompareRects[i];

if (area.intersects(currentRect))
{
topCompareRects.push(currentRect);
}
}

var nearestTop:Rectangle = null;

for (i = 0, length = topCompareRects.length; i < length; i++)
{
currentRect = topCompareRects[i];

if (currentRect.bottom < targetRect.top)
{
if (nearestTop)
{
nearestTop = nearestTop.bottom < currentRect.bottom ? currentRect : nearestTop;
}
else
{
nearestTop = currentRect;
}
}
}

area.top = nearestTop ? nearestTop.bottom : area.top;
}

private function checkForBottomIntersections(targetRect:Rectangle, area:Rectangle):void
{
var sideCompareRects:Vector.<Rectangle> = new <Rectangle>[];
var i:int = 0;
var length:int = 0;
var currentRect:Rectangle = null;

for (i = 0, length = rects.length; i < length; i++)
{
currentRect = rects[i];

if (currentRect === targetRect)
continue;

if (area.intersects(currentRect))
{
sideCompareRects.push(currentRect);
}
}

var nearestLeft:Rectangle = null;
var nearestRight:Rectangle = null;

for (i = 0, length = sideCompareRects.length; i < length; i++)
{
currentRect = sideCompareRects[i]

if (currentRect.right <= targetRect.left)
{
if (nearestLeft)
{
nearestLeft = nearestLeft.right < currentRect.right ? currentRect : nearestLeft;
}
else
{
nearestLeft = currentRect;
}
}

if (currentRect.left >= targetRect.right)
{
if (nearestRight)
{
nearestRight = nearestRight.left > currentRect.left ? currentRect : nearestRight;
}
else
{
nearestRight = currentRect;
}
}
}

area.left = nearestLeft ? nearestLeft.right : area.left;
area.right = nearestRight ? nearestRight.left : area.right;

var bottomCompareRects:Vector.<Rectangle> = new <Rectangle>[];

for (i = 0, length = sideCompareRects.length; i < length; i++)
{
currentRect = sideCompareRects[i];

if (area.intersects(currentRect))
{
bottomCompareRects.push(currentRect);
}
}

var nearestBottom:Rectangle = null;

for (i = 0, length = bottomCompareRects.length; i < length; i++)
{
currentRect = bottomCompareRects[i];

if (currentRect.top < targetRect.bottom)
{
if (nearestBottom)
{
nearestBottom = nearestBottom.top > currentRect.top ? currentRect : nearestBottom;
}
else
{
nearestBottom = currentRect;
}
}
}

area.bottom = nearestBottom ? nearestBottom.bottom : area.bottom;
}

private function checkForLeftIntersections(targetRect:Rectangle, area:Rectangle):void
{
var verticalCompareRects:Vector.<Rectangle> = new <Rectangle>[];
var i:int = 0;
var length:int = 0;
var currentRect:Rectangle = null;

for (i = 0, length = rects.length; i < length; i++)
{
currentRect = rects[i];

if (currentRect === targetRect)
continue;

if (area.intersects(currentRect))
{
verticalCompareRects.push(currentRect);
}
}

var nearestTop:Rectangle = null;
var nearestBottom:Rectangle = null;

for (i = 0, length = verticalCompareRects.length; i < length; i++)
{
currentRect = verticalCompareRects[i]

if (currentRect.bottom <= targetRect.top)
{
if (nearestTop)
{
nearestTop = nearestTop.bottom < currentRect.bottom ? currentRect : nearestTop;
}
else
{
nearestTop = currentRect;
}
}

if (currentRect.top >= targetRect.bottom)
{
if (nearestBottom)
{
nearestBottom = nearestBottom.top > currentRect.top ? currentRect : nearestBottom;
}
else
{
nearestBottom = currentRect;
}
}
}

area.top = nearestTop ? nearestTop.bottom : area.top;
area.bottom = nearestBottom ? nearestBottom.top : area.bottom;

var leftCompareRects:Vector.<Rectangle> = new <Rectangle>[];

for (i = 0, length = verticalCompareRects.length; i < length; i++)
{
currentRect = verticalCompareRects[i];

if (area.intersects(currentRect))
{
leftCompareRects.push(currentRect);
}
}

var nearestLeft:Rectangle = null;

for (i = 0, length = leftCompareRects.length; i < length; i++)
{
currentRect = leftCompareRects[i];

if (currentRect.right < targetRect.left)
{
if (nearestLeft)
{
nearestLeft = nearestLeft.right < currentRect.right ? currentRect : nearestLeft;
}
else
{
nearestLeft = currentRect;
}
}
}

area.left = nearestLeft ? nearestLeft.right : area.left;
}

private function checkForRightIntersections(targetRect:Rectangle, area:Rectangle):void
{
var verticalCompareRects:Vector.<Rectangle> = new <Rectangle>[];
var i:int = 0;
var length:int = 0;
var currentRect:Rectangle = null;

for (i = 0, length = rects.length; i < length; i++)
{
currentRect = rects[i];

if (currentRect === targetRect)
continue;

if (area.intersects(currentRect))
{
verticalCompareRects.push(currentRect);
}
}

var nearestTop:Rectangle = null;
var nearestBottom:Rectangle = null;

for (i = 0, length = verticalCompareRects.length; i < length; i++)
{
currentRect = verticalCompareRects[i]

if (currentRect.bottom <= targetRect.top)
{
if (nearestTop)
{
nearestTop = nearestTop.bottom < currentRect.bottom ? currentRect : nearestTop;
}
else
{
nearestTop = currentRect;
}
}

if (currentRect.top >= targetRect.bottom)
{
if (nearestBottom)
{
nearestBottom = nearestBottom.top > currentRect.top ? currentRect : nearestBottom;
}
else
{
nearestBottom = currentRect;
}
}
}

area.top = nearestTop ? nearestTop.bottom : area.top;
area.bottom = nearestBottom ? nearestBottom.top : area.bottom;

var leftCompareRects:Vector.<Rectangle> = new <Rectangle>[];

for (i = 0, length = verticalCompareRects.length; i < length; i++)
{
currentRect = verticalCompareRects[i];

if (area.intersects(currentRect))
{
leftCompareRects.push(currentRect);
}
}

var nearestRight:Rectangle = null;

for (i = 0, length = leftCompareRects.length; i < length; i++)
{
currentRect = leftCompareRects[i];

if (currentRect.left > targetRect.right)
{
if (nearestRight)
{
nearestRight = nearestRight.left < currentRect.left ? currentRect : nearestRight;
}
else
{
nearestRight = currentRect;
}
}
}

area.right = nearestRight ? nearestRight.left : area.right;
}
}

}



Выглядит он совершенно люто, так что если у кого-то есть предложения по правкам - пожалуйста.

Вкратце алгоритм делает следующее (на примере верхней области):
- Берем прямоугольник всей области
- Отсекаем его низ по верхней границе вставленного прямоугольника
- Берем множество прямоугольников, которые эта область пересекает
- Находим ближайший левый (не пересекающийся проекциями на ось Х) прямоугольник (если есть) и по его правой границе отсекаем область
- Такая же история для правой стороны
- Еще раз находим множество прямоугольников, теперь уже попадающих в новую область
- Находи ближайший верхний и по его границе отсекаем область

Как-то так.

Как закончу - выложу окончательный вариант.

[Tails]

Может, проще просто рандомно выбирать на карте точку и ставить туда дом? Если место занято, запускать поиск ближайшего свободного места возле этой точки. С сеткой это будет легче всего сделать.

Вроде как, обычно так в играх происходит, если место занято, объект вставляется в ближайшее свободное место или не вставляется.

[Фенёк]

Tails
Собственно моя реализация для задания так делает. Но этот алгоритм не кажется мне эффективным. Во-первых, на достаточно заполненном поле неизвестно сколько итераций потребуется чтобы таким образом отыскать свободное место. Во-вторых, такой алгоритм не может ответить на вопрос о том есть ли вообще свободное место.

[Tails]

По сути, это будет некоторая разновидность алгоритма A*. Попробуйте почитать о способах их реализаций и оптимизаций, думаю, решение найдётся.

[Фенёк]

Интересная мысль, хотя мне кажется что поиск пути это скорее история о том как дойти из точки в точку обходя препятствия, а не выйти из пересечения в свободную область.

Но да, поищу информацию.

[Tails]

Посмотрите как именно происходит поиск в этих алгоритмах. Конкретно на ум приходит волновой алгоритм. Поиск свободного места будет очень похож на поиск пути, ищите начиная от исходной позиций в разные стороны.

Если волновой алгоритм обошёл все свободные клетки от исходной точки и больше клеток не осталось -значит места нету. Если остались не проверенные пустые места, запустите поиск в них.