关于寻路算法的一些思考（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集）。

OPEN = priority queue containing START

CLOSED = empty set

while lowest rank in OPEN is not the GOAL:

  current = remove lowest rank item from OPEN

  add current to CLOSED

  for neighbors of current:

    cost = g(current) + movementcost(current, neighbor)

    if neighbor in OPEN and cost less than g(neighbor):

      remove neighbor from OPEN, because new path is better

    if neighbor in CLOSED and cost less than g(neighbor): **

      remove neighbor from CLOSED

    if neighbor not in OPEN and neighbor not in CLOSED:

      set g(neighbor) to cost

      add neighbor to OPEN

      set priority queue rank to g(neighbor) + h(neighbor)

      set neighbor

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

 查看Python和C++实现.

连通性

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

性能

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

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

关于网格地图，我有一些。

源代码和演示

演示（demos）

这些demos运行于浏览器端：

• 我写了一篇带交互式演示的文章，它是对A*的介绍。
• 我为、、都编了flash演示。这些demos采用Actionscript 3编写，点此查看（其中，Pathfinder.as可视作主算法，Graph.as是图形的抽象接口）。
• 有在公路图（不是网格）上运行的demos，针对如下算法：A*、广度优先搜索、Dijkstra算法、贪婪最佳优先搜索。
• 可以改变道路权重，源代码在，使用MIT的开源代码许可。Demo中可以中断计算，因此可以每帧运行几个迭代。
• .
• .
• 很好，而且包含
• 很好，源码也是可见的。
• 介绍跳点搜索，其中有在线demo。
• 采用Actionscript的A* 教程，在接近结尾的地方有一个demo。
• 是javascript写的，代码可读，但是我不知道其源代码许可是什么。
• 这个和用Unity编写。

代码

如果你用C++，一定要看看Mikko Mononen的。

如果你计划自己实现图搜索，。

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

• C++: 
• Java: 
• Javascript: [2]
• Python: 
• Objective C + Cocos2D: parts  and 
• Lua: 
• Ruby: 
• C#: 
• Unity: 
• Assembly: 
• Actionscript 3 (Flash): 
• Flex (Flash): [1]
• Go: 
• Prolog: 
• Processing: 

集合表示

要表示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++中，可以使用优先级队列）类，这个类没有增加优先级方法，也可以使用支持这个操作的。Python中使用的是。

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

二叉堆的一个变种是d元堆（），其中每个节点的孩子数大于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)时间内完成。

我们可以采用队列，以有效利用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队列插入代价低，删除代价相当低，成员隶属测试稍微低些。索引数组，成员隶属测试和插入代价都很低，但删除代价异常高，而且也会占用大量内存。哈希表性能同索引数组差不多，不过占用内存通常要少得多，而且删除代价仅仅是高，而不是异常高。

参阅，获得更多有关更先进的优先级队列的论文和实现。

混合表示

要获得更好的性能，你会采用混合数据结构。我的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*反过来用（找从目标到单元的路径）。

改进

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


原文链接