AI:查找路径是否存在的最快算法？

Question

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

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

有没有不同的算法可以用来找到比A*更快的路径，如果路径不一定是最短路径的话？

谢谢,

流明

Answer 1

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

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

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

Answer 2

要查找路径而不是最短路径，请使用任意图遍历(例如，深度优先或最佳优先)。它不一定会更快，事实上，在某些图上，它可能会检查比A*多得多的节点，因此它取决于您的数据。然而，它将更容易实现，恒定因素将显著降低。

为了避免在没有路径的情况下搜索路径，您可以创建disjoint sets (在构建图形之后)，以非常快速地检查两个给定点是否连接。这需要线性空间和线性时间来构建，查找需要摊销的实际恒定时间，但您仍然需要有时运行完整的算法，因为它只会告诉您是否存在路径，而不是路径的去向。

如果您事先已经在构建数据结构，并且在运行时有更多的时间和空间来交换即时最短路径，那么您可以既有蛋糕又吃蛋糕：Floyd-Warshall algorithm在相对适中的O(|V|^3)时间内为您提供了所有最短路径，考虑到有|V|²(开始，目的地)对，这是最划算的。它计算一个|V| * |V|矩阵，这个矩阵可能有点大，但考虑到这是一个整数矩阵，您只需要|V| * |V| * log_2 |V|位(例如，1024个顶点的1.25 MiB )。

Answer 3

您可以使用DFS或BFS，因为您只想知道这两个顶点是否连接。这两种算法都在O(|V|)中运行，其中V是图中所有顶点的集合。

如果你的启发式算法需要花费一些时间来计算，那么可以使用这两种算法中的任何一种，否则我认为A*应该运行得与DFS或BFS相似或更好。

作为另一种选择，您可以在创建网格后使用Floyd-Warshall algorithm (O(V^3))来计算每对顶点之间的最短距离路径，从而在模拟开始时执行所有繁重的操作，然后将所有最短路径存储在哈希中供O(1)访问，或者如果这被证明是内存爆炸性的，您可以只保留一个矩阵next，以便next[i][j]存储从顶点i到顶点j必须采用的顶点。因此，我们可以将从i到j的路径构建为(i, k1=next[i][j]), (k1, k2=next[k1][j]) ... (kr, j)