关于寻路算法的一些思考(3):A*算法的实现

概述

剥除代码,A* 算法非常简单。算法维护两个集合:OPEN 集和 CLOSED 集。OPEN 集包含待检测节点。初始状态,OPEN集仅包含一个元素:开始位置。CLOSED集包含已检测节点。初始状态,CLOSED集为空。从图形上来看,OPEN集是已访问区域的边界,CLOSED集是已访问区域的内部。每个节点还包含一个指向父节点的指针,以确定追踪关系。

算法有一个主循环,重复地从OPEN集中取最优节点n(即f值最小的节点)来检测。如果n是目标节点,那么算法结束;否则,将节点n从OPEN集删除,并添加到CLOSED集中,然后查看n的所有邻节点n’。如果邻节点在CLOSED集,它已被检测过,则无需再检测(*);如果邻节点在OPEN集,它将会被检测,则无需此时检测(*);否则,将该邻节点加入OPEN集,设置其父节点为n,到n’的路径开销g(n’) = g(n) + movementcost(n, n’)。

这里有更详细的介绍,其中包含交互图。

(*)这里我略过了一个小细节。你应当检查节点的g值,如果新计算得到的路径开销比该g值低,那么要重新打开该节点(即重新放入OPEN集)。

(**)如果启发式函数值始终是可信的,这种情况就不应当出现。然而在游戏中,经常会得到不可信的启发式函数

请点击这里 查看PythonC++实现.

连通性

如果游戏中起点和终点在图上根本就不连通,此时A*算法会耗时很久,因为从起点开始,它需要查探所有的节点,直到它意识到根本没有可行的路径。因此,我们可以先确定连通分支,仅当起点和终点在同一个连通分支时,才使用A*算法。

性能

A*算法的主循环从一个优先级队列中读取节点,分析该节点,然后再向优先级队列插入新的节点。算法还追踪哪些节点被访问过。要提高算法的性能,考虑以下几方面:

  • 能缩减图的大小吗?这能减少需处理的节点数目,包括在最终路径上和不在最终路径上的节点。可以考虑用导航网格(navigation meshes)代替网格(grids),还可以考虑分层地图表示(hierarchical map representations)
  • 能提高启发式函数的准确性吗?这可以减少不在最终路径上的节点数目。启发式函数值越接近真实路径长度(不是距离),A*算法需要检查的节点就越少。可以考虑用于网格的启发式函数,也可以考虑用于一般图形(包括网格)的ALT(A*,路标Landmarks,三角不等式Triangle Inequality)。
  • 能让优先级队列更快吗?考虑使用其他数据结构来构建优先级队列。也可以参考边缘搜索的做法,对节点进行批处理。还可以考虑近似排序算法。
  • 能让启发式函数更快吗?每个open节点都要调用启发式函数,可以考虑缓存函数的计算结果,也可以采用内联调用。

关于网格地图,我有一些建议

源代码和演示

演示(demos)

这些demos运行于浏览器端:

代码

如果你用C++,一定要看看Mikko MononenRecast

如果你计划自己实现图搜索,这里是我的PythonC++实现指南

我收集了一些源代码链接,但是我还没有仔细看这些项目,所以也没有更具体的建议:

集合表示

要表示OPEN集和CLOSED集,你首先能想到什么?如果你像我一样,可能就会考虑“数组”。你也可能想到“链表。有很多数据结构都可以用,我们应当依据需要的操作来选择一个。

对OPEN集主要执行三个操作:主循环重复地寻找最优节点,然后删除它;访问邻节点时检查节点是否在集合中;访问邻节点时插入新节点。插入和删除最优都是优先级队列的典型操作。

数据结构的选择不仅依赖于操作,还与每个操作运行的次数有关。成员隶属测试对每个已访问节点的每个邻节点运行一次,插入对每个要考虑的节点运行一次,删除最优对每个已访问的节点运行一次。大部分考虑的节点都会被访问,没有被访问的是搜索空间的边缘节点。评估各种数据结构下操作的开销时,我们应当考虑最大边缘值(F)。

另外还有第四种操作,这种操作相对较少,但仍需要实现。如果当前检测的节点已经在OPEN集中(经常出现的情况),并且其f值低于OPEN集中原来的值(很少见的情况),那么需要调整OPEN集中的值。调整操作包括删除节点(这个节点的f值不是最优的)以及再插入该节点。这两步操作可以优化为一步移动节点的“增加优先级”操作(也被称为“降键”)。

我的建议:一般最好的选择是采用二叉堆。如果有现成的二叉堆库,直接用就可以了。如果没有,开始就使用有序数组或无序数组,当要求更高的性能时,切换到二叉堆。如果OPEN集中的元素超过10,000个,就要考虑使用更复杂的数据结构,比如桶系统(bucketing system)。

无序数组或链表

最简单的数据结构就是无序数组或链表了。成员隶属测试很慢,要扫描整个结构,时间复杂度为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(F),而增大其优先级竟然只要O(log F)。然而,大部分优先级队列库中都没有该操作。幸运的是,这个操作不是绝对必要的。因此我建议,除非特别需要,不用考虑该操作。我们可以通过向优先级队列插入新元素来代替增加优先级操作。虽然最终可能一个节点要处理两次,但是相比实现增加优先级操作,这个开销比较少。

C++中,可以使用优先级队列(priority_queue)类,这个类没有增加优先级方法,也可以使用支持这个操作的Boost库可变优先级队列。Python中使用的是heapq库

你可以混合使用多种数据结构。采用哈希表或索引数组做成员隶属测试,采用优先级队列管理优先级;详情请看下文的混合部分

二叉堆的一个变种是d元堆(d-ary heap),其中每个节点的孩子数大于2。插入和增加优先级操作更快一些,而删除操作则略慢一点。它们可能有更好的缓存性能。

有序跳跃列表(sorted skip lists)

无序链表的查找操作很慢,可以使用跳跃列表加快查找速度。对于跳跃列表,如果有排序键,成员隶属测试只要O(log F)。如果知道插入位置,同链表一样,跳跃列表的插入也是O(1)。如果排序键是f,查找最优节点很快,是O(1)。删除一个节点是O(1)。增加优先级操作包括查找节点,删除该节点,再插入该节点。

如果将地图位置作为跳跃列表的键,成员隶属测试是O(log F);执行过成员隶属测试后,插入是O(1);查找最优节点是O(F);删除一个节点是O(1)。这比无序链表要好,因为它的成员隶属测试更快。

如果将f值作为跳跃列表的键,成员隶属测试是O(F);插入是O(1);查找最优节点是O(1);删除一个节点是O(1)。这并不比有序链表好。

索引数组(indexed arrays)

如果节点集合有限,且大小还可以的话,我们可以采用直接索引结构,用一个索引函数i(n)将每个节点n映射到数组的一个下标。无序数组和有序数组的大小都对应于OPEN集的最大尺寸,而索引数组的数组大小则始终是max(i(n))。如果函数是密集的(即不存在未使用的索引),max(i(n))是图中的节点数目。只要地图是网格结构,函数就很容易是密集的。

假设函数i(n)时间复杂度是O(1),成员隶属测试就是O(1),因为只需要检测Array[i(n)]有没有数据。插入也是O(1),因为只需要设置Array[i(n)]。查找和删除最优节点是O(numnodes),因为需要查找整个数据结构。增加优先级操作是O(1)。

哈希表

索引数组占用大量内存来存储所有不在OPEN集中的节点。还有一种选择是使用哈希表,其中哈希函数h(n)将每个节点n映射到一个哈希码。保持哈希表大小是N的两倍,以保证低冲突率。假设h(n)时间复杂度是O(1),成员隶属测试和插入预期时间复杂度是O(1);删除最优时间复杂度是O(numnodes),因为需要搜索整个结构;增加优先级操作是O(1)。

伸展树(splay trees)

堆是基于树的一种结构,它的操作预期时间复杂度是O(log F)。然而问题是,在A*算法中,常见的操作是,删除一个低开销节点(引起O(log F)的操作,因为必须将数值从树底向上移)后,紧跟着添加多个低开销节点(引起O(log F)的操作,因为这些值被插入树底,然后再向上调整到树根)。这种情况下,预期情况就等价于最坏情况了。如果能找到一种数据结构,使预期情况更好,即使最坏情况没有变好,A*算法的性能也可以有所提高。

伸展树是一种自调整的树型结构。对树节点的任何访问,都会将那个节点向树顶方向移动,最终呈现“缓存”的效果,即不常用节点在底部,从而不会减慢操作。不管伸展树多大,结果都是这样,因为操作仅像“缓存大小”一样慢。在A*算法中,低开销节点很常用,高开销节点则不常用,所以可以将那些高开销节点移到树底。

采用伸展树,成员隶属测试、插入、删除最优、增加优先级的预期时间复杂度都是O(log F),最坏情况时间复杂度都是O(F),然而缓存使最坏情况通常不会发生。然而如果启发式函数低估开销,由于Dijkstra算法和A*算法的一些奇特特性,伸展树可能就不是最好的选择了。特别地,对于节点n和其邻节点n’,如果f(n’) >= f(n),那么所有的插入可能都发生在树的一侧,最终导致树失衡。我还没有测试这种情况。

HOT队列

还有一种数据结构可能比堆要好。通常你可以限制优先级队列中值的范围。给定一个范围限制,往往会有更好的算法。例如,任意值排序时间复杂度是O(N log N),但是如果有固定范围,桶排序或基数排序可以在O(N)时间内完成。

我们可以采用HOT(Heap On Top)队列,以有效利用f(n’) >= f(n)的情况,其中n’是n的一个邻节点。我们将删除f(n) 最小的节点n,然后插入满足下列情况的邻节点n’:f(n) <= f(n’) <= f(n) + delta,其中delta <= C,常量C是从一个节点到邻节点的开销的最大变化。由于f(n)是OPEN集中的最小f值,且所有插入的节点其f值都小于等于f(n) + delta,因此OPEN集中的所有f值都在0到delta的范围内。就像桶/基数排序一样,我们可以维护一些“桶”来对OPEN集中的节点排序。

用K个桶,可以将任何O(N)花费降低到其平均值O(N/K)。HOT队列中,最前面的桶是一个二叉堆,其他的桶都是无序数组。对于最前面的桶,成员隶属测试预期时间复杂度是O(F/K),插入和删除最优时间复杂度是O(log (F/K))。对于其他桶,成员隶属测试时间复杂度是O(F/K),插入是O(1),而删除最优元素永远不会发生。如果最前面的桶空了,就要将下一个桶从无序数组转换为二叉堆。事实证明,这一操作(”heapify”)运行时间是O(F/K)。增加优先级操作最好是处理为O(F/K)的删除和随后O(log (F/K))或O(1)的插入。

事实上,A*算法中,大部分放入OPEN集的节点都不需要。HOT队列结构脱颖而出,因为它只堆化(heapified)需要的元素(开销不大),不需要的节点都在O(1)时间内被插入。唯一大于O(1)的操作是从堆中删除节点,其时间复杂度也仅是O(log (F/K))。

此外,如果C小的话,可以设置K = C,那么最小的桶甚至不需要是堆,因为一个桶中的所有节点f值都相同。插入和删除最优都是O(1)!有个人报告说,当OPEN集最多有800个节点时,HOT队列和堆一样快;当最多有1500个节点时,HOT队列比堆快20%。我预测随着节点数的增加,HOT队列会越来越快。

HOT队列的一个简单变种是两级队列:将好节点放到一种数据结果(堆或数组),将坏节点放入另一种数据结构(数组或链表)。因为大部分放入OPEN集的节点都是坏节点,所以它们从不被检测,而且将它们放入大数组也没什么坏处。

数据结构比较

要记住,我们不仅要确定渐近(”大O”)行为,也要找一个低常数。要说为什么,我们考虑一个O(log F)的算法和一个O(F)的算法,其中F是堆中的元素个数。那么在你的机器上,第一个算法的实现可能运行10,000 * log(F)秒,而第二个算法的实现可能运行2 * F秒。如果F = 256,那么第一个是80,000秒,而第二个仅需512秒。这种情况下,“更快的”算法用时更长。仅当F > 200,000时算法才开始变得更快。

你不能只比较两个算法,还需要比较那些算法的实现,还需要知道数据的大致规模。上述例子中,当F > 200,000,第一种实现更快。但如果在游戏中,F始终低于30,000,第二种实现更好。

没有一种基本数据结构是完全令人满意的。无序的数组或链表,插入代价很低,但成员隶属测试和删除代价则很高。有序的数组或链表,成员隶属测试代价稍微低些,删除代价很低,而插入代价则很高。二叉堆插入和删除代价稍微低些,成员隶属测试代价则很高。伸展树的所有操作代价都稍微低些。HOT队列插入代价低,删除代价相当低,成员隶属测试稍微低些。索引数组,成员隶属测试和插入代价都很低,但删除代价异常高,而且也会占用大量内存。哈希表性能同索引数组差不多,不过占用内存通常要少得多,而且删除代价仅仅是高,而不是异常高。

参阅Lee Killough的优先级队列页面,获得更多有关更先进的优先级队列的论文和实现。

混合表示

要获得更好的性能,你会采用混合数据结构。我的A*代码中,用一个索引数组实现O(1)的成员隶属测试,用一个二叉堆实现O(log F)的插入和删除最优元素。至于增加优先级,我用索引数组在O(1)时间内测试我是否真的需要改变优先级(通过在索引数组中存储g值),偶尔地,如果真的需要增加优先级,我采用二叉堆实现O(F)的增加优先级操作。你也可以用索引数组存储每个节点在堆中的位置;这样的话,增加优先级操作时间复杂度是O(log F)。

游戏交互循环

交互式(特别是实时)游戏的需求可能会影响计算最优路径的能力。相比最好的答案,可能更重要的是答案。尽管如此,其他所有事都还是一样的,更短的路径总是更好的。

通常来说,计算接近起点的路径比计算接近目标的路径更为重要。立即开始原理:即使沿一个次优路径,也要尽快移动单元,然后再计算更好的路径。实时游戏中,A*的时延往往比吞吐量更重要。

单元要么跟随直觉(简单地移动),要么听从大脑(预先计算路径)。除非大脑跟他们说不要那样做,单元都将跟随直觉行事。(这个方法在大自然中有应用,而且Rodney Brook在机器人架构中也用到了。)我们不是一次性计算所有的路径,而是每一个或两个或三个游戏循环,计算一次路径。此后单元按照直觉开始移动(可能仅仅朝目标沿直线运动),然后重新开始循环,再为单元计算路径。这种方法可以摊平寻路开销,而不是一次性全做完。

提前退出

通常A*算法找到目标节点后退出主循环,但也可能提前退出,那么得到的是一段局部路径。在找到目标节点前任何时刻退出,算法返回到OPEN集当前最优节点的路径。这个节点最有可能达到目标,因此这是一个合理的去处。

与提前退出类似的情况包括:已经检测了一定数量的节点;A*算法已经运行了数毫秒;或者检查的节点距开始位置已经有一段距离。当使用路径拼接时,较之完整路径,拼接路径的限制应当更小。

可中断算法

如果基本上不需要寻路服务,或者用于存储OPEN集和CLOSED集的数据结构很小,一种可选的方案是:存储算法的状态,退出游戏循环,然后再回到A*算法退出的地方继续。

群体移动

路径请求的到达不是均匀分布的。实时战略游戏中,一个常见的情况是,玩家选择多个单元,并命令它们向同一个目标移动。这造成了寻路系统的高负载。

这时,为某个单元找到的路径很有可能对其他单元也有用。那么一种想法是,可以找从单元中心点到目标中心点的路径P,然后对所有单元都应用这条路径的大部分,仅仅将前10步和后10步路,替换成为每个单元所找的路。单元i获得的路径是:从开始位置到P[10]的路径,接着是P[10..len(P)-10]的共享路径,再接着是从P[len(P)-10]到终点的路径。

另请参阅:将路径放到一块叫做路径拼接,这部分在这些笔记的另一个模块中有介绍。

为每个单元找的路很短(大概平均10个步骤),长的路都是共享的。大部分路径只要找一次,然后在所有单元中共享。但如果所有单元都沿同样的路径移动,可能无法给用户留下深刻印象。为了改善系统的这种表象,让单元沿稍稍不同的路走。一种方法是,单元选择邻近位置,自行修改路径。

另一种方法是,让单元意识到其它单元的存在(可能随机选一个“领头”单元,或者选那个最清楚现状的单元),并只为领头单元寻找一条路径,然后采用集群算法,将单元作为一个群体移动。

有些A*变种,可以处理移动目标,或者对目标理解逐渐加深的情况。其中一些适用于处理多个单元向相同目标移动的情况,它们将A*反过来用(找从目标到单元的路径)。

改进

如果地图上基本没有障碍物,取而代之,增加了地形变化的开销,那么可以降低实际地形开销,来计算初始路径。例如,如果草原开销是1,丘陵开销是2,大山开销是3,那么A*会为了避免在大山上走1步,考虑在草原走3步。而如果假设草原开销是1,丘陵是1.1,大山是1.2,那么A*在计算最初的路径时,就不会花很多时间去避免走大山,寻路就更快。(这与精确启发式函数的成效近似。)知道一条路径后,单元就立刻开始移动,游戏循环可以继续。当备用CPU可用时,用真实的移动开销计算一个更好的路径。

1 6 收藏 评论

关于作者:hf_cherish

(新浪微博:@丫丫_Cherish) 个人主页 · 我的文章 · 11

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部