Размещение здания в 2D дискретной игре

Question

Я работаю в сетке-вселенной - объекты существуют только в целочисленных местах в двумерной матрице.

Некоторые термины:

Площадь - дискретное место. Каждый квадрат имеет координаты int x и int y, и никакие два квадрата не имеют одинаковую пару x и y.

Смежный: Квадрат X смежен с другим квадратом Y, если величина разницы в их координатах x или y не больше 1. Проще говоря, все квадраты сразу в N, NE, E, SE, S, SW Направления W и NW являются смежными.

Legend:
'?' - Unknown Traversibility
'X' - Non Traversable Square
'O' - Building (Non Traversable)
' ' - Traversable Square

Эта проблема:

Учитывая следующую общую ситуацию:

? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? O O ? ? ?
? ? ? O O ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?

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

Основные действительные решения:

X X X X X X X X          X X X     X X X          X X X X X X X X
X X X X X X X X          X X X     X X X          X X X X X X X X
X X X X X X X X          X X X     X X X          X X X X X X X X
X X X O O X X X          X X X O O X X X          X X X O O X X X
X X X O O X X X          X X X O O X X X          X X O O O X X X
                         X X X O   X X X                O X X X X
      O O                X X X O   X X X                X X X X X
                         X X X     X X X                X X X X X 

В настоящее время я перебираю все пройденные квадраты, прилегающие к четырем зданиям, и ищу квадраты, которые имеют 3 смежных проходных квадрата, но иногда это приводит к ситуациям, таким как:

X X X X X X X X          X X X X X X X X          X X X X X X X X
X X X X X X X X          X X X X X X X X          X X X X X   X X
X X X X X X X X          X X   O     X X          X     X X   O X
X X X O O X X X          X X   O O O X X          X     O O O X X
X X X O O X X X          X X   O O   X X          X X   O O   X X
X X X     X X X          X X         X X          X X         X X
X X X O O X X X          X X X     X X X          X X X     X X X
X X X     X X X          X X X     X X X          X X X     X X X 

Любые мысли о том, как я могу улучшить свой алгоритм?

РЕДАКТИРОВАТЬ: Добавлен еще один неудачный случай.

РЕДАКТИРОВАТЬ: Я также хотел бы быть в состоянии знать, если нет возможной конфигурации, в которой эти условия могут быть выполнены. Мне не гарантировано жизнеспособное решение, и я не хотел бы попробовать, если нет способа сделать это успешно.

Answer 1

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

Это должно сработать, если вы можете с уверенностью предположить, что вы не более стеснены, чем в случае задачи 2. Если имеется только один квадрат выхода, то единственные решения должны будут нарушать условие "не более одного", предложенное выше.

Answer 2

Ваши недействительные случаи из-за разделения свободного пространства на 2 части, верно? В этом случае грубым методом будет заполнение свободного пространства после размещения здания и проверка правильности размера подключенного пространства (на 2 клетки меньше, чем до размещения здания). Это кажется чрезмерным. Вы действительно хотите знать, связан ли график квадратов свободного пространства. В частности, вы хотите знать, все ли свободные площади вокруг новых зданий все еще связаны. Должны ли они быть локально связаны, или путь может быть сколь угодно длинным? то есть это действительно:

XXXXXXXX
XXX
XXXXXX
XXXXXX
XOXX
XXOOOXX
XXOOXX
XXXX
XXXXXX
XXXXXX

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

Answer 3

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

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