最短路径搜寻之A*算法
声明
本文译自 Patrick Lester先生的一片博文，觉着实在是一片优秀的文章，于是打算花点时间将其翻译成中文，一来自己学习一番，二来可以方便国内读者。如有谬误，欢迎拍砖。原文请参见： https://www.gamedev.net/articles/programming/artificial-intelligence/a-pathfinding-for-beginners-r2003/
序
A-Start 算法对于初学者来说可能有些复杂，尽管网上有很多讲解它的文章，但大多是在认为读者已对该算法有一定程度了解的基础上写的。这篇博文则主要面向入门小白。
这篇文章不是我们学习A*算法的终点，而是我们阅读其他相关内容的基础，因此在文末我列出了一些优秀的博文以供大家进一步学习。
最后我还得声明一点，这篇文章并不是面向程序设计的，你可以将本文的观点运用到任何编程语言当中。我也在文末给出了一个例子程序的链接，你也许会用得上。这个例子包含C++和Basic两个版本，当然也包含了可执行文件在里面。
介绍：搜索区
假设有个人想从A点到达B点，A、B之间有一堵墙阻隔。如下图所示，绿色的方框代表A点，红色的方框代表B点，中间蓝色的条状物则代表这堵墙。
图1
你应该已经发现，我们需要做的第一件事就是把搜索区与分成一个一个的网格，即搜索区简化。通过这个方法将我们的搜索区域简化成了一个二维数组，数组中的每个元素都代表一个网格，并且记录了状态为可达或不可达。在路径搜寻的过程中，逐步判断下一步应当踏入哪个网格，直到达到目标点。
我们把每个网格的中心点叫做“节点”，当参阅其他一些关于路径搜寻的文章时，你会发现他们也是称“节点”。为什么不直接叫网格呢？因为除了正方形格网外我们还可将搜索去分成其他不同形状的多边形，比如矩形、正六边形、三角形甚至其他任意形状。所以我们在这些多边形上选取一个代表点（几何中心、重心等）来代表多边形本身，统一称为“节点”。
开始搜索
在上面的讨论中，我们将搜索区简化成了一个个网格，下一步就是在此基础上搜索最短路径。从A点开始，向外搜索相邻网格知道到达目标点。
1.从A点开始，将其添加到待考虑的“open list”中，"open list"就像一张购物清单，现在单子里只有一件物品，但稍后我们会往里加入更多。里面包含了到目标点的最短路径沿途可能会经过的网格，因此需要我们逐个检查判别。
2.考察与起点A相邻的所有网格，代表墙、水域或其他非法区域（不可达区域）的直接略过，可达的网格加入“open list”，对于所有选中的相邻的网格，同时记录网格A为其"父亲网格"，这对于我们追踪路径十分重要，后面我们将详细讨论。
3.把网格A从"open list"中去掉，将其加入"closed list"中，从现在开始就不需要再考虑它了。
到这一步你就进行到了如下图所示的一个状态。中间绿色的网格代表你的起点，起点网格的边缘以亮绿色高亮显示表示该网格已经加入到"closed list"。周围所有相邻的网格都被加入到了"open list"等待检核，并且每个网格里都有一个个灰色的指针标记指向该网格的“父亲网格”，也就是我们的起点网格A。
图2
下一步我们将从"open list"中选取一个F值最小的网格，因此如何计算F值是我们接下来要讨论的内容。
路径评分
路径构建过程中网格选取的关键就是如何计算下面这个等式：F=G+H
- G=从起始网格A到指定其他网格的移动耗费
- H=任意格网到终点网格B的移动耗费。我们通常使用启发式算法来计算，看到这里你也许有些迷惑。之所以称为启发式算法是因为它实质就是一种估计，在找到最短路径之前我们都不清楚到B的实际最短距离是多少，因为中途可能遇到挡墙、水体等障碍物而导致你绕道。在本文我们将介绍一种计算H值的方法，当然你在其他文章中还可以找到更多优秀的方法。通过反复遍历"open list"选取具有最小F值的网格。在后面我们将详细讨论这个过程，首先我们来看看如何计算这个等式。
上面我们指出，G代表起点网格A到路径经过的网格所耗费的距离。在这个例子中，定义网格移动的水平或垂直耗费为10，对角移动的耗费为14。采用这两个距离耗费值是因为，对角移动的实际耗费距离为2的算术平方根，大概是水平和垂直移动距离耗费的1.414倍。为了简单起见，分别使用10和14代替，这样可避免开方和浮点数的计算。所以这并不是因为我们在犯迷糊或者讨厌数学，哈哈。在计算机中使用整数进行计算比使用小数更快，很快你会发现，如果不使用整数计算，那么路径寻找真的是太慢了。
计算G值的方法就是获取到该点“父亲节点”的G值，然后在此基础上根据从"父亲节点"是否对角移动到该节点加上10或者14的耗费。这个方法的必要性稍后会显得更加明显，因为我们有不止一条从起始网格开始的路径。
H 值的计算方法有很多，我们在这里采用的是曼哈顿距离，通过计算从考察网格到目标网格的水平和垂直移动的网格数目之和，期间不可虑对角移动以及途中的障碍物，然后将总数和乘上10。看到这里你也许会猜想说，这启发式算法就是估算当前网格与目标网格之间的直线距离。其实不对，我们实际上是在尝试估计到终点的剩余距离，估计越准确，算法就越快。如果估计距离大于实际距离，那就不能保证最后得到的路径是最短的了，只能说近似最短，我们称这种情况为“不可接受的启发式”。在这个例子采用的曼哈顿方法就是“不可接受”的，因为曼哈顿距离比实际距离稍长。但因为这种方法简单明了，并且只是比实际长度稍微长了些，所以还是坚持采用它。在很少情况下会导致求得的路径不是最短的，如果你想了解更多关于启发式算法的内容，请参考这个链接。
通过逐步累加G和H值计算得到F，路径搜索第一步的结果如下图所示，每个网格都标注了F、G和H评分，左上角是F值，左下角是G值，右下角是H值。
图3
注意看标记了字母的这个网格，G=10表示从起点网格A向右移动一个水平距离即到达该网格，类似的，从该网格向右移动三个水平距离即到达终点红色网格，因此H值为30，而紧接着这个网格上面一个网格的H值对应就是40（注意H值的计算我们只能水平或是垂直运动）。以此类推你就可以计算出其他网格的评分值了。
继续搜索
在路径搜索过程中，我们从"open list"中选出F值最小的网格，然后进行下面的步骤：
最初的9个网格中，在起始网格A(绿色)被移至"closed list"后，"open list"中就还剩下周围的8个网格，从图4我们会发现，紧接着右边的那个网格就是F最小(40)的网格，所以选择这个格网作为下一步位置。对应图中边缘高亮显示的网格。
图4
首先将选出的最小F值的网格从"open list"中移除并加入到"closed list"（这就是为什么该网格边缘现在是高亮显示的），该网格记为node1，然后开始检核node1接下周围的8个网格再次选出F值最小的一个网格。右边的网格代表的是墙体所以忽略掉，左边的绿色网格（即我们的起始网格）由于在前面的步骤中已经加入到"closed list"，所以也不予考虑。剩下的四个网格已经加入的"open list"，接下来我们考察经由网格node1到达"open list"中的网格的路径长度是否比不经过node1的路径短。以node1正上方的网格为例，如果我们不经由node1直接从网格A到达该点，那么G值为14，如果经过了node1，G值为20（在node1 G值为10的基础上再加上垂直向上移动的耗费10），20>14所以选择不经过node1直接从A对角到达node1正上方的网格。对"open list"中的4个网格执行同样的判断，我们发现都不会因为经过node1而使得路径变短。所以将直接考察这4个网格以从中选出下一步将到达的位置。
去除node1后"open list"还剩下7个考察对象，遍历"open list"获取F最小的那个网格，在给出的例子中，F最小值为54,并且有两个网格都是54。选哪个呢？这不是那么重要。处于算法的速度考虑，我们应该选择相对后加入到"open list"中那个网格，这会使得我们的搜索算法在一步步接近终点的搜索过程中更偏向于选择最新发现的网格。但这确实不是那么重要（这就是为什么两个不同版本的A-Start算法会得到不同的最短路径长度）。因此我们选择起始网格A右下方的网格，如下图所示，同样边缘已高亮显示。
图5
当前我们处于node2这个位置，考察node2邻接的网格发现，右边格网代表隔墙，所以不予考虑。node2右下方的网格也不考虑，因为我们认为有墙体的拐角存在二导致无法直接到达，只能通过下移然后再向右移动一个网格到达。（注意：这里的拐角是否可直接到达你根据你的应用场景二定的，并不是说这种情况一定不可达）。
这么一来，node2周围就剩下5个网格待考，底下的两个还没有加入到"open list"，所以把它两加进去并且记录node2作为它们的父亲节点。剩下的三个网格中，有两个（绿色起点网格和它左边的网格都已经加入到"closed list"），因此也忽略掉。剩下的最后一个网格（node2左边的这个）我们将考察如果路径经过node2再到达该网格是否会获得更低的耗费，答案是否定的，所以我们继续考察"open list"中剩下的网格。重复这个步骤知道将重点网格加入到"closed list"。最终就是如下图所示的状态。
图6
注意：如上图所示起始网格以下的第二个网格的个指标值发生了变化，在此之前G值为28，父亲节点为它右上方的网格，现在它的父亲节点为正上方的网格。在路径搜索过程中，当我们发现有一条更低耗费的路径存在时，该网格的父亲节点就会更新并且重新计算各指标值。但是这个改变在这个例子中看起来也不是那么重要，因为整个过程中有那么多的最佳道路的调整选择二导致了许多不同的解决方案。
所以我们是如何获取到这条路径的呢？简单，从红色的目标网格开始，根据记录的父亲节点逐个往回取，和箭头的指示方向是一致的。这样就回到了起始的网格Ａ，同时也得到了我们的最短路径链。如下面的插图所示，Ａ移动到Ｂ的路径搜寻说白了就是这么简单的一件事：从一个网格的中心点移动到下一个网格的中心点，直到找到你希望到达的目标点为止。
图７
算法总结
到这里你已经对整个算法有了大概的了解，现在让我们逐步罗列出算法过程：
1.将当前网格currentNode从open list中删除并加入到closed list；
2.检查currentNode周围的网格，对于已加入到closed list的和现实中不可达的网格（如墙体、水域或其他非法区）直接忽略，对于剩下的并且尚未加入到open list的网格，我们将其加入到open list，同时记录currentNode为它们的父亲网格；
3.对于剩下的并且已经加入到open list的与currentNode相邻的网格记为neighborNode，考虑从起始点到该neighborNode是否还存在一条更佳的路径。换句话说，如果我们选择经由currentNode到达neighborNode是否会使得neighborNode的G值变得更小，如果不会，那啥也不用做；如果G值可变得更小，就改变neighborNode的父亲节点为currentNode，最后计算出neighborNode新的F值和G值并更新记录。
4.接着步骤2说，尚未加入到open list的网格我们会将其加入进去（当然也可能是算法启动时初次加入起始点网格）；
5.重复下面的步骤：
a)获取到open list中最小F值对应的网格，将其作为新的currentNode
b)将currentNode移到closed List
c)对于其周围相邻的8个网格......
- 如果网格不可达或者已经加入到closed list，忽略，否则执行下面的步骤
- 如果网格不在open list中，则加入到open list，记录当前网格currentNode为其父亲节点，计算出F值、G值和H值并记录。
- 如果已经加入到open list中，以G为指标考察是否存在更佳路径，G值越低我们则认为路径约佳。如果经由currentNode达到这个相邻网格的路径耗费更低（即路径更佳），那么就需更改这个相邻网格的付清节点为currentNode并重新计算F值和G值。如果你的open list是按F值排序的，那么还需要进行重排序。
d)出现下列情况之一则算法终止：
- 终点网格已加入到closed list，表示已找到最佳路径，现在我们需要把这条路径保存下来。从终点网格开始，根据记录的父亲节点往回逐步递推直到起始网格，沿途经过的网格即是我们所求的路径了；
- 还没有移动到终点网格但open list已经空了，那就表示无解，算法终止；
（注意：在这篇文章的早期版本中我们建议当目标网格被加入到open list时即终止算法，而不是等到加入到closed list才终止，这样可以提升算法效率并且在大多数时候会得到最短路径解。但也并不总是这样，比如如果有条河流处于倒数第二个网格和最后一个网格之间时，它们之间的移动耗费可能发生很大变化）
题外话
值得一提的是，当你在网上或者一些论坛读到关于A-Star的文章时，你可能会发现有些人把一些并不是A-Star算法的代码也称作是A-Start。提到A-Star算法，那一定包含我们在上面提到的这些元素，尤其是"open list"、"closed list"以及F、G、H的评分机制。当然还有许多其他的路径搜索算法，但它们都不是A-Star，A-Star的算法性能总体上来说更为优秀，在本文末给出的一片参考文章中，Bryan Stout先生讨论了很多路径寻找的算法的原理以及它们的优缺点。其实这些算法无孰优孰劣之分，都有其适应的场景，所以你在应用相应的算法之前必须搞清楚你的应用场景。好啦，回到正文......
算法实现的注意事项
现在你已经弄清楚了算法的基本原理，但是在算法实现的过程中还有一些需要注意的点。下面这些观点虽然是针对C++和Blitz Basic的，但对于其他程序设计语言我想也同样适用。
1.避免碰撞
如果你仔细看过我的代码就会发现，屏幕上的其他单元都是被忽略掉的，这些单元之间可相互穿行。是否考虑这些单元取决与你的游戏设计。如果你打算在算法中考虑这些单元并让他们相互移动，那么我建议你只考虑在计算路径时已停止或与寻路单元相邻的单位，把它们代表的当前位置视为不可达。对于正在移动的相邻单元，你可以通过惩罚位于其各自路径上的节点来阻止冲突，从而促使寻路单元找到备用路径。
如果你选择考虑那些移动着非相邻单元，那么需要一个方法来预测在给定时间点该单元的位置，这样才能准确避开它。否则你可能得到的是一条为了避开一些实际并不存在的单元而形成的弯弯曲曲的路径。
当然了，你还需要碰撞检测代码，因为无论当前计算出的路径多么优质，它都是会随着时间改变的。当一个单元发生碰撞时，就会重新计算路径，如果另一个单元正在移动而不是正面碰撞，则在继续当前路径之前等待另一个单元走开。
上面这些建议也许已经足够你开始A-Star之旅了，如果你想了解更多，下面这些链接倒是很有用哦。
- 自主导航：Craig Reynold's在自主导航上的工作与路径搜索有所不同，但是也可集成到路径搜索中以使单元移动和障碍规避方面的内容更加完善；
- 计算机游戏中的转向长短：这是一片十分有意思的关于导航和路径搜索的文章，PDF格式。
- 协调单位运动：这篇文章的前面两部分第一部分是由Age of Empires设计师Dava Pottinger撰写的关于运动的形成和群体运动的内容；
-
协调单位运动-续：Dava Pottinger的第二部分内容。
2.可变区域耗费
在这篇文章以及我提供的代码中，区域被分为两大类---可达区域和不可达区域。但是如果如果有一种区域可达但是需要更高的移动耗费该如何处理呢？比如沼泽、山丘、地牢中的台阶等等，我们有很多这样的例子。同样的也存在一些区域可达但是移动耗费更低的区域，比如开阔地。
这个问题还是比较好处理的，在计算G值时把这些额外的耗费也考虑进去。在我们之前讨论的A-Star算法中，区域被分为可达和不可达两类，A-Star将会找出最短、最直接的路径。但是在区域耗费可变的情况下，最低耗费的路径可能意味着更长的距离，比如说我们选择绕过沼泽区域而不是直接坐船通过。
还需要考虑的一个比较有趣的点就是"影响地图"，跟上面讨论到的可变区域耗费类似，我们可以创建一个额外的点体系运用到人工智能路径中。设想一下，你有一张地图，其中存在一片难以同行的山区。每次我们的计算机在送角色通过这片区域时都十分“费劲”。因此你可以创建一个“影响地图”，对经过“屠杀区”的网格赋予响应的惩罚因子。这样就会促使电脑选择更为安全的区域通行，这样就可避免往一些危险的地方输送军队，因为仅考虑了路径最短二忽视了安全因素。
另外一个需要加惩罚因子的就是移动单元附近的网格。A-Star算法的一个不足之处在于，当一组单元都在寻找到达相近位置的路径时可能会产生大量的交叉覆盖区域，因为会有多个网格选择了相近的路径到达目的地。对已经被其他起始网格占据的网格添加惩罚因子可保证各条线路的独立性并减少碰撞。但不可以简单把这些网格视为不可达区域，因为我们还是希望能在这有限的区域内尽可能开辟更多的路径。当然了，对于路径周围的网格我们也应施与一定的惩罚力度，但并不是所有道路都这样，否则你就会得到一条为了闪避这些网格二形成的奇奇怪怪的路径。道路所处的当前网格和即将通过的网格也要施以惩罚因子，但并不包括已经通过的网格区域。
3.未知区域的处理
你有没有玩过这种电脑游戏，电脑总是很清楚该选择哪条道路，即使你面对的是一片未知的地图区域。在游戏中看起来这似乎是不可实现的，但实际上这个问题很容易解决。
问题的答案就是为每个玩家建立一个"已知可通行区"这样一个数组来记录玩家已经达到过的区域。使用这种方法，移动网格最终会走投无路并作出一些类似的错误选择，知道它们清楚的了解到路径周围的情况。一旦地图都被玩家“勘探”过以后，那么正常的路径查找也就不是问题了。
4.道路平滑
尽管A-Star算法可以搜索出历程最短、耗费最低的路径，但却没有保证所给路径是最平滑的。看看前面的插图7就会发现，路径第一步是向右下方迈出的，还有没有什么其他选择让道路看起来更加平滑呢，如果你想深入了解，请参考这篇文章如何获取更加真实的路径。
5.非正方形网格搜索区
在本文的例子中，
......未完待续
