在2D离散游戏中构建位置

Question

我在网格宇宙中工作 - 对象仅存在于二维矩阵中的整数位置.

一些术语:

广场 - 一个离散的位置.每个正方形都有一个int x和int y坐标,没有两个正方形具有相同的x和y对.

相邻:如果x或y坐标的差值大小不大于1,则正方形X与另一个正方形Y相邻.更简单地说,所有正方形立即在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 中的情况更受限制，那么这应该可行。如果出口只有一格，那么唯一的解决方案将需要违反上面提出的“不超过一个”条件。