[笔记]A*寻路算法初探

写在开始之前

最近突然对各路游戏的寻路算法很感兴趣，于是去学习了下游戏里的AI们是如何寻路的。网上相关内容很多，但同时有些说法也不一，制作自己的A* 算法时也有因不同的说法而困惑。整理多方资料并自己实践之后，以下是我对寻路算法，尤其是A* 算法的一些自己的总结。以下为自己的思考与想法，可能不准确之处，请指正。
我本次的模拟比较简单，下面简述一下模拟环境：

1. 地图是棋盘式的格子地图；
2. 各个点没有权值，或者说权值为1；
3. 只能上下左右走，不支持斜着走；
4. 未考虑终点被包住而到达不了的情况，发生此类情况时，算法会遍历所有可到达点无果后才证明目标无法到达。

虽然模拟的比较简单，但是足以学习、说明问题。为了使算法更形象可视化，我给算法的过程做了小动画。成品存在了我的Github里：https://github.com/XieNaoban/Pathfinding 这里代码就不贴了。使用的java编写。由于是初学java，所以代码写的*一样不要介意（讲道理我现在自己也看不下去了。不过做出来的GUI效果还挺满意。）另外一开始对这个寻路理解的比较混乱，体系没有建全，所以不同算法所在的函数也很不一样，函数分类也不合理（然而不高兴改了）。

寻路的基本思路

首先总结一下寻路的最常见的两个思路，遍历与贪心算法。

遍历：只考虑起点

这里说的遍历其实用的是Dijkstra算法或BFS，也就从起点开始一扩散出去寻找最短路径。也就是遍历距离起点最短距离为1、2、3……n-1、n的点。对于地形复杂比如有山有沼泽（即有权值）的地图（图），使用Dijkstra算法，用优先队列存储遍历到地图的每一个点时的权值和。对于一张平滑的也就是无权值（权值相同）的地图，Dijkstra的表现与BFS相同，即只需退化使用队列进行BFS遍历即可，无需使用Dijkstra算法。这里我的模拟的地图没有权值，直接使用了BFS。

黄色代表被搜索过，蓝色代表搜索完成后找到的路径（在这里显然也是最短路径）。格子中的值为从起点到本格子的最短距离。由图可知算法从起点向周围扩散，直到扩散到终点。
结论是，BFS（或带权图中用的Dijkstra）肯定找到最短路径，但是问题在于，它太耗时了，访问的点（黄色格子）太多了。想想就知道很多点完全没有必要遍历。
造成这一现象的原因是，这个算法只考虑了起点，一直找距离起点最短的路直到遇到终点。

贪心：只想着终点

试图不遍历，直接找到终点去，那基本就是使用贪心算法了吧。
以上的启发式函数仅仅考虑了起点，因而导致算法无目的地向四周扩散寻找。那既然是使用贪心算法，每次寻找目前为之的最优解，那么这次只要考虑终点在哪里就行了，一路向终点走，起点不用考虑。这使得算法疯狂试图向终点靠近。

结果发现无障碍情况下效果杠杠的，没有一块多余的白色。但是如果有障碍呢？

虽然一格都没有多搜索，但是游戏里AI要是这样走路那玩家肯定吃不消。而且还有一个问题，万一走到了死胡同里，算法就会判定无法到达终点，而事实却是是算法自己钻了牛角尖。所以必须允许算法倒退，从死胡同里后退一步或多步，换条路子走。可以使用栈即可实现。有时会发现换了路之后反而更快地到达了之前到过的一个点，于是有些点重复搜索了，重复搜索的话很有可能比无脑遍历都不划算。于是我关闭了重复搜索，效果好多了。

可以看到算法产生了很多失败的搜索（黄格子）（都是被自己走过的路堵死的。。。创战记既视感）但是搜索的路比遍历少多了，但是说起来，允许倒退重新寻路，说到底这也还算是是进行遍历了。。。有时候还不及遍历。（其实我搜索完后画的路径不是完全根据算法来的，算法找的路还要更绕，我很多地方已经根据黄格子的梯度抄近路了。）
同时贪心算法只考虑了终点，永远只向着终点方向走，不考虑目前离起点已经走了多少格了。

A*算法

A* 用的也是Dijkstra。每次找出当前期望值最高的点（即最可能最快速度通往终点的点），一步步搜索过去。Wiki上也说了，这是对Dijkstra’s Algorithm 的扩展，因为它使用了性能更好的启发式引导其搜索。

疑问：“最短”路径还是“最合理”路径

这是个令我困惑的问题。翻了些知乎或博客等，竟然众说纷纭。有人说“不是。因为‘启发’是不精确的。”。也有人说“尽管A*基于无法保证最佳解的启发式方法，A*却能保证找到一条最短路径。”这就很尴尬了。
看了这么多资料以及加上我以往的玩游戏经验，我认为A*只是个比较宽的概念，它可以找到最佳路径，也可以找的只是合理路径。既然用了启发，那么它很可能找的不是“最短”而只是说根据这个启发找到的最“合理”路径。但是也可能你的启发式函数做的很好，找到的最合理路径就是最佳路径（就比如文章开头的说的遍历，下面说）。关键就在于你给他的“启发”是怎么样的。 小时候玩红警还是什么游戏时就遇到过单位走的路不是最短路径。

核心：寻找启发式函数h(n)

A*既然用了Dijkstra，那它的基本过程就是：从优先队列里拉出期望最高的n点（在我的算法里表示为h(n)值最低），标记，并把它周围的未知点放进优先队列。所以关键就是这个h(n)。
h(n)怎么找？其实最简单的，上面讲的遍历说起来也是h(n)的一种。从起点进行遍历的
h(n) = n.t （t为距离起点的距离），也就是说而对距离近的优先搜索。而这个算法其实就是最短路径的算法，这里“最合理路径”就是“最短路径”。
而对于上面讲的贪心算法，他的引导函数可以看作是
h(n) = max(abs(n.x - end.x), abs(n.y - end.y)) ，哪边离终点近就走哪里。之前这是用贪心实现的，但如果用做A*的h(n)实现呢？

效果很好，不过这只能用在仅支持上下左右行走的场景，找的路也比较“合理”（虽然明显不是最短路径）。现在只考虑还有什么可以试试呢？
想到起点终点都要考虑进去，首先想到了这个：
h(n) = sqrt((n.x - end.x) ^ 2 + (n.y - end.y) ^ 2) + sqrt((n.x - start.x) ^ 2 + (n.y - end.y) ^ 2) 。即点n到起始点的距离加上n到终点的距离。也就是说，距离起点终点所在的直线越近，h(n)就越低。

效果还不错。但是问题在于sqrt计算成本太高。即时策略类游戏的话这不好。而且对于这次只有直着走的模拟有些大材小用了。而且还是有些部分是不需要搜索的。

还有几个可用的函数，一个和之前的h(n) = max(abs(n.x - end.x), abs(n.y - end.y)) 比较像：
h(n) = abs(x - end.x) + abs(y-end.y) 找出x、y轴方向哪边离终点远，哪边远倾向于走哪边。还有一个和sqrt那个比较像：
h = abs((x - end.x) * (start.y-end.y) - (start.x-end.x) * (y-end.y)) ，倾向与走与起点终点所在直线方向的平行线，这个个人觉得不错，比sqrt那个计算少，而且在棋盘式地图里效果也好。但是它也有一个问题：

他会搜索反向于终点的方向。所以可以考虑用多个函数组合：
h = abs((x - end.x) * (start.y-end.y) - (start.x-end.x) * (y-end.y)) + (abs(x - end.x) + abs(y-end.y))*500;
效果比单一使用好很多。虽然实际效果其实不比h(n) = max(abs(n.x - end.x), abs(n.y - end.y)) 强，但也给我们提供一个寻找h(n)的思路，将来可以运用到任意方向的地图上。其中里面不同函数还有权重，比如第二个函数乘以了500。权重可以按照实战效果来定。

不过你可能也根据我放的截图发现了，这些算法都倾向于走起点与终点所在直线之上。即每当越过一个障碍物，就试图重新靠近起点终点所在连线上。尽管连线上或许还有障碍物。这也是我应该改进的地方。

总结：“精度”还是“速度”

显然，复杂些的启发式函数或是会造成更多搜索的方法往往能取得更好的效果，但是同时速度也更慢。因此如何选择将是本算法的一道难题。对于本次模拟的图，甚至BFS的表现都非常良好，但对于很大的地图、有很多NPC的游戏，就得权衡运行速度与寻路精度了。只要运行结果看似合理不会引起玩家破口大骂，A*算法的目的也算是达到了。