Forever Loop.

Trouble Busters

Thoughts on Pathfinding – 实现(上)

如果不考虑具体的实现代码,A* 算法其实是相当简单的。想象它有一个 OPEN 集和一个 CLOSED 集。其中 OPEN 集保存着等待那些筛选的节点。在最初,OPEN 集只包含一个元素,那就是最开始的起始节点。CLOSED 集包含那些已经被访问过的节点。在最初,CLOSED 集是没有任何内容的。如果用图的方式来理解,那么 OPEN 集就是边境而 CLOSED 集就是那些可访问区域的内部。由于每一个节点同时保存着指向其父节点的指针,所以我们可以知道它是如何被访问到的。

在实际流程中,有一个主要的循环不停地从 OPEN 集中取出最佳的节点 n(拥有最小 f 值的节点)并检查这个节点。如果 n 是最终的目标节点,那么我们的任务就完成了。否则,节点 n 将从 OPEN 集中移除并加入 CLOSED 集。接着检查节点 n 的邻居,节点 n’。如果 n’ 也被访问过,那么我们就不再考虑这个节点(注)。如果 n’ 在 OPEN 集中,那么它以后肯定是会被检查到的,所以我们现在也不需要考虑这个节点(注)。否则,我们把 n’ 加入 OPEN 集中,并把它的父节点设置成 n。通往节点 n’ 的花费 g(n’) 将被设置成 g(n) + movementcost(n, n’)。

你可以在这里查看一些交互式图例的演示。

注:我在这里忽视了一个小小的细节。操作时你其实需要检查节点的 g 值是否变小了,如果变小了,你应该重新 OPEN 它。

注:如果你使用的是始终最小的启发式,这种情况不会发生。在实际设计中,通常使用的是不最小的启发式

你可以在这里看到 Python 的 C++ 的实现方法。

连通性

如果你的起点和终点并不在同一个图里,A* 会运行一段时间,探索所有的节点以后才发现它们之间没有路径。所以你应该先检测可连通性并只在两点之间在同一图中的情况下才使用 A*。

性能

A* 中的主循环从一个队列中读取节点并分解最后将它插入回队列之中。换句话说,它会跟踪哪些节点是被访问过的。

为了提高性能表现,考虑一下以下的情况:

  • 你能够减少图的规模么?这样可以减少那些无论是否在路径上的节点数量。考虑使用导航网格代替传统的网格图。考虑使用分层地图表示。
  • 你能够提高启发式的精度么?这样可以减少最终路径中的无效节点数量。启发式越接近路径的实际长度(不是距离),A* 就可以探索更少的节点。考虑使用这些网格启发式。考虑给图使用地标、三角不等式(包括网格图)。
  • 你可以使队列的速度更快么?考虑为你的队列使用另一种数据结构。考虑按批处理节点,比如条纹搜索做的那样。考虑一种近似的结构。
  • 你可以是启发式的速度更快么?每访问一次节点,启发式都会被调用。考虑缓存启发式的结果。考虑内联调用。

对于网格图,可以查看这些建议

源代码以及示例

示例

这些示例可以在你的浏览器中运行:

代码

如果你正在使用 C++,请在这里查看由 Mikko Mononen 提供的代码。

如果你正在计划自己实现一个图,这里是一些 Python 以及 C++ 的实现

这里有一些使用不同语言的实现,但是还来不及查看所有项目所以没法做出特别的推荐:

集合的表示

当你尝试实现 OPEN 以及 CLOSED 集的时候第一个想到的数据结构是什么?如果你和我一样,你可能会想到的是“数组”。你也可能会想到“链表”。我们可以使用很多不同的数据结构,但为了选择,我们应该考虑我们需要什么样的操作。

对于 OPEN 集我们主要进行三种操作:主循环不断的寻找最佳的节点并移除它;检查邻居节点是否在集合之中;插入新的节点。其中插入以及移除最佳节点的操作是优先级队列的一种典型。

但选择哪种数据结构并不仅仅取决于你的操作,还取决于你每种操作的执行次数。每个邻居节点被访问的时候,都会被检查一次它在集中的存在性。如果一个节点被考虑了,那么插入操作也会运行。移除最佳节点的操作对每个被访问的节点也都执行一次。大部分被考虑到的节点都会被访问;不会被访问的仅仅是那些位于边缘的节点。当评估这些操作在不同数据结构上的花费时,我们需要考虑边缘最大值 (F)。

除此之外,还有第四种操作,虽然执行的次数非常之少但仍然是需要实现的。如果被访问的节点确实存在在 OPEN 集之中(这种情况经常发生),并且如果它的 f 值比起已经在 OPEN 集中的节点要好(比较少见),那么 OPEN 集中的值就应该被调整。调整操作包括删除节点(f 值不是最佳的节点)和重插入。这两个步骤应该被优化成一个提升节点移动优先级的操作。

我的建议:最佳的类似选择应该是二叉堆。如果你有一个可用的二叉堆库,那么可以选择使用它。如果你没有,你可以从有序数组或者无序数组入手并转换成二叉堆来提高性能。如果在你的 OPEN 集中有超过 10,000 个元素,那么你应该考虑一些更复杂的结构,比如桶。

无序数组与链表

最简单的数据结构就是无序数组或者链表了。这种结构的关系检查操作速度很慢,扫描整个结构的复杂度为 O(F)。插入操作快速,在末尾位置插入数据的复杂度为 O(1)。寻找元素的速度很慢,复杂度为 O(F)。对于数组,移除最佳节点的操作复杂度为 O(F),链表为 O(1)。在调整操作中,提升优先级的复杂度为 O(F),改变值的复杂度为 O(1)。

有序数组

为了加快移除最佳节点的操作速度,我们可以对数组进行排序。因为我们可以用二分查找,在种情况下,关系检查操作的复杂度将变成 O(log F),插入操作变慢了,为了给新元素腾出空间,移动操作的复杂度为 O(F)。查找速度快速,因为指针已经在末尾,所以复杂度为 O(1)。而且移除最佳节点操作的复杂度也将变成 O(1) 如果我们保证排序范围达到数组的尾部。调整操作中,查找复杂度变成了 O(log F),改变值/位置的复杂度为 O(F)。

确保数组是有序的这样最佳选择才会在数组尾部。

有序链表

在有序数组中,插入操作非常慢。如果我们使用链表的话,则可以加速这个操作。但是链表结构中关系检查操作的速度却很慢,扫描链表的复杂度为 O(F)。插入操作快速,插入一个新链表的复杂度为 O(1),但是为它找一个正确的位置的复杂却为 O(F)。查找最佳节点的速度很快,复杂度依然为 O(1),因为最佳元素仍然在最末尾。移除最佳节点操作的复杂度仍然为 O(1)。在调整操作中,查找节点的复杂度为 O(F),改变值/位置的复杂度为 O(1)。

二叉堆

二叉堆(不要和内存堆混淆)是一个用数组存储的树形结构。不像大部分的树使用指针指向他们的子树,二叉堆使用索引来找到子树。

在二叉堆中,关系检查操作的复杂度为 O(F),因为你不得不扫描整个结构,所以插入操作的复杂度为 O(log F),移除操作的复杂度为 O(log F)。

调整操作的复杂度则比较微妙,查找节点的复杂度只有 O(F),提升优先级的复杂度只有 O(log F)。但不巧的是,大部分的库并不包含这种操作。但又幸运的是,这种操作不是严格需求的。所以我推荐各位不要过分担心除非你确实需要这种操作。取代提升优先级的操作,在队列中插入一个新元素。你可能最终会处理节点两次,但是比起提升优先级的花费这还是相对较低的。

在 C++ 中,使用 priority_queue 类,尽管它不含有提升优先级的操作,或者 Boost 实现的可变优先级队列。或者使用 Python 的 heapq 库。

你可以在关系检查操作中结合哈希表或者索引数组,在管理优先级时你也可以引入优先级队列;在后面的部分我们会提到。

二叉堆的一种变种叫做 D 堆,每个节点有超过两个的字数。插入和提升优先级的操作会变得更快一些,但是移除操作却变得比原来慢了一点。它可能拥有更好的缓存表现。

有序跳表

搜索一个无序的链表速度很慢。我们可以使用跳表代替来让它变快一些。如果你的表中有一个排序键,那么关系检查操作的复杂度将只有 O(log F)。插入操作的复杂度为 O(1)。查找最佳节点的复杂度为 O(1),移除节点的复杂度也为 O(1)。要记得提升优先级的操作包括查找节点,移除它和重插入它。

如果我们使用位置作为跳表的排序键,那么关系检查的复杂度为 O(log F),插入操作的复杂度为 O(1)。查找节点的复杂度为 O(F),移除节点的复杂度为 O(1)。这个表现比起无序链表要好的多。

如果我们使用 f 值作为排序键,关系检查的复杂度变为 O(F),插入操作的复杂度为 O(1),查找最佳节点的复杂度为 O(1),移除节点的复杂度为 O(1)。这比起有序链表的表现稍微差了点。

索引数组

如果节点的集是一个合理的规模,我们可以直接使用索引结构,索引函数 i(n) 把节点 n 映射到一个数组的索引。不像无序与有序数组那样数组的长度等于 OPEN 集的最大值,在所有的 n 中,索引数组的长度总是等于 max(i(n))。如果你的函数是密集的(比如没有不被使用的索引),那么 max(i(n)) 将是你图中的节点数目。只要你的图是网格的,让索引函数变得密集是非常容易的。

因为我们几乎不需要检查 Array[i(n)] 是否包含任何数据, i(n) 的复杂度是 O(1),关系检查操作的复杂度是 O(1)。因为我们刚刚设置了 Array[i(n)],插入操作的复杂度是 O(1)。因为我们必须搜索整个结构,查找以及移除节点操作的复杂度是 O(节点数量)。提升优先级操作的复杂度为 O(1)。

在 Thoughts on Pathfinding – 实现(下)的部分中,将为大家继续介绍诸如哈希表、伸展树、HOT 队列等不同数据结构以及它们之间的比较,以及在实际情况中的应用。

评论

  1. 自动引用通知:Thoughts on Pathfinding – 实现(下) | Forever Loop.