寻路算法——A*算法_a*中 如何判定是否到达目的地

2 寻路算法——A*算法剖析

2.1 A*算法简介

原文链接：http://www.gamedev.net/reference/articles/article2003.asp

原作者文章链接：http://www.policyalmanac.org/games/aStarTutorial.htm

搜索区域

假设有人想从A点移动到一墙之隔的B点，如下图，绿色的是起点A，红色是终点B，蓝色方块是中间的墙。

图1

你首先注意到，搜索区域被我们划分成了方形网格。像这样，简化搜索区域，是寻路的第一步。这一方法把搜索区域简化成了一个二维数组，数组的每一个元素是网格的一个方块，方块被标记为可通过的和不可通过的。路径被描述为从A到B我们经过的方块的集合，一旦路径被找到，我们的人就从一个方格的中心走向另一个，直到到达目的地。这些点被称为“节点”。当你阅读其他的寻路资料时，你将经常会看到人们讨论节点。为什么不把他们描述为方格呢？因为有可能你的路径被分割成其他不是方格的结构。他们完全可以是矩形，六角形，或者其他任意形状。节点能够被放置在形状的任意位置－可以在中心，或者沿着边界，或其他什么地方。我们使用这种系统，无论如何，因为它是最简单的。

开始搜索

正如我们处理上图网格的方法，一旦搜索区域被转化为容易处理的节点，下一步就是去引导一次找到最短路径的搜索。在A*寻路算法中，我们通过从点A开始，检查相邻方格的方式，向外扩展直到找到目标。我们做如下操作开始搜索：

(1) 从点A开始，并且把它作为待处理点存入一个“开启列表”。开启列表就像一张购物清单。尽管现在列表里只有一个元素，但以后就会多起来。你的路径可能会通过它包含的方格，也可能不会。基本上，这是一个待检查方格的列表。

(2) 寻找起点周围所有可到达或者可通过的方格，跳过有墙，水，或其他无法通过地形的方格。也把他们加入开启列表。为所有这些方格保存点A作为“父方格”。当我们想描述路径的时候，父方格的资料是十分重要的。后面会解释它的具体用途。

(3) 从开启列表中删除点A，把它加入到一个“关闭列表”，列表中保存所有不需要再次检查的方格。

在这一点，你应该形成如下图的结构。在图中，暗绿色方格是你起始方格的中心。它被用浅蓝色描边，以表示它被加入到关闭列表中了。所有的相邻格现在都在开启列表中，它们被用浅绿色描边。每个方格都有一个灰色指针反指他们的父方格，也就是开始的方格。

图2

接着，我们选择开启列表中的临近方格，大致重复前面的过程，如下。但是，哪个方格是我们要选择的呢？是那个F值最低的。

路径评分

选择路径中经过哪个方格的关键是下面这个等式：

F = G+ H，这里：

* G =从起点A，沿着产生的路径，移动到网格上指定方格的移动耗费。
* H = 从网格上那个方格移动到终点B的预估移动耗费。这经常被称为启发式的，可能会让你有点迷惑。这样叫的原因是因为它只是个猜测。我们没办法事先知道路径的长度，因为路上可能存在各种障碍(墙，水，等等)。虽然本文只提供了一种计算H的方法，但是你可以在网上找到很多其他的方法。

我们的路径是通过反复遍历开启列表并且选择具有最低F值的方格来生成的。文章将对这个过程做更详细的描述。首先，我们更深入的看看如何计算这个方程。
正如上面所说，G表示沿路径从起点到当前点的移动耗费。在这个例子里，我们令水平或者垂直移动的耗费为10，对角线方向耗费为14。我们取这些值是因为沿对角线的距离是沿水平或垂直移动耗费的的根号2（别怕），或者约1.414倍。为了简化，我们用10和14近似。比例基本正确，同时我们避免了求根运算和小数。这不是只因为我们怕麻烦或者不喜欢数学。使用这样的整数对计算机来说也更快捷。你不就就会发现，如果你不使用这些简化方法，寻路会变得很慢。

既然我们在计算沿特定路径通往某个方格的G值，求值的方法就是取它父节点的G值，然后依照它相对父节点是对角线方向或者直角方向(非对角线)，分别增加14和10。例子中这个方法的需求会变得更多，因为我们从起点方格以外获取了不止一个方格。

H值可以用不同的方法估算。我们这里使用的方法被称为曼哈顿方法，它计算从当前格到目的格之间水平和垂直的方格的数量总和，忽略对角线方向。然后把结果乘以10。这被成为曼哈顿方法是因为它看起来像计算城市中从一个地方到另外一个地方的街区数，在那里你不能沿对角线方向穿过街区。很重要的一点，我们忽略了一切障碍物。这是对剩余距离的一个估算，而非实际值，这也是这一方法被称为启发式的原因。想知道更多？你可以在这里找到方程和额外的注解。

F的值是G和H的和。第一步搜索的结果可以在下面的图表中看到。F，G和H的评分被写在每个方格里。正如在紧挨起始格右侧的方格所表示的，F被打印在左上角，G在左下角，H则在右下角。

图3

现在我们来看看这些方格。写字母的方格里，G = 10。这是因为它只在水平方向偏离起始格一个格距。紧邻起始格的上方，下方和左边的方格的G值都等于10。对角线方向的G值是14。

H值通过求解到红色目标格的曼哈顿距离得到，其中只在水平和垂直方向移动，并且忽略中间的墙。用这种方法，起点右侧紧邻的方格离红色方格有3格距离，H值就是30。这块方格上方的方格有4格距离(记住，只能在水平和垂直方向移动)，H值是40。你大致应该知道如何计算其他方格的H值了～。每个格子的F值，还是简单的由G和H相加得到。

继续搜索

为了继续搜索，我们简单的从开启列表中选择F值最低的方格。然后，对选中的方格做如下处理：

4，把它从开启列表中删除，然后添加到关闭列表中。

5，检查所有相邻格子。跳过那些已经在关闭列表中的或者不可通过的(有墙，水的地形，或者其他无法通过的地形)，把他们添加进开启列表，如果他们还不在里面的话。把选中的方格作为新的方格的父节点。

6，如果某个相邻格已经在开启列表里了，检查现在的这条路径是否更好。换句话说，检查如果我们用新的路径到达它的话，G值是否会更低一些。如果不是，那就什么都不做。

另一方面，如果新的G值更低，那就把相邻方格的父节点改为目前选中的方格（在上面的图表中，把箭头的方向改为指向这个方格）。最后，重新计算F和G的值。如果这看起来不够清晰，你可以看下面的图示。

好了，让我们看看它是怎么运作的。我们最初的9格方格中，在起点被切换到关闭列表中后，还剩8格留在开启列表中。这里面，F值最低的那个是起始格右侧紧邻的格子，它的F值是40。因此我们选择这一格作为下一个要处理的方格。在紧随的图中，它被用蓝色突出显示。

图4

首先，我们把它从开启列表中取出，放入关闭列表(这就是他被蓝色突出显示的原因)。然后我们检查相邻的格子。哦，右侧的格子是墙，所以我们略过。左侧的格子是起始格。它在关闭列表里，所以我们也跳过它。其他4格已经在开启列表里了，于是我们检查G值来判定，如果通过这一格到达那里，路径是否更好。我们来看选中格子下面的方格。它的G值是14。如果我们从当前格移动到那里，G值就会等于20(到达当前格的G值是10，移动到上面的格子将使得G值增加10)。因为G值20大于14，所以这不是更好的路径。如果你看图，就能理解。与其通过先水平移动一格，再垂直移动一格，还不如直接沿对角线方向移动一格来得简单。

当我们对已经存在于开启列表中的4个临近格重复这一过程的时候，我们发现没有一条路径可以通过使用当前格子得到改善，所以我们不做任何改变。既然我们已经检查过了所有邻近格，那么就可以移动到下一格了。

于是我们检索开启列表，现在里面只有7格了，我们仍然选择其中F值最低的。有趣的是，这次，有两个格子的数值都是54。我们如何选择？这并不麻烦。从速度上考虑，选择最后添加进列表的格子会更快捷。这种导致了寻路过程中，在靠近目标时，优先使用新找到的格子的偏好。但这无关紧要。（对相同数值的不同对待，导致不同版本的A*算法找到等长的不同路径。）那我们就选择起始格右下方的格子，如下图。

图5

这次，当我们检查相邻格的时候，发现右侧是墙，于是略过。上面一格也被略过。我们也略过了墙下面的格子。为什么呢？因为你不能在不穿越墙角的情况下直接到达那个格子。你的确需要先往下走然后到达那一格，按部就班的走过那个拐角 (穿越拐角的规则是可选的。它取决于你的节点是如何放置的) 。这样一来，就剩下了其他5格。当前格下面的另外两个格子目前不在开启列表中，于是我们添加他们，并且把当前格指定为他们的父节点。其余3格，两个已经在关闭列表中（起始格，和当前格上方的格子，在表格中蓝色高亮显示)，于是我们略过它们。最后一格，在当前格的左侧，将被检查通过这条路径，G值是否更低。不必担心，我们已经准备好检查开启列表中的下一格了。

我们重复这个过程，直到目标格被添加进关闭列表，就如在下图中所看到的。

图6

注意，起始格下方格子的父节点已经和前面不同的。之前它的G值是28，并且指向右上方的格子。现在它的G值是20，指向它上方的格子。这在寻路过程中的某处发生，当应用新路径时，G值经过检查变得低了－于是父节点被重新指定，G和F值被重新计算。尽管这一变化在这个例子中并不重要，在很多场合，这种变化会导致寻路结果的巨大变化。

那么，我们怎么确定这条路径呢？很简单，从红色的目标格开始，按箭头的方向朝父节点移动。这最终会引导你回到起始格，这就是你的路径！看起来应该像图中那样。从起始格A移动到目标格B只是简单的从每个格子（节点）的中点沿路径移动到下一个，直到你到达目标点。就这么简单。

图7

2.2 A*算法总结与深入分析

现在我们把每一步的操作写在一起：(1) 把起始格添加到开启列表。

(2) 重复如下的工作：

a) 寻找开启列表中F值最低的格子，我们称它为当前格。

b) 把它切换到关闭列表。

c) 对相邻的8格中的每一个？

* 如果它不可通过或者已经在关闭列表中，略过它。反之如下。

* 如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。

* 如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序，改变之后你可能需要重新对开启列表排序。

d) 停止，当你

* 把目标格添加进了关闭列表(注解)，这时候路径被找到，或者

* 没有找到目标格，开启列表已经空了。这时候，路径不存在。

(3) 保存路径。从目标格开始，沿着每一格的父节点移动直到回到起始格。这就是你的路径。

(注解:在这篇文章的较早版本中，建议的做法是当目标格（或节点）被加入到开启列表，而不是关闭列表的时候停止寻路。这么做会更迅速，而且几乎总是能找到最短的路径，但不是绝对的。当从倒数第二个节点到最后一个（目标节点）之间的移动耗费悬殊很大时－例如刚好有一条河穿越两个节点中间，这时候旧的做法和新的做法就会有显著不同。)

题外话

离题一下，值得一提的是，当你在网上或者相关论坛看到关于A的不同的探讨，你有时会看到一些被当作A算法的代码而实际上他们不是。要使用A*，必须包含上面讨论的所有元素——特定的开启和关闭列表，用F,G和H作路径评价。有很多其他的寻路算法，但他们并不是A*，A*被认为是他们当中最好的。Bryan Stout在这篇文章后面的参考文档中论述了一部分，包括他们的一些优点和缺点。有时候特定的场合其他算法会更好，但你必须很明确你在作什么。

**实现的注解
**现在你已经明白了基本原理，写你的程序的时候还得考虑一些额外的东西。下面这些材料中的一些引用了我用C++和Blitz Basic写的程序，但对其他语言写的代码同样有效。

1. 其他单位(避免碰撞)

如果你恰好看了我的例子代码，你会发现它完全忽略了其他单位。我的寻路者事实上可以相互穿越。取决于具体的游戏，这也许可以，也许不行。如果你打算考虑其他单位，希望他们能互相绕过，我建议你只考虑静止或那些在计算路径时临近当前单位的单位，把它们当前的位置标志为可通过的。对于临近的运动着的单位，你可以通过惩罚它们各自路径上的节点，来鼓励这些寻路者找到不同的路径(更多的描述见#2).

如果你选择了把其他正在移动并且远离当前寻路单位的那些单位考虑在内，你将需要实现一种方法及时预测在何时何地碰撞可能会发生，以便恰当的避免。否则你极有可能得到一条怪异的路径，单位突然转弯试图避免和一个已经不存在的单位发生碰撞。

当然，你也需要写一些碰撞检测的代码，因为无论计算的时候路径有多完美，它也会因时间而改变。当碰撞发生时，一个单位必须寻找一条新路径，或者，如果另一个单位正在移动并且不是正面碰撞，在继续沿当前路径移动之前，等待那个单位离开。这些提示大概可以让你开始了。如果你想了解更多，这里有些你可能会觉得有用的链接：

* 自治角色的指导行为：Craig Reynold在指导能力上的工作和寻路有些不同，但是它可以和寻路整合从而形成更完整的移动和碰撞检测系统。* 电脑游戏中的长短距指导：指导和寻路方面著作的一个有趣的考察。这是一个pdf文件。* 协同单位移动：一个两部分系列文章的第一篇，内容是关于编队和基于分组的移动，作者是帝国时代(Age of Empires)的设计者Dave Pottinger.
* 实现协同移动：Dave Pottinger文章系列的第二篇。

2. 不同的地形损耗

在这个教程和我附带的程序中，地形只能是二者之——可通过的和不可通过的。但是你可能会需要一些可通过的地形，但是移动耗费更高——沼泽，小山，地牢的楼梯，等等。这些都是可通过但是比平坦的开阔地移动耗费更高的地形。类似的，道路应该比自然地形移动耗费更低。

这个问题很容易解决，只要在计算任何地形的G值的时候增加地形损耗就可以了。简单的给它增加一些额外的损耗就可以了。由于A算法已经按照寻找最低耗费的路径来设计，所以很容易处理这种情况。在我提供的这个简单的例子里，地形只有可通过和不可通过两种，A会找到最短，最直接的路径。但是在地形耗费不同的场合，耗费最低的路径也许会包含很长的移动距离——就像沿着路绕过沼泽而不是直接穿过它。

一种需额外考虑的情况是被专家称之为“influence mapping”的东西（暂译为影响映射图）。就像上面描述的不同地形耗费一样，你可以创建一格额外的分数系统，并把它应用到寻路的AI中。假设你有一张有大批寻路者的地图，他们都要通过某个山区。每次电脑生成一条通过那个关口的路径，它就会变得更拥挤。如果你愿意，你可以创建一个影响映射图对有大量屠杀事件的格子施以不利影响。这会让计算机更倾向安全些的路径，并且帮助它避免总是仅仅因为路径短(但可能更危险)而持续把队伍和寻路者送到某一特定路径。

另一个可能的应用是惩罚周围移动单位路径上的节点。A*的一个底限是，当一群单位同时试图寻路到接近的地点，这通常会导致路径交叠。以为一个或者多个单位都试图走相同或者近似的路径到达目的地。对其他单位已经“认领”了的节点增加一些惩罚会有助于你在一定程度上分离路径，降低碰撞的可能性。然而，如果有必要，不要把那些节点看成不可通过的，因为你仍然希望多个单位能够一字纵队通过拥挤的出口。同时，你只能惩罚那些临近单位的路径，而不是所有路径，否则你就会得到奇怪的躲避行为例如单位躲避路径上其他已经不在那里的单位。还有，你应该只惩罚路径当前节点和随后的节点，而不应处理已经走过并甩在身后的节点。

3. 处理未知区域

你是否玩过这样的PC游戏，电脑总是知道哪条路是正确的，即使它还没有侦察过地图？对于游戏，寻路太好会显得不真实。幸运的是，这是一格可以轻易解决的问题。

答案就是为每个不同的玩家和电脑（每个玩家，而不是每个单位－－那样的话会耗费大量的内存）创建一个独立的“knownWalkability”数组，每个数组包含玩家已经探索过的区域，以及被当作可通过区域的其他区域，直到被证实。用这种方法，单位会在路的死端徘徊并且导致错误的选择直到他们在周围找到路。一旦地图被探索了，寻路就像往常那样进行。

4. 平滑路径

尽管A*提供了最短，最低代价的路径，它无法自动提供看起来平滑的路径。看一下我们的例子最终形成的路径（在图7）。最初的一步是起始格的右下方，如果这一步是直接往下的话，路径不是会更平滑一些吗？

有几种方法来解决这个问题。当计算路径的时候可以对改变方向的格子施加不利影响，对G值增加额外的数值。也可以换种方法，你可以在路径计算完之后沿着它跑一遍，找那些用相邻格替换会让路径看起来更平滑的地方。想知道完整的结果，查看Toward More RealisticPathfinding，一篇(免费，但是需要注册)Marco Pinter发表在Gamasutra.com的文章。

5. 非方形搜索区域

在我们的例子里，我们使用简单的2D方形图。你可以不使用这种方式，可以使用不规则形状的区域。想想冒险棋的游戏，和游戏中那些国家。你可以设计一个像那样的寻路关卡。为此，你可能需要建立一个国家相邻关系的表格，和从一个国家移动到另一个的G值；你也需要估算H值的方法。其他的事情就和例子中完全一样了。当你需要向开启列表中添加新元素的时候，不需使用相邻的格子，取而代之的是从表格中寻找相邻的国家。

类似的，你可以为一张确定的地形图创建路径点系统，路径点一般是路上，或者地牢通道的转折点。作为游戏设计者，你可以预设这些路径点。两个路径点被认为是相邻的如果他们之间的直线上没有障碍的话。在冒险棋的例子里，你可以保存这些相邻信息在某个表格里，当需要在开启列表中添加元素的时候使用它。然后你就可以记录关联的G值（可能使用两点间的直线距离），H值（可以使用到目标点的直线距离），其他都按原先的做就可以了。Amit Patel 写了其他方法的摘要。另一个在非方形区域搜索RPG地图的例子，查看我的文章Two-Tiered A* Pathfinding。

6. 一些速度方面的提示

当你开发你自己的A*程序，或者改写我的，你会发现寻路占据了大量的CPU时间，尤其是在大地图上有大量对象在寻路的时候。如果你阅读过网上的其他材料，你会明白，即使是开发了星际争霸或帝国时代的专家，这也无可奈何。如果你觉得寻路太过缓慢，这里有一些建议也许有效：

* 使用更小的地图或者更少的寻路者。

* 不要同时给多个对象寻路。取而代之的是把他们加入一个队列，把寻路过程分散在几个游戏周期中。如果你的游戏以40周期每秒的速度运行，没人能察觉。但是当大量寻路者计算自己路径的时候，他们会发觉游戏速度突然变慢。

* 尽量使用更大的地图网格。这降低了寻路中搜索的总网格数。如果你有志气，你可以设计两个或者更多寻路系统以便使用在不同场合，取决于路径的长度。这也正是专业人士的做法，用大的区域计算长的路径，然后在接近目标的时候切换到使用小格子/区域的精细寻路。如果你对这个观点感兴趣，查阅我的文章Two-Tiered A* Pathfinding。

* 使用路径点系统计算长路径，或者预先计算好路径并加入到游戏中。

* 预处理你的地图，表明地图中哪些区域是不可到达的。我把这些区域称作“孤岛”。事实上，他们可以是岛屿或其他被墙壁包围等无法到达的任意区域。A*的下限是，当你告诉它要寻找通往那些区域的路径时，它会搜索整个地图，直到所有可到达的方格/节点都被通过开启列表和关闭列表的计算。这会浪费大量的CPU时间。可以通过预先确定这些区域（比如通过flood-fill或类似的方法)来避免这种情况的发生，用某些种类的数组记录这些信息，在开始寻路前检查它。

* 在一个拥挤的类似迷宫的场合，把不能连通的节点看作死端。这些区域可以在地图编辑器中预先手动指定，或者如果你有雄心壮志，开发一个自动识别这些区域的算法。给定死端的所有节点可以被赋予一个唯一的标志数字。然后你就可以在寻路过程中安全的忽略所有死端，只有当起点或者终点恰好在死端的某个节点的时候才需要考虑它们。

7. 维护开启列表

这是A寻路算法最重要的组成部分。每次你访问开启列表，你都需要寻找F值最低的方格。有几种不同的方法实现这一点。你可以把路径元素随意保存，当需要寻找F值最低的元素的时候，遍历开启列表。这很简单，但是太慢了，尤其是对长路径来说。这可以通过维护一格排好序的列表来改善，每次寻找F值最低的方格只需要选取列表的首元素。当我自己实现的时候，这种方法是我的首选。在小地图中这种方法工作得很好，但它并不是最快的解决方案。更苛求速度的A程序员使用叫做二叉堆的方法，这也是我在代码中使用的方法。凭我的经验，这种方法在大多数场合会快2～3倍，并且在长路经上速度呈几何级数提升(10倍以上速度)。如果你想了解更多关于二叉堆的内容，查阅我的文章，Using Binary Heaps in A*Pathfinding。

另一个可能的瓶颈是你在多次寻路之间清除和保存你的数据结构的方法。我个人更倾向把所有东西都存储在数组里面。虽然节点可以以面向对象的风格被动态的产生，记录和保存，我发现创建和删除对象所增加的大量时间，以及多余的管理层次减慢的整个过程的速度。但是，如果你使用数组，你需要在调用之间清理数据。这中情形你想做的最后一件事就是在寻路调用之后花点时间把一切归零，尤其是你的地图很大的时候。

我通过使用一个叫做whichList(x,y)的二维数组避免这种开销，数组的每个元素表明了节点在开启列表还是在关闭列表中。尝试寻路之后，我没有清零这个数组。取而代之的是，我在新的寻路中重置onClosedList和onOpenList的数值，每次寻路两个都+5或者类似其他数值。这种方法，算法可以安全的跳过前面寻路留下的脏数据。我还在数组中储存了诸如F,G和H的值。这样一来，我只需简单的重写任何已经存在的值而无需被清除数组的操作干扰。将数据存储在多维数组中需要更多内存，所以这里需要权衡利弊。最后，你应该使用你最得心应手的方法。

8. Dijkstra的算法

尽管A被认为是通常最好的寻路算法(看前面的“题外话”)，还是有一种另外的算法有它的可取之处-Dijkstra算法。Dijkstra算法和A本质是相同的，只有一点不同，就是Dijkstra算法没有启发式(H值总是0)。由于没有启发式，它在各个方向上平均搜索。正如你所预料，由于Dijkstra算法在找到目标前通常会探索更大的区域，所以一般会比A*更慢一些。

那么为什么要使用这种算法呢？因为有时候我们并不知道目标的位置。比如说你有一个资源采集单位，需要获取某种类型的资源若干。它可能知道几个资源区域，但是它想去最近的那个。这种情况，Dijkstra算法就比A更适合，因为我们不知道哪个更近。用A，我们唯一的选择是依次对每个目标寻路并计算距离，然后选择最近的路径。我们寻找的目标可能会有不计其数的位置，我们只想找其中最近的，而我们并不知道它在哪里，或者不知道哪个是最近的。

进一步的阅读

好，现在你对一些进一步的观点有了初步认识。这时，我建议你研究我的源代码。包里面包含两个版本，一个是用C++写的，另一个用Blitz Basic。顺便说一句，两个版本都注释详尽，容易阅读，这里是链接。

* 例子代码： A* Pathfinder (2D) Version 1.9

如果你既不用C++也不用Blitz Basic,在C++版本里有两个小的可执行文件。Blitz Basic可以在从BlitzBasic网站免费下载的Blitz Basic 3D(不是Blitz Plus)演示版上运行。Ben O’Neill提供一个联机演示可以在这里找到。你也该看看以下的网页。读了这篇教程后，他们应该变得容易理解多了。

* Amit的 A* 页面:这是由Amit Patel制作，被广泛引用的页面，如果你没有事先读这篇文章，可能会有点难以理解。值得一看。尤其要看Amit关于这个问题的自己的看法。

* Smart Moves:智能寻路：Bryan Stout发表在Gamasutra.com的这篇文章需要注册才能阅读。注册是免费的而且比起这篇文章和网站的其他资源，是非常物有所值的。Bryan用Delphi写的程序帮助我学习A*，也是我的A代码的灵感之源。它还描述了A的几种变化。

* 地形分析：这是一格高阶，但是有趣的话题，Dave Pottinge撰写，Ensemble Studios的专家。这家伙参与了帝国时代和君王时代的开发。别指望看懂这里所有的东西，但是这是篇有趣的文章也许会让你产生自己的想法。它包含一些对mip-mapping，influence mapping以及其他一些高级AI/寻路观点。对"flood filling"的讨论使我有了我自己的“死端”和“孤岛”的代码的灵感，这些包含在我Blitz版本的代码中。其他一些值得一看的网站：

* aiGuru: Pathfinding
* Game AI Resource: Pathfinding
* GameDev.net: Pathfinding

2.3 A*算法中使用二叉堆

游戏AI之旅——A*寻路中使用二叉堆。原文链接：http://www.policyalmanac.org/games/binaryHeaps.htm

这篇文章是文章“A* Pathfinding forBeginners.”的补充。在读这篇文章之前，你应该先读那一篇文章，或者对A*做透彻的理解。

A算法中最缓慢的部分就是在开启列表中寻找F值最低的节点或者方格。取决于地图的大小，你可能有十几，成百甚至上千的节点需要在某个时候使用A搜索。无需多讲，反复搜索这么大的列表会严重拖慢整个过程。然而，这些时间在极大程度上受你存储列表的方式影响。

有序和无序的开启列表。最简单的方法就是顺序存储每个节点，然后每次需要提取最低耗费元素的时候都遍历整个列表。这提供可快速的插入速度，但是移除速度可能是最慢的，因为你需要检查每个元素才能够确定哪个才是F值最低的。

通常你可以保持你列表处于有序状态来提升效率。这花费了稍微多一点的预处理时间，因为你每次插入新元素都必须把他们放在恰当的位置。不过移除元素倒是很快。你只要移除第一个元素就可以了，它一定是F值最低的。有很多方法可以保持你的数据有序（选择排序，冒泡排序，快速排序，等等）并且你可以用你最熟悉的搜索引擎找到这方面的文章。不过我们至少可以先提几种想法。最简单的方法可能是，当你需要添加新元素的时候，从列表开始的地方，依次比较每个元素的F值和要插入的F值的大小。一旦找到一个相等或者更高的F值，你就可以把新元素插入到列表中那个元素的前面。取决于你使用的计算机于亚，使用class或者struct实现的链表可能是不错的方法。这种方法可以通过保持列表中所有元素的平均值来得到改进，使用这个平均值来决定是从头（如上所说）还是从尾开始处理。总的说来，比平均F值低的新元素将被从头开始处理，而比平均F值高的则从末尾开始。这种方法可以节省一半的时间。复杂一些，但是更快的方法是把这一想法提高到新的层次使用快速排序，它基本上是从比较新元素和列表中间元素的F值开始。如果新元素的F值低，你接着把它和1/4处元素进行比较，如果还是更低你就比较它和1/8处的元素，如此这般，不断的折半你的列表并且比较，直到找到合适的位置。这个描述很简单，你可能会想到网上寻找快速排序的更多资料。这比至此描述的任何方法都快。

二叉堆

二叉堆和刚才说的快速排序很像，经常被那些苛求A速度的人使用。根据我的经验，二叉堆平均提高寻路速度2-3倍，对于包含大量节点的地图(也就是说100×100节点或者更多）效果更明显。友情提醒，然而二叉堆很难处理，除非你使用含有大量节点的地图，速度至关重要，否则不值得为它头痛。文章其他的部分深入说明了二叉堆和它在A算法中的用途。如果你对我的文章存有疑惑，在文章末尾进一步阅读的小节中提供了更多的观点。仍然有兴趣？好，我们继续。。。

在有序列表中，每个元素都按照由低到高或由高到低的顺序保存在恰当的位置。这很有用，但是还不够。事实上，我们并不关心数字127是否比128在更低的位置上。我们只是想让F值最低的元素能放在列表顶端以便容易访问。列表的其他部分即使是混乱的也不必在意。列表的其他部分只有在我们需要另一个F值最低的元素的时候，才有必要保持有序。基本上，我们真正需要的是一个“堆”，确切的说，是个二叉堆。二叉堆是一组元素，其中最大或者最小（取决于需要）的元素在堆顶端。既然我们要寻找F值最小的元素，我们就把它放在堆顶端。这个元素有两个子节点，每个的F值等于，或者略高于这个元素。每个子节点又有两个子节点，他们又有和他们相等或略高的子节点。。。依次类推。这里是一个堆可能的样子：

注意，F值最低的元素(10)在最顶端，第二低的元素(20)是它的一个子节点。可是，其后就没有任何疑问了。在这个特定的二叉堆里，第三低的元素是24，它离堆顶有两步的距离，它比30小，但是30却在左侧离堆顶一步之遥的地方。简单的堆放，其他的元素在堆的哪个位置并不重要，每个单独的元素只需要和它的父节点相等或者更高，而和它的两个子节点相比，更低或者相等，这就可以了。这些条件在这里都完全符合，所以这是个有效的二叉堆。

很好，你可能会想，这的确有趣，但是如何把它付诸实施呢？嗯，关于二叉堆的一个有趣的事实是，你可以简单的把它存储在一个一维数组中。在这个数组中，堆顶端的元素应该是数组的第一个元素(是下标

1而不是0)。两个子节点会在2和3的位置。这两个节点的4个子节点应该在4－7的位置。

总的来说，任何元素的两个子节点可以通过把当前元素的位置乘以2（得到第一个子节点）和乘2加1（得到第二个子节点）来得到。就这样，例如堆中第三个元素（数值是20）的两个子节点，可以在位置23 = 6和23 +1 = 7这两个位置找到。那两个位置上的数字非别是30和24，当你查看堆的时候就能理解。

你其实不必要知道这些，除了表明堆中没有断层之外知道这些没有任何价值。7个元素，就完整的填满了一个三层堆的每一层。然而这并不是必要的。为了让我们的堆有效，我们只需要填充最底层之上的每一行。最底层自身可以是任意数值的元素，同时，新的元素按照从左到右的顺序添加。这篇文章描述的方法就是这样做的，所以你不必多虑。

往堆中添加新元素

当我们实际在寻路算法中使用二叉堆的时候，还需要考虑更多，但是现在我们只是学习一下如何使用二叉堆。我跳过这部分以便更容易理解基本的东西。我会在文章后面的部分给出处理这一切的完整公式，但了解这些细节仍然十分重要。大致的，为了往堆里添加元素，我们把它放在数组的末尾。然后和它在当前位置/2 处的父节点比较，分数部分被圆整。如果新元素的F值更低，我们就交换这两个元素。然后我们比较这个元素和它的新父节点，在（当前位置）/2 ，小数部分圆整，的地方。如果它的F值更低，我们再次交换。我们重复这个过程直到这个元素不再比它的父节点低，或者这个元素已经到达顶端，处于数组的位置1。

我们来看如何把一个F值为17的元素添加到已经存在的堆中。我们的堆里现在有7个元素，新元素将被添加到第8个位置。这就是堆看起来的样子，新元素被加了下划线。

10 30 20 34 38 30 24 17

接下来我们比较它和它的父节点，在 8/2 也就是 4的位置上。位置4当前元素的F值是34。既然17比34低，我们交换两元素的位置。现在我们的堆看起来是这样的:

10 30 20 17 38 30 24 34

然后我们把它和新的父节点比较。因为我们在位置4，我们就把它和 4/2 = 2 这个位置上的元素比较。那个元素的F值是30。因为17比30低，我们再次交换，现在堆看起来是这样的：

10 17 20 30 38 30 24 34

接着我们比较它和新的父节点。现在我们在第二个位置，我们把它和 2/2 = 1，也就是堆顶端的比较。这次，17不比10更低，我们停止，堆保持成现在的样子。

从堆中删除元素

从堆中删除元素是个类似的过程，但是差不多是反过来的。首先，我们删除位置1的元素，现在它空了。然后，我们取堆的最后一个元素，移动到位置1。在堆中，这是结束的条件。以前的末元素被加了下划线。

34 17 20 30 38 30 24

然后我们比较它和两个子节点，它们分别在位置(当前位置2)和(当前位置* 2 + 1)。如果它比两个子节点的F值都低，就保持原位。反之，就把它和较低的子节点交换。那么，在这里，该元素的两个子节点的位置在 1 * 2 = 2和 12 + 1 = 3。显然，34不比任何一个子节点低，所以我们把它和较低的子节点，也就是17，交换。结果看起来是这样：

17 34 20 30 38 30 24

接着我们把它和新的子节点比较，它们在 22 = 4，和22 + 1 = 5的位置上。它不比任何一个子节点低，所以我们把它和较低的一个子节点交换（位置4上的30）。现在是这样：

17 30 20 34 38 30 24

最后一次，我们比较它和新的子节点。照例，子节点在位置 42 = 8和42+1 = 9的位置上。但是那些位置上并没有元素，因为列表没那么长。我们已经到达了堆的底端，所以我们停下来。

二叉堆为什么这么快？

现在你知道了堆基本的插入和删除方法，你应该明白为什么它比其他方法，比如说插入排序更快。假设你有个有1000个节点的开启列表，在一格有很多节点的相当大的地图上，这不是不可能（记住，即使是100×100的地图，上面也有10,000个节点）。如果你使用插入排序，从起点开始，到找到新元素恰当的位置，在把新元素插入之前，平均需要做500次比较。

使用二叉堆，你从底端开始，可能只要1－3次比较就能把新元素插入到正确的位置。你还需要9次比较用来从开启列表中移除一个元素，同时保持堆仍然有序。在A中，你通常每次只需要移除一个元素(F值最低的元素)，在任意位置添加0到5个新节点(就像主文章里描述的2D寻路)。这总共花费的时间大约是同样数量节点进行插入排序的1%。差别随你地图的增大(也就是节点更多)呈几何增长。地图越小，就越没优势，这也是为什么你的地图和节点越少，二叉堆的价值就越低的原因。顺便，使用二叉堆并不意味着你的寻路算法会快100倍。在下面还讲了一些棘手的问题。额外的，A不仅仅是为开启列表排序。然而，根据我的经验，用二叉堆在大部分场合可以提高2－3倍的速度，更长的路径，速度提高的更多。

创建开启列表数组

现在我们了解了二叉堆，那么如何使用它呢？首先要做的是构造我们的一维数组。为此，我们先要确定它的大小。一般来说，列表大小不会超过地图上的节点总数（在最坏的情况下，我们搜索整个地图寻找路径）。在一个方形二维地图中，就如我的主文章中描述的，我们的节点不超过地图宽 × 地图高。那么我们的一维数组就是那个大小。在这个例子里，我们叫这个数组 openList()。堆最顶端的元素被存储在openList(1)，第二个元素在openList(2)，依此类推。

使用指针

现在我们有了正确大小的数组，几乎可以开始用来寻路了。不过，在进一步的添加或者删除操作之前，我们再看看原始的堆。

现在，它只是个F值的列表，而且已经被正确安排。但是我们忽略了一个重要的元素。是的，我们有一系列的F值按顺序保存在堆里，但是我们没有他们代表哪一格的任何线索。基本上，我们只是知道10是堆中最低的F值。但那指的是那个格子？为了解决这个问题，**我们必须改变数组中元素的值。我们不储存排序好的F值，取而代之的是保存关联到地图网格的唯一标志。**我的方法是为每个新加入堆的元素创建一个唯一ID叫做squaresChecked。每次往开启列表中添加新元素，我们给squaresChecked增加1，并把它作为列表中新元素的唯一ID。第一个添加进列表的是#1，第二个是#2，依此类推。最后，我们把具体的F值存储在单独的一维数组中，我把它叫做 Dcost()。和开启列表相同，我们把它的大小定为(地图宽 x 地图高)。我们同时存储节点的x和y坐标在类似的一维数组中，叫做 openX() 和 openY()。看起来就像下面的图：

尽管这看起来有点复杂，但它和前面讲的堆是相同的。只是储存的信息更多了。

#5元素，有最低的F值10，仍然在堆顶，在一维数组的第一列。不过现在我们在堆里存储它的唯一ID 5，而不是它的F值。换句话说，openList(1) = 5。这个唯一数值用来查找元素的F值，以及地图x和y坐标。这个元素的F值是Fcost(5) = 10，x坐标是openX(5) = 12，y坐标是openY(5) = 22。顶端的元素有两个子节点，数值是2和6，他们的F值是30和20，分别存储在opneList()中2和3的位置，等等。基本上，我们的堆和以前相同，只是多了一些关于元素在地图上的位置，F值是多少，等等的信息。

在堆中添加新元素(第二部分）

好，我们实际的把这种技术用在A*寻路的开启列表排序中。我们使用的技术和先前描述的大体相同。

我们添加到开启列表中的第一个元素，一般是起始节点，被分配了一个数值是1的唯一ID，然后放入开启列表的#1位置，也就是 openList(1) = 1。我们还跟踪开启列表中元素的数量，现在也是1。我们把它保存在名为numberOfOpenListItems的变量里。

当我们往开启列表中添加新元素的时候，首先我们计算G，H和F值，就如在主文章中所述。然后按照前面讲的方法把他们添加进开启列表。首先我们给新元素分配一格唯一 ID号，也就是squaresChecked变量的用途。每次我们添加一个新节点，就给这个变量加1，然后把它的数值分配给新节点。然后给numberOfOpenListItems加1。然后把它添加到开启列表的底部，所有这些可以翻译成：

squaresChecked = squaresChecked +1

numberOfOpenListItems =numberOfOpenListItems+1

openList(numberOfOpenListItems) =squaresChecked
1
2
3
4
5

然后我们依次把它和父节点比较直到它到达正确的位置。这是这些操作的代码：

m = numberOfOpenListItems

While m <> 1 ;

While item hasn't bubbled to the top(m=1);

Check if child is <= parent. If so,swap them.  
If**Fcost(openList(m))** <=**Fcost(openList(m/2))**Then  
temp = openList(m/2)

openList(m/2)= openList(m)

openList(m) = temp

m= m/2

Else

Exit ;exit the while/wend loop

End If

Wend
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

从堆中删除元素(第二部分)

无疑，我们不能只建立堆，当不需要的时候，我们也要从堆中删除元素。特别的，在A*寻路中，我们在检查和切换到关闭列表之后，从堆顶需要删除F值最低的元素。如前所述，你从把末元素移动到堆顶开始，然后把堆中的元素总数减1。伪代码是这样：

openList(1) = openList(numberOfOpenListItems)

numberOfOpenListItems =numberOfOpenListItems – 1
1
2
3

接着我们需要依次比较它和两个子节点的数值。如果它的F值更高，我们就把它和更低F值的子节点交换。然后我们把它和新的子节点比较（看它是否更低）。如果它的F值比两个子节点更高，我们把它和较低的一个交换。我们重复这个过程直到找到它的正确位置，这可能会一直持续到堆底，但并不是完全必要。伪代码看起来是这样：

v = 1;

Repeat the following until the item sinksto its proper spot in the binary heap.

Repeat

u = v

If 2*u+1 <= numberOfOpenListItems ;

if both children exist; Select the lowestof the two children.

If **Fcost(openList(u)) >=Fcost(openList(2*u))** then v = 2*u ;SEE NOTE BELOW

If Fcost(openList(v)) >=Fcost(openList(2\*u+1))then v = 2\*u+1 ;SEE NOTE BELOW

Else If 2*u <= numberOfOpenListItems ;

if only child #1 exists; Check if the Fcost is greater than the child

If Fcost(openList(u)) >=Fcost(openList(2\*u))then v = 2\*u

End If

If u <> v then ;

If parent's F > one or both of itschildren, swap them

temp = openList(u)

openList(u)= openList(v)

openList(v) = temp

Else

Exit ;if item <= both children, exitrepeat/forever loop

End if

Forever ;Repeat forever
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

请注意两行代码中粗体(红色)的u和v的数值。在第二行，你应该使用 v而不是u，这不是很显而易见。这确保了你把它和较低的子节点交换。如果做错会造成不完整的堆，完全打乱你的寻路。

对开启列表的元素重排序

就如在主文章中描述的，有时候你会发现现有的开启列表中的元素会改变。这种情况发生的时候，我们不必要取出这个元素重新来过。只要从当前位置开始，用它新的（更低的）F值和它的父节点比较。如果它的F值低到足以替换它的父节点，你就把它替换掉（不然你就会得到一个错误的堆，一切都完了）。一般，你使用和“在堆中添加新元素”的小节中相同的代码。不幸的是，因为你的数据是在一个庞大，无序的堆里，你需要遍历整个堆查找先有开启列表中的元素。你主要要查找由openX(openList()) 和openY(openList())获取的确切坐标的格子，找到之后，你就可以从那一点开始，像往常那样做必要的比较和交换。

最后的注解

好了，我希望你仍然能读懂，没有被搞昏头。如果你不着急，并且希望在自己的寻路算法中使用二叉堆，那么这就是我的建议。首先，把二叉堆放一放。把注意力放在你的A*寻路算法上，使用简单点的排序算法，保证算法正常工作没有bug。一开始你并不需要它很快速，你只需要它能工作；其次，在你把二叉堆添加到代码中之前，试着把二叉堆写成独立的功能，用适当的方法添加和删除元素。确保你写的程序中，可以看到整个过程中每一步的操作，也许可以把结果打印在屏幕上，如果你愿意。你还得包含一些中途退出的代码，以便在必要的时候结束整个流程。如果二叉堆写的不对，你很容易就会陷入到无限循环中。一旦你确信两个程序都运行无误，备份他们，然后开始把他们结合起来。除非你比我还聪明，否则一开始你难免遇到麻烦。输出都是些错误信息，或者看到寻路者因为bug走出各种怪异的方向。不过最终你会搞定一切。

2.4 A*分层寻路

在我的主题A* Path finding for Beginners中中，我概述了A*算法，说明了如何创建一个通用的寻路功能。然而仅创建一个寻路功能，用途是很有限的。考虑如下的RPG场景，一个剑士想找到绕过旁边墙壁的路：

对于这类地图，你可以用不同的方式，密度来放置节点。在这个例子中，我们使用高密度网格，如下：

在这个图中，白色节点是可通过的。没有节点的地方是不可通过的。这个例子还有一些不同的地方。在这个例子中，你可以“穿越”不可通过区域的拐角。同时，“方格”也不再是方格。因为这是一个投影视角的例子，我们在Y(垂直方向)拥有X(水平方向)两倍的节点。这使得正确的投影路径成为可能。如你所见，用这么密集的节点网络，我们不仅能寻路绕过旁边的墙壁，还能在墙壁和旁边的桶之间找到路径。我们密集的网格也使得绕过底部不可通过的火把成为可能。这总的说来是精确寻路。

好，在短距离上，那的确很酷，但是如果我们要穿越整个地图进行寻路，该怎么办？使用像这么密的网格，轻易就会让你在一条路径上使用A*的搜索节点的数量达到10,000+。这几乎会让任何PC失去响应。那么我们来看另一种选择。创建一个低密度的网格，就像下面这样，如何？

在这个例子里，节点在等边菱形的中心。菱形之间通过性的数据沿边界存储在同一个数组中，在图片上用小红点表示。要从一个图素移动到它周围8个图素上，相邻的图素必须是可通过的，并且路径没有被挡住。

这个节点网格的密度是先前的72分之一。原来我们需要面对10,000+的节点，而现在，取而代之的是1/72原来的数量，或者说，少于200个。我们的电脑可以轻易处理这个。穿越地图寻路的问题迎刃而解。

合而为一

那么，我们用哪种方法呢？两者！在给定的搜索中，你得先在地图范围内，用宏观寻路的方法。然后切换到微观寻路，寻找从当前位置到路径上两个宏观节点以外的路径。每次你进入一个宏观菱形“方格”，你应该用微观寻路算法寻路到两个宏观节点之前。这导致浪费了每次微观寻路的后半截路径，但是你有必要这样做以便路径看起来足够好，并且这也不是很严重的浪费，因为你的微观寻路算法只计算了相关的一小段路径。一旦你到达了距离目标2-3宏观节点的地方，你应该完全切换到微观寻路算法，完成到最终位置的寻路。用这种方法，你将得到更接近现实的快速穿越地图的寻路以及能穿越角落，木桶等等就像最开始那个微观寻路例子的效果。有够酷，哈！

如果你真的有野心，你可以开发3种寻路器，如果你的地图实在太大，一个工作在真正的宏观层次，一个在中间层，一个在微观层。专家已经为像帝国时代(Age of Empires)这样的游戏设计了这些。这仅仅取决于你的需要。