A*寻路（一） 顽皮猫详解A*算法的工作原理
最近在学习U3D人工智能的A*寻路，相信只要是对游戏开发有所了解或者对算法有一定研究的同学，一定都听说过A*算法。那么A*算法究竟是什么原理能，下面我来进行详细的解答。
在讲解A*之前，我们先来了解一下，A*算法是要建立在一个“地图”上的，这个所谓的“图”主要分为3类：1.基于单元的导航图 2.可视点导航图 3.导航网格
单元的导航图简单的说，就像是纱窗一样，由一些形状一样的规整的图形组成的图，这些图形一般是正方形或者六边形，例如下面的图形：
其他两种图由于和我这篇讲的不相关，我就不展开了，感兴趣的同学可以自己查资料。
我们接下来要讲解的A*算法就是建立在此单元导航图上的。
A*算法是为了寻找从起点到终点的最短路径，并且有障碍物的时候会避开障碍物。为了达到此目的，我们必须要有三个参数：1.记录起点到当前位置的距离 2.当前位置到终点的最小距离 3.从起点开始经过此节点，并且加上从当前节点到达终点的最小距离（听上去有点拗口，不过意思很简单，就是 从起点开始，经过此节点，到达终点）
这里我们分别用：
g表示从起点出发，到达当前位置的距离。
h表示从当前节点出发到达终点的估计最小距离。（注意这里的h一般是通过某种算法得到的估计值，不一定准确，但是可以作为A*算法的参考）
f表示 g+h
当然，我们还需要一个记录当前节点是从何处走来的，即：当前节点的父节点parent。这下，计算A*的数据结构就出来了，每个节点包括以上4个属性,代码表示如下:
struct StartNode
{
float g=0;
float h=估算当前与终点的距离;
float f=g+h;
StartNode parent =null;
}
在上面的单元导航图中，每一个格子周围有8个相邻的格子，每次移动的时候，只能移动到这8个相邻的格子上面。（这里说明一下，格子分的越多，寻找的路径为好（越短），但是寻路的时间也越长）
A*算法还需要用到两张表：1.Open表由待考察的节点组成。 2.Closed表由已经考察过的节点组成。（以考察过：表示已经检查过所有与它相邻的节点的f,g,h值，并把他们放入Open表以待考察，那么，这个中间的节点就是以考察过的，此时放入Closed表）
在介绍完了数据结构和算法所需要的表后，我们来看看A*算法的具体实现步骤：
①.开始时，Closed表为空，Open表里面只有我们的起点。
②.从起点开始，检查它相邻的8个节点，把这8个节点加入到Open表中来，计算他们的f,g,h，并且记录它们这8个节点的父节点为起点。
③.之后每次迭代的时候，将Open表中的f值最小的节点取出来进行检查，若这个f最小的节点不是终点，则检查它相邻的8个节点，继续下面的操作：1.如果相邻节点不再Open或者Closed表中，则将它加入到Open表中。 2.如果已经在Open表中，此时若新的距离（由它父节点计算得到的距离，后面例子会讲到）小于之前计算得到的距离，则更新它。 3.如果它已经在Closed表中，检查它的新距离（由它父节点计算得到的距离）是否小于上次计算得到的值。如果小于，则将此节点从closed表中移出到Open表中，否则忽略。
重复上面的步骤，直到到达终点。如果到达终点之前，Open表已经空了，则表示起点到终点没有可达到的路径。
如下图，我们假设起点的位置是（6,c），终点在（2，H），起点的f,g,h分别如图所示。黄色表示此节点在Open表中。Closed表中的节点我们用红色表示。
最开始Closed表为空，Open表内只有起点：由于起点自己就在起点的位置，所以g=0；h的计算，我们假设每次只能上下左右移动，这样计算得到到达终点需要9步（或者用其他算法也可以，但我们这里是这样算的），f=0+9=9；
然后，我们将起点周围的8个节点都加到Open表中，并且计算这8个节点的f,g,h的值。同时，记录它们的父节点，结果如下图所示：
8个相邻节点中，上下左右的g=1，因为走一步单位是1，左上、左下、右上、右下这四个节点的g=1.41,即为2开根号(当然，我们不想用这种算法也可以，我们也可以认为g是2，这样相应的f值也要变)，蓝色箭头是记录了父节点的指针。
接下来，由于起点已经检测完毕，所以我们将起点至于Closed表中，同时寻找Open表中，f值最小的节点。此时，我们发现这个f最小的节点是（5，D）,f=8.41。
我们就已（5，D）进行第二轮循环，我们为了讲解如何避开障碍物，我们现在来加一个灰色的障碍物：此时表已成为下图的样子：
我们以（5，D）为中心，再次对他的8个相邻的节点进行循环操作（5，D）的相邻8个节点放入open表，计算他们的f,g,h，如下表:
这里我们写了左上、上、右上、右、右下这5个节点的值，对于下，左下，左这3个节点的值我们没有更新，因为 “从起点到（5,D），再从（5，D）到这四个节点的距离大于 直接从起点到这四个节点”，所以对此我们不更新它们4个的f,g,h值。我们来看看（4，C）这个节点，它是由（5，D）得来的，其g的值是（5，D）的g再加上从（5，D）到此节点的距离的和，即1.41+1.41=2.82；
下面的步骤就是重复上面的循环，直到：1.终点放入Open； 2.Open表空了，还未到达终点，返回不可达；
下面是循环步骤：（好难画啊！！！）
此时（4,E）是open表里面f最小得节点，周围的8个节点进行循环操作，所以得到如下的图：
下面（4,E）已经检查过，放入closed,继续寻找f最小的节点，此时是（4，F）,但是对（4，F）进行检测后，它8个相邻的节点的数据无需改变，得到下图：
由于没有到达终点，所以我们继续找f最小的，找到（4，D）和（5，E）这两个节点，谁先谁后没关系，具体根据代码的遍历来。我们就先以(5,E)这个节点来看，注意，此时（5，F）这个节点的g值更小了，所以我们更新这个节点，得到下图：
（画的好累啊！）这里我们再来看f最小的，先看（5，F），可以很清楚知道，8个相邻节点不变。将（5，F）放入closed表。
继续来看（4，D）节点。计算8个相邻节点后，得到下图：
也就改变了（3，c）这一个节点，而且这个改变一看就知道并没有什么卵用，为什么这么说，我们画这个图的时候，要有一个全局意识，就上图而言，当我们要从起点到达（3，C）这个节点的时候，最短的路线肯定是从起点直接向上就可以了 ，而不需要经过（4，D）这个节点，所以接下来的循环，肯定会更新这个（3，C）节点的值。（提醒一下，在关注f,g,h值的同时，别忘记蓝色的箭头才是标识着我们行走的路线！）
那我们继续，此时f最小是（5，C）和（6，D）这两个节点。我们就直接看（5，C）吧！（笑哭，实在太难画了，如果先看（6，D）的话，后面也会找到（5，c）的），所以检查（5，c）的8个相邻节点得到下图：
此时（4，C）最小，继续得到下图：
此时（3，C）更新了，并且f最小，我们继续：
此时（2，D）的f最小，我们继续：（注意了，这个判断的过程可以更具我们的算法改变，比如我很如果非要认为（3，D）这里挡住了，无法直接到（2，D），那么我们可以不将（2，D）放入open表中即可）
go on:
快到终点了，有木有很激动！！！
继续：
最后这里，我们来检查（2，G）这个节点的相邻节点：
在（2，G）的相邻节点里面，我们搜索到了终点！！！多么令人激动啊！！！（终于用ps画完了！！！）
这时，我们就根据我们一路走来的路径追溯到起点就可以了！
如下图：
这就是A*算法的原理，主要就是2个表和3个参数，具体的判断是否可达到可以视情况而变化！
如果这篇文章让你对于A*有了理解，或者觉得博主画图辛苦了，那么请不要吝啬你们的赞哦！！（快赞一个给我安慰！）
后面我还会写一篇关于A*算法的运用，记得关注博主哟！博主会慢慢成长，及时分享自己的经验和知识。