[转]关于寻路算法的一些思考

川长思鸟来 2022-07-15 15:57 280阅读 0赞

# 关于寻路算法的一些思考（1）：A\*算法介绍 #

物体的移动算法似乎显得很简单，然而寻路规划问题却十分复杂。考虑下面这个例子：

![7cc829d3gw1evvx18hteqj20ci08ujs9.jpg][]

这个单位的初始位置在地图的下方，想要到达地图的顶部。如果物体所能侦测到的地方（粉色部分所示）并没有障碍，那么物体就会直接向上走到它的目标位置。但在距离顶端较近的位置时，物体侦测到了障碍，因而改变了方向。该物体将不得不行进一个“U”形的路径绕过障碍物（如红色路径所示）。通过对比可知，寻路系统能够通过搜索一个更大的范围（如蓝色区域所示），并寻找一个更短的路线（如蓝色路径所示），使物体避免绕这条由凹陷障碍物造成的远路。

当然，可以通过改进物体的移动算法解决上图所示的陷阱。即要么避免在地图上创建有凹陷的物体，要么标记整个凹陷物体的整个凸包为危险区域（即除非目标在该区域内，否则避免进入该区域），如下图所示：

![7cc829d3gw1evvx192gq3j20ci08uwf2.jpg][]

而寻路系统则会让路径的决定提前，而不是像上图一样，物体直到移动到最后一刻才发现问题所在。对于“改进物体移动算法”和“使用寻路系统规划路径”两种方式有以下的折中：规划路径一般来说更慢，但效果更好；改进移动算法则会快一些，但有时候会卡住。如果游戏地图经常改变，那么路径规划的方式可能就意义不大了。我建议两者都使用：在更大的尺度、缓慢变换的地图和更长的路径上进行寻路规划，而对于局部区域、快速更改的地图和短的路径则使用改进的物体移动算法。

## 算法 ##

普通教科书上的寻路算法往往只应用在数学意义上的“图”上，即由顶点集合和边集合互相连接组成的结构。因此我们需要将一个栅格化的游戏地图转化为一个“图”：地图上的每一格可以作为一个顶点，而相邻的格子则各有一条边，如图所示：

![7cc829d3gw1evvx19fbcwj206u06uglm.jpg][]

我们只考虑[二维网格][Link 1]。如果你没有关于图的背景知识，可以参见[此链接][Link 2]。之后我会讨论如何在游戏世界中[创建其他类型的图][Link 3]。

大部分在AI和算法领域的寻路算法都是针对作为数学结构的“图”本身，而并非针对这种网格化游戏地图。我们希望寻找一种能利用游戏地图自身特征的方法。其实有些在二维网格图中我们认为是常识的事情，一些在普通图上使用的寻路算法本身可能并没有考虑到，例如如果两个物体距离较远，那么可能从一个物体到另一个物体的移动的时间和路径会较长（当然，假设空间中没有虫洞存在）。对于方向来说，如果方向是朝东，那么最优路径的路径也应当是大体往东走，而不是向西去。在网格中还可以从对称中获取信息，即先向北再向西，大部分情况下和先向西再向北等价。这些额外的信息可以让寻路算法更加快速。

## Dijkstra算法和最好优先搜索(best-first search) ##

Dijkstra算法简单说来，就是从起始点访问其他临近节点，并将该节点加入待检查节点集合中，使用松弛算法更新待检查节点的路径长度值。只要图不存在负权值的边，Dijkstra算法能够确保找到最短路径。在下面的图中，粉色的方格为起始点，蓝紫色的方格为目标点，青绿色的方格则为Dijkstra算法所扫描的节点。淡色的节点是距离起始点较远的节点。

![7cc829d3gw1evvx19tdbrj20em0ag0v3.jpg][]

贪心最好优先搜索算法大体与之类似，不同的是该算法对目标点的距离有一个估计值（启发值）。该算法并不在待检查节点集合中选取距离起始点近的节点进行下一步的计算，而是选择距离目标点近的节点。贪心最好优先搜索算法并不能保证寻找到最优路径，然而却能大大提高寻路速度，因为它使用了启发式方法引导了路径的走向。举例来说，如果目标节点在起始点的南方，那么贪心最好优先搜索算法会将注意力集中在向南的路径上。下图中的黄色节点指示了具有高启发值的节点（即到目标节点可能花费较大的节点），而黑色则是低启发值的节点（即到目标节点的花费较小的节点）。下图说明了相比于Dijkstra算法，贪心最好优先算法能够更加快速地寻路。

![7cc829d3gw1evvx1adi3lj20em0ag0ua.jpg][]

然而上述的例子仅仅是最简单的：即地图上没有障碍物。考虑前文中我们曾经提到的凹陷障碍物，Dijkstra算法仍然能够寻找到最短路径：

![7cc829d3gw1evvx1at4psj20em0agmzm.jpg][]

贪心最好优先算法虽然做了较少的计算，但却并不能找到一条较好的路径。

![7cc829d3gw1evvx1basdyj20em0agac5.jpg][]

问题在于最好优先搜索算法的贪心属性。由于算法仅仅考虑从目前节点到最终节点的花费，而忽略之前路径已经进行的耗费，因此即使在路径可能错误的情况下仍然要移动物体。

1968年提出的A\*算法结合了贪心最好优先搜索算法和Dijsktra算法的优点。A\*算法不仅拥有发式算法的快速，同时，A\*算法建立在启发式之上，能够保证在启发值无法保证最优的情况下，生成确定的最短路径。

## A\*算法 ##

下面我们主要讨论A\*算法。A\*是目前最流行的寻路算法，因为它十分灵活，能够被应用于各种需要寻路的场景中。

与Dijkstra算法相似的是，A\*算法也能保证找到最短路径。同时A\*算法也像贪心最好优先搜索算法一样，使用一种启发值对算法进行引导。在刚才的简单寻路问题中，它能够像贪心最好优先搜索算法一样快：

![7cc829d3gw1evvx1bplq1j20em0aggn6.jpg][]

而在后面的具有凹陷障碍物的地图中，A\*算法也能够找到与Dijkstra算法所找到的相同的最短路径。

![7cc829d3gw1evvx1c7ynxj20em0agq4v.jpg][]

该算法的秘诀在于，它结合了Dijkstra算法使用的节点信息（倾向于距离起点较近的节点），以及贪心最好优先搜索算法的信息（倾向于距离目标较近的节点）。之后在讨论A\*算法时，我们使用g(n)表示从起点到任意节点n的路径花费，h(n)表示从节点n到目标节点路径花费的估计值（启发值）。在上面的图中，黄色体现了节点距离目标较远，而青色体现了节点距离起点较远。A\*算法在物体移动的同时平衡这两者的值。定义f(n)=g(n)+h(n)，A\*算法将每次检测具有最小f(n)值的节点。

之后的系列文章将主要探讨[启发值设计][Link 4]、[具体实现][Link 5]、[地图表示][Link 6]等，并讨论与游戏中寻路问题相关的一系列话题。

# 关于寻路算法的一些思考（2）：Heuristics 函数 #

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

## 启发式函数在A\* 中的作用 ##

启发式函数可以用来控制A\*的行为。

*  一种极端情况，如果h(n)是0，则只有g(n)起作用，此时A\* 算法演变成Dijkstra算法，就能保证找到最短路径。
 *  如果h(n)总是比从n移动到目标的代价小（或相等），那么A\* 保证能找到一条最短路径。h(n)越小，A\* 需要扩展的点越多，运行速度越慢。
 *  如果h(n)正好等于从n移动到目标的代价，那么A\* 将只遵循最佳路径而不会扩展到其他任何结点，能够运行地很快。尽管这不可能在所有情况下发生，但你仍可以在某些特殊情况下让h(n)正好等于实际代价值。只要所给的信息完善，A\* 将运行得很完美。
 *  如果h(n)比从n移动到目标的代价高，则A\* 不能保证找到一条最短路径，但它可以运行得更快。
 *  另一种极端情况，如果h(n)比g(n)大很多，则只有h(n)起作用，同时A\* 算法演变成贪婪最佳优先搜索算法（Greedy Best-First-Search）。

所以h(n)的选择成了一个有趣的情况，它取决于我们想要A\* 算法中获得什么结果。h(n)合适的时候，我们会非常快速地得到最短路径。如果h(n)估计的代价太低，我们仍会得到最短路径，但运行速度会减慢。如果估计的代价太高，我们就放弃最短路径，但A\* 将运行得更快。

在游戏开发中，A\* 的这个特性非常有用。例如，你可能会发现在某些情况下，你宁愿有一个“好”的路径而不是一个“完美”的路径。为了平衡g(n)和h(n)之间的关系，你可以修改其中的任何一个。

注释： 从技术上来看，如果启发式函数值低估了实际代价，A\* 算法应该被称为简单的A算法(simply A)。不过，我将继续称之为A\* 算法，因为它们的实现是相同的，而且游戏编程社区对A算法和A\* 算法并不区分对待。

## 速度和准确性？ ##

A\* 基于启发式函数和代价函数来改变其行为的能力在游戏中非常有用。速度和准确性之间的折衷可以提高游戏速度。对于大多数游戏而言，你并不需要两个点之间的最佳路径。你只需要知道[近似的路径][Link 7]就足够了。你所需要的路径往往取决于游戏中接下来要发生什么，或是运行游戏的计算机有多快。

假设你的游戏中有两种地形，平原和山地，它们的移动代价分别是1和3，A\* 算法沿着平原搜索的路径长度是沿着山区的三倍。这是因为可能有一条绕着山地的平原路径。你可以把两个地图单位之间的启发式距离设为1.5可以加快A\* 的搜索速度。于是A\* 会将山区的移动成本3改为1.5，这个变化不像3到1那么大。这种方法在山区的移动成本不像之前那样高，因此不用花太多的时间去寻找绕着山地的路径。或者，你可以通过告诉A\* 在山区的移动成本为2而不是3，以减少山区周围路径的搜索量，来加快A\* 的搜索速度。现在，沿着平原搜索路径的速度只是沿着山区的两倍。这两种方法都放弃了理想路径来获得更快的搜索速度。

速度和准确性之间的权衡不需要是固定的。你可以根据CPU速率、用于寻路的时间片数、地图上物体的数量、物体的重要性、组(group)的大小、难度级别，或其他任何因素来进行动态地选择。一种动态的折衷启发式函数方法是，假设通过一个网格空间的最小代价为1，然后建立一个在下式中范围内的代价函数(cost function)：

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

你也应该考虑在启发式函数返回的绝对最小代价和期望最小代价中做选择。例如，如果你的地图上大部分地形是移动代价为2的草地而一些地形是移动代价为1的道路，那么你可以考虑让启发式函数假设没有道路，而只返回两倍的距离。

速度和准确性之间的选择并不必是全局的。在地图上的某些区域，你可以基于其准确性的重要性来进行动态选择。举个例子，假设我们在任意点都可能停止并重新计算路径或改变方向，那么为什么要困扰于后续路径的准确性呢？在这种情况下快速选择一条的路径更加重要。或者，对于地图上的某个安全区域，准确的最短路径并不那么重要；但在渡过危险区域时，安全和准确是必需的。

## 度量 ##

A\* 计算f(n) = g(n) + h(n)。为了将两个值相加，这两个值必须使用相同的单位去度量。如果度量g(n)的单位是小时，衡量h(n)的单位是米，则A\* 将认为g或h太大或太小，因此，要么你无法得到好的路径，要么A\* 的运行速度会更慢。

## 精确启发式函数 ##

如果你的启发式函数值正好等于最佳路径的距离，正如[下一部分][Link 8]的图中所示，你会看到A\* 扩展的结点非常少。A\* 算法所做的是在每个结点处计算f(n) = g(n) + h(n)。当h(n)和g(n)完全匹配时，f(n)的值不会沿着路径改变。不在正确路径上的所有结点的f值均大于正确路径上结点的f值。由于A\* 在考虑f值较低的点前，不会考虑f值较高的点，因此它肯定不会偏离最短路径。

### 预先计算的精确启发式函数 ###

构造精确的启发式函数的一种方法是预先计算每对结点之间的最短路径的长度。这种做法对于大多数游戏的地图而言并不可行。但是，有几种方法可以近似模拟启发式函数：

*  在细网格(fine grid)拟合合适密度的粗网格(coarse grid)。 预先计算粗网格中任何一对结点之间的最短路径。
 *  预先计算任何一对[路径点(waypoints)][waypoints]之间的最短路径。这是粗网格方法的一般化。

然后添加一个启发式函数h’来估计从任何位置到其邻近路径点的代价。(如果需要，后者也可以通过预计算得到。)最终的启发式函数将是：

或者，如果你想要一个更好但代价更大的启发式函数，则分别用靠近结点和靠近目标的所有w1, w2对上式进行计算。

### 线性的精确启发式函数 ###

在特殊情况下，不需要预先计算也能使启发式函数很精确。如果你的地图没有障碍物或者移动缓慢的区域，那么从初始点到目标点的最短路径应该是一条直线。

如果你使用的是简单的启发式函数（不知道地图上障碍物的情况），那么它应该匹配精确的启发式函数。如果没有，那么你选择的启发式函数的类型和衡量单位可能有问题。

## 网格地图中的启发式函数 ##

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

启发式函数的距离与所允许的移动方式相匹配：

*  在正方形网格中，允许向4邻域的移动，使用曼哈顿距离(L1)。
 *  在正方形网格中，允许向8邻域的移动，使用对角线距离(L∞)。
 *  在正方形网格中，允许任何方向的移动，欧几里得距离(L2)可能适合，但也可能不适合。如果用A\* 在网格上寻找路径，但你又不允许在网格上移动，你可能要考虑[用其它形式表现该地图][Link 9]。
 *  在六边形网格中，允许6个方向的移动，使用[适合于六边形网格][Link 10]的曼哈顿距离。

### 曼哈顿距离(Manhattan distance) ###

对于方形网格，标准的启发式函数就是[曼哈顿距离][Link 11]。考虑一下你的代价函数并确定从一个位置移动到相邻位置的最小代价D。在简单的情况下，你可以将D设为1。在一个可以向4个方向移动的方向网格中，启发式函数是曼哈顿距离的D倍：

如何确定D？你使用的衡量单位应该与你的代价函数相匹配。对于最佳路径，和“可采纳的”的启发式函数，应该将D设为邻近方格间移动的最低代价值。在一个没有障碍物、最小移动代价为D的地形上，每向目标靠近移动一步，g就增加D的移动代价同时h减少D的代价。此时将g和h相加时，f保持不变；这是启发式函数与代价函数的衡量单位相匹配的一个标识。你也可以通过放弃最优路径增加代价D或是降低最低和最高边际代价之间比率的手段，来让A\* 的运行速度更快。

![6941baebjw1epz9dwxxl3j20em06adh0.jpg][]

（注：上述图像的启发式函数中加入了 [决胜值(tie-breaker)][tie-breaker]

### 对角线距离 ###

如果你允许在地图中沿着对角线移动，那么你需要一个不同的启发式函数（有时被称为[契比雪夫距离(Chebyshev distance)][Chebyshev distance]）。偏东4个单位偏北4各单位(4 east, 4 north)的曼哈顿距离是`8*D`。然而，对对角线距离而言，你可以简单地移动4个对角线长度，因此启发式函数将为`4*D`。下面这个函数用于处理对角线，假设直线和对角线的移动代价都是D:

![6941baebjw1epz9dwpjxij20em06a75f.jpg][]

如果你沿对角线移动的代价并不是D，而是类似于D2 = sqrt(2)\*D，那么上面的启发式函数并不适合你。你会想要一个更复杂而准确的函数：

在这里，我们计算不走对角线所需要的步数，然后减去走对角线节约的步数。在对角线上的步数有min(dx, dy)个，其每步的代价为D2，可以节约2\*D的非对角线步数的代价。

[Patrick Lester用一种不同的方式来写这个启发式函数][Patrick Lester]，他使用`dx > dy`及`dx < dy`显式的表达。上面的代码有相同的测试方法，但它隐藏了内部对min函数的调用。

### 欧几里得距离 ###

如果你允许沿着任何角度移动（而不是网格方向），那么你或许应该使用直线距离：

然而，在这种情况下，你直接使用A\* 将可能有麻烦，因为代价函数g不会匹配启发式函数h。由于欧几里得距离比曼哈顿距离或对角线距离更短，你仍然会得到最短路径，但A\* 将需要更长的运行时间：

![6941baebjw1epz9dwfiv2j20em06aq4f.jpg][]

### 平方后的欧几里得距离 ###

我曾看到一些有关A\* 的网页推荐你使用距离的平方来避免欧几里得距离中耗时的平方根计算。

千万不要这样做！这无疑会导致衡量单位的问题。因为你要将函数g和h的值相加，它们的衡量单位需要相匹配。当A\* 计算f(n) = g(n) + h(n)时，距离的平方将比函数g的代价大很多，并且你会因为启发式函数的评估值过高而停止。对于较长的距离，这样做会接近g(n)的极端情况而对计算f(n)没有任何帮助，A\* 算法将退化成贪婪最佳优先搜索算法(Greedy Best-First-Search):

![6941baebjw1epz9dw5wlij20em0agac5.jpg][]

你也可以缩小启发式函数的度量单位。然而，此时你会面临相反的问题：对于较短的距离，相比于g(n)，启发式函数的代价将小得多，A\* 算法将退化成Dijkstra算法。

如果你经过分析发现平方根的代价很显著，要么使用快速平方根逼近欧几里得距离，要么使用对角线距离作为欧几里得距离的近似值。

### 多个目标 ###

如果你想要搜索几个目标中的一个，构建一个启发式函数h'(x)，它是h1(x), h2(x), h3(x), …中最小的，其中h1, h2, h3是每个目标点附近的启发式函数。

如果你想要搜索一个目标附近的点，要求A\* 算法找到一条路径通往目标区域的中心。当处理的节点来自开放集(OPEN set)时，在得到一个足够近的节点时退出。

### 值相等时的决胜法(Breaking ties) ###

在一些网格地图上，有许多具有相同的长度的路径。例如，在没有变化的地形平坦的区域中，使用网格会产生许多等长的路径。A\* 可能会搜索具有相同f值的所有路径，而不是其中一条。

![6941baebjw1epz9dvwou5j20dn09rjtx.jpg][]

f值的相等情况

为了解决这个问题，我们需要调整g或h的值；调整h的值通常会更容易。决胜值(tie breaker)必须根据顶点来确定（即，它不应该仅是一个随机数），而且它必须使f值不同。因为A\* 对f值排序，让f值不同意味着所有“等价”的f值中只有一个将被搜索到。

在相等的值中进行抉择的一种方式是稍微改变(nudge)h值的衡量单位。如果减小衡量单位，那么当我们朝着目标点移动时，f值将逐渐增加。不幸的是，这意味着A\* 将更倾向于扩展靠近初始点的结点，而不是靠近目标点的结点。我们可以稍微增大衡量单位(甚至是0.1%)。A\* 将更倾向于扩展靠近目标点的结点。

因子p的选择应该使得p<(移动一步的最小代价)/(期望的最长路径长度)。假设你不希望路径超过1000步，你可以使p = 1/1000。（注意，这稍微打破了“可受理”启发式函数，但在游戏中几乎从来不重要。）改变这个关键值(tie-breaking)的结果使A\* 在地图上搜索的结点比以前更少：

![6941baebjw1epz9dvhxazj20dn09r40a.jpg][]

加入比例决胜值后的启发式函数。

当有障碍物时，仍然要在其周围寻找路径，但要注意在绕过障碍物之后，A\* 搜索的区域非常少：

![6941baebjw1epz9dv481tj20dn09rjtl.jpg][]

加入比例型决胜值的启发式函数在在有障碍物时也能得到较好的效果。

Steven van Dijk建议，一个更直截了当的方法是把h作为比较函数的依据。当f值相等时，比较函数将通过检查h来解决f值相等的情况。

另一种方法是添加一个确定的随机数到启发式函数或边的代价（选择确定的随机数的一种方法是计算坐标的哈希值。）这比上面提到的调整h值能更好的解决f值相等的问题。感谢Cris Fuhrman的这个建议。

另一种的方法更倾向于沿着从起始点到目标点的直线路径：

这段代码计算初始-目标向量和当前-目标向量之间的向量叉积。当这些向量不平行时，叉积将很大。其结果是，这段代码选择的路径稍微倾向于沿着初始点到目标点的直线路径。当没有障碍物时，A\* 不仅搜索很少的区域，而且它找到的路径看起来非常好：

![6941baebjw1epz9duun6rj20dn09rabv.jpg][]

启发式函数中加入叉积作为决胜值，产生更好的路径。

但是，因为这个决胜值更倾向于从初始点到目标点的直线路径，当出现障碍物时会出现奇怪的结果（请注意，这条路径仍然是最佳的；它只是看起来很奇怪）：

![6941baebjw1epz9dunpxuj20dn09r76l.jpg][]

启发式函数中加入叉积作为决胜值，在有障碍物时效果不够好。

为了交互式地探索这种关键值方法的改进，请参考[James Macgill的A\* 应用][James Macgill_A_]?\[或使用[这个镜像][Link 12]或[这个镜像][Link 13]\]。使用”Clear”来清除地图，并选择地图上对角的两个点。当你使用“Classic A\*”方法时，你会看到关键值的效果。当你使用“Fudge”方法时，你会看到上面提到给启发式函数添加叉积后的效果。

另一种方法是小心地构造你的A\* 优先队列，使新插入的特定f值的结点总是比那些具有相同f值的旧结点有更高的优先级。

同时，另一种在网格上打破平局的方法是尽量减少转向。从上一结点到当前结点x,y的变化将告诉你你的移动方向。对于所有当前点到下一相邻点构成的边而言，如果x,y的移动方向与从上一结点到当前结点的移动方向不同，那么在移动代价中增加一个小的惩罚值。

如果多个相等的f值出现次数很多，上述对启发式函数的修改可能仅仅是一个“创口贴”般的低效方法。当有大量一样好的路径时，多个相等f值的出现会导致大量结点被搜索。考虑“更聪明而不是更辛苦”的方法：

*  替换[地图表征][Link 6]可以通过减少图形上结点的数量来解决这个问题。将多个结点归于一个，或删除重要结点外的所有结点。[长方形对称缩减(Rectangular Symmetry Reduction)][Rectangular Symmetry Reduction]是在方形网格上实现这个的一个办法；同时还可以考虑“framed quad trees”方法。[分层寻路(Hierarchical pathfinding)][Hierarchical pathfinding]使用具有少量结点的高层级图形来找到最佳路径，然后使用具有大量结点的低层级图形完善该路径。
 *  某些方法让大量结点独立但减少了被访问结点的数量。?[Jump Point 搜索][Rectangular Symmetry Reduction]跳过大面积含有大量关系的结点；该方法被设计用于方形网格。[跳过链接][Link 14]添加“捷径”的边来跳过地图上的区域。[AlphA\* 算法][AlphA_]添加了一些深度优先搜索到A\* 通常的广度优先的行为中，以便它可以探索单条路径而不是同时处理所有这些路径。
 *  [Fringe 搜索(PDF)][Fringe _PDF]?通过结点快速处理来解决这个问题。它分批处理结点，只扩展具有低f值的结点，而不是保存一个排序的开放集，并一次访问一个结点。这涉及到[HOT 队列][HOT]方法。

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

[这里][Link 15]有更详细的介绍，其中包含交互图。

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

<table style="margin-left: 0px; font-size: 13px; border: none !important; margin-top: 0px !important; margin-right: 0px !important; margin-bottom: 0px !important; padding: 0px !important; border-collapse: collapse !important; border-spacing: 0px !important; width: auto !important; table-layout: auto !important; background: none !important;"> 
 <tbody style="border: 0px; margin: 0px; padding: 0px;"> 
  <tr style="border: none !important; margin: 0px !important; padding: 0px !important; vertical-align: top !important; background: none;"> 
   <td style="font-size: 13px; text-align: center; border: none !important; margin: 0px !important; padding: 0px !important; vertical-align: top !important; font-family: Monaco, MonacoRegular, 'Courier New', monospace !important; background-image: none; background-attachment: initial; background-color: rgb(238, 238, 238) !important; background-size: initial; background-origin: initial; background-clip: initial; background-position: initial; background-repeat: initial;"> 
    <div style="border: none; margin: 0px; padding-right: 0px; padding-left: 0px; text-align: left; white-space: nowrap; padding-top: 5px !important; padding-bottom: 3px !important; line-height: 15px !important; background: none;"> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       1 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       2 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       3 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       4 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       5 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       6 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       7 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       8 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       9 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       10 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       11 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       12 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       13 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       14 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       15 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       16 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       17 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       18 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       19 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       20 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       21 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       22 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       23 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       24 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       25 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       26 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       27 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       28 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       29 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       30 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       31 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       32 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       33 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       34 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       35 
     </div> 
    </div></td> 
   <td style="font-size: 13px; text-align: center; width: 581px; border: none !important; margin: 0px !important; padding: 0px !important; vertical-align: top !important; font-family: Monaco, MonacoRegular, 'Courier New', monospace !important; background: none;"> 
    <div style="margin: 0px; padding-right: 0px; padding-left: 0px; text-align: left; white-space: pre; overflow: visible; tab-size: 4; border: none !important; padding-top: 5px !important; padding-bottom: 3px !important; line-height: 15px !important; background: none !important;"> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">OPEN</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">=</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">priority </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">queue </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">containing </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">START</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">CLOSED</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">=</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">empty </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">set</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">while</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">lowest </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">rank </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">in</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">OPEN </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">is</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">not</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">the </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">GOAL</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">:</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">&nbsp;&nbsp;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">current</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">=</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">remove </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">lowest </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">rank </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">item </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">from </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">OPEN</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">&nbsp;&nbsp;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">add </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">current </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">to</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">CLOSED</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">&nbsp;&nbsp;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">for</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">neighbors </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">of </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">current</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">:</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">cost</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">=</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">g</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">current</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">+</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">movementcost</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">current</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">,</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">neighbor</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">if</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">neighbor </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">in</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">OPEN </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">and</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">cost </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">less </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important;">than</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">g</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">neighbor</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">:</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">remove </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">neighbor </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">from </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">OPEN</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">,</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">because </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">new</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">path </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">is</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">better</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">if</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">neighbor </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">in</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">CLOSED </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">and</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">cost </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">less </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important;">than</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">g</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">neighbor</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">:</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">*</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">*</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">remove </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">neighbor </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">from </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">CLOSED</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">if</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">neighbor </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">not</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">in</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">OPEN </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">and</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">neighbor </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">not</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">in</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">CLOSED</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">:</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important;">set</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">g</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">neighbor</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">to</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">cost</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">add </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">neighbor </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">to</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">OPEN</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">set </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">priority </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">queue </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">rank </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">to</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">g</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">neighbor</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">+</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">h</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">neighbor</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">set </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important;">neighbor</span>' 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important;">s</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">parent</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">to</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">current</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">reconstruct </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">reverse </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">path </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">from </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">goal </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">to</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">start</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">by </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">following </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">parent</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">pointers</span> 
     </div> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

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

[请点击这里][Link 16] 查看Python和C++实现.

连通性

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

## 性能 ##

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

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

关于网格地图，我有一些[建议][Link 9]。

## 源代码和演示 ##

演示（demos）

这些demos运行于浏览器端：

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

代码

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

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

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

*  C++: [\[1\]][1][\[2\]][2][\[3\]][3][\[4\]][4]
 *  Java: [\[1\]][1 1][\[2\]][2 1][\[3\]][Link 12]
 *  Javascript: [\[1\]][demo 1][\[2\]][2 2][\[3\]][3 1][\[4\]][4 1][\[5\]][javascript]
 *  Python: [\[1\]][1 2]
 *  Objective C + Cocos2D: parts [\[1\]][1 3] and [\[2\]][2 3]
 *  Lua: [\[1\]][1 4][\[2\]][2 4][more][]
 *  Ruby: [\[1\]][1 5][\[2\]][2 5][\[3\]][3 2]
 *  C\#: [\[1\]][1 6][\[priority queue helper class\]][priority queue helper class]
 *  Unity: [\[1\]][1 7]
 *  Assembly: [\[1\]][1 8]
 *  Actionscript 3 (Flash): [\[1\]][1 9][\[2\]][2 6][\[3\]][3 3][\[4\]][4 2][\[5\]][5]
 *  Flex (Flash): [\[1\]][1 10]
 *  Go: [\[1\]][1 11]
 *  Prolog: [\[1\]][1 12]
 *  Processing: [\[1\]][1 13]

## 集合表示 ##

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

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

数据结构的选择不仅依赖于操作，还与每个操作运行的次数有关。成员隶属测试对每个已访问节点的每个邻节点运行一次，插入对每个要考虑的节点运行一次，删除最优对每个已访问的节点运行一次。大部分考虑的节点都会被访问，没有被访问的是搜索空间的边缘节点。评估各种数据结构下操作的开销时，我们应当考虑最大边缘值（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)改变其值或位置。

二叉堆

[二叉堆][Link 26]（不要和内存堆搞混了）是树型结构，存储在数组中。大部分树采用指针指向孩子节点，二叉堆则使用下标确定孩子节点。

采用二叉堆时，成员隶属测试需要扫描整个结构，时间复杂度O(F)。插入和删除最优元素都是O(log F)。

增加优先级操作很有技巧性，找节点用O(F)，而增大其优先级竟然只要O(log F)。然而，大部分优先级队列库中都没有该操作。幸运的是，这个操作不是绝对必要的。因此我建议，除非特别需要，不用考虑该操作。我们可以通过向优先级队列插入新元素来代替增加优先级操作。虽然最终可能一个节点要处理两次，但是相比实现增加优先级操作，这个开销比较少。

C++中，可以使用优先级队列[（priority\_queue][priority_queue]）类，这个类没有增加优先级方法，也可以使用支持这个操作的[Boost库可变优先级队列][Boost]。Python中使用的是[heapq库][heapq]。

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

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

有序跳跃列表（sorted skip lists）

无序链表的查找操作很慢，可以使用[跳跃列表][Link 28]加快查找速度。对于跳跃列表，如果有排序键，成员隶属测试只要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）][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的优先级队列页面][Lee Killough]，获得更多有关更先进的优先级队列的论文和实现。

混合表示

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

## 游戏交互循环 ##

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

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

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

提前退出

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

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

可中断算法

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

群体移动

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

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

另请参阅：将路径放到一块叫做[路径拼接][Link 30]，这部分在这些笔记的另一个模块中有介绍。

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

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

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

改进

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

# 关于寻路算法的一些思考（4）：A\* 算法的变体 #

## 定向搜索 ##

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

**迭代深化（Iterative deepening）**

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

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

## 动态加权 ##

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

有一个权值(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\*算法。

*  [D\*算法概述][D]
 *  [D\*文章1][D_1]
 *  [D\*文章2][D_2]
 *  [终身规划算法概述][Link 34]
 *  [终身规划算法论文(PDF)][PDF]
 *  [终身规划 A\*算法 applet][A_ applet]

## 跳跃点搜索 ##

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

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

## Theta\* ##

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

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

# 关于寻路算法的一些思考（5）：处理移动中的障碍物 #

一个寻路算法会计算出一条绕过静止障碍物的路径，但如果障碍物会移动呢？当一个单位移动到达某特定点时，原来的障碍物可能不在那点了，或者在那点上出现了新的障碍物。如果路线可以绕过典型的障碍物，那么只要使用单独的避障算法来配合你的寻路算法。寻路算法会寻找到期望的路径，并且在沿着路径的同时绕过障碍物。但是如果障碍物可以移动，进而导致路径不停地发生显著改变，就应考虑使用寻路算法来避障。

### 重新计算路径 ###

我们希望游戏世界随着时间改变。一条一段时间之前发现的路径，可能不再是现在的最优路径。用新的信息更新旧路径是值得的。下面列出的是一些用来判断决定是否需要重新计算路径的标准：

*  每N步一次：这样保证用来计算路径的信息不会旧于N步。
 *  当额外的CPU时间可用时：这样可以实现路径质量的动态调整。即使使用了更多的游戏单位，或者是在一台较慢的电脑上运行游戏，每个游戏单位的CPU使用率都可以降低。
 *  当游戏单位转弯或者通过一个关键路径点的时候。
 *  当游戏单位附近的世界发生改变的时候。

重新计算路线的主要缺点在于有很多路径信息被丢弃了。例如，如果路径长100步，并且每十步进行一次重新计算，那么路径的总步数是100+90+80+70+60+50+40+30+20+10 = 550。对于一个长M步的路径，总共大概进行了M^2步计算。因此，如果你想要得到很多条长路径，重新计算路线并不是一个好主意。重复使用路线信息，而非丢弃，这样会是更好的办法。

### 路径剪接 ###

当一条路径需要被重新计算时，意味着世界正在改变。给定一个变化中的世界，地图上的邻近部分比远处的部分更好了解。我们可以遵循一个局部修正策略：找到附近的一条好路径，并且假定较远的路径直到我们靠近它了才需要重新计算。我们可以仅仅重新计算路径的前M步，而不是整条路径：

1.  设p\[1\]..p\[N\] 是路径剩余部分（N步）
2.  计算一条从p\[1\]到p\[M\]新路径
3.  剪接新路径到旧路径中，通过移除p\[1\]..p\[M\]然后插入新路径到这些空位置上。

[![mtn\_path][mtn_path]][mtn_path]

因为p\[1\]和p\[M\]相距不到M步，所以新路线不太可能长。不幸的是，像新路径又长又不是非常好的情况，也有可能发生。上图展示了这样一个情况。原始的红色路径是1-2-3-4，棕色区域是障碍。如果我们到达2然后发现从2到3的路径被阻挡了，路径剪接会用绿色的路径2-5-3来替换2-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和进行新路径的寻找的时间，所以它可以被调整为适合不同的情况（即使是在运行的时候）。但是路径剪接并不能处理游戏单位需要确定位置进而来互相穿过的情况。

### 监视地图的改变 ###

选择重新计算全部或部分路径在特定的时间间隔，是对地图的改变来触发重新计算。地图可以分成不同的区域，每个游戏单位可以在特定的区域表现出兴趣。（所有包括部分路径的区域都可能是感兴趣的，或者仅仅是邻近的包含部分路径的区域）无论障碍进入或离开某个区域，那个区域就标记为已经改变，然后所有对那个区域感兴趣的游戏单位都会被通知，所以路径可以在考虑障碍发生变化这一前提下被重新计算。

这一技术有很多可能的变化。例如，我们可以仅仅在特定的时间间隔通知游戏单位而不是立即通知。并且多次改变可以被组合成一次通知，所以不再需要过多的进行重新计算路径。另一个变化是让游戏单位来查询地区的状态，而不是让地区来通知游戏单位。

监视地图的改变，避免了游戏单位在障碍物没有发生变化的时候进行重新计算，因此当你有很大地区不会经常发生改变的时候，可以考虑使用这种方法。

### 预测障碍物移动 ###

如果障碍物的移动可以被预测，那就可以在进行寻路时把未来的障碍物位置纳入考虑。像A\*这类算法有一个代价函数，来决定通过地图上某点的困难程度。A\*可以被修改成实时更新到达一点所需要的时间（由当前的路径长度决定），这个时间也可以被传入代价函数中。代价函数就可以把时间纳入考虑，然后就可以使用在那个时刻的障碍物预测位置，来决定那个地图位置是否无法通过。但是这个修改并不完美，因为它不会考虑在某个点等待障碍物离开路径的可能性，另外A\*并不是设计用来区分相同路线上的路径，而是时间不同的点。

# 关于寻路算法的一些思考（6）：预先计算好的路径的所用空间 #

有时候，影响计算寻路路径的不是时间，而是计算路径所需的上百个单元格所占的空间。寻路是需要内存来运行寻路算法，还需要额外内存来存储寻到的路径。运行寻路算法（A\*,开集或闭集）所需的临时空间经常会比存储这些寻到的路径所需的空间更大。通过在同一时间内只进行一条路径计算来限制游戏中的计算量，可以将你需要的临时空间降到最少。另外，对开集闭集的数据结构的选择也会对减少你所需的临时内存产生很大的影响。在本章中将会转而关注通过生成的路径减少使用的空间。

位置vs方向

一条路径可以是一堆位置或者一堆方向，位置需要更多的空间，但是它的优势在于它很容易决定一条路径上的一个任意的位置点或者方向而不用遍历这条路径。当存储方向的时候，只需要这个方向就可以很容易的决定；而位置只能通过遵循某个方向经由整条路径才能决定，在传统的栅格化地图中，位置可能使用两个16位的整数来存储，这样的话，每一步存储都需要32字节。因为它有更少的方向所以需要的空间就更少。如果一个单元格只能在四个方向上移动，每一步只需要2字节；如果单元格可以在六个或者八个方向上移动，每一步就会需要3字节。这些存储在存储位置上的路径点在路径中是非常重要的。Hannu Kankaanpaa建议你可以通过存储绝对的方向(比如”向北”)而不是存储这些相对方向(比如”右转60度”)来进一步的减少存储所需的空间。一些相对方向可能让一些单元格难以理解。比如说如果你的单元格在想北方移动，那它下一步就不大可能向南移动。在一个六方向的游戏中，你只有五个有意义的方向。在一些地图中你可能只有3个方向(直走，左转60度，右转60度)有意义。但是在一些其他的地图中右转120度可能才是一个有效的移动(比如通过Z字形路线爬一座陡峭的山)。

路径压缩

一旦一个路径被找到，它将会通过某种方式被压缩。我们可以使用一个通用的压缩算法，但是我们不会在这篇文章中讨论这个算法。一个针对具体路径的压缩算法可以用来缩短基于位置的路径或者基于方向的路径。在做决定之前，考虑你游戏中的具体的典型路径来决定哪一种压缩算法最适合你所寻到的路径。同时 也要考虑在你游戏中实施(或者调试)的可行性，代码的体积还有这个压缩算法是否真的很重要。如果你有 个300单元格的限制，在同一时间只有50个单元格在移动，并且路径很短(只有100步)，那么所需要的内存可能最多只有50k，那么你就不需要再考虑使用路径的压缩算法了。

位置点存储

在一张地图中如果障碍是寻路的主要影响因子而不是地形，那么就可以将路径分成很多条线段，如果是这种情况的话，那么一条路径只需要包括这些线段集合的各个终点位置(有时也被称为路径点)。运动就是由检查这条路径的下一个终点位置并沿着直线向终点移动组成。

方向存储

当方向被存储的时候，它可能是在一排中多次出现的方向，你可以利用那种常见的模式使用较少的空间去存储那条路径。

一种最好的存储路径方式是同时存储这个方向和指明单元格将在这个方向上移动多少次的数字。不同于位置存储的优化，当这个方向在这一排中并没有多次使用的时候这种优化可能会变得很糟。当然，对于很多直线路径的位置存储这种方式很有效，由于线可以不与的行走方向之一对齐，这种情况并不适用方向存储的压缩。当有多种可选方向时，你可以选择清除“一直直走”作为一个可行的方向。Hannu Kankaanpaa指出在一个八方向图中，你可以清除直走，后退还有135度左，右转（假设你的地图允许这样），然后你可以仅仅使用2字节去存储每个方向。

另一种存储路径的方法是使用可变长度的编码。这是指使用一个单字节去存储大部分的一般性步骤比如说：直走。使用数字1去标记转向，在跟上一个数字1使用一些字节去表示转向，在一个4向图中，你只可以左转或者右转，所以你可能需要使用10来表示左转11来表示右转。

可变长度编码更为通用，可能比游程编码工作起来更好，但是对于长直型的路径就不如混合编码了。这个(北向，六步直走，左转，直走三步，右转，直走5步，左转，直走六步)的序列被使用长编码的\[(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字节。如果初始化的方向和每次转向代表一步，你可以每次转向省下一字节，这样你只需要20字节就可以存储这条路径。但是使用可变长度编码在遇到较长的路径可能需要使用更多的空间。如果使用游程编码这个序列(north,直走200步)是\[(NORTH,200)\]只需要10个字节，同样的序列如果使用可变长度编码就变成\[NORTH 0 0…\],总共需要202字节。

计算路径点

路径点是指一条路径上的所有点。寻路完成后处理步骤时，可以折叠多个步骤到一个单一的路径点钟，通常存储的是路径改变方向的点，或者像城市的主要位置点，而不是存储一路走来的每一步。然后使用算法在路径点之间沿着路径运动。

限制路径长度

考虑到地图条件或者指令可能会发生变化，存储一条长路径可能意义并不大，因为余下的路径点可能根本就不会被使用到。每个单元格可以在路径开始的时候存储一些合适的步骤数，然后在路径快要走完时在重新计算心的路径。这种方法可以控制每个单元格的数据量。

总结

路径在游戏中可能占用很多空间，尤其是当路径很长，并且这个路径上有很多游戏单元的时候。路径压缩、路径点还有信标（beacon）都会在一定程度上减少在一小块数据里存储很多行路步骤的空间。在一条直线路径上加入需要存储路径点的话，只需要存储末尾点就可以了，信标是依靠在地图上特意标明的地方之间事先计算好的路径上使用。如果路径仍然需要占用很大的空间，就要限制路径的长度了，在经典的实时路径计算中是这样做的：为了节省空间，消息可以被忽略并且延迟计算。

# 关于寻路算法的一些思考（7）：地图表示 #

在本系列文档大部分内容中，我都假设A\*用于某种网格上，其中的“节点”是一个个网格的位置，“边”是从某个网格位置出发的各个方向。然而，A\*可用于任意图形，不仅仅是网格，有很多种地图表示都可以使用A\*算法。

地图表示可能对性能和路径的质量产生很大影响。

寻路算法不是线性的，而是越来越差。如果需要行进的距离翻倍了，那么会消耗超过两倍的时间来找路径。你可以想象寻路算法是在搜索一个类似圆的区域，当圆的直径加倍时，区域变成原来的四倍。一般来说，在地图表示中，节点越少，A\*算法越快。而且节点越匹配角色单元将要移向的位置，路径质量越好。

游戏中，用于寻路的地图表示不需要和用于其他用途的地图表示一样。但是采用相同的表示是一个不错的起点，直到你发现需要更好的路径或更高的性能。

### 网格（Grid） ###

网格图将世界（world）均匀分割为小的规则图形，这些图形有时被称为“图块（tile）”。常用的网格有[正方形、三角形和六边形][Link 1]。网格很简单，也很容易了解，很多游戏都采用它来表示世界，因此本文中我重点关注网格。

![6941baebjw1euyhvuojoxj2051051t8r.jpg][]

在《[BlobCity][]》游戏中我采用网格表示，因为在每个网格位置，移动成本都不同。如果在一大片空间内，移动成本都是均匀的（正如前文我举过的例子），那么用网格可能就相当浪费。因为此时，A\*无需一次走一步，它可以跳过一大片区域走到另一端。在网格上寻路，得到的也是网格上的路径，可以通过[后期处理，消除锯齿状移动][Link 40]。但是如果你的角色单元没有限制必须在网格上移动，或者你的世界甚至不采用网格，那么在网格上寻路可能不是最好的选择。

### 图块移动（Tile movement） ###

![6941baebjw1euyhvvmk5uj2047047aa0.jpg][]

即使在网格中，也可以选择沿[图块、边或顶点][Link 1]移动。图块是默认选项，尤其是角色单元只能移动到图块中心的那些游戏。在上图中，在A处的单元可以移到所有标B的位置。你也许还允许对角线移动，代价相同或者更高。

如果你采用网格寻路，但角色单元不限制仅沿网格移动，并且移动成本是均匀的的，那么你可能想要拉直路径，即如果某两个节点之间没有障碍，可以从一个节点沿直线移动到另一个远处的节点。

### 边移动（Edge movement） ###

![6941baebjw1euyhvux80uj2047047q2t.jpg][]

如果角色单元可以移动到一个网格内的任何一点，或者图块很大，就应该考虑，你的应用是否选择边寻路或顶点寻路更好。

一个单元通常从一个边（一般是边的中点）进入图块，并从另一个边离开那个图块。图块寻路中，单元移到图块中心，但边寻路中，单元直接从一个边移到另一个边。我写了一个[java applet，演示绘制边之间的道路][java applet]，可能帮助说明边是如何使用的。  
顶点移动（Vertex movement）

![6941baebjw1euyhvvbd93j2039038glg.jpg][]

网格图中的障碍通常在顶点处有拐角。在障碍物周围，最短的路径就是要绕过这些拐角。顶点寻路中，角色单元从一个拐角移到另一个拐角。这是一种最节省开销的移动，但是要依据角色单元的大小调整路径。

### 多边形地图（Polygonal maps） ###

除了网格，最常用的是多边形表示。如果一大片区域的移动成本是均匀的，并且角色单元可以沿直线移动，而不是沿网格移动，你可能想采用一种非网格的表示。在你的游戏中，即使其他东西采用网格，寻路也可以使用非网格的图形表示。这里有个简单的例子，是一种多边形的地图表示。这个例子中，角色单元需要绕过两个障碍。

![6941baebjw1euyhvp5g44j20ci074q3g.jpg][]

想象在这个地图中角色单元如何移动。最短路将在这些障碍的拐角点之间，因此我们选择这些拐角点（红色圆点）作为A\*算法的关键“导航点”；每次地图改变，就计算一次这些点。如果障碍和网格对齐，那么导航点和网格顶点对齐。此外，寻路的起点和终点应当标示在图中；每次调用A\*，都需要将这两个点加到图上。

除了导航点，A\*需要知道哪些点是连通的。一个简单的算法是构建[可视图][Link 41]：互相可见的点对。这个简单算法可能满足你的需求，尤其是当游戏中地图不常改变时。但是如果这个算法太慢，你可能需要一个更复杂的算法。另外，在图上添加起点和终点后，对任意两个顶点（包括起点和终点），如果两点可见，添加一条这两点连接而成的边。

A\*需要的第三条信息是点之间的行进时间。如果在网格上移动，时间就是[曼哈顿距离][Link 8]（[manhattan distance][Link 8]）或[对角网格距离][Link 42]（[diagonal grid distance][Link 42]）。如果可以在导航点之间直接移动，时间就是[直线距离][Link 43]。

接下来，A\*考虑从导航点到导航点的路径，图中粉色线就是其中一条路径。如果导航点很少，而网格位置很多，这种方法要比从网格点到网格点的寻路快得多。如果路上没有障碍，A\*性能非常好——起点和终点将由边连接，无需扩展任何导航点，A\*可以立即找到路径。即使有障碍，A\*也将从一个拐角点跳到另一个拐角点，直到找到最优路径，这将仍然比在网格位置间寻路要快得多。

维基百科中有更多关于机器人文学中的[可视图][Link 41]。

### 复杂性管理（Managing complexity） ###

上边的例子非常简单，图也很合理。然而在一些有很多开放区域或长廊的地图中，可视图的一个弊端就显现出来了。连接每对障碍拐角点的一个主要缺点是，如果有N个拐角点（顶点），则至多有N2条边。下图展示了这个问题：

![6941baebjw1euyhvucgynj20b5086gms.jpg][]

这些额外的边主要影响内存使用。相比网格，这些边提供一种捷径，大大加快了寻路。虽然有算法可以删除冗余的边，以简化图形，但删除之后仍然有很多边。

可视图的另一个缺陷是，每次调用A\*，都要添加起点和终点，以及以它们为顶点的新边，然后在找到路径之后，删除这些添加的东西。节点很好加，但增加边需要考虑从这些新节点到所有已有节点的可见情况，如果地图很大，这可能会很慢。一种优化方案是只看附近的节点，或者也可以用简化可视图，删除和两个顶点都不相切的边（这种边永远不会出现在最短路中）。

### 导航网（Navigation Meshes） ###

不用多边形表示障碍，而是将可行区域用不重叠的多边形表示，这也被称为导航网。这些可行区域还可以附有一些信息（如“要求游泳”或“移动成本为2”）。这种表示法不需要存储障碍。

前面的例子就变成了下图这样：

![6941baebjw1euyhvti7dgj20d20b7mxo.jpg][]

我们可以像处理网格一样处理这个，同样的，可以选择多边形中心点、边或顶点作为导航点。

### 多边形移动（Polygon movement） ###

同网格一样，每个多边形的中心提供了一个合理的寻路节点集。此外，还要添加起点和终点，以及这两个点与所在区域中心点所连成的边。下图中，黄色路径是沿多边形中心点寻路所得的路径，粉色路径是理想路径。

![6941baebjw1euyhvt2bypj20d20b7jsc.jpg][]

可视图表示可以产生那条粉色理想路径。采用导航网使地图易于管理了，但是路径的质量受到影响。我们可以消除路径，使其看起来更好一些。

多边形边移动（Polygon edge movement）

移到多边形的中心通常是不必要的。相反，我们可以穿过相邻多边形的边而移动。下面这个例子中，我选择每条边的中点。黄色路径是沿边中点寻路所得的路径，相比理想的粉红色路径，是一条不错的路径。

![6941baebjw1euyhvsp7arj20d20b7aay.jpg][]

你也可以增加成本，在边上选更多的点，来产生更好的路径，

### 多边形顶点移动（Polygon vertex movement） ###

绕过障碍的最短路径是绕过其拐角，这也是为什么我们在可视图表示中采用拐角点，在这里即是导航网的顶点：

![6941baebjw1euyhvtw5ypj20dd0bhq3x.jpg][]

上图中，路上只有一个障碍。当要绕过障碍时，黄色路径会穿过一个顶点，粉色路径（理想路径）也一样。然而，可视图方法将直接连线起点和障碍拐角点，导航图则要更多步。这些步骤不应该沿顶点走，因此路径看起来不自然，有“抱墙”行为。

### 混合式移动（Hybrid movement） ###

对于多边形的哪个部分可以用作寻路导航点，我们并没有任何约束。你可以在一条边上多加一些点，顶点也不错，多边形的中心点则基本没用。下图是采用了边中点和顶点的一种混合方案：

![6941baebjw1euyhvnp6owj20dd0bhab9.jpg][]

注意要绕过障碍，需要穿过一个顶点，但在其他地方，则可以穿过边中点。

### 路径消除（Path smoothing） ###

只要移动成本是固定的，路径消除相当容易。算法很简单：如果点i到点i+2可见，删除点i+1，循环直到邻节点之间都不可见。剩下的只有绕过障碍物拐角点的导航点。这些点都是导航网的顶点。因此如果使用路径消除，就不需要采用边中点或多边形中心点作为导航点，只要顶点就可以了

上面的例子中，路径消除可以将黄色路径变成粉红色路径。然而，寻路算法并不知道这些更短的路径，因此它的决策不会优化。导航网是一种近似地图表示，而可视图是一种精确地图表示。缩短在导航网中找到的路，结果并不总能像通过可视图找到的路一样好。

### 分层（Hierarchical） ###

平面地图只有一层。而游戏很少只有一层——往往有一个“图块”层，然后有一个“子图块”层，物体可以在图块中移动。然而我们通常只在高层寻路。你也可以添加更高的层，如“房间”。

在地图表示中，节点越少，寻路越快。还有一种加快寻路速度的方法是多层次搜索。例如，要从你家到另一个城市的某个位置，你会找到一条路，从你的椅子到你的车，从车到街道，从街道到高速公路，从高速公路到城市边缘，再从那儿到另一个城市，然后到一个街道，到一个停车场，最终到达目的地门前。此时，有下述几层搜索：

*  街道层，你从一个位置走到附近的某个位置，但不会走出这条街。
 *  城市层，你从一条街道走到另一条，直到找到高速公路。你无需担心进入建筑物或停车场，也不用担心在高速公路上行驶。
 *  州层，在高速公路上，你从一个城市到另一个城市。在到达目的城市之前，你无需担心城市内的街道。

将问题分层，可以忽略很多选项。例如当从一个城市到另一个城市时，考虑路上每个城市的每条街道是很乏味的。相反，你可以忽略它们，只考虑高速公路，问题就变得很小且易于管理，解决也变得很快。

分层地图在表示上有很多层。异构层次结构（heterogenous hierarchy）通常有固定层数，各有不同特点。例如，《Ultima 5》有一个“世界”地图，上边有城市和地牢。你可以进入一个城市或地牢，这就进入地图的第二层。另外，世界之上还有世界，从而是一个三层结构。这些层可以是不同的类型（图块网格、可视图、导航网、路标）。而同质层次结构（homogeneous hierarchy）层数任意，每层都有相同的特性。四叉树和八叉树就是同质层次结构的。

分层地图中，寻路可能发生在几个层次。例如，假设一个 1024×1024 的世界被划分为 64×64 个“区域”，则可以这样找到一条路径，从玩家位置到区域边缘，然后从一个区域到另一个区域，直到到达目的区域，然后从那个区域的边缘到达目的位置。粗级别上，更容易找到长路径，因为寻路算法没有考虑所有的细节。当玩家穿过每个区域时，可以再次调用寻路算法，找一个短路径。保证问题规模很小，寻路算法就可以运行得更快。

你可以结合使用分层和图搜索算法，如A\*，但是不需要每一层都采用一样的算法。对一些小的层级，你可以预算所有节点间的最短路（用Floyd-Warshall或其他算法）。在分层地图中，通常找不到最优路径，但一般都接近最优。

还有个类似的方法是改变分辨率。首先，绘制低分辨率路径。当接近一个点时，用高分辨率精化路径。这个方法可以结合[路径拼接][Link 30]使用，以避免移动障碍。

一些文章：《[“龙腾世纪：起源”中的寻路算法][Link 44]》解释某商业游戏中使用的几种分层方法，《[采用线性预处理的超快最短路查询][Link 45]》在道路图中使用“运输节点”\[PDF\]，《[游戏网格地图的运输节点][Link 46]》、《[分层A\*：有效搜索抽象层][A 2]》、《[道路网路线规划][Link 47]》（Dominic Schulte的博士论文），逐层注解A\*（[第一部分][Link 48]，[第二部分][Link 49]，[源代码][Link 50]）。

### 环绕式地图（Wraparound maps） ###

如果你的世界是球形或环形的，物体可以从地图的一端绕到另一端。最短路可能在任一方向，因此必须探索所有的方向。如果用网格，环绕时可以用[启发式方法][Link 43]。此时，我们不用abs(x1 – x2)，而采用min(abs(x1 – x2), (x1+mapsize) – x2, (x2+mapsize) – x1)，即考虑三种情况的最小值：待在地图上不绕行，x1在左边时绕行，或x2在左边时绕行。绕行每个轴时都这样做。本质上来说，你计算启发值时，假设地图与其副本邻接。

### 连通组件（Connected Components） ###

有些游戏地图中，起点和终点之间根本就无路可通。如果用A\*找路，它会探索图的很大一个子集，才能确定根本没路。如果可以预先分析地图，用不同的标记标识出所有的连通子图，那么在找路之前，首先检查起点和终点是否都在同一个子图中。如果不在，那么这两者之间无路可通。另外分层寻路在这也可以用，特别是子图之间有单向边时。

### 道路图（Road maps） ###

如果你的角色单元只能在道路上走，你可能需要提供A\*道路和交叉口的信息。每个交叉口是图上的一个节点，每条路是图上一条边。A\*找从交叉口到交叉口的路，这比用网格表示要快得多。

有时，角色单元的起点和终点可能不在交叉口。此时，每次运行A\*时，都要修改点/边图（和可视图和导航图采用的技术一样），将起点和终点作为新节点加到图中，然后在这两个点和最近的交叉点之间连线。寻路结束后，再删除这些额外的节点和边，这样图在下次调用A\*时还可以使用。

![6941baebjw1euyhvofgp6j20b40bct9f.jpg][]

上图中，交叉口是寻路图中的节点，节点之间的道路是边，且每条边都应给定道路行驶距离。在这个框架中，你可以把单向道路作为图上的单向边。

如果你想给转向分配成本，你可以稍稍扩展这个框架：将原来单一的位置节点，变为<位置，方向>节点（静态空间的一个点），其中方向指你到达那个位置后所面向的方向；将原来从X到Y的边，换成从<X，方向>到<Y，方向>的边（代表直行），和从<X，方向1>到<Y，方向2>的边（代表转向）。每条边都或者代表直行，或者代表转向，不可能两者都是。然后你可以给代表转向的边分配成本。

如果你还要考虑转向限制，如“只能右转”，你可以改变上述框架，即结合使用那两种边，每个转向边之后都是直行。例如，在这个框架中，你想表示一个限制“只能右转”：添加一个直行边<X，北>到<Y，北>，一个转向边<X，北>到<Z，东>，转向之后是直行。不要添加<X，北>到任何向西的边，因为这意味着左转，也不要添加任何向南的边，因为这意味着掉头。

利用上述框架，可以对一个大型市中心建模，其中有单向道路，特定路口转向限制（通常禁止掉头，有时禁止左转），以及转向成本（建模在右转之前减速和等待行人）。相比网格图，道路图中A\*找路相当快，因为每个节点处的选择很少，而且图上的节点也相对较少。

如果是大型道路图，一定要读读[Goldberg和Harrelson发表在ALT（A\*, Landmarks, Triangle inequality）上的文章][Goldberg_Harrelson_ALT_A_ Landmarks_ Triangle inequality]（[PDF][PDF 1]，或者[这篇论文][Link 51]）。

### 跳跃链（Skip links） ###

基于网格创建的寻路图，一般给每个位置分配一个顶点，给相邻位置之间的每个可能的移动分配一条边。然而边不一定必须是相邻顶点之间的，“跳跃链”或“快捷链”就是非相邻点之间的边，它可以加快寻路进程。

跳跃链的移动成本怎么算呢？有两种方法：

*  使成本匹配最优路径的移动成本。这保留了A\*的优良特性，如寻找最优路径。为了将A\*推向正确的方向，要[打破跳跃链和常规链之间的关联][tie-breaker]，即将跳跃链的成本减少1%左右。
 *  使成本匹配启发成本。这对性能有很大影响，但是放弃了最优路径。

添加跳跃链类似于分层地图，花费更少的精力，但往往能给你一样的性能。

对于有地下室和走廊的网格图，[矩形对称性缩减和跳跃点搜索][Rectangular Symmetry Reduction]提供两种方法建立跳跃链。矩形对称性缩减（Rectangular Symmetry Reduction）静态建立附加边（他们称为宏边），然后调用标准的图搜索算法。跳跃点搜索（Jump Point Search）动态建立长边，是图搜索算法的一部分。对于道路图和其他类型的图，[抽象分层][Link 52]值得一看。

### 路标（Waypoints） ###

路标是路径上的一个点。路标可以具体到每条路，或者是游戏地图的一部分。路标可以手动输入或自动计算。很多实时策略游戏中，玩家点击就可以手动添加特定路径的路标。当自动计算时，路标可以简化路径表示。地图设计者可以在地图上人工添加路标（或“信标灯”），以标识好路径的位置，或者也可以用算法自动标识。

使用跳跃链是为了加快寻路，因此跳跃链应当放在设计者设置的路标之间，这可以使其利益最大化。

如果路标不是很多，可以预算每对路标之间的最短路（用全对最短路算法，不用A\*）。常见的情况就是，一个角色单元先按照自己的路径到达一个路标，然后按照预算的路标间的最短路走，最后离开路标这个高速路，走自己的路到达目标。

如果路标或跳跃链的成本错误，可能导致找到次优路径。有时我们可以通过后期处理或在移动中，消除一个糟糕的路径。

### 图形格式建议（Graph Format Recommendations） ###

一开始你在已使用的游戏世界表示中寻路，如果你不满意，考虑将游戏世界转换为方便寻路的另一种表示形式。

很多网格游戏中，地图的很多大块区域移动成本都是均匀的，但是A\*不知道这些，并且浪费时间来探索它们。创建一个简单图（导航网，可视图，或者网格图的分层表示）可以帮助A\*。

移动成本固定时，[可视图][Link 3]产生的是最优路径，且A\*运行很快，但是[边存储耗费大量内存][Link 53]。网格允许移动成本有细微改变（[地形][Link 54]，[斜坡][Link 55]，[惩罚用的危险区域][Link 56]等），边存储耗费内存少，但点存储耗费很多内存，而且A\*可能很慢。导航网居于两者之间。在大块区域移动成本均匀时，它效果很好，而且允许移动成本的些微改变，还能产生合理的路径。这些路径并不总如可视图产生的一样短，但是通常都是合理的。[分层地图][Hierarchical pathfinding]采用多层表示来处理长距离内的大致路径，以及短距离内的详细路径。

你可以读读这篇很形象的[文章][Link 57]，了解更多关于导航网的知识。注意这篇文章比较了：（a）仅保持可行多边形和仅保持导航点，（b）沿顶点走和沿多边形中心点走。这些大多是正交的。保持可行多边形有利于后期动态调整路径，但是并非所有的游戏都需要。使用顶点更有利于避免障碍，并且如果你采用了路径消除，还不会影响路径质量。如果没有路径消除，边的效果可能更好，所以考虑边或是边+顶点。

除了给网格地图构建一个独立的非网格表示，你也可以改变A\*，使其更好得理解成本均匀分布的网格地图。可以参照[跳点搜索][Link 58]在方格上加速A\*的方法，以及[Theta\*][Theta 1]在网格上生成非网格移动的方法。

# 关于寻路算法的一些思考（8）：长期和短期目标 #

我已经集中讲过了从一个地方到另一个地方寻找路径的任务。然而，一个与之同等重要的问题是：一旦我有一个路径，我该怎样沿着它移动？最明显的答案是从一个位置到另一个的位置的直线移动。然而，你可能想在曲线上移动，或者多次的移动。你可能想把位置偏离成为低优先级的目标。一个更高层次的问题是：你要去哪里？除非你先回答的是高层次的问题，路径规划不是很有用。当然，目标设定的一个形式就是让用户点击目的地。不过，你可能已经自动执行了任务——探索，间谍活动，攻击和建设都是常见的方式。

### 单元移动 ###

我已经集中讲解了在寻路问题，它减少了从一个位置移动到另一个位置中的问题，也减少了从一个空间到相邻空间的许多小问题。

你可以从一个位置到另一个位置的直线上移动，但有很多可选方案。考虑一下这幅图上的四个移动路径：

[![splines][]][splines]

红色路径是标准方法：从一个正方形的中心移动到另一个正方形的中心移动。绿色路径比较好些：代替了在瓷砖的中心，而在瓷砖边沿之间的直线上移动。你也可以尝试在瓷砖的对角的连线上移动。蓝色的路径使用样条曲线，深蓝色的是低阶样条曲线，浅蓝色是高阶样条曲线（这需要花更长时间来计算）。

对角线和瓷砖边沿之间的连线是最短的解决方案。但是，曲线能使你的单元格看起来少了些机械化，多了些“活力”。这是一个低级的把戏，但不是最好的。

如果您的单位不能轻易转向，你可能在绘制运动路径时，要考虑到这一点。克雷格·雷诺兹有一个关于[转向][Link 59]的网页，其中有一页是关于转向和用Java小程序来演示各种各样的行为。如果你有不止一个的单元沿着路径移动时，你可能还需要研究[群集][Link 31]。克雷格建议，你应该将路径当做一个指导路线，它反应出了你偏离了条件要求，而不是作为你的单元必须要访问的位置清单。

如果你正在使用网格寻路，你的单位是不受约束的网格，这和移动成本是一致的， 当两点没有障碍物的时候，你可能希望把[路径伸直][Link 38]，然后在两点之间的直线上运动就可以遥遥领先。如果你使用的导航网格，去看看[漏斗算法][Link 60]。

### 行为标志或堆栈 ###

你的单位也许有一个以上的目标。例如，你可能有一个像“间谍活动”的总体目标，但也可能是一个更直接的目标，像“去敌人司令部”。此外，还有可能是暂时的目标，如“避开巡逻卫士”。下面是一些目标的说明：

*  停止：留在当前位置
 *  停留：停留在一个区域
 *  逃跑：移动到安全区域
 *  撤退：移动到安全区域，同时击退敌方单位
 *  探索：查找并了解了这一点信息是已知的领域
 *  游荡：漫无目的的四处移动
 *  搜索：寻找一个特定的对象
 *  间谍：靠近一个对象或单位来更多地了解它，而不被发现
 *  巡逻：反复走过某个区域，以确保没有敌方单位通过它
 *  保卫：停留在一些对象或单位附近，使敌方单位离开
 *  警卫：入口附近保持在一定区域，以保持敌军单位出
 *  攻击：移动到一些对象或单位，以捕获或消灭它
 *  环绕：与其他单位一起，尽量包围一个敌方单位或对象
 *  回避：从某些对象或单元移开 避免：与任何其他单位烤翅距离
 *  跟随：保持近一些单位，因为它到处移动
 *  群组：寻求和形成群组单位
 *  工作：执行一些任务，如采矿，耕种，或搜集

对于每一个单位，你可以用一个标志来表明该行为是执行。用多个层次来保持一个行为堆栈。该堆栈的顶部是最直接的目标，堆栈的底部将是总体目标。当你需要做一些新的东西，但后来想回去你过去正在做的东西，那就压入栈中一个新的行为。如果你需要做一些新的东西，但不想再回到老的行为，那就清除栈。一旦你的完成了某些目标，把它从栈中弹出，并开始执行堆栈中的下一个行为。

### 等待移动 ###

运动算法会碰上那些曾被认为不会出现在寻路过程中的障碍，这是不可避免的。一个容易实施的技术是基于其他障碍物会首先移动的假设。当障碍物是一个友好的单位时，这是特别有用的。当一个障碍挡住了去路，并且它只是等待一段时间后才移动。如果那段时间之后它还是没有移动，就要重新计算它周围或到目的地的路径。如果提前检测障碍物，你的单位只需简单地走慢一点来给其他单位更多时间离开挡你的道路。

两个单元会互相碰撞，并且每个将等待另一个继续行进，这种情况是非常有可能的。在这种情况下，优先级方案可以派上用场：分配给每个单元一个唯一的编号，然后使编号较低的单元等待更高编号的单元。如果两者都在等待，这将迫使其中一个单元继续前行。当提前检测到障碍物，编号较低的单元应该到达碰撞的预期点之前减速。

### 协调移动 ###

当单位试图要穿越一条狭窄的通道时，上面所描述的技术将不起作用。如果一个单位静止不动，而其他单位试图绕过去，通道不能同时使用这两个单位。一个单位将阻塞住它，而另一个将花费一段漫长的道路。

第二个单元与第一个单元进行通信，并要求其退回来，这种情况应该是可能的。一旦通道畅通无阻，第二单元就可以穿过，然后第一单元就可以通过。这可能是复杂的实现，除非你能事先能确定这些通道。对于随机生成的地图，通道在哪里和在多远的地方第一个单位需要退回来，这将是非常难以确定的。

# 关于寻路算法的一些思考（9）：寻路者的移动成本 #

寻路者的移动成本

当使用寻路算法的时候，你可能想把地图空间当做一种不单是用通畅或阻碍来表达的东西。通常地图空间会有更多的已知信息，比如通过那片区域的移动难度。比如，沼泽和高山可能比草地和沙漠更难通过。使用算法，比如A\*，你可以把给信息编码代入成本函数中。下面列出了一些计算移动成本的想法，也许会派上用场。

### 海拔 ###

高海拔（比如高山）比低海拔有更高的移动成本。当使用成本函数计算的时候，只要可能移动单元会试图一直停留在低洼的地方。例如，如果你的起始点和终点都在高地，移动单元可能会先下山，移动一段时间后再次登山。

### 爬山移动 ###

相对于高海拔有一个高的成本，爬山成本也很高。这就避免了上面描述的奇怪状况。使用这种成本函数，移动单元就会尽量避免爬山寻路。面对同样的情况，移动单元也会避免寻路时最后还要爬山；在整个移动过程中，单元能始终保持在一个高的海拔区间。使用这种成本函数有益于士兵（soldiers）这样的下山容易上山难的单元。

### 上下山移动 ###

一些单元，比如坦克（tanks），上下山都很困难。你可以设置一个比较高的成本下山，然后一个更高的成本上山。这个单元就会尽力避免改变移动时的海拔。

### 地形 ###

不同的地形，可以设置不同的移动成本。

### 森林、高山和山丘 ###

可以使用不同的地形类型来代替使用海拔的概念。比如在游戏《文明》（civilization）中，每个地形都有一个和它相关的移动成本。这种移动成本表可以适用于所有的单元，或者每一个单元类型都有匹配它的不同的移动成本。比如solider在森林中移动可能没有任何困难，但是tanks在森林中移动就很艰难。改变地形的时候设置移动成本是个很好的办法，从草地到高山会比从山丘到高山成本高，从山丘到高山移动又比高山之间移动成本高。

### 道路 ###

在很多游戏里，道路的原始目的就是让移动变得可能或者更简单。在选择好移动成本函数后，可以加一条道路来修正它。一个可能的办法就是用成本除一个常数(比如2)；另外的办法是设置一个表示沿着道路移动的成本常量。

我强烈的建议不要设道路移动成本为零。这会给寻路算法比如A\*带来麻烦，因为它可能会算出这样的一种路径，即从一点到另一点间沿着一条弯曲的道路行进，其实没有指向任何目的地。这样算法不得不搜索一个很大的区域，确保没有这样的路存在。注意在Civilization的游戏中，铁路移动成本是零，但是当使用”auto-goto”函数的时候，铁路的移动成本就不是零了。这就是游戏使用了寻路算法的证据。

### 墙壁或其它障碍 ###

无需既检查移动成本又要检查寻路算法里的路障，用移动成本一个计算就可以了。只要给你的路障设置一个非常高的移动成本即可。 (在A\*算法里)当展开节点的时候，检查成本是否太高；如果是的话，就放弃这个节点吧。

### 有坡度的地形 ###

你也许想在任何山丘中的移动设置较高的成本，来代替使用上山和下山。这样做，需要计算全部地势的斜度（通过观察行进路径的当前位置和它相连部分的最大高度差），使用这个来作为移动的成本。地势陡峭的陆地成本高，地势比较平缓的成本低。这种方法和上下山移动方法计算成本不同，因为它关注的是陡峭的地势，而之前的方法关注的是在一个陡峭的方向上移动的单元。特别是，如果你正在一个山丘上，而且可以向左或向右移动而不用向上或向下，那么上下山方法会认为这种情况成本低，而这个方法会认为成本高（因为地形本身陡峭，即便不用上下山的移动）。

根据地形陡峭判断成本的方法可能对于单元的移动来说不是很合理，但是你可以使用寻路算法不只是寻找单元的路径。我会使用它来寻找道路，管道，桥梁等等。如果你想在平地上建设这些项目，寻找一条道路或者管道的路线时，你可以考虑这种判断地势坡度的方法。参考[这部分的应用][Link 61]可以挖掘出更多的想法。

### 敌对和友好单元 ###

再设置一个修正器可以帮你避免敌人的单元。使用 [influence 地图][influence]，你可以监视附近有敌人或者友好单元的区域、或最近有士兵被杀的区域、或最近刚被探索过的区域、或是靠近一条逃跑路线的区域、抑或是最近穿越过区域（[《帝国时代2》里在 influence 寻路中使用了 influence 地图][2_ influence _ influence]）。一个influence地图可能对友好单元有积极的作用，对敌人单元有消极的作用。无论何时你在一个敌对的领域里，通过增加移动成本，你可以改变你的单元离敌人远一点。

更复杂的是（可能在influence地图下是不行的）参考可见度。对敌对单元来说你的单元是否可见？换句话说，你的单元是否可遭受攻击？你的敌对单元有可能向你开火么？

### 设置信号标（beacon） ###

如果你的地图是设计出来的不是自动生成的，你可以添加额外的信息进去。比如，旧的贸易路线经常会经过一些变成贸易城镇的特定地点。这些地方就叫beacon，即优质路线上的已知地点。与beacon的距离值可以加入移动成本中，这种方法是根据对beacon的偏好影响寻路结果的。

灯塔、城市、山路和桥梁等都是beacon比较好的选择。

### 燃料消耗 ###

注：为了保持状态空间比较小，你需要将燃料的价值四舍五入成一个近似的测量单元。不幸的是，这会将让搜索变得效率低下。

不但需要观察单元去某些地方所用的时间，你也要考虑它花费掉的燃料。当单元的燃料级别比较低的时候，燃料消耗可能会被赋予更大的权重。

就像上面描述的，为了跟踪地图上能源的耗费量，你需要使用状态空间。每个状态可能是成对的描述：<坐标,燃料>。然而，状态空间可能会变得非常大，所以不用普通的A\*算法，寻找其他替代方法也是值得考虑的。

我们的另一个选择是加入有界成本的A\*算法（A\* with Bounded Costs (ABC)）使用 ABC 算法，你可以给成本（比如“燃料”）设置一个界限（比如”20加仑”）。

# 关于寻路算法的一些思考（10）：最短路径的用户体验 #

### 最短路径的用户体验 ###

玩家是游戏最重要的部分。你想让用玩家愉快地玩耍！你不想让他（她） 认为电脑在作弊，或是游戏单位运行不正常。

### 愚蠢的移动 ###

如果寻路算法运行不正常，用户将最后放弃并选择手动移动单位。避免出现这种情况！在《文明》中，游戏的规则允许利用铁路无代价地移动。但是，游戏的导航只能进行其他方式的有代价移动。这样导致玩家拒绝使用游戏导航，而选择利用铁路手动移动单位。在《命令与征服》中，游戏单位会被困在U形的陷阱中，玩家将不得不手动引导这些游戏单位。一个愚蠢的游戏导航会使激起玩家的不满，导致他们自己手动移动单位，因此请让你游戏的导航程序更加完善。

### 聪明的移动 ###

把游戏单元做得太过聪明和做得太过愚蠢一样会造成不好的后果。如果玩家需要应对战争迷雾导致的视野受限影响，而游戏寻路单元能看到全地图，能在玩家毫不知情的时候神秘地知道该去往哪里。这会让玩家明显地感到奇怪的事情正在发生。换句话说，它给出了更好的路径。一种妥协的方法是提高在未被探索区域的移动花费。例如，如果你的正常移动花费是草地上1，森林中3，山地7，在未被探索区域就应该设置对应的不同花费：草地为5，森林为6，山地为7。这样游戏单元会把山地和草地纳入考虑，但只是一个提示，不会过度考虑。提高穿越未被探索地区的移动代价，将会使寻路程序倾向于尽可能停留在已被探索的区域中。你可能也想为侦察单元提供一个相反的策略：它们应偏爱未被探索的区域。

尽量使你的寻路单元在太过愚蠢和太过聪明之间保持平衡。你的目标应该是使游戏寻路单元和玩家可能的移动行为相匹配。

### 多线程 ###

你可以使用多线程来改善玩家体验。当有一个游戏单位需要一条路径时，允许它开始向着目标位置直线移动，同时向寻路队列添加一个请求。在另一个（优先级较低）的线程中，把请求从队列中去除并进行路径寻找。该游戏单位会立即开始移动，因此玩家不会疑惑是不是出现了问题，你也不会有过高的CPU负载（会拖慢游戏的其余部分）在进行路径计算的时候。

### 多单元 ###

如果你的游戏允许多个单位构成组一起移动，请试着让移动看起来更加有趣。你可以找到一条路径让它们都沿着路径移动，然后让它们单独沿着路径移动，但这会导致这些单位中的一条直线或者单位会穿过其它单位前进。因此，稍微区分一下路径它们就能平行地移动了。另外，还可以选取一个“领导”单元来沿着路径移动，同时让其它单元执行单独编写的“跟随”行为。这个跟随行为可以非常简单，只要向着“领导”所处的方向前进，同时停留在一段距离之外，或者它就像鸟类成群结队飞行。

### 多路径点 ###

即使给定了最优的路径，玩家可能会偏爱其它不同的路径。你应该允许玩家在路径上标记路径点：玩家可以点击通向目的地的路径上二到三个路径点，而不是简单地点击目的地。（很多实时策略游戏使用shift-点击来完成这项操作。）你当前有了三到四条较短的路径来进行计算，同时你节省了一些时间。玩家对于整体的路径安排同样拥有部分的控制权，例如，你的游戏导航找到了一条通向西部山地的路径，但出于安全考虑，玩家希望停留在东部山地（靠近友军防御塔）。

在单位移动程序中的主要改变是，你将拥有一个目的地的列表，而不是一个单一的目的地。首先寻找一条到达第一个目的地的路径，当你到达时，从列表中删除它然后继续寻找到达下一目的地的路径。这种做法可以降低游戏过程中的延时并且提高系统的吞吐量。

# 关于寻路算法的一些思考（11）：寻路算法的其他应用 #

除了查找一条可沿着移动找到一个单位的路径之外，寻路在其它方面还有很多用途。

### 探索 ###

如果你的成本函数对已知世界的路径进行惩罚，那路径更有可能会通过处女地。这些路径能很好地侦测到其它单位。

### 侦查 ###

如果你的成本函数对敌方瞭望塔等单位附近的路径进行惩罚，那你的单位会倾向保持隐蔽。但请注意，为了能良好运行，你需要考虑到敌方单位的移动，定期更新你的路径。

### 道路建设 ###

从历史上看，道路沿着是经常使用的路径被建造。当路径走的越来越多时，植被被清除，变成泥路，再后来用石头或其它材料覆盖。寻路的一个应用就是找到道路。考虑到人们通行（去城市，湖泊，泉水，矿山等等），会随机得找到这些重要地点之间的路径。在发现上百上千次路径后，确定地图上的哪些空间最常被使用在路径上，然后把这些空间变成道路。跟随探索者喜欢的道路，重复该实验，你会发现更多的道路需要被建设。这种技术可以用于多种类型的道路（高速公路，公路，泥路）：最常用的空间应该变成高速公路，不太常用的空间变成普通公路或者泥路。

### 地形分析 ###

结合势力图，寻路和视线可以给你有趣的方式来分析地形。

用与道路建设同样的方法，给定一组起点和目标点，我们可以使用寻路来确定哪些区域是最有可能被访问到的，这些区域附近往往具有重要的战略意义。Clash of Civilizations就是使用这种方式来实现它们的地图AI。

通过进一步分析公共路径，我们可以找到伏击点。路径上没有被视线扫到的位置，继续沿着路径再走N步之后才能被看到，部署伏击点在这些位置上意味着当前敌方无法看到你，直到你们的距离小于N时，这样你就能伏击大部队了。

### 城市建设 ###

城市往往是围绕着自然资源形成的，比如农田和矿产。城市里的居民相互交易需要贸易路线，使用寻路来帮助他们找到自己的贸易路线，并且在路线上标注行进一天的价值。当商队走了一天需要找个地方驻扎时：一个完美的城市位置！沿着一条以上的贸易路线的村庄是用于交易的好地方，最终它会成长为城市。

道路建设和城市建设相结合可以用于生成出逼真的地图，无论是脚本还是随机地图。

# 关于寻路算法的一些思考（12）：AI 技术 #

AI技术

寻路问题常常会和人工智能（AI） 联系在一起，原因是 A\*算法和许多其他寻路算法是由 AI 研究者开发出来的。一些生物启发式的 AI 技术目前十分流行，我也收到一些为何不使用这类技术的咨询。神经网络是依据实例的大脑学习建模——给定一个正解的集合，它会学习出一个一般的解决问题模式。强化学习是依据经验的大脑学习建模——给定一些行为的集合和最终奖惩结果，它会学习出哪种行为是正确或错误的。遗传算法根据自然选择的进化规律建模——给定一些agent 集合，优胜劣汰。通常情况下，遗传算法不允许 agent 在他们的生存时间内进行学习。强化学习则不但允许 agent 在生存时间内学习，还可以和其他 agent 分享知识。（译注：agent：智能体，正文保留未翻）

神经网络

神经网络是这样构建的：它受到训练，来对输入进行模式识别。他们是一种用来处理函数近似的方法:给定 y1 = f(x1),y2 = f(x2), …, yn = f(xn)，构建一个函数 f’使得 f’逼近 f。近似函数 f’一般都是光滑的：对于接近 x 点的 x’，我们希望 f’(x)也能接近f’(x’)。

函数近似方法可以满足以下两个目的：

*      规模：近似函数的表达可以明显小于真实的函数规模。
 *      泛化：未知函数值的输入数据可以使用近似函数

神经网络典型做法是使用一组输入值向量，产生一组输出值向量。在算法内部，训练“神经元”(neurons)的权重。神经网络使用监督学习，即输入和输出都是已知的，学习的目标是建立一个可以近似输入输出映射的函数表达。

在寻路问题中，函数 f(start,goal)=path。我们并不知道输出路径是什么。我们可以使用一些方法，可能是 A\*算法，来计算它们。但是如果我们能根据(start, goal)计算路径，那么我们就已经知道了函数 f，那么为什么还要自找麻烦的找它的近似函数呢？因为我们已经完全知道了函数 f，再归纳 f 就没有用了。用函数近似的唯一潜在的好处可能会降低 f 的表达规模。但f 表达的是个相当简洁几乎不占用空间的算法，所以我认为神经网络在这里也没有什么用。另外，神经网络输出规模是固定的，而寻路问题规模是可变的。

但另一方面，函数近似可能对构建寻路的一些组成部分有用。比如移动的成本函数是未知的。例如，没有实际移动操作和战役的情况下，穿越怪兽聚集森林的成本，我们可能并不知道。使用函数近似的方法的话，每次穿越森林时，移动成本函数f(number of orcs, size of forest)可以测量出来并装入神经网络模型中（注：这里移动成本f的自变量是怪兽数量和森林规模）。对于未来的寻路部分，根据算出的未知移动成本，我们可以找到更好的路线。

另一个可以从归功于近似计算的函数是启发式函数。A\*算法中的启发式函数可以计算到达目的地的最小成本，如果一个单元沿着路径 P=p1,p2,…,pn移动，当每穿过一段路径的时候，我们可以更新 n到近似函数 h 中，其中g(pi,pn)=（从i到 n 的实际移动成本）。当启发函数优化了，A\*算法也会运行的更快。

神经网络尽管对于寻路算法本体不太实用，但对 A\*算法使用的函数可以起到作用。移动函数和启发式函数都可以测算，因此能给函数近似反馈。

### 遗传算法 ###

根据适应度函数（fitness function），遗传算法允许开发参数空间来求得效果良好的解。他们是一种用来处理函数优化的方法：给定一个函数g(x)（x 是一组典型的参数值向量），求得能最大化（或最小化）g(x)的 x 值。这是一种非监督学习——问题的正确答案预先并不知道。

对于寻路问题，给定一个起始位置和一个目标位置，x 是这两点间的路径，g(x)是穿越这路径的成本。简单的优化方法，比如爬山算法会以增加g(x)为代价的方法改变 x。不幸的是，在一些问题中，会遇到“局部最大值”，x 值周围没有点 具有更大的对应g值，但是某个离x 值比较远的点表现更好。遗传算法改善了爬山算法，它保留了 x 的多样性，使用比如变异和交换的进化-启发式方法更新 x。

爬山算法和遗传算法可以用来学习出 x 的最优值。然而对于寻路问题，我们已经有了 A\*算法找到最优的 x ，因此函数优化的方法就不需要了。

遗传编程是遗传算法的更深层次，它把程序当做参数。例如，你可以输入的是寻路算法而不是寻路路径，你的适应值函数会根据表现测算每个算法。对于寻路问题来说，我们已经有个很好的算法，我们无需在进化出一个新的算法。

也许在和神经网络结合的情况下，遗传算法可以应用于寻路问题的某个部分。但是，在这篇文章中我还不知道有何用处。相反，如果问题解是已知的，估计会有一个更有前途的方法作为许多可行工具之一，在寻路问题中优化 agent。

### 强化学习 ###

和遗传算法一样，强化学习是一种非监督学习。然而，和遗传算法不同的是，agent 可以在他们的生存时间内学习；没必要等着观察他们的存活情况。并且，多 agents 同时参与到不同部分中分享各自学习成果是可能的。强化学习和 A\*的核心部分有着一些相似的地方。

在 A\*中，到达结束目标后会沿着经过的路径追溯回去，标记到目前为止所有路径的选择；其他选择就被去掉了。在强化学习中，可以测算每个状态时的情况，并且当前的奖（惩）都可以追溯回导致这个状态之前的所有选择。使用一个值函数表达这个追溯的过程，这有点像 A\*中的启发式函数，但随着 agent 尝试新路径并对这过程进行学习的更新，这一方面两者是不同的。

相比于更简单的算法来说，强化学习和遗传算法的一个关键的优势是：在探求新解和利用目前学到的信息两者间是可以做出选择的。遗传算法，通过变异寻找（新解）；强化学习，通过明确给出选择新行为的概率寻找（新解）。

即使和遗传算法结合，我认为强化学习也不会在寻路问题本身上使用。但是相对来说，它却可以作为一个向导，指导agent 在游戏世界中如何表现。

注： 函数近似方法可以变形为函数优化问题。为了找到最逼近 f(x)的f'(x),令 g(f’)=∑(f’(x)-f(x))^2（即在所有输入 x 上(f’(x)-f(x))^2的和）。

## 参考 ##

作者写这个系列的参考文章在[这里][Link 62]。我们翻译组的工作，基本结束了此为止咯，欢迎大家保持关注伯乐在线的其他文章 :)

文章来源：http://blog.jobbole.com/71044/

[7cc829d3gw1evvx18hteqj20ci08ujs9.jpg]: /images/20220715/6fddf1cf3b0949d18fbe2088159ad94e.png
[7cc829d3gw1evvx192gq3j20ci08uwf2.jpg]: /images/20220715/288c32e6382f43a4805963ce82e40191.png
[7cc829d3gw1evvx19fbcwj206u06uglm.jpg]: /images/20220715/8922ef1f76fb4a6baa031dbbd559e66a.png
[Link 1]: http://www-cs-students.stanford.edu/~amitp/game-programming/grids/
[Link 2]: http://www.redblobgames.com/pathfinding/grids/graphs.html
[Link 3]: http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html#polygonal-maps
[7cc829d3gw1evvx19tdbrj20em0ag0v3.jpg]: /images/20220715/9ef45949acf14ef5be6d178063815ac6.png
[7cc829d3gw1evvx1adi3lj20em0ag0ua.jpg]: /images/20220715/3004d8cda2834d8dbdc681115e636092.png
[7cc829d3gw1evvx1at4psj20em0agmzm.jpg]: /images/20220715/e9b5a2e84c0c41c1af8fcfe660c842cc.png
[7cc829d3gw1evvx1basdyj20em0agac5.jpg]: /images/20220715/1b991d0348a145918bfbec50efa7a5e4.png
[7cc829d3gw1evvx1bplq1j20em0aggn6.jpg]: /images/20220715/7227bf5f625148e0afdd20bd7c90d0f5.png
[7cc829d3gw1evvx1c7ynxj20em0agq4v.jpg]: /images/20220715/bdf96a1f02a84758aeb3aa3edfd8a368.png
[Link 4]: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
[Link 5]: http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html
[Link 6]: http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html
[Link 7]: http://realtimecollisiondetection.net/blog/?p=56
[Link 8]: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#manhattan-distance
[waypoints]: http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html#waypoints
[Link 9]: http://www.redblobgames.com/pathfinding/grids/algorithms.html
[Link 10]: http://www.redblobgames.com/grids/hexagons/#distances
[Link 11]: http://en.wikipedia.org/wiki/Taxicab_geometry
[6941baebjw1epz9dwxxl3j20em06adh0.jpg]: /images/20220715/092398b7f665497a9e5d9edc091cb931.png
[tie-breaker]: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#breaking-ties
[Chebyshev distance]: http://en.wikipedia.org/wiki/Chebyshev_distance
[6941baebjw1epz9dwpjxij20em06a75f.jpg]: /images/20220715/2ff3d2ccdd5949e897d60d0bec93311b.png
[Patrick Lester]: http://www.policyalmanac.org/games/heuristics.htm
[6941baebjw1epz9dwfiv2j20em06aq4f.jpg]: /images/20220715/ca2bbc606d544f05a606c95a93392c6b.png
[6941baebjw1epz9dw5wlij20em0agac5.jpg]: /images/20220715/7b51896cf7774901857c7b3e34418999.png
[6941baebjw1epz9dvwou5j20dn09rjtx.jpg]: /images/20220715/1f06356a578547268d15fc253f957e08.png
[6941baebjw1epz9dvhxazj20dn09r40a.jpg]: /images/20220715/a88bce8095444394b74ce6dc7aae95f1.png
[6941baebjw1epz9dv481tj20dn09rjtl.jpg]: /images/20220715/c9734f033bce4d3ab9060aad2d05c521.png
[6941baebjw1epz9duun6rj20dn09rabv.jpg]: /images/20220715/80d5d5b7962d43b496f8eef44331be32.png
[6941baebjw1epz9dunpxuj20dn09r76l.jpg]: /images/20220715/df8549ebeb57477ab80be6c33333128c.png
[James Macgill_A_]: http://www.ccg.leeds.ac.uk/people/j.macgill/xaStar/
[Link 12]: http://www.vision.ee.ethz.ch/~cvcourse/astar/AStar.html
[Link 13]: http://web.archive.org/web/www.ccg.leeds.ac.uk/james/aStar/
[Rectangular Symmetry Reduction]: http://aigamedev.com/open/tutorial/symmetry-in-pathfinding/
[Hierarchical pathfinding]: http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html#hierarchical
[Link 14]: http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html#skip-links
[AlphA_]: http://home1.stofanet.dk/breese/papers.html
[Fringe _PDF]: http://cswww.essex.ac.uk/cig/2005/papers/p1039.pdf
[HOT]: http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html#hot-queues
[Link 15]: http://blog.jobbole.com/85676/
[Link 16]: http://www.redblobgames.com/pathfinding/a-star/implementation.html
[Link 17]: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#exact-heuristics
[Link 18]: http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html#set-representation
[Link 19]: http://en.wikipedia.org/wiki/Fringe_search
[A]: http://blog.jobbole.com/71044/
[Link 20]: http://theory.stanford.edu/~amitp/game-programming/a-star-flash/main-square.swf
[Link 21]: http://theory.stanford.edu/~amitp/game-programming/a-star-flash/main-hexagon.swf
[Link 22]: http://theory.stanford.edu/~amitp/game-programming/a-star-flash/main-triangle.swf
[Link 23]: http://kevanahlquist.com/osm_pathfinding/
[Javascript_A_ demo]: http://easystar.nodejitsu.com/demo.html
[github]: https://github.com/prettymuchbryce/easystarjs
[A_Dijkstra_demo]: http://www.growingwiththeweb.com/projects/pathfinding-visualiser/
[demo]: http://qiao.github.com/PathFinding.js/visual/
[javascript]: https://github.com/qiao/PathFinding.js
[demo 1]: http://will.thimbleby.net/a-shortest-path-in-javascript/
[javascript demo]: http://www.briangrinstead.com/files/astar/
[Link 24]: http://zerowidth.com/2013/05/05/jump-point-search-explained.html
[Actionscript_A_]: http://www.untoldentertainment.com/blog/2010/08/20/introduction-to-a-a-star-pathfinding-in-actionscript-3-as3-2/
[demo 2]: http://cs.williams.edu/~morgan/codeheartjs/examples/pathfinding/play.html
[A_ demo]: http://singul4rity.com/misc/astar/
[demo 3]: http://singul4rity.com/2013/04/jump-point-search-unity3d-online-demo/
[Mikko Mononen]: http://digestingduck.blogspot.com/
[Recast]: http://code.google.com/p/recastnavigation/
[1]: https://code.google.com/p/policy-based-search/
[2]: https://gist.github.com/codemonkey-uk/8240501
[3]: http://code.google.com/p/a-star-algorithm-implementation/
[4]: https://github.com/vandersonmr/A_Star_Algorithm/tree/master/libs/c%2B%2B
[1 1]: http://memoization.com/2008/11/30/a-star-algorithm-in-java/
[2 1]: http://code.google.com/p/a-star/source/browse/trunk/java/AStar.java?r=8
[2 2]: http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript
[3 1]: http://ahuynh.posterous.com/javascript-a-implementation
[4 1]: http://jsastar.tapirpirates.net/dfdemo/
[1 2]: https://github.com/vandersonmr/A_Star_Algorithm/tree/master/libs/python
[1 3]: http://www.raywenderlich.com/4946/introduction-to-a-pathfinding
[2 3]: http://www.raywenderlich.com/4970/how-to-implement-a-pathfinding-with-cocos2d-tutorial
[1 4]: https://github.com/Yonaba/Jumper
[2 4]: https://love2d.org/forums/viewtopic.php?f=5&t=7983
[more]: https://www.love2d.org/forums/viewtopic.php?f=4&t=78021&p=168522#p168522
[1 5]: https://github.com/shawn42/polaris/tree/master/lib/
[2 5]: https://github.com/DanaDanger/a_star/tree/master/ruby
[3 2]: https://github.com/vandersonmr/A_Star_Algorithm/blob/master/libs/ruby/AlgorithmA.rb
[1 6]: http://www.codeproject.com/KB/recipes/csharppathfind.aspx
[priority queue helper class]: https://bitbucket.org/BlueRaja/high-speed-priority-queue-for-c/wiki/Home
[1 7]: http://www.arongranberg.com/unity/a-pathfinding/
[1 8]: http://magervalp.github.io/2014/05/07/astar-in-asm.html
[1 9]: http://theory.stanford.edu/~amitp/game-programming/a-star-flash/
[2 6]: http://www.antimodal.com/astar/
[3 3]: http://lassieadventurestudio.wordpress.com/2008/12/09/a-star-pathfinding/
[4 2]: http://proto.layer51.com/d.aspx?f=998
[5]: http://www.dauntless.be/astar/
[1 10]: http://web.archive.org/web/http:/blog.topholt.com/2007/12/07/a-pathfinding-in-an-isometric-world-with-flex/
[1 11]: https://github.com/beefsack/go-astar
[1 12]: http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/5_1.html
[1 13]: http://www.robotacid.com/PBeta/AILibrary/Pathfinder/index.html
[Link 25]: http://en.wikipedia.org/wiki/Priority_queue
[Link 26]: http://en.wikipedia.org/wiki/Heap_%28data_structure%29
[priority_queue]: http://en.cppreference.com/w/cpp/container/priority_queue
[Boost]: http://www.boost.org/doc/libs/1_50_0/doc/html/heap/concepts.html#heap.concepts.mutability
[heapq]: https://docs.python.org/3/library/heapq.html
[Link 27]: http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html#hybrid-representations
[d-ary heap]: http://en.wikipedia.org/wiki/D-ary_heap
[Link 28]: http://en.wikipedia.org/wiki/Skip_list
[HOT_Heap On Top]: http://www.star-lab.com/goldberg/pub/neci-tr-97-104.ps
[Lee Killough]: http://www.leekillough.com/heaps/
[Link 29]: http://theory.stanford.edu/~amitp/GameProgramming/MovingObstacles.html#recalculating-paths
[Link 30]: http://theory.stanford.edu/~amitp/GameProgramming/MovingObstacles.html#path-splicing
[Link 31]: http://www.red3d.com/cwr/boids/
[A 1]: http://en.wikipedia.org/wiki/Incremental_heuristic_search
[Link 32]: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#linear-exact-heuristic
[Link 33]: http://www.apl.jhu.edu/~hall/AI-Programming/IDA-Star.html
[D]: http://www.frc.ri.cmu.edu/~axs/dynamic_plan.html
[D_1]: http://www.frc.ri.cmu.edu/~axs/doc/icra94.ps
[D_2]: http://www.frc.ri.cmu.edu/~axs/doc/ijcai95.ps
[Link 34]: http://idm-lab.org/project-a.html
[PDF]: http://csci.mrs.umn.edu/UMMCSciWiki/pub/CSci3903s03/KellysPaper/seminar.pdf
[A_ applet]: http://idm-lab.org/applet.html
[Link 35]: http://harablog.wordpress.com/2011/09/07/jump-point-search/
[Link 36]: http://www.reddit.com/r/programming/comments/1es39b/speed_up_a_using_jump_point_search_explained/
[Link 37]: http://harablog.wordpress.com/2011/09/01/rectangular-symmetry-reduction/
[Link 38]: http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html#path-smoothing
[Link 39]: http://aigamedev.com/open/tutorials/theta-star-any-angle-paths/
[Theta]: http://aigamedev.com/open/tutorial/lazy-theta-star/
[mtn_path]: /images/20220715/af68621445334ddfa24ced202f587e01.png
[6941baebjw1euyhvuojoxj2051051t8r.jpg]: /images/20220715/609a1fbf1ea34507a2a2dc889a73c825.png
[BlobCity]: http://www-cs-students.stanford.edu/~amitp/games.html
[Link 40]: http://theory.stanford.edu/~amitp/GameProgramming/Goals.html#unit-movement
[6941baebjw1euyhvvmk5uj2047047aa0.jpg]: /images/20220715/894b1fc3157c4058bfbfc75eca61103b.png
[6941baebjw1euyhvux80uj2047047q2t.jpg]: /images/20220715/b0b10fb641c04473857d9b0e6c7b48d4.png
[java applet]: http://theory.stanford.edu/~amitp/game-programming/road-applet/roads.html
[6941baebjw1euyhvvbd93j2039038glg.jpg]: /images/20220715/2646289cbfa64dd8ad8df2b19dfb3e13.png
[6941baebjw1euyhvp5g44j20ci074q3g.jpg]: /images/20220715/a522fc48cf7a44d2bef3dbf2e36357b2.png
[Link 41]: http://en.wikipedia.org/wiki/Visibility_graph
[Link 42]: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#diagonal-distance
[Link 43]: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#euclidean-distance
[6941baebjw1euyhvucgynj20b5086gms.jpg]: /images/20220715/eb20cd5ff07a4f3db44ab37d2883751f.png
[6941baebjw1euyhvti7dgj20d20b7mxo.jpg]: /images/20220715/f81b53ea107341a3bc6e9756c91caace.png
[6941baebjw1euyhvt2bypj20d20b7jsc.jpg]: /images/20220715/7ed1515b7b2145249e8061d2f8ba6bad.png
[6941baebjw1euyhvsp7arj20d20b7aay.jpg]: /images/20220715/6e9cc0302fea4f92a7037969750e475f.png
[6941baebjw1euyhvtw5ypj20dd0bhq3x.jpg]: /images/20220715/55af868c17c34fb2bdcc319f57f0555b.png
[6941baebjw1euyhvnp6owj20dd0bhab9.jpg]: /images/20220715/f3c60dfcfd1040d4958b5880fbad1d4a.png
[Link 44]: http://aaai.org/ocs/index.php/AIIDE/AIIDE10/paper/view/2139/2547
[Link 45]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.7223
[Link 46]: http://www.aaai.org/ocs/index.php/AIIDE/AIIDE12/paper/view/5459/5688
[A 2]: http://scholar.google.com/scholar?q=Hierarchical+A*%3A+Searching+Abstraction+Hierarchies+Efficiently&hl=en&btnG=Search&as_sdt=1%2C5&as_sdtp=on
[Link 47]: http://algo2.iti.kit.edu/schultes/hwy/schultes_diss.pdf
[Link 48]: http://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/
[Link 49]: http://harablog.wordpress.com/2009/02/05/hierarchical-clearance-based-pathfinding/
[Link 50]: http://code.google.com/p/ahastar/
[6941baebjw1euyhvofgp6j20b40bct9f.jpg]: /images/20220715/709215067ede4d189424978c07a0dad3.png
[Goldberg_Harrelson_ALT_A_ Landmarks_ Triangle inequality]: http://research.microsoft.com/apps/pubs/default.aspx?id=154937
[PDF 1]: http://research.microsoft.com/pubs/64511/tr-2004-24.pdf
[Link 51]: http://research.microsoft.com/apps/pubs/default.aspx?id=60764
[Link 52]: http://algo2.iti.kit.edu/schultes/hwy/contract.pdf
[Link 53]: http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html#managing-complexity
[Link 54]: http://theory.stanford.edu/~amitp/GameProgramming/MovementCosts.html#terrain
[Link 55]: http://theory.stanford.edu/~amitp/GameProgramming/MovementCosts.html#altitude
[Link 56]: http://theory.stanford.edu/~amitp/GameProgramming/MovementCosts.html#enemies-and-friendly-units
[Link 57]: http://www.ai-blog.net/archives/000152.html
[Link 58]: http://theory.stanford.edu/~amitp/GameProgramming/Variations.html#jump-point-search
[Theta 1]: http://theory.stanford.edu/~amitp/GameProgramming/Variations.html#theta
[splines]: /images/20220715/36adf8dfe3cb43b1b08e412e33eb76a5.png
[Link 59]: http://www.red3d.com/cwr/steer/
[Link 60]: http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html
[Link 61]: http://theory.stanford.edu/~amitp/GameProgramming/Applications.html
[influence]: http://www.slideshare.net/mobius.cn/influence-map
[2_ influence _ influence]: http://www.ensemblestudios.com/news/devnews/terrain2.shtml
[Link 62]: http://theory.stanford.edu/~amitp/GameProgramming/References.html