9

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

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

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

谢谢，

管腔

4

7 回答 7

9

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

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

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

于 2013-03-19T19:19:50.643 回答
4

要查找路径而不是最短路径，请使用任何图遍历（例如深度优先或最佳优先）。它不一定会更快，实际上它可能会在某些图表上检查比 A* 更多的节点，因此这取决于您的数据。但是，它会更容易实现，并且常数因子会显着降低。

为避免在没有路径时搜索路径，您可以创建不相交集（在构建图形后）以非常快速地检查两个给定点是否连接。这需要线性空间和线性时间来构建，并且查找需要摊销的几乎恒定的时间，但您有时仍需要运行完整的算法，因为它只会告诉您是否存在路径，而不是路径的去向。

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

于 2013-03-19T19:37:02.350 回答
2

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

如果您的启发式算法需要一些不平凡的时间来计算，请使用这两种算法中的任何一种，否则我认为 A* 应该与 DFS 或 BFS 类似或更好地运行。

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

于 2013-03-19T19:15:42.007 回答
1

如果图足够小，您可以使用Floyd-Warshall 算法预先计算所有最短路径。这需要O(|V|²)内存来存储路径，并且需要O(|V|³)时间来进行预计算。

显然，这不是非常大的图表的选择。对于那些您应该使用 Thomas 的答案并预先计算连接的组件（需要线性时间和内存）以避免最昂贵的 A* 搜索。

于 2013-03-19T19:34:40.073 回答
0

如果您的迷宫永远不会改变并且任何存在的路径永远存在，您是否可以不使用映射算法来找到迷宫的“区域”并以某种格式存储它们？内存使用量与节点或单元的数量呈线性关系，速度是访问和比较数组的两个元素的速度。

计算（分割到区域）可能会更耗时，但它在一开始就完成了一次。也许您可以为此目的调整一些洪水填充算法？

不确定从上面是否清楚，但我认为一个例子总是有帮助的。我希望你能原谅我使用 PHP 语法。

示例（迷宫 5x5）（[]标记障碍物）：

    0 1 2 3 4
  +----------+
0 |[][]   2  |
1 |  [][]    |
2 |    []  []|
3 |  1 []    |
4 |    []    |
  +----------+

索引区域（使用数字哈希而不是 'x:y' 可能会更好）：

$regions=array(
    '0:1'=>1,'0:2'=>1,'0:3'=>1,'0:4'=>1,'1:2'=>1,'1:3'=>1,'1:4'=>1,
    '2:0'=>2,'3:0'=>2,'3:1'=>2,'3:2'=>2,'3:3'=>2,'3:4'=>2,'4:0'=>2,
    '4:1'=>2,'4:3'=>2,'4:4'=>2
);

那么你的任务就是找出你的起点和终点是否都在同一个区域：

if ( $regions[$startPoint] == $regions[$endPoint] )
    pathExists();



现在，如果我没记错的话，A* 复杂度（速度）取决于起点和终点之间的距离（或解决方案的长度），这也许可以用来加快您的搜索速度。

我会尝试在迷宫中创建一些“连接节点”（ JN ）。这些可以位于一个函数上（以快速了解最近的JN在哪里），并且您将预先计算所有相邻JN之间的路径。

因此，您只需要从起点到最近的JN以及从终点到最近的JN搜索解决方案（所有这些都在同一区域（以上））。现在我可以看到一个场景（如果在迷宫的复杂性方面没有很好地选择函数），它有几个区域，其中一些可能根本没有JN，或者你的所有JN都落在迷宫中的障碍物上。 ..因此，如果可能的话，最好手动定义这些JN，或者使这个JN放置函数变得不平凡（考虑到每个区域的面积）。

到达JN后，您可能会将它们之间的路径编入索引（以快速检索开始和结束JN之间的预定义路径）或执行另一个 A* 寻路，但这次仅在“连接节点”集上 - 因为少得多其中JN之间的路径搜索会更快。

于 2013-03-21T11:10:26.887 回答
0

您可以考虑使用 Anytime A* 算法（ANA* 或其他变体）。

这些将首先执行贪婪的最佳优先搜索以找到初始路径。

然后，它将通过运行启发式函数的权重越来越小来进行渐进式改进。

您可以随时取消搜索并获得迄今为止找到的最佳路径。

于 2013-04-14T00:40:23.610 回答
0

A*、BFS、DFS 和所有其他搜索算法在没有路径时必须检查完全相同数量的节点，因此“先使用 DFS”不是一个好的答案。并且完全没有必要使用 Floyd-Warshall。

对于静态图，解决方案很简单；请参阅@Thomas 的回答。对于非静态图，问题更复杂；请参阅此答案以获得一个好的算法。

于 2013-03-19T23:33:35.890 回答