我在网格宇宙中工作-对象仅存在于二维矩阵中的整数位置。
一些术语:
正方形-离散位置。每个正方形都有一个x和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 ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
如果 builder 与四座建筑物之一相邻，则我要 build 两座建筑物，以使它们都共享一个共同的相邻正方形，该正方形也与四个现有建筑物中的至少一个相邻，并且该共同的相邻正方形不会在。
有效的基本解决方案:
X X X X X X X X X X X X X X X X X X X X X X
X X X X X X X X X X X X X X X X X X X X X X
X 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
关于如何优化算法的任何想法？
编辑:添加了另一个失败的案例。
编辑:我也想知道是否没有可能满足这些条件的配置。我不能保证有一个可行的解决方案，并且如果无法成功完成此操作，则不要尝试。
最佳答案
进行检查以确保新建筑物不正交相邻将消除问题案例1之类的情况，并确保不超过一个新建筑物与任何原始建筑物相邻将清除问题案例2。
如果可以安全地假设自己没有问题2那样的局限，这应该可以工作。如果只有一个导出正方形，那么唯一的解决方案将需要违反上面提出的“不超过一个”条件。
关于algorithm - 在2D离散游戏中的建筑物放置，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5395655/