概述

剥除代码，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集）。
 

1. OPEN = priority queue containing START
3. CLOSED = empty set
5. while lowest rank in OPEN is not the GOAL:
7.   current = remove lowest rank item from OPEN
9.   add current to CLOSED
11.   for neighbors of current:
13.     cost = g(current) + movementcost(current, neighbor)
15.     if neighbor in OPEN and cost less than g(neighbor):
17.       remove neighbor from OPEN, because new path is better
19.     if neighbor in CLOSED and cost less than g(neighbor): **
21.       remove neighbor from CLOSED
23.     if neighbor not in OPEN and neighbor not in CLOSED:
25.       set g(neighbor) to cost
27.       add neighbor to OPEN
29.       set priority queue rank to g(neighbor) + h(neighbor)
31.       set neighbor's parent to current
33. reconstruct reverse path from goal to start
35. by following parent pointers

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

连通性

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

性能

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

能缩减图的大小吗？这能减少需处理的节点数目，包括在最终路径上和不在最终路径上的节点。可以考虑用导航网格（navigation meshes）代替网格（grids），还可以考虑分层地图表示（hierarchical map representations）。

能提高启发式函数的准确性吗？这可以减少不在最终路径上的节点数目。启发式函数值越接近真实路径长度（不是距离），A*算法需要检查的节点就越少。可以考虑用于网格的启发式函数，也可以考虑用于一般图形（包括网格）的ALT（A*，路标Landmarks，三角不等式Triangle Inequality）。

能让优先级队列更快吗？考虑使用其他数据结构来构建优先级队列。也可以参考边缘搜索的做法，对节点进行批处理。还可以考虑近似排序算法。

能让启发式函数更快吗？每个open节点都要调用启发式函数，可以考虑缓存函数的计算结果，也可以采用内联调用。

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

源代码和演示

演示（demos）

这些demos运行于浏览器端：

我为方形网格、六角形网格、三角网格都编了flash演示。这些demos采用Actionscript 3编写，点此查看源代码（其中，Pathfinder.as可视作主算法，Graph.as是图形的抽象接口）。

这里有在公路图（不是网格）上运行的demos，针对如下算法：A*、广度优先搜索、Dijkstra算法、贪婪最佳优先搜索。

用Javascript写的A* demo可以改变道路权重，源代码在github，使用MIT的开源代码许可。Demo中可以中断计算，因此可以每帧运行几个迭代。
 

• James Macgill 写的java applet.
• 可以选择A*或Dijkstra算法的交互式demo.
• 这个demo很好，而且包含javascript源码
• 这个demo很好，源码也是可见的。
• 另一个javascript demo
• 这个页面介绍跳点搜索，其中有在线demo。
• 采用Actionscript的A* 教程，在接近结尾的地方有一个demo。
• 这个demo是javascript写的，代码可读，但是我不知道其源代码许可是什么。
• 这个A* demo和跳点搜索demo用Unity编写。

代码

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

如果你计划自己实现图搜索，这里是我的Python和C++实现指南。

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

集合表示

要表示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可用时，用真实的移动开销计算一个更好的路径。

A* 算法的变体


定向搜索

在A*算法的循环中，OPEN集合用来保存所有用于寻找路径的被搜索节点。定向搜索是在A*算法基础上，通过对OPEN集合大小设置约束条件而得到的变体算法。当集合太大的时候，最不可能出现在最优路径上的节点将会被剔除。这样做会带来一个缺点：由于必须得保持这样的筛选，所以可选择的数据结构类型会受到限制。

迭代深化（Iterative deepening）

迭代深化是一种很多AI算法采用的方法，开始的时候给一个估计值，然后通过迭代使它越来越精确。这个名字来源于游戏树搜索中对接下来几次操作的提前预判（例如，在象棋游戏中）。你可以通过向前预判更多的操作来深化游戏树。一旦当你的结果不发生变化或提高很多，就可以认为你已经得到了一个非常好的结果，即使让它更精确，结果也不会再改善。在迭代深化A*(IDA*)算法中，“深度”是 f 值当前的一个截断值。当 f 值太大的时候，节点不会被考虑（也就是说，不会被加入到OPEN集中）。第一次循环时，只需要处理非常少的节点。随后的每次循环，都会增加访问的节点数。如果发现路径得到优化，就继续增加当前的截断值，否则结束。更多细节，参见链接。

我个人并不看好IDA*算法在游戏地图寻路中的应用。迭代深化的算法往往增加了计算时间，同时降低了内存需求。然而，在地图寻路的场景中，节点仅仅包含坐标信息，所需要的内存非常小。所以减少这部分内存开销并不会带来什么优势。

动态加权

在动态加权算法中，你假定在搜索开始时快速达到(任意)一个位置更为重要，在搜索结束时到达目标位置更为重要。

1. f(p) = g(p) + w(p) * h(p)

有一个权值(w >=  1 )和该启发式关联。当不断接近目标位置的时候，权重值也不断降低。这样降低了启发式函数的重要性，并增加了路径实际代价的相对重要性。

带宽搜索

带宽搜索有两个被认为非常有用的特性。这个算法变体假设 h 是一个估计过高的值，但它的估计误差不会超过 e。那么在这样的条件下，搜索到的路径代价与最优路径代价的误差不会超过 e。这里需要再一次强调，启发值设置得越好，那么得到的结果也将越好。

另外一个特性是用来判断你是否可以删掉OPEN集合中的某些节点。只要 h+d 大于路径真实代价（对于一些 d），那么你可以丢掉任意满足其 f 值比OPEN集合中最优节点 f 值至少大 e+d 的节点。这是一个很奇异的特性。你相当于得到了一个 f 值的带宽；所有在这个带宽意外的节点都可以被丢弃掉，因为他们被保证一定不会出现在最优路径中。

有意思地是，对于这两种特性分别使用不同的启发值，仍然可以计算得到结果。你可以使用一个启发值来保证路径代价不会太大，另外一个启发值来决定丢弃掉OPEN集中的哪些节点。

双向搜索

与从头到尾的搜索不同，你也可以并行地同时进行两个搜索，一个从开始到结束，一个从结束到开始。当它们相遇的时候，你就会得到一个最优路径。

这个想法在一些情况下非常有用。双向搜索的主要思想是：搜索结果会形成一个在地图上呈扇形展开的树。而一个大的树远不如两个小的树，所以使用两个小的搜索树更好。

面对面的变体将两个搜索结果链接到一起。该算法选择满足最佳 g(start,x) + h(x,y) + g(y,goal) 的一对节点，而不是选择最佳前向搜索节点 g(start,x) + h(x,goal) 或者最佳后向搜索节点 g(y,goal) + h(start,y)。

重定向算法放弃同时前向和后向的搜索方法。该算法首先进行一个短暂的前向搜索，并选出一个最佳的前向候选节点。接着进行后向搜索。此时，后向搜索不是朝向开始节点，而是朝向刚刚得到的前向候选节点。后向搜索也会选出一个最佳后向搜索节点。然后下一步，再运行前向搜索，从当前的前向候选节点到后向候选节点。这个过程将会不断重复，直到两个后选节点重合。

动态A*与终身规划A*

有一些A*的变体算法允许初始路径计算之后地图发生改变。动态A*可以用于在不知道全部地图信息的情况进行寻路。如果没有全部信息，那么A*算法的计算可能会出现错误，动态A*的优势在于可以快速改正那些错误而不会花费很多时间。终身规划A*算法可以用于代价发生改变的情况。当地图发生改变的时候，A*计算得到路径可能会失效；终身规划A*可以重复利用以前的A*计算来产生新的路径。

然而，动态A*与终身规划A*都要求大量的空间——运行A*算法时需要保持它的内部信息（OPEN/CLOSED集合，路径树，g值）。当路径发生改变的时候，动态A*或终身规划A*算法会告诉你是否需要根据地图的变化调整你的路径。

对于一个有大量运动单元的游戏，通常不会想要保存所有的信息，所以动态D*和终身规划A*可能不适用。这两种算法主要为机器人而设计。当只有一个机器人的时候，你不需要为了其他机器人的路径来重复使用内存。如果你的游戏只有一个或比较少的单元，你能会想要研究一下动态A*或者终身规划A*算法。

提高A*算法计算速度的大多数技术都是采取减少节点数量的策略。在统一代价的方格网络中，每次单独搜索一个独立格空间是非常浪费的。一个解决办法是对其中关键节点（例如拐角）建立一个用来进行寻路的图。但是，没有人愿意预先计算出一个路标图，那就来看看可以在网格图上向前跳跃的A*变体算法，跳跃点搜索。 考虑到当前节点的孩子节点有可能会出现在OPEN集合中，跳跃点搜索直接跳跃到从当前点可看到的遥远的节点。随着OPEN集合中节点的不断减少，每一步的代价都会越来越高虽然都很高，但是步数也会越来越少。

此外，在矩形对称消减中，有对地图进行分析和图中嵌入跳跃。这两种技术都是应用于方格网络图中的。

Theta*

有时网格会用来寻路是因为地图是用网格来生成，而不是因为真的要在网格上移动。如果给定一个关键点的图（例如拐角）而不是网格的话，A*算法可以运行得更快并得到更优的路径。但是，如果你不想预先计算那些图的拐角，你可以通过A*算法的变体Theta*在方格网络上进行寻路而不必严格遵循那些方格。当构建父亲指针的时候，如果有一个祖先与该节点间存在边，那么Theta*算法会直接将该指针指向该祖先而忽略所有的中间节点。不像路径光滑那样将A*找到的路径变为直线，Theta*可以把那些路径的分析作为A*算法过程的一部分。这样的做法可以比后处理方格路径使之成为任意倾角的路径的方式，可以得到更短的路径。

Theta*的思路也可能被应用于导航网格。