游戏寻路算法基础篇 A*算法入门

在游戏中经常需要进行寻路操作，比如点击目标点，主角就自动从当前位置走向目标点，这件事情对人来说是非常简单的，但是计算机想完成这个问题却要花费一番周折！下面就让我看看要怎么解决问题吧。

                                                  

相信大家最常想到的就是两点之间线段最短这条定理，不过只在起点和终点可视可达的情况下，可以这样做。但是如上图中这样又应该怎么办呢？

相信大家也会有办法，就是以起点为中心画圆，一层一层向外扩展，直到某一层拓展到目标位置，那么这段拓展的线就是最短路径，但是这样的复杂度未免太大了（其实这种方法就是Dijkstra算法）。如下

                                                

为了解决算法过于复杂的问题，我们换一种思路，只对面向节点的方向进行探索，如下图

                                                

像这样只想一个方向前进，不去探索其他方向可以极大的节省空间，对于绝大多数的情况都是好用的但是如果起点和终点之间存在障碍

                                                                  

像这样，那么上述算法是不是不好用了呢，其实不然，算法还是会绕开墙过去（本算法被称为最佳优先搜索Best First Search 是dfs的一种）。

不过如果二者之间的障碍物是一个凹字形的。又会怎么样？

                                              

BFS算法会像Dijkstra算法一样，进行大面积的搜索，才能找到目标位置，甚至很多时候，会陷入死路出现无法找到无标位置的情况。不过我们要是将第一种和第二种结合起来？会怎么样

 

其实二者的结合正是A*算法即 启发式的最短路径算法 ！！！

将Dijkstra融合进来就是全局搜索方式，而BFS带来了启发式搜索功能。将二者数学化：
Dijkstra算法可以变成A*中的代价计算函数 G(n) 表示从起点到n点需要的代价，相当于记录整条路线，寻找最短路径。

BFS算法可以变成A*中的启发式搜索函数H(n)表示从n点到终点需要的估算代价（因为这个代价很少能被直接精确的计算出来）。

因此H（n）函数在整个算法中就显得尤为重要。

最后将G（n）和H（n）相加得到每个节点的加权值F（n）

在从一个点开始搜索的时候，对他周围的点都计算F（n），选出F（n）最小值的点，将当前节点加入到closeList，移动到选出来最小的节点上，重复之前的计算。

再加上扩大范围的回溯算法，可以很好的找到目标位置。