2D离散游戏中的建筑放置

Question

我正在一个网格世界中工作 - 对象仅存在于二维矩阵的整数位置。

一些术语:

方块 - 离散的位置。每个方块都有一个 int x 和 int y 坐标，并且没有两个方块具有相同的 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 ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?

当建筑物毗邻四座建筑物之一时，我希望建造两座建筑物，它们共享一个相邻的正方形，并且该正方形也与至少四座现有建筑物之一相邻，而这个共享的相邻正方形没有被阻塞。

基本有效解决方案：

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

您有没有想过如何优化我的算法？

编辑：添加了另一个失败的案例。

编辑：我还想知道是否存在一种可能的配置，可以满足这些条件。我不能保证一定有可行的解决方案，如果没有成功的方法，我希望不要尝试。

- T.K.

---

如果您能准确地描述最后一个示例的问题，那么您可能已经得到了答案。 - Michael McGowan

@Michael 没错。我无法想象如何描述最后几个示例中的问题。至少，没有涉及过度蛮力的方式可以做到。 - T.K.

暴力破解永远不会浪费资源 ;) - Amir Afghani

Answer 1

检查确保新建筑物不是正交相邻的，可以消除像问题情况1这样的情况，并且检查确保不超过一个新建筑物与任何原有建筑物相邻，将解决问题情况2。

如果您可以安全地假设您受到的限制不超过问题情况2，那么这应该能够奏效。如果只有一个出口方块，则唯一的解决方案需要违反上述“不超过一个”的条件。

- user538917

---

@user5389167 感谢您的建议。乍一看，它们似乎非常合理，但我可能发现了一些漏洞。问题情况3是一种需要违反第一条规则的情况 - 解决该情况涉及正交构造。此外，我正在编辑问题以包括这个方面，但我也希望它能够确定我是否更受限制 - 我不能保证自己处于可以成功执行此操作的情况下，此时，我希望不去尝试。 - T.K.

问题3不是可以生成的解决方案。所选位置没有三个相邻可穿越的正方形。话虽如此，我现在看到我可以构建一个有问题的情况，但这需要建造者开始被困住。我们可以安全地假设建造者不会在无法解决的位置开始吗？ - user538917

@user538917 哦，我的错误。我会去编辑那个案例。是的，我们可以假设构建器不会被困住。 - T.K.

Answer 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

如果这样是可以的，那么这是一个难题，因为路径可能非常长。

- phkahler

---

我很担心那种情况是完全有可能的。更糟糕的是，我处于一种无知的状态 - 我不知道我的建筑物范围之外的方块是否可遍历。我在中心四个建筑物周围留出了3个方块的缓冲区，因为我不能保证得到更多的信息。 话虽如此，如果我能够简单地到达距离我的中心建筑物三个方块层面，那么我将满意地称之为一个答案。 - T.K.

Answer 3

我能想到的唯一解决方案是从相邻的正方形开始进行路径规划，直到到达地图边缘。在我看来，所有的问题都可以归结为“相邻的正方形被封锁”，因此确保它不被封锁的方法是从该正方形找到通往地图开放边缘的路径。

我不知道这是否是最有效的方法，但实现起来相当简单，因为A*路径规划例程已经被广泛实现。实际上，由于您不需要最短路径，只需要一个路径，因此您可以从相邻的正方形开始进行自由空间的泛洪填充，直到触及地图的边缘。

- jhocking

---

是的，这听起来与我之前的头脑风暴非常相似 - 我可以获取所有可遍历边界方块，并列出所有可到达的位置。然后，如果我的建筑完成后可到达的位置列表更短，我就知道我搞砸了，我会放弃那个位置。这样做计算效率相当低下，但我相信人们可以利用问题中“需要任何路径而不是最佳路径”的特点，将运行时间大大缩短。 - T.K.