在前面的文章中，原力君跟大家一起分享了无人车根据地图信息设定导航路线的基本思路，并且最后发现这个问题可以转化为一个经典的问题：带权有向图的最短路径搜索问题。实际工程中，通常选择一种在游戏领域广泛应用的路径搜索算法---A*算法（也叫A星算法）。本文将会用一个简单的路径搜索的例子来解释A*算法的求解过程。
最短路径搜索的前提：
1）有一个地图（有向或者无向的），地图用一个一个的小格子（可以抽象为点）构成，地图中包含障碍物信息（即哪些点是可以通过的，哪些点是不可以通过的）
2）设定起始点、目标点。
3）建立地图上点与点之间的关系，即需要提前设定地图中每个点移动到它周边8个方向的邻居点位置时需要经过的距离、需要消耗的资源、或者是某一个代价值。这个在路径搜索的时候要用到。
4）计算每个地图点到目标点的理想距离，即不考虑障碍物、不可经过的点等，假设地图上所有点都是可以通过的。仅仅利用横向移动或者纵向移动，一直到目标点所经过的距离
我们有个地图格子，格子中有个绿色的起始点（记为A），红色的终止点（记为B），蓝色的障碍物。有人想从A点移动到B点，而且要避开中间的蓝色区域，如下图：
图片来自文献[1]
我们可能一眼就能看出来有很多条路径可以连通A点和B点。但是，如果要找到最短路径，可能需要仔细去数每条路径经过的格子数，最后找到通过格子数最少的那条路径。这种方法实际上非常暴力。这个例子中格子数比较少，这种粗暴的方法是可用的；但是，当格子数变得非常大，比如变成10000*10000个，人眼也无能为力了。
虽然这样做可以找到最短路径，但是消耗的计算资源非常大，而且非常慢。如果什么问题都去遍历一遍，那优化算法就没有存在的意义了。优化算法的意义就在于，用最短的时间、最少的计算资源，结算出最优的结果。
因此，我们需要借助计算机算法来找到最短路径。那么，问题来了：
1）算法不会遍历所有的点
2）算法需要找到最短路径
3）算法需要避开障碍物
A*算法的基本思路就是每次只关注一个点（记为当前点，用C表示），然后根据下面几条做决策：
1）计算或者读取周边的邻居点到目标的理想距离，记为H。H的作用，相当于是告诉算法要一直想着目标在哪里，不要迷失了方向。
2）计算或者读取当前点移动到周边的邻居点经过的距离，记为G。G点的作用是告诉算法，不要觉得当前点距离目标点很近就完事儿了，你也得考虑你从起始点到现在，一共走了多远的距离了。G可以避免算法走弯路。
图片来自文献[2]
3）计算可行路径（当前点-邻居点-目标点）的理想距离，记为F。当前点到邻居点的距离，是确定的，而邻居点到目标点，只能用理想距离来评估。所以，F可以为G和H的加和。
4）找到可以让F最小的那个邻居点，并把这个邻居点作为关注点，记录上一个关注点，将其与当前关注点连接起来（编程时，用指针指向它即可）。选择最小的F，可以在一定程度上保证我们可以找到相对较短的那条路径。但是由于算法的局限性，A*没法保证找到的路径是最短的，只能说在一定程度上是最短的。
5）重复步骤1)到步骤4）的计算过程，直到找到目标点为之。根据所有关注点的连接关系，得到整条最短路径。
再回到例子，假设每个格子的边长是10，则对角线长为14（也可以边长1，则对角线为1.414，小数计算会降低程序运行的速度，所以我们用整数，不影响搜索结果）。
准备工作：
1）准备一个Open表格，用来存放算法已经提取的点（当前点的邻居点，邻居点的邻居点，以此类推）
2）准备一个Close表格，用来存放算法已经关注过的点（如果当前关注点是A，则将A放到Close表中；下一次根据F值移动到A的右边，则将A的右边点放入Close表；以此类推，只要是关注点 C曾经占用过的点，都要放到Close表中；同时，如果放入Close表的点也在Open表中，则将其从Open表中删除）
3）关注过得点用蓝色的框框高亮显示
首先关注起始点A（绿色格子），将A放入Close表。它的周边邻居点一共有8个：左上，上，右上，右，右下，下，左下，左。将这8个点放入到Open表中。
当前点（用C表示）从A移动到上下左右四个方向时，移动距离为10；移动到左上、右上、左下、右下四个方向时，移动距离为14. 因此，可以计算C点在A处时，其8个邻居点的G,H,F值了。将F, G, H分别写在格子的左上角、左下角、右下角，如下图所示。
图片来自[1]
从图中可以看到，绿色格子的右边格子F值最小，因此关注点C移动到A点右边的格子处，并且将A右边的格子点放入Close表中，同时将其从Open表中删除。
查看当前关注点C的邻居点：左上，上，下，左下，共4个点。左边点是起始点，已经在Close表中，右边三个点是墙，所以都忽略掉，不参与计算。C在A的位置时，这4个点在已经在Open表中了，所以没有新点加入Open表中。
根据C的位置，重新计算C的4个可用邻居点的G,H,F值。发现4个点的新G值都比原来的大，所以当前的关注点并不是最好的点。算法不需要更新4个点的F,G,H值。
检查C的4个邻居点，找到F最小的那个点。我们发现上、下两个点的F值是一样的，所以随机选择下面那个点作为新的关注点（这个处理方式，可能会导致最终计算出来的路径不是真正的最短，只是相对较短），并将其放入到Close表中，同时将其从Open表中删除。
图片来自[1]
检查当前关注点C的邻居点：左，左下，下，共3个点。左下和下两个点是新点，需要加入到Open表中。根据C的位置，重新计算C的3个可用邻居点的G,H,F值。检查C的3个邻居点，找到F最小的那个点。我们发现C左边那个点的F值最小，所以将关注点C移动到左边那个点，并将其放入到Close表中。
检查当前关注点C的邻居点：左，左下，下，右下，共3个点。左下是新点，需要加入到Open表中……，就这样迭代执行，用F值最小作为牵引，最后得到下面表格所示的算法执行结果图。
问题来了：最短路径就是蓝色框框代表的格子吗？在起始点哪里，蓝色框框转了一个圈圈，这不是绕远路了吗？
A*算法使用了一个父节点的概念来从这些蓝色框框（也就是Close表所包含的所有框框）中提取最短路径。算法在关注一个点时，其周边邻居点都有一个属性变量，这个变量可以告诉算法它是谁的邻居，或者说它的父节点是谁。
前面说了，G值代表了从起始点到这个点的移动距离。某个邻居点的G值，是根据当前关注点的G值来计算的。某个邻居点，可能是多个关注点的邻居点，所以它的G值可能会被计算很多遍。
哪个关注点能够让这个邻居点的G值最小，这个关注点就是这个邻居点的父节点。这个很现实，假设起始点是个富翁，谁让某个点离富翁最近，谁就是这个点的亲人。真是个唯利是图的点！
重新看这张图，图中用一个圈圈加线条指向来表达父子节点的关系。直线指向谁，谁就是这个格子的父节点。
我们再来看这张图，起始点右下角的点是关注点，它启动了左下和下面两个新点，让他们有了G值（没有启动是他们的G值是无穷大），所以他们就唯利是图，认了当前关注点为父亲，线条都指向关注点。但是，关注点左边的点，也就是起始点下面的点，它的G值比关注点给他的G值要小，所以它不愿意改变父亲，觉得起始点更亲，所以它的父节点是起始点。
以此类推，虽然蓝色框框围着起始点转了一圈，但是算法并没有改变起始点右下角那个格子的父节点。
最后，从红色终止点格子开始，根据指示其父节点的线条指向，就可以回溯到起始点，回溯过程经过的格子点，就是最短路径（见图中红色原点所示）。
好了，到目前为止，A*算法的求解过程已经基本清楚了，主要总结为以下几条：
1）把起始点添加到Close表，将其邻居点加入到Open表。
2）重复以下几个步骤：
2.1 ) 寻找Open表中F值最低的格子，设为关注点C。
2.2) 存放C到Close表；
2.3) 对相邻的8个点，如果它不可通过或者已经在Close表中，略过它。反之， 如果它不在Open表中，把它添加进去。把当前关注点作为这一格的父节点。记录这一格的F,G,和H值；如果它已经在Open表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。
2.4) 满足下列条件是停止搜索：把目标点添加进了Open表，找到了路径；或没有找到目标点，Open表已空了，路径不存在。
3）保存路径。从目标点开始，沿着每一点的父节点移动直到回到起始点。这就是最短路径。
[1] A* Path finding for Beginners. https://www.gamedev.net/articles/programming/artificial-intelligence/a-pathfinding-for-beginners-r2003/
[2] 无人驾驶汽车系统入门（十六）——最短路径搜索之A*算法 . https://blog.csdn.net/AdamShan/article/details/79945175
[3] a*自动寻路算法详解. https://blog.csdn.net/jialeheyeshu/article/details/53105810
[4] 我见过的最容易读懂的 a*算法(A*寻路初探). https://blog.csdn.net/windcao/article/details/1533879