堪称最好最全的A*算法详解（译文）

    英文原文链接：http://theory.stanford.edu/~amitp/GameProgramming/

    英文原文参考：http://www-cs-students.stanford.edu/%7Eamitp/gameprog.html#Paths

    翻译参考链接：http://blog.csdn.net/b2b160/article/details/4057781

    我们尝试解决的问题是把一个游戏对象（game object）从出发点移动到目的地。路径搜索(Pathfinding)的目标是找到一条好的路径——避免障碍物、敌人，并把代价（燃料，时间，距离，装备，金钱等）最小化。运动（Movement）的目标是找到一条路径并且沿着它行进。把关注的焦点仅集中于其中的一种方法是可能的。一种极端情况是，当游戏对象开始移动时，一个老练的路径搜索器（pathfinder）外加一个琐细的运动算法（movement algorithm）可以找到一条路径，游戏对象将会沿着该路径移动而忽略其它的一切。另一种极端情况是，一个单纯的运动系统（movement-only system）将不会搜索一条路径（最初的“路径”将被一条直线取代），取而代之的是在每一个结点处仅采取一个步骤，同时考虑周围的环境。同时使用路径搜索(Pathfinding)和运动算法（movement algorithm）将会得到最好的效果。

1 导言

1.1 算法

1.2 Dijkstra算法与最佳优先搜索

1.3 A*算法

2 启发式算法

2.1 A*对启发式函数的使用

2.2 速度还是精确度？

2.3 衡量单位

2.4 精确的启发式函数

2.4.1 预计算的精确启发式函数

2.4.2 线性精确启发式算法

2.5 网格地图中的启发式算法

2.5.1 曼哈顿距离

2.5.2 对角线距离

2.5.3 欧几里得距离

2.5.4 平方后的欧几里得距离

2.5.5 Breaking ties

2.5.6 区域搜索

3 Implementation notes

3.1 概略

3.2 源代码

3.3 集合的表示

3.3.1 未排序数组或链表

3.3.2 排序数组

3.3.3 排序链表

3.3.4 排序跳表

3.3.5 索引数组

3.3.6 哈希表

3.3.7 二元堆

3.3.8 伸展树

3.3.9 HOT队列

3.3.10 比较

3.3.11 混合实现

3.4 与游戏循环的交互

3.4.1 提前退出

3.4.2 中断算法

3.4.3 组运动

3.4.4 细化

4 A*算法的变种

4.1 beam search

4.2 迭代深化

4.3 动态衡量

4.4 带宽搜索

4.5 双向搜索

4.6 动态A*与终身计划A*

5 处理运动障碍物

5.1 重新计算路径

5.2 路径拼接

5.3 监视地图变化

5.4 预测障碍物的运动

6 预计算路径的空间代价

6.1 位置VS方向

6.2 路径压缩

6.2.1 位置存储

6.2.2 方向存储

6.3 计算导航点

6.4 极限路径长度

6.5 总结

　　移动一个简单的物体（object）看起来是容易的。而路径搜索是复杂的。为什么涉及到路径搜索就产生麻烦了？考虑以下情况：

　　物体（unit）最初位于地图的底端并且尝试向顶部移动。物体扫描的区域中(粉红色部分)没有任何东西显示它不能向上移动，因此它持续向上移动。在靠近顶部时，它探测到一个障碍物然后改变移动方向。然后它沿着U形障碍物找到它的红色的路径。相反的，一个路径搜索器（pathfinder）将会扫描一个更大的区域（淡蓝色部分），但是它能做到不让物体(unit)走向凹形障碍物而找到一条更短的路径(蓝色路径）。

　　然而你可以扩展一个运动算法，用于对付上图所示的障碍物。或者避免制造凹形障碍，或者把凹形出口标识为危险的(只有当目的地在里面时才进去):

　　比起一直等到最后一刻才发现问题，路径搜索器让你提前作出计划。不带路径搜索的运动(movement)可以在很多种情形下工作，同时可以扩展到更多的情形，但是路径搜索是一种更常用的解决更多问题的方法。

　　计算机科学教材中的路径搜索算法在数学视角的图上工作——由边联结起来的结点的集合。一个基于图块(tile)拼接的游戏地图可以看成是一个图，每个图块(tile)是一个结点，并在每个图块之间画一条边：

　　目前，我会假设我们使用二维网格(grid)。稍后我将讨论如何在你的游戏之外建立其他类型的图。

　　许多AI领域或算法研究领域中的路径搜索算法是基于任意(arbitrary)的图设计的，而不是基于网格(grid-based)的图。我们可以找到一些能使用网格地图的特性的东西。有一些我们认为是常识，而算法并不理解。例如，我们知道一些和方向有关的东西：一般而言，如果两个物体距离越远，那么把其中一个物体向另一个移动将花越多的时间；并且我们知道地图中没有任何秘密通道可以从一个地点通向另一个地点。（我假设没有，如果有的话，将会很难找到一条好的路径，因为你并不知道要从何处开始。）

　　Dijkstra算法从物体所在的初始点开始，访问图中的结点。它迭代检查待检查结点集中的结点，并把和该结点最靠近的尚未检查的结点加入待检查结点集。该结点集从初始结点向外扩展，直到到达目标结点。Dijkstra算法保证能找到一条从初始点到目标点的最短路径，只要所有的边都有一个非负的代价值。（我说“最短路径”是因为经常会出现许多差不多短的路径。）在下图中，粉红色的结点是初始结点，蓝色的是目标点，而类菱形的有色区域（注：原文是teal areas）则是Dijkstra算法扫描过的区域。颜色最淡的区域是那些离初始点最远的，因而形成探测过程（exploration）的边境（frontier）：

　　最佳优先搜索（BFS）算法按照类似的流程运行，不同的是它能够评估（称为启发式的）任意结点到目标点的代价。与选择离初始结点最近的结点不同的是，它选择离目标最近的结点。BFS不能保证找到一条最短路径。然而，它比Dijkstra算法快的多，因为它用了一个启发式函数（heuristic function）快速地导向目标结点。例如，如果目标位于出发点的南方，BFS将趋向于导向南方的路径。在下面的图中，越黄的结点代表越高的启发式值（移动到目标的代价高），而越黑的结点代表越低的启发式值（移动到目标的代价低）。这表明了与Dijkstra 算法相比，BFS运行得更快。

　　然而，这两个例子都仅仅是最简单的情况——地图中没有障碍物，最短路径是直线的。现在我们来考虑前边描述的凹型障碍物。Dijkstra算法运行得较慢，但确实能保证找到一条最短路径：

　　另一方面，BFS运行得较快，但是它找到的路径明显不是一条好的路径：

　　问题在于BFS是基于贪心策略的，它试图向目标移动尽管这不是正确的路径。由于它仅仅考虑到达目标的代价，而忽略了当前已花费的代价，于是尽管路径变得很长，它仍然继续走下去。

　　结合两者的优点不是更好吗？1968年发明的A*算法就是把启发式方法（heuristic approaches）如BFS，和常规方法如Dijsktra算法结合在一起的算法。有点不同的是，类似BFS的启发式方法经常给出一个近似解而不是保证最佳解。然而，尽管A*基于无法保证最佳解的启发式方法，A*却能保证找到一条最短路径。

　　我将集中讨论A*算法。A*是路径搜索中最受欢迎的选择，因为它相当灵活，并且能用于多种多样的情形之中。

　　和其它的图搜索算法一样，A*潜在地搜索图中一个很大的区域。和Dijkstra一样，A*能用于搜索最短路径。和BFS一样，A*能用启发式函数（注：原文为heuristic）引导它自己。在简单的情况中，它和BFS一样快。

　　在凹型障碍物的例子中，A*找到一条和Dijkstra算法一样好的路径：

　　成功的秘决在于，它把Dijkstra算法（靠近初始点的结点）和BFS算法（靠近目标点的结点）的信息块结合起来。在讨论A*的标准术语中，g(n)表示从初始结点到任意结点n的代价，h(n)表示从结点n到目标点的启发式评估代价（heuristic estimated cost）。在上图中，yellow(h)表示远离目标的结点而teal(g)表示远离初始点的结点。当从初始点向目标点移动时，A*权衡这两者。每次进行主循环时，它检查f(n)最小的结点n，其中f(n) = g(n) + h(n)。

　　启发式函数h(n)告诉A*从任意结点n到目标结点的最小代价评估值。选择一个好的启发式函数是重要的。

　　启发式函数可以控制A*的行为：

　　所以我们得到一个很有趣的情况，那就是我们可以决定我们想要从A*中获得什么。理想情况下（注：原文为At exactly the right point），我们想最快地得到最短路径。如果我们的目标太低，我们仍会得到最短路径，不过速度变慢了；如果我们的目标太高，那我们就放弃了最短路径，但A*运行得更快。

在游戏中，A*的这个特性非常有用。例如，你会发现在某些情况下，你希望得到一条好的路径（"good" path）而不是一条完美的路径（"perfect" path）。为了权衡g(n)和h(n)，你可以修改任意一个。

注:在学术上，如果启发式函数值是对实际代价的低估，A*算法被称为简单的A算法（原文为simply A）。然而，我继续称之为A*，因为在实现上是一样的，并且在游戏编程领域并不区别A和A*。

　　A*改变它自己行为的能力基于启发式代价函数，启发式函数在游戏中非常有用。在速度和精确度之间取得折衷将会让你的游戏运行得更快。在很多游戏中，你并不真正需要得到最好的路径，仅需要近似的就足够了。而你需要什么则取决于游戏中发生着什么，或者运行游戏的机器有多快。

　　假设你的游戏有两种地形，平原和山地，在平原中的移动代价是1而在山地则是3。A* is going to search three times as far along flat land as it does along mountainous land. 这是因为有可能有一条沿着平原到山地的路径。把两个邻接点之间的评估距离设为1.5可以加速A*的搜索过程。然后A*会将3和1.5比较，这并不比把3和1比较差。It is not as dissatisfied with mountainous terrain, so it won't spend as much time trying to find a way around it. Alternatively, you can speed up up A*'s search by decreasing the amount it searches for paths around mountains―just tell A* that the movement cost on mountains is 2 instead of 3. Now it will search only twice as far along the flat terrain as along mountainous terrain. Either approach gives up ideal paths to get something quicker.

速度和精确度之间的选择前不是静态的。你可以基于CPU的速度、用于路径搜索的时间片数、地图上物体（units）的数量、物体的重要性、组（group）的大小、难度或者其他任何因素来进行动态的选择。取得动态的折衷的一个方法是，建立一个启发式函数用于假定通过一个网格空间的最小代价是1，然后建立一个代价函数（cost function）用于测量（scales）：

g’(n) = 1 + alpha * ( g(n) – 1 )

　　如果alpha是0，则改进后的代价函数的值总是1。这种情况下，地形代价被完全忽略，A*工作变成简单地判断一个网格可否通过。如果alpha是1，则最初的代价函数将起作用，然后你得到了A*的所有优点。你可以设置alpha的值为0到1的任意值。

　　你也可以考虑对启发式函数的返回值做选择：绝对最小代价或者期望最小代价。例如，如果你的地图大部分地形是代价为2的草地，其它一些地方是代价为1的道路，那么你可以考虑让启发式函数不考虑道路，而只返回2*距离。

　　速度和精确度之间的选择并不是全局的。在地图上的某些区域，精确度是重要的，你可以基于此进行动态选择。例如，假设我们可能在某点停止重新计算路径或者改变方向，则在接近当前位置的地方，选择一条好的路径则是更重要的，因此为何要对后续路径的精确度感到厌烦？或者，对于在地图上的一个安全区域，最短路径也许并不十分重要，但是当从一个敌人的村庄逃跑时，安全和速度是最重要的。（译者注：译者认为这里指的是，在安全区域，可以考虑不寻找精确的最短路径而取近似路径，因此寻路快；但在危险区域，逃跑的安全性和逃跑速度是重要的，即路径的精确度是重要的，因此可以多花点时间用于寻找精确路径。）

　A*计算f(n) = g(n) + h(n)。为了对这两个值进行相加，这两个值必须使用相同的衡量单位。如果g(n)用小时来衡量而h(n)用米来衡量，那么A*将会认为g或者h太大或者太小，因而你将不能得到正确的路径，同时你的A*算法将运行得更慢。

　　如果你的启发式函数精确地等于实际最佳路径（optimal path），如下一部分的图中所示，你会看到此时A*扩展的结点将非常少。A*算法内部发生的事情是：在每一结点它都计算f(n) = g(n) + h(n)。当h(n)精确地和g(n)匹配（译者注：原文为match）时，f(n)的值在沿着该路径时将不会改变。不在正确路径（right path）上的所有结点的f值均大于正确路径上的f值（译者注：正确路径在这里应该是指最短路径）。如果已经有较低f值的结点，A*将不考虑f值较高的结点，因此它肯定不会偏离最短路径。

　　构造精确启发函数的一种方法是预先计算任意一对结点之间最短路径的长度。在许多游戏的地图中这并不可行。然后，有几种方法可以近似模拟这种启发函数：

　　（译者：此处不好翻译，暂时保留原文）

然后添加一个启发函数h’用于评估从任意位置到达邻近导航点（waypoints）的代价。（如果愿意，后者也可以通过预计算得到。）最终的启发式函数可以是：

h(n) = h'(n, w1) + distance(w1, w2), h'(w2, goal)

或者如果你希望一个更好但是更昂贵的启发式函数，则分别用靠近结点和目标的所有的w1,w2对对上式进行求值。（译者注：原文为or if you want a better but more expensive heuristic, evaluate the above with all pairs w1, w2 that are close to the node and the goal, respectively.）

　　在特殊情况下，你可以不通过预计算而让启发式函数很精确。如果你有一个不存在障碍物和slow地形，那么从初始点到目标的最短路径应该是一条直线。

　　如果你正使用简单的启发式函数（我们不知道地图上的障碍物），则它应该和精确的启发式函数相符合（译者注：原文为match）。如果不是这样，则你会遇到衡量单位的问题，或者你所选择的启发函数类型的问题。

　　在网格地图中，有一些众所周知的启发式函数。

标准的启发式函数是曼哈顿距离（Manhattan distance）。考虑你的代价函数并找到从一个位置移动到邻近位置的最小代价D。因此，我的游戏中的启发式函数应该是曼哈顿距离的D倍：

       H(n) = D * (abs ( n.x – goal.x ) + abs ( n.y – goal.y ) )

你应该使用符合你的代价函数的衡量单位。

(Note: the above image has a tie-breaker added to the heuristic.}

（译者注：曼哈顿距离——两点在南北方向上的距离加上在东西方向上的距离，即D（I，J）=|XI-XJ|+|YI-YJ|。对于一个具有正南正北、正东正西方向规则布局的城镇街道，从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离因此曼哈顿距离又称为出租车距离，曼哈顿距离不是距离不变量，当坐标轴变动时，点间的距离就会不同——百度知道）

如果在你的地图中你允许对角运动那么你需要一个不同的启发函数。（4 east, 4 north）的曼哈顿距离将变成8*D。然而，你可以简单地移动（4 northeast）代替，所以启发函数应该是4*D。这个函数使用对角线，假设直线和对角线的代价都是D：

h(n) = D * max(abs(n.x - goal.x), abs(n.y - goal.y))

如果对角线运动的代价不是D，但类似于D2 = sqrt(2) * D，则上面的启发函数不准确。你需要一些更准确（原文为sophisticated）的东西：

h_diagonal(n) = min(abs(n.x - goal.x), abs(n.y - goal.y))

h_straight(n) = (abs(n.x - goal.x) + abs(n.y - goal.y))

h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))

这里，我们计算h_diagonal(n)：沿着斜线可以移动的步数；h_straight(n)：曼哈顿距离；然后合并这两项，让所有的斜线步都乘以D2，剩下的所有直线步(注意这里是曼哈顿距离的步数减去2倍的斜线步数)都乘以D。

如果你的单位可以沿着任意角度移动（而不是网格方向），那么你也许应该使用直线距离：

h(n) = D * sqrt((n.x-goal.x)^2 + (n.y-goal.y)^2)

然而，如果是这样的话，直接使用A*时将会遇到麻烦，因为代价函数g不会match启发函数h。因为欧几里得距离比曼哈顿距离和对角线距离都短，你仍可以得到最短路径，不过A*将运行得更久一些：

我曾经看到一些A*的网页，其中提到让你通过使用距离的平方而避免欧几里得距离中昂贵的平方根运算：

h(n) = D * ((n.x-goal.x)^2 + (n.y-goal.y)^2)

不要这样做！这明显地导致衡量单位的问题。当A*计算f(n) = g(n) + h(n)，距离的平方将比g的代价大很多，并且你会因为启发式函数评估值过高而停止。对于更长的距离，这样做会靠近g(n)的极端情况而不再计算任何东西，A*退化成BFS：

导致低性能的一个原因来自于启发函数的ties（注：这个词实在不知道应该翻译为什么）。当某些路径具有相同的f值的时候，它们都会被搜索（explored），尽管我们只需要搜索其中的一条：

Ties in f values.

为了解决这个问题，我们可以为启发函数添加一个附加值（译者注：原文为small tie breaker）。附加值对于结点必须是确定性的（也就是说，不能是随机的数），而且它必须让f值体现区别。因为A*对f值排序，让f值不同意味着只有一个"equivalent"的f值会被检测。

一种添加附加值的方式是稍微改变（译者注：原文为nudge）h的衡量单位。如果我们减少衡量单位（译者注：原文为scale it downwards），那么当我们朝着目标移动的时候f将逐渐增加。很不幸，这意味着A*倾向于扩展到靠近初始点的结点，而不是靠近目标的结点。我们可以增加衡量单位（译者注：原文为scale it downwards scale h upwards slightly）（甚至是0.1%），A*就会倾向于扩展到靠近目标的结点。

heuristic *= (1.0 + p)

选择因子p使得p = f(n)，其中n’是n的一个邻居结点。我们删除f(n)值最小的结点n，插入满足f(n) 200000时更快，但如果在你的游戏中，F小于30000，那么第二种实现好一些。

基本数据结构没有一种是完全合适的。未排序数组或者链表使插入操作很快而集体关系检查和删除操作非常慢。排序数组或者链表使集体关系检查稍微快一些，删除（最佳元素）操作非常快而插入操作非常慢。二元堆让插入和删除操作稍微快一些，而集体关系检查则很慢。伸展树让所有操作都快一些。HOT队列让插入操作很快，删除操作相当快，而集体关系检查操作稍微快一些。索引数组让集体关系检查和插入操作非常快，但是删除操作不可置信地慢，同时还需要花费很多内存空间。哈希表和索引数组类似，但在普通情况下，它花费的内存空间少得多，而删除操作虽然还是很慢，但比索引数组要快。

关于更高级的优先队列的资料和实现，请参考Lee Killough的优先队列页面（http://members.xoom.com/killough/heaps.html）。

为了得到最佳性能，你将希望使用混合数据结构。在我的A*代码中，我使用一个索引数组从而集合关系检查是O(1)的，一个二元堆从而插入操作和删除最佳都是O(log F)的。对于调整操作，我使用索引数组从而花费O(1)时间检查我是否真的需要进行调整（通过在索引数组中保存g值），然后在少数确实需要进行调整的情况中，我使用二元堆从而调整操作花费O(F)时间。你也可以使用索引数组保存堆中每个结点的位置，这让你的调整操作变成O(log F)。

交互式的（尤其是实时的）游戏对最佳路径的计算要求很高。能够得到一个解决方案比得到最佳方案可能更重要。然而在所有其他因素都相同的情况下，短路径比长路径好。

一般来说，计算靠近初始结点的路径比靠近目标结点的路径更重要一些。立即开始原理（The principle of immediate start）：让游戏中的物体尽可能快地开始行动，哪怕是沿着一条不理想的路径，然后再计算一条更好的路径。在实时游戏中，应该更多地关注A*的延迟情况（latency）而不是吞吐量（throughput）。

可以对物体编程让它们根据自己的本能（简单行为）或者智力（一条预先计算好的路径）来行动。除非它们的智力告诉它们怎么行动，否则它们就根据自己的本能来行动（这是实际上使用的方法，并且Rodney Brook在他的机器人体系结构中也用到）。和立即计算所有路径所不同，让游戏在每一个，两个，或者三个循环中搜索一条路径。让物体在开始时依照本能行动(可能仅仅是简单地朝着目标直线前进)，然后才为它们寻找路径。这种方法让让路径搜索的代价趋于平缓，因此它不会集中发生在同一时刻。

可以从A*算法的主循环中提前退出来同时得到一条局部路径。通常，当找到目标结点时，主循环就退出了。然而，在此之前的任意结点，可以得到一条到达OPEN中当前最佳结点的路径。这个结点是到达目标点的最佳选择，所以它是一个理想的中间结点（原文为so it's a reasonable place to go）。

可以提前退出的情况包括检查了一定数量的结点，A*算法已经运行了几毫秒时间，或者扫描了一个离初始点有些距离的结点。当使用路径拼接时，应该给被拼接的路径一个比全路径（full path）小的最大长度。

如果需要进行路径搜索的物体较少，或者如果用于保存OPEN和CLOSED集的数据结构较小，那么保存算法的状态是可行的，然后退出到游戏循环继续运行游戏。

路径请求并不是均匀分布的。即时策略游戏中有一个常见的情况，玩家会选择多个物体并命令它们朝着同样的目标移动。这给路径搜索系统以沉重的负载。

在这种情况下，为某个物体寻找到的路径对其它物体也是同样有用的。一种方法是，寻找一条从物体的中心到目的地中心的路径P。对所有物体使用该路径的绝大部分，对每一个物体，前十步和后十步使用为它自己寻找的路径。物体i得到一条从它的开始点到P[10]的路径，紧接着是共享的路径P[10..len(P)-10]，最后是从P[len(P)-10]到目的地的路径。

为每个物体寻找的路径是较短的（平均步数大约是10），而较长的路径被共享。大多数路径只寻找一次并且为所有物体所共享。然而，当玩家们看到所有的物体都沿着相同的路径移动时，将对游戏失去兴趣。为了对系统做些改进，可以让物体稍微沿着不同的路径运动。一种方法是选择邻近结点以改变路径。

另一种方法是让每个物体都意识到其它物体的存在（或许是通过随机选择一个“领导”物体，或者是通过选择一个能够最好地意识到当前情况的物体），同时仅仅为领导寻路。然后用flocking算法让它们以组的形式运动。

然而还有一种方法是利用A*算法的中间状态。这个状态可以被朝着相同目标移动的多个物体共享，只要物体共享相同的启发式函数和代价函数。当主循环退出时，不要消除OPEN和CLOSED集；用A*上一次的OPEN和CLOSED集开始下一次的循环（下一个物体的开始位置）。（这可以被看成是中断算法和提前退出部分的一般化）

如果地图中没有障碍物，而有不同代价的地形，那么可以通过低估地形的代价来计算一条初始路径。例如，如果草地的代价是1，山地代价是2，山脉的代价是3，那么A*会考虑通过3个草地以避免1个山脉。通过把草地看成1，山地看成1.1，而山脉看成1.2来计算初始路径，A*将会用更少的时间去设法避免山脉，而且可以更快地找到一条路径（这接近于精确启发函数的效果）。一旦找到一条路径，物体就可以开始移动，游戏循环就可以继续了。当多余的CPU时间是可用的时候，可以用真实的移动代价去计算更好的路径。

在A*的主循环中，OPEN集保存所有需要检查的结点。Beam Search是A*算法的一个变种，这种算法限定了OPEN集的尺寸。如果OPEN集变得过大，那些没有机会通向一条好的路径的结点将被抛弃。缺点是你必须让排序你的集合以实现这个，这限制了可供选择的数据结构。

迭代深化是一种在许多AI算法中使用的方法，这种方法从一个近似解开始，逐渐得到更精确的解。该名称来源于游戏树搜索，需要查看前面几步（比如在象棋里），通过查看前面更多步来提高树的深度。一旦你的解不再有更多的改变或者改善，就可以认为你已经得到足够好的解，当你想要进一步精确化时，它不会再有改善。在ID-A*中，深度是f值的一个cutoff。当f的值太大时，结点甚至将不被考虑（例如，它不会被加入OPEN集中）。第一次迭代只处理很少的结点。此后每一次迭代，访问的结点都将增加。如果你发现路径有所改善，那么就继续增加cutoff，否则就可以停止了。更多的细节请参考这些关于ID-A*的资料：http://www.apl.jhu.edu/~hall/AI-Programming/IDA-Star.html。

我本人认为在游戏地图中没有太大的必要使用ID-A*寻路。ID算法趋向于增加计算时间而减少内存需求。然而在地图路径搜索中，“结点”是很小的——它们仅仅是坐标而已。我认为不保存这些结点以节省空间并不会带来多大改进。

在动态衡量中，你假设在开始搜索时，最重要的是讯速移动到任意位置；而在搜索接近结束时，最重要的是移动到目标点。

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

启发函数中带有一个权值（weight）（w>=1）。当你接近目标时，你降低这个权值；这降低了启发函数的重要性，同时增加了路径真实代价的相对重要性。

带宽搜索（Bandwidth Search）有两个对有些人也许有用的特性。这个变种假设h是过高估计的值，但不高于某个数e。如果这就是你遇到的情况，那么你得到的路径的代价将不会比最佳路径的代价超过e。重申一次，你的启发函数设计的越好，最终效果就越好。

另一个特性是，你可以丢弃OPEN集中的某些结点。当h+d比路径的真实代价高的时候（对于某些d），你可以丢弃那些f值比OPEN集中的最好结点的f值高至少e+d的结点。这是一个奇怪的特性。对于好的f值你有一个“范围”（"band"），任何在这个范围之外的结点都可以被丢弃掉，因为这个结点肯定不会在最佳路径上。

好奇地（Curiously），你可以对这两种特性使用不同的启发函数，而问题仍然可以得到解决。使用一个启发函数以保证你得到的路径不会太差，另一个用于检查从OPEN集中去掉哪些结点。

与从开始点向目标点搜索不同的是，你也可以并行地进行两个搜索——一个从开始点向目标点，另一个从目标点向开始点。当它们相遇时，你将得到一条好的路径。

这听起来是个好主意，但我不会给你讲很多内容。双向搜索的思想是，搜索过程生成了一棵在地图上散开的树。一棵大树比两棵小树差得多，所以最好是使用两棵较小的搜索树。然而我的试验表明，在A*中你得不到一棵树，而只是在搜索地图中当前位置附近的区域，但是又不像Dijkstra算法那样散开。事实上，这就是让A*算法运行得如此快的原因——无论你的路径有多长，它并不进行疯狂的搜索，除非路径是疯狂的。它只尝试搜索地图上小范围的区域。如果你的地图很复杂，双向搜索会更有用。

面对面的方法（The front-to-front variation）把这两种搜索结合在一起。这种算法选择一对具有最好的g(start,x) + h(x,y) + g(y,goal)的结点，而不是选择最好的前向搜索结点——g(start,x) + h(x,goal)，或者最好的后向搜索结点——g(y,goal) + h(start,y)。

Retargeting方法不允许前向和后向搜索同时发生。它朝着某个最佳的中间结点运行前向搜索一段时间，然后再朝这个结点运行后向搜索。然后选择一个后向最佳中间结点，从前向最佳中间结点向后向最佳中间结点搜索。一直进行这个过程，直到两个中间结点碰到一块。

有一些A*的变种允许当初始路径计算出来之后，世界发生改变。D*用于当你没有全局所有信息的时候。如果你没有所有的信息，A*可能会出错；D*的贡献在于，它能纠正那些错误而不用过多的时间。LPA*用于代价会改变的情况。在A*中，当地图发生改变时，路径将变得无效；LPA*可以重新使用之前A*的计算结果并产生新的路径。然而，D*和LPA*都需要很多内存——用于运行A*并保存它的内部信息（OPEN和CLOSED集，路径树，g值），当地图发生改变时，D*或者LPA*会告诉你，是否需要就地图的改变对路径作调整。在一个有许多运动着的物体的游戏中，你经常不希望保存所有这些信息，所以D*和LPA*在这里并不适用。它们是为机器人技术而设计的，这种情况下只有一个机器人——你不需要为别的机器人寻路而重用内存。如果你的游戏只有一个或者少数几个物体，你可以研究一下D*或者LPA*。

一个路径搜索算法沿着固定障碍物计算路径，但是当障碍物会运动时情况又怎样？当一个物体到达一个特写的位置，原来的障碍物也许不再在那儿了，或者一个新的障碍物也许到达那儿。处理该问题的一个方法是放弃路径搜索而使用运动算法（movement algorithms）替代，这就不能look far ahead；这种方法会在后面的部分中讨论。这一部分将对路径搜索方法进行修改从而解决运动障碍物的问题。

当时间渐渐过去，我们希望游戏世界有所改变。以前搜索到的一条路径到现在也许不再是最佳的了。对旧的路径用新的信息进行更新是有价值的。以下规则可以用于决定什么时候需要重新计算路径：

重计算路径的主要缺点是许多路径信息被丢弃了。例如，如果路径是100步长，每10步重新计算一次，路径的总步数将是100+90+80+70+60+50+40+30+20+10 = 550。对M步长的路径，大约需要计算M^2步。因此如果你希望有许多很长的路径，重计算不是个好主意。重新使用路径信息比丢弃它更好。

当一条路径需要被重新计算时，意味着世界正在改变。对于一个正在改变的世界，对地图中当前邻近的区域总是比对远处的区域了解得更多。因此，我们应该集中于在附近寻找好的路径，同时假设远处的路径不需要重新计算，除非我们接近它。与重新计算整个路径不同，我们可以重新计算路径的前M步：

因为p[1]和p[M]比分开的M步小（原文：Since p[1] and p[M] are fewer than M steps apart），看起来新路径不会很长。不幸的是，新的路径也许很长而且不够好。上面的图显示了这种情况。最初的红色路径是1-2-3-4，褐色的是障碍物。如果我们到达2并且发现从2到达3的路径被封锁了，路径拼接技术会把2-3用2-5-3取代，结果是物体沿着路径1-2-5-3-4运动。我们可以看到这不是一条好的路径，蓝色的路径1-2-5-4是一条更好的路径。

通常可以通过查看新路径的长度检测到坏的路径。如果这严格大于M，就可能是不好的。一个简单的解决方法是，为搜索算法设置一个最大路径长度。如果找不到一条短的路径，算法返回错误代码；这种情况下，用重计算路径取代路径拼接，从而得到路径1-2-5-4.。

对于其它情况，对于N步的路径，路径拼接会计算2N或者3N步，这取决于拼接新路径的频率。对于对世界的改变作反应的能力而言，这个代价是相当低的。令人吃惊的是这个代价和拼接的步数M无关。M不影响CPU时间，而控制了响应和路径质量的折衷。如果M太大，物体的移动将不能快速对地图的改变作出反应。如果M太小，拼接的路径可能太短以致不能正确地绕过障碍物；许多不理想的路径（如1-2-5-3-4）将被找到。尝试不同的M值和不同的拼接标准(如每3/4 M步)，看看哪一种情况对你的地图最合适。

路径拼接确实比重计算路径要快，但它不能对路径的改变作出很好的反应。经常可以发现这种情况并用路径重计算来取代。也可以调整一些变量，如M和寻找新路径的时机，所以可以对该方法进行调整(甚至在运行时)以用于不同的情况。

Note：Bryan Stout 有两个算法，Patch-One和Patch-All，他从路径拼接中得到灵感，并在实践中运行得很好。他出席了GDC 2007（https://www.cmpevents.com/GD07/a.asp?option =C &V=11& SessID=4608）；一旦他把资料放在网上，我将链接过去。

Implementation Note：

反向保存路径，从而删除路径的开始部分并用不同长度的新路径拼接将更容易，因为这两个操作都将在数组的末尾进行。本质上你可以把这个数组看成是堆栈因为顶部的元素总是下一个要使用的。

与间隔一段时间重计算全部或部分路径不同的是，可以让地图的改变触发一次重计算。地图可以分成区域，每个物体都可以对某些区域感兴趣（可以是包含部分路径的所有区域，也可以只是包含部分路径的邻近区域）。当一个障碍物进入或者离开一个区域，该区域将被标识为已改变，所有对该区域感兴趣的物体都被通知到，所以路径将被重新计算以适应障碍物的改变。

这种技术有许多变种。例如，可以每隔一定时间通知物体，而不是立即通知物体。多个改变可以成组地触发一个通知，因此避免了额外的重计算。另一个例子是，让物体检查区域，而不是让区域通知物体。

监视地图变化允许当障碍物不改变时物体避免重计算路径，所以当你有许多区域并不经常改变时，考虑这种方法。

如果障碍物的运动可以预测，就能为路径搜索考虑障碍物的未来位置。一个诸如A*的算法有一个代价函数用以检查穿过地图上一点的代价有多难。A*可以被改进从而知道到达一点的时间需求（通过当前路径长度来检查），而现在则轮到代价函数了。代价函数可以考虑时间，并用预测的障碍物位置检查在某个时刻地图某个位置是否可以通过。这个改进不是完美的，然而，因为它并不考虑在某个点等待障碍物自动离开的可能性，同时A*并不区分到达相同目的地的不同的路径，而是针对不同的目的地，所以还是可以接受的。

有时，路径计算的限制因素不是时间，而是用于数以百计的物体的存储空间。路径搜索器需要空间以运行算法和保存路径。算法运行所需的临时空间（在A*中是OPEN和CLOSED集）通常比保存结果路径的空间大许多。通过限制在一定的时间计算一条路径，可以把临时空间数量最小化。另外，为OPEN和CLOSED集所选择的数据结构的不同，最小化临时空间的程度也有很大的不同。这一部分聚集于优化用于计算路径的空间代价。

一条路径可以用位置或者方向来表示。位置需要更多的空间，但是有一个优点，易于查询路径中的任意位置或者方向而不用沿着路径移动。当保存方向时，只有方向容易被查询；只有沿着整个路径移动才能查询位置。在一个典形的网格地图中，位置可以被保存为两个16位整数，每走一步是32位。而方向是很少的，因此用极少的空间就够了。如果物体只能沿着四个方向移动，每一步用两位就够了；如果物体能沿着6个或者8个方向移动，每一步也只需要三位。这些对于保存路径中的位置都有明显的空间节省。Hannu Kankaanpaa指出可以进一步减少空间需求，那就是保存相对方向（右旋60度）而不是绝对方向（朝北走）。有些相对方向对某些物体来说意义不大。比如，如果你的物体朝北移动，那么下一步朝南移动的可能性很小。在只有六种方向的游戏中，你只有五个有意义的方向。在某些地图中，也许只有三个方向（直走，左旋60度，右旋60度）有意义，而其它地图中，右旋120度是有效的（比如，沿着陡峭的山坡走之字形的路径时）。

一旦找到一条路径，可以对它进行压缩。可以用一个普通的压缩算法，但这里不进行讨论。使用特定的压缩算法可以缩小路径的存储，无论它是基于位置的还是基于方向的。在做决定之前，考察你的游戏中的路径以确定哪种压缩效果最好。另外还要考虑实现和调试，代码量，and whether it really matters.如果你有300个物体并且在同一时刻只有50个在移动，同时路径比较短（100步），内存总需求大概只有不到50k，总之，没有必要担心压缩的效果。

在障碍物比地形对路径搜索影响更大的地图中，路径中有大部分是直线的。如果是这种情况，那么路径只需要包含直线部分的终止点（有时叫waypoints）。此时移动过程将包含检查下一结点和沿着直线向前移动。

保存方向时，有一种情况是同一个方向保存了很多次。可以用简单的方法节省空间。

一种方法是保存方向以及朝着该方向移动的次数。和位置存储的优化不同，当一个方向并不是移动很多次时，这种优化的效果反而不好。同样的，对于那些可以进行位置压缩的直线来说，方向压缩是行不通的，因为这条直线可能没有和正在移动的方向关联。通过相对方向，你可以把“继续前进”当作可能的方向排除掉。Hannu Kankaanpaa指出，在一个八方向地图中，你可以去掉前，后，以及向左和向右135度（假设你的地图允许这个），然后你可以仅用两个比特保存每个方向。

另一种保存路径的方法是变长编码。这种想法是使用一个简单的比特（0）保存最一般的步骤：向前走。使用一个“1”表示拐弯，后边再跟几个比特表示拐弯的方向。在一个四方向地图中，你只能左转和右转，因此可以用“10”表示左转，“11”表示右转。

变长编码比run length encoding更一般，并且可以压缩得更好，但对于较长的直线路径则不然。序列（向北直走6步，左转，直走3步，右转，直走5步，左转，直走2步）用run length encoding表示是[(NORTH, 6), (WEST, 3), (NORTH, 5), (WEST, 2)]。如果每个方向用2比特，每个距离用8比特，保存这条路径需要40比特。而对于变长编码，你用1比特表示每一步，2比特表示拐弯——[NORTH 0 0 0 0 0 0 10 0 0 0 11 0 0 0 0 0 10 0 0]——一共24比特。如果初始方向和每次拐弯对应1步，则每次拐弯都节省了一个比特，结果只需要20比特保存这条路径。然而，用变长编码保存更长的路径时需要更多的空间。序列(向北直走200步)用run length encoding表示是[(NORTH, 200)]，总共需要10比特。用变长编码表示同样的序列则是[NORTH 0 0 ...]，一共需要202比特。

一个导航点（waypoint）是路径上的一个结点。与保存路径上的每一步不同，在进行路径搜索之后，一个后处理（post-processing）的步骤可能会把若干步collapse（译者：不好翻译，保留原单词）为一个简单的导航点，这经常发生在路径上那些方向发生改变的地方，或者在一个重要的（major）位置如城市。然后运动算法将在两个导航点之间运行。

当地图中的条件或者秩序会发生改变时，保存一条长路径是没有意义的，因为在从某些点开始，后边的路径已经没有用了。每个物体都可以保存路径开始时的特定几步，然后当路径已经没用时重新计算路径。这种方法虑及了（allows for）对每个物体使用数据的总量的管理。

在游戏中，路径潜在地花费了许多存储空间，特别是当路径很长并且有很多物体需要寻路时。路径压缩，导航点和beacons通过把多个步骤保存为一个较小数据从而减少了空间需求。Waypoints rely on straight-line segments being common so that we have to store only the endpoints, while beacons rely on there being well-known paths calculated beforehand between specially marked places on the map.（译者：此处不好翻译，暂时保留原文）如果路径仍然用了许多存储空间，可以限制路径长度，这就回到了经典的时间-空间折衷法：为了节省空间，信息可以被丢弃，稍后才重新计算它。