algorithm - 二维离散游戏中的建筑物放置

Question

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

一些条款:

Square - 一个离散的位置。每个方 block 都有一个 int x 和 int y 坐标，没有两个方 block 具有相同的 x 和 y 对。

相邻:如果方 block X 或 y 坐标的差异幅度不大于 1，则方 block X 与另一个方 block Y 相邻。更简单地说，所有方 block 都紧邻 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 两栋建筑，使它们共享一个公共(public)相邻广场，该广场也至少与四栋现有建筑中的一栋相邻，而这个公共(public)相邻广场是没有被封锁。

基本有效的解决方案:

X X X X X X X X          X X X     X X X          X X X X X X X X
X X X X X X X X          X X X     X X X          X X X X X X X X
X 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 更受限制，那么这应该可行。如果只有一个导出方格，那么唯一的解决方案将需要违反上面提出的“不超过一个”条件。