1

为了在我的一个简单项目中使用，我遇到了一些障碍。

我在网格中有一系列点，“墙壁”和“开放空间”。网格外的空间被假定为墙。我在这个网格中有任意数量的开放点，如果我让网格中的一个特定块从开放空间变为墙壁，我必须确定连接的点是否会改变。

这样做的有效方法是什么？

例子 .

示例：如果绿色方块是墙壁或开放空间，则确定红色方块之间路径的存在/不存在是否会改变。（PS：我真诚地为我糟糕的网格道歉）

现在，我假设某种元胞自动机是最好的，但我不确定。我以前看过寻路，但从未真正看到任何涉及此类问题的东西。

请注意：我不在乎路径有多长，（我知道它们的最大长度）它们必须存在。所以没有必要找到点之间的最佳路径。

哦，虽然没关系，但我正在用 Java 编写这个项目，但是任何语言（或伪代码）或算法的英文描述就足够了。（我知道大多数花括号语言，以及有限的 Haskell 和 LISP，他们都可以。）

4

1 回答 1

1

这可能不是最好的解决方案，但解决方案如下：

  • 首先填充网格，直到所有连接的点都被分配相同的编号（连接的意思是相邻的或在相同的数字“岛”上）。有很多方法可以做到这一点，没有一种方法需要太复杂。只需从第一个节点到最后一个节点运行网格并在尚未填充的情况下填充它是一种选择。
  • 只有在将岛屿一分为二的墙中放置一堵墙，才能破坏相邻或相同编号的节点之间的路径。因此，当您添加一堵墙时，请检查是否是这种情况。您可以使用 A* 合理有效地检查这一点：从与新墙相邻的所有 4 个节点中，检查它们是否具有相同的编号，它们仍然可以相互到达。
  • 如果墙没有造成分裂：没有路径被破坏，一切都是一样的。
  • 如果墙确实导致了分裂：再次填充网格，并再次检查两个节点是否相邻或在相同的数字上（如果您正在检查的块始终是打开的，它将始终是相邻的）。

以这种方式检查所有节点是相当有效的（我认为检查 n*n/2-n/2 路径将花费 O(n^2)），但如果只创建必要的岛，添加新墙可能会更有效没有洪水填充，但这可能更难以实施。

于 2010-10-04T22:09:43.993 回答