寻找一系列点之间的路径

Question

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

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

执行此操作的有效方法是什么？

。

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

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

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

哦，虽然这并不重要，但我正在用 Java 编写这个项目，但是任何语言（或伪代码）或算法的英语描述就足够了。 （我知道大部分大括号语言，以及有限的 Haskell 和 LISP，它们都可以。）

Answer 1

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

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

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