Размещение здания в 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 

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

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

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

Answer 1

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

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   O 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

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

Answer 2

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

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

Answer 3

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

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