5

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

一些条款：

广场 - 一个离散的位置。每个正方形都有一个 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

关于如何改进我的算法的任何想法？

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

编辑：我还想知道是否有可能满足这些条件的配置。我不能保证一个可行的解决方案，如果没有办法成功地做到这一点，我不想尝试。

4

3 回答 3

1

检查以确保您的新建筑物不正交相邻将消除诸如问题案例 1 之类的情况，并检查以确保不超过一个新建​​筑物与任何原始建筑物相邻将清除问题案例 2。

如果您可以安全地假设您没有比问题案例 2 更受限制，这应该有效。如果只有一个出口方格，那么唯一的解决方案将需要违反上面提出的“不超过一个”条件。

于 2011-03-22T18:29:57.950 回答
1

我能想到的唯一解决方案是从公共相邻方格到地图边缘进行寻路。在我看来，所有问题案例都归结为“相邻方格被阻塞”，因此确保它不被阻塞的方法是找到从那个方格到地图开放边缘的路径。

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

于 2011-03-31T15:38:20.823 回答
1

您的无效案例是由于将可用空间分成两部分，对吗？在这种情况下，一种粗略的方法是在建筑物放置后填充可用空间，并查看连接空间是否具有正确的大小（比建筑物放置前少 2 个方格）。这似乎太过分了。您真的想知道自由空间正方形的图形是否仍然连接。更具体地说，您想知道新建筑物周围的所有自由空间广场是否仍然相连。它们是否必须在本地连接，或者路径可以任意长？即这是有效的：

XXXXXXX
XXX
XXXXXX
XXXXXX
XOXX
XXOOXX
XXOOXX
XXXX
XXXXXX
XXXXXX

如果没问题，这是一个难题，因为这条路可能很长。

于 2011-03-22T18:42:28.167 回答