algorithm - 人工智能 : Fastest algorithm to find if path exists?

Question

我正在寻找一种寻路算法，用于控制 2D 网格中需要找到从 A 到 B 的路径的实体的 AI。它不一定是最短路径，但需要计算得非常快.网格是静态的(永远不会改变)，一些网格单元被障碍物占据。

我目前正在使用 A*，但它对我的目的来说太慢了，因为它总是试图计算最快的路径。主要性能问题发生在路径不存在时，在这种情况下，A* 将尝试探索过多的单元格。

如果路径不必是最短路径，我是否可以使用其他算法找到比 A* 更快的路径？

谢谢，

发光

Answer 1

假设您的网格是静态的并且不会改变。您可以在构建网格后计算一次图形的连通分量。

然后您可以轻松检查源顶点和目标顶点是否在组件内。如果是，则执行 A*，如果不是，则不执行，因为组件之间不能有路径。

您可以使用 BFS 或 DFS 获取图的连通分量。