代码之家 › 专栏 › 技术社区 › TaslemGuy

在一系列点之间寻找路径

path-finding

1

TaslemGuy · 技术社区 · 14 年前

在我的一个简单项目中,我遇到了一点障碍。

什么是有效的方法?

.

示例:如果绿色正方形是墙或开放空间,则确定红色正方形之间是否存在路径。(附言:我真诚地为我的糟糕表现道歉)

现在,我假设某种细胞自动机是最好的,但我不确定。我以前看过寻路,但从来没有真正看到过这种问题。

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

哦,虽然这不重要,但我是用Java编写这个项目的,但是任何语言(或伪代码)或算法的英文描述都足够了。(我知道大多数的花括号语言,还有有限的Haskell和LISP,它们都能做到。)

1 回复 | 直到 5 年前

1

Herman Schaaf 14 年前

这可能不是最佳解决方案,但解决方案如下:

从填充网格开始,直到所有连接的点都被分配了相同的编号(连接的意思是相邻的或在相同编号的“岛”上)。有很多方法可以做到这一点,其中没有一个需要太复杂。简单地从第一个节点到最后一个节点遍历网格,如果还没有填充的话就填充它是一种选择。
只有在将孤岛一分为二的墙中放置,才能断开与同一编号相邻或位于同一编号上的节点之间的路径。所以,当你添加一堵墙时,检查是否是这样。您可以通过使用*:从与新墙相邻的所有4个节点中,检查它们是否具有相同的编号,它们是否仍然可以彼此接触,从而合理有效地检查这一点。
如果这堵墙没有造成裂痕:没有路径被打破,一切都是一样的。
如果墙确实导致拆分:再次整体应用填充网格,然后再次检查两个节点是否相邻或位于相同的编号上(如果要检查的块始终处于打开状态,则始终相邻)。

以这种方式检查所有节点是相当有效的(我认为检查n*n/2-n/2路径需要O(n^2)),但是如果只创建必要的孤岛而不进行泛洪填充,则添加新墙可能会更有效,但这可能更难实现。