950 views
# A*寻路算法入门 ###### tags: `blog` 原文链接:[A* Pathfinding for Beginners](http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/a-pathfinding-for-beginners-r2003) 对初学者来说,A*(读作“A星”)算法可能有点复杂难懂。在网上有很多介绍A*算法的文章,但大多数是写给那些已经有了相关基础知识的人看的。而这篇文章,是真正写给初学者看的。 要真正学懂A*算法,并不是靠这篇文章就够了,这里只是介绍了A*算法的基础,方便你深入去阅读并理解其他相关的资料上关于A*算法的介绍。本文最后给出了其他一些好的相关资料的链接,列出在“扩展阅读”之后。 另外,这篇文章不是面向编程的,读完该文章后,你可以用任何的编程语言来实现该算法。然而,如你所料,我在文章的最后给出了一个示例程序的链接,包含了C++和Blitz Basic两个版本的程序。如果你只想看看A*算法是怎样进行的,链接里也包含了一个可以直接运行的可执行程序。 现在让我们重头开始学习A*算法... ## 介绍:搜索区域 假设我们有人想从一个地点A到达另一个地点B,再假设有一堵墙把两个地点分隔开了。如下图,绿色的方块代表地点A,而红色的方块代表地点B,蓝色的方块代表两个地点之间的那堵墙。 ![](https://i.imgur.com/rF0VG8i.png) [图1] 你应当注意到的第一件事是,我们已经把搜索区域划分成了一个个的正方形格子。这样做,是为了简化我们的搜索区域,这是寻路算法要做的第一步。这个特定的方法把我们的搜索区域简化成了一个二维数组,数组里的每个元素代表网格上的一个方块,它有可行走和不可行走两种状态。当我们找出从A到B应该选取哪些格子,我们的路径就找出来了。当路径找到之后,我们的人就从一个格子的中心走到下一个格子的中心,如此进行,直到到达目标格子。 这些中心点,我们称之为“节点”("nodes")。当你阅读其他关于寻路算法的资料时,你会常常见到关于“节点”的讨论。为什么我们不直接把它们叫做“正方形”呢?因为我们除了正方形,我们还可能把搜索区域划分成其他的形状,可能是长方形、六边形、三角形或者其他的任何形状。并且这些节点可以被放置在那个形状里的任何位置,在中心、沿着边沿或者其他任何位置。我们使用正方形并把节点放在中心的方式,是因为这是最简单易懂的。 ## 开始搜索 当我们已经把搜索区域简化成可控数量的节点之后,比如上面的网格布局,下一步就是进行搜索以找到最短的路径。我们从A点开始搜索,检查它的相邻节点,并且按照常规地往外搜索,直至找到目标节点。 我们以下面的方式来开始搜索: 1. 从A点开始,并把A点加入到所谓的“开放列表”,这个列表由一些需要被考虑到的节点组成。这个开放列表类似于购物清单。目前,开放列表里只有一个元素,但是往后会有更多。被加入开放列表里的节点,最后可能会被采纳,出现在最终的路径上,不过也可能不会。基本上,开放列表就是一个需要被检查的节点组成的列表。 2. 遍历开始节点所有可行走的相邻节点,忽略那些墙壁、水或者其他规定不可行走的节点,并把它们加入到开放列表里。对于这些节点,把A设置为它们的“父节点”。这个“父节点”对于我们找到路径非常重要,这个在后面会介绍。 3. 把A点从开放列表里移除,并把它加入到所谓的“关闭列表”中,关闭列表里的节点是那些不需要再次检查的节点。 现在,你得到下图呈现的一个状态。如图所示,中间的暗绿色正方形就是那个起始的正方形,用亮蓝色的线把它框起来以表示它已经被加入了关闭列表。现在,开放列表里的所有正方形都准备被检查,它们被用亮绿色的线框了起来。每个正方形里都有一个灰色的指针,指向它的父节点,即那个起始节点。 ![](https://i.imgur.com/1qJ9605.png) [图2] 下一步,我们从开放列表里选取节点,并重复上述步骤。但我们应该选取哪个节点呢?选取那个具有最小F值得节点。 ## 路径评分 寻找路径时,决定选取哪个节点的关键是以下这个等式: ``` F = G + H ``` 这里: - G = 从起始节点A移动到网格中给定节点的代价(从A移动到该节点的上一个节点的代价,加上上一个节点到该节点的代价); - H = 从该给定节点移动到终点B的代价的估计值。这通常被称作“启发式”,它可能有点让你觉得迷惑。之所以把它叫做“启发式的”,是因为它只是一个估算或者说一个猜测。我们实际上不知道某个给定节点到终点的真实距离,直到我们已经找到了最终的路径,因为路上可能有各种各样的东西(墙壁、水等等)。我们这里给出一种计算H的值的方法,但你从网上的其他文章里找到很多其他的计算方法。 我们的路径是通过重复地遍历开放列表里的节点并选取F值最小的节点来产生的。这个过程的细节会在文章接下来的部分作介绍,这里首先让我们详细地看一下怎么计算上述的那个等式。 如上所述,G是从起点经过生成的路径到达给定的节点消耗的代价,在这个例子中,我们假设从某个节点水平或垂直移动到相邻节点的代价是10,而移动到对角的相邻节点的代价是14。之所以假设这样的值,是因为移动到对角上的相邻节点的真实距离是2的开方根,或者大致地说,是1.414倍于水平或垂直移动到相邻节点的距离。出于简便的目的,我们使用了10和14,这样假设的比例是大致正确的,而且这也避免了计算开方根和浮点数。这并不是因为我们不会或者不喜欢数学,而是这同时能够让计算机在运算的时候更加快,因为接下来你会发现,如果你不采用这些简化策略,寻路算法运行起来可能会相当的慢。 我们需要计算沿着特定路径到达指定的节点的代价G,方法就是在它的父节点的G值的基础上,加上10或者14(这取决于它在父节点的正交方向还是对角方向)。如果我们从开始节点往前多走几步,这种方法会显得更加明朗一些。 H的值可以用多种不同的方法来估算。我们在这里使用的方法叫做“曼哈顿法”(Manhattan method),这个方法中,把到达目的节点的水平距离和垂直距离的总和作为路径长度,而忽略对角线方向的移动以及路途中可能存在的障碍物。然后我们把这个总数乘以10,即水平或垂直移动一个方格的代价。这个方法之所以被叫做“曼哈顿法”,(可能)是因为这类似于计算从城市里的一个地点到达另一个地点需要经过的街区数目,这时你是不能够从对角线方向穿过一个街区的。 看到这里,你可能觉得启发式搜索只是从给定节点沿着直线前进到达目的节点的距离的一个粗略估算,但实际不是这样,我们实际上是在尽量估算路径剩余的距离(通常来说比估算值更大)。我们估算的距离与实际距离越接近,这个算法运行得就越快。如果我们高估这个距离,这个算法就不能保证找到最短的路径,在这种情况下,我们把它叫做“不能接受的启发”。 从技术上说,在这个例子中,曼哈顿法是不可接受的启发,因为它稍微有点高估了剩余距离。但我们还是采用这个方法,因为对于入门者来说,它便于理解,并且它仅仅是稍微高估了实际值。在极少的情况下,该方法得到的路径可能不是最短路径,但也会很接近最短的了。如果你想了解更多估算方法以及关于启发式的知识,可以通过[这个链接](http://www.policyalmanac.org/games/heuristics.htm)。 F通过把G和H相加得到。我们搜索的第一步的结果可以从下图中看到,F、G和H的值标在了每个节点的方块上。拿起始节点相邻的右边那个节点来说,F标在左上方,G标在左下方,而H标在了右下方。 ![](https://i.imgur.com/2380Fxd.png) [图3] 现在我们来看看其中一些节点。对于那个里面标了字符的节点,G = 10,因为它距离起始的节点只有一个方格的水平距离。同理,其实节点上方、下方和左方的节点的G值都是10,而对角上的节点的G值是14。 节点的H值通过计算它到红色的目标节点的曼哈顿距离而获得,也就是只沿着垂直和水平方向前进并且忽略障碍物的距离。通过这个方法,起始节点右边节点到达红色目标节点的距离是3个方格,因此H值是30,而起始节点上方的节点(记住只沿着垂直和水平方向走)的H值是40。现在你应该也可以计算出其他各个节点的H值了。 再次提醒读者,至于节点的F值,只需要简单地将该节点的G值和H值相加即可。 ## 继续搜索 继续搜索的时候,我们从开放列表中选取F值最小的节点,并对选中的节点作如下操作: 把它从开放列表中移除,并把它加入到关闭列表。 检查它所有的相邻节点,忽略那些在关闭列表中或者不可以行走的节点(墙壁、水或者其他非法的),如果这些相邻节点还没被加入开放列表里,就把它们加入到开放列表,并把选中的节点作为新加入开放列表的节点的“父节点”。 如果一个相邻节点已经在开放列表里,就检查是否途经选中节点的路劲是一条更优的路径。也就是说,如果经过选中节点再去到那个相邻节点,那个节点会不会获得一个更小的G值。如果不,就不需要做任何操作。如果能够获得一个更小的G值,就应该把该相邻节点的父节点设置为选中的那个节点(如图,也就是把节点方块里的指针箭头指向选中的节点),然后重新计算这个节点F值和G值。如果你觉得迷惑,请继续往下看。 那现在我们看看这是怎么进行的。对于我们开始的9个节点,把起始节点放进关闭列表中之后,我们还有8个节点在开放列表中,在这8个节点当中,起始节点右边那个节点的F值是最小的,即40,因此我们选中了这个节点作为下一步的节点,下图将该节点用蓝色框作了标注。 ![](https://i.imgur.com/jYRoZrs.png) [图4] 首先,我们把这个节点从开放列表中移除并加入关闭列表。然后,检查它所有的相邻节点。它右边的相邻节点以及右边对角上下的两个节点都是墙壁,因此忽略它们,而它正左方的相邻节点是起始节点,这个节点已经被加入到关闭列表,因此也忽略它。 另外的四个相邻节点都已经在开放列表中了,因此我们需要通过计算G值来确认,经过这个节点再到达这4个相邻节点,是否能够得到一条更优的路径。我们看一下选中节点正上方那个节点,它目前的G值是14,如果我们经过选中节点再到达这个节点,它的G值就会是20(选中节点的G值是10,从选中节点需要沿着垂直方向向上走一格到达该节点,因此要加上10)。20比14要大,因此这不是一条更优的路径。看图你应该可以理解其中的实际意义,从起始节点直接沿着对角方向走一格到达该节点的距离更近,而不需要先水平向右走一格再垂直向上走一格。 如果我们对这4个已经在开放列表中的节点都重复上述计算过程,我们会发现,途经选中节点,没有一个节点的G值会变得更小,因此我们不需要做任何的操作。目前我们已经检查了选中节点的所有相邻节点,因此我们对选中节点的操作已经完成了,现在我们准备移到下一个节点。 现在开放列表里的节点减到了7个,我们现在需要遍历一次这些节点,并且选中F值最小的那个节点。有趣的是,现在有两个节点的F值是最小的54,我们应该选取哪一个呢?其实选哪个都没关系。为了快速,选取后来加入开放列表的那个节点会快一点。这个方法偏向了在搜索过程中后来才找到的那个节点,你把后来的节点加入开放列表的时候,你是相对更加靠近目标节点的。可是实际上选取哪个都没关系。(在这个步骤中采用不同的策略是两个版本的A*算法得到长度相同的不同路径的原因。) 我们选取起始节点右下方对角的那个节点,如下图所示: ![](https://i.imgur.com/vO6rULc.png) [图5] 这次,当我们检查选中节点的相邻节点时,我们发现它正右方的节点是墙壁,因此忽略它,右上方对角那个节点同理。我们也忽略墙壁下方那个节点。为什么呢?因为除非把墙壁左下方那个转角砍掉,否则你无法穿过这个墙角从选中节点到达墙下方这个节点,你需要先往下走一格绕开那个墙角。(注意:这个需要绕开墙角的规则是可选的,这可视实际情况入定)。 现在只剩下5个相邻节点需要检查。在选中节点下方的两个节点还没被加入到开放列表中,因此把它们加入开放列表并把选中节点设为它们的父节点。至于其他3个节点,两个节点已经被加入了关闭列表(起始节点以及选中节点正上方的节点,图上把两者都用蓝色框做了标注),因此忽略这两个。剩下最后一个节点,也就是选中节点正左方那个,计算一下是否途经选中节点会使得它得到更小的G值。显然不,因此我们结束这个节点的操作并准备选取开放列表中的下一个节点。 不断重复上述的步骤,直到我们把目标节点加入关闭列表为止,最后的图示如下: ![](https://i.imgur.com/4MKTt2J.png) [图6] 注意,对比[图5],起始节点正下方两个方格距离的那个节点的父节点已经发生了改变。在[图5]中,它的G值是28并且指针箭头指向它右上方对角的那个节点,而现在它的G值是20并且指针箭头指向它正上方的节点。这个改变发生在我们继续搜索的过程中,我们发现一条新路径使得这个节点能获得更小的G值,因此我们改变它的父节点并且重新计算它的G值和F值。虽然在这个例子中,这个改变的意义不是很大,但在很多情况下,这种改变对你找到最优路径意义重大。 最后,我们应该怎么确定路径呢?很简单,只需要从红色的目标节点开始,然后沿着它的父节点往回走,也就是沿着指针箭头的方向,这最终会引导你走到起始节点,这就是我们需要找的路径了。如下图所示。从起始节点A走到目标节点B实际上就是从路径上的方格的中心(即上文说的节点)走到下一个方格的中心,直到到达目标节点。 ![](https://i.imgur.com/NTpyWNs.png) [图7] (完)