引言

。

A算法是一种启发式的搜索算法，它是基于深度优先算法和广度优先算法的一种融合算法，按照一定规则确定如何选取下一个节点。在介绍A算法之前，需要了解一下什么是启发式搜索算法，深度优先算法以及广度优先算法。

启发式搜索算法

启发式搜索算法指的是，从起点出发，先寻找与起点相邻的栅格，判断它是否是前往终点最好的位置，基于这个栅格再往外向与其相邻的栅格扩展，找到一个当前时刻最好的位置，通过这样一步一步逼近终点，减少了盲目的搜索，提高了搜索的可行性和搜索效率。

深度优先算法

深度优先算法的思想是，搜索算法从起点开始搜索（初始状态下待搜索区域的节点都未被访问），将起点周围所有邻点进行比较，选择其中距离终点最近的节点进行存储，然后再以该邻点为基础对比其周围未被访问的所有邻点，仍然选择距离终点最近的邻点进行存储。

若访问完所有节点仍未到达终点则视为搜索失败，搜索成功所存储的节点连接形成的路径即为起点到终点的路径

广度优先算法

广度优先算法的原理是，从起点出发依次访问与它相连接的邻点，访问完毕后再从这些邻点出发访问邻点的邻点，但是要保证先被访问的邻点的邻点要比后被访问的邻点的邻点先访问，直到图中所有已被访问的节点的邻点都能被访问到。如果此时图中还有未被访问的节点，则需要选取一个未被访问的节点作为起点继续搜索访问，直到图中所有的节点都能被访问到。

A*算法

基于深度优先算法和广度优先算法的优缺点，A*算法基于启发函数构建了代价函数，既考虑了新节点距离起点的代价，又考虑了新节点距离目标点的代价。

地图

我们把要搜寻的区域划分成了正方形的格子。这是寻路的第一步，简化搜索区域，这个方法把我们的搜索区域简化为了 2 维数组。数组的每一项代表一个格子，它的状态就是可走和不可走。蓝色是墙壁，为不可走状态。通过计算出从绿色格子到红色格子需要走过哪些方格，就找到了路径。一旦路径找到了，人物便从一个方格的中心移动到另一个方格的中心，直至到达目的地。

寻路步骤

1. 先将起点放入开启列表（即OPEN表，存放的是未访问的节点）
2. 寻找起点周围可以到达的节点，将它们放入开启列表，并将它们的父节点设置为起点
3. 从开启列表中删除起点，将它放入关闭列表（即CLOSE表，存放的是已经访问过的节点）

图中浅绿色描边的方块表示已经加入 “开启列表” 等待检查。淡蓝色描边的起点表示已经放入 “关闭列表” ,它不需要再执行检查.

4. 对开启列表中的节点进行路径评分，从而给出一个从小到大的排列。

路径评分需要一个代价函数判断出该节点是否为OPEN表中代价最小的节点。
通常采用如下代价函数评估路径
$F=G+H$,其中$G$为当前节点到起点的路径代价，$H$为当前节点到目标点的预估路径代价，$F$为两者之和

如上图所示，假设横向移动一个格子的耗费为10, 为了便于计算, 沿斜方向移动一个格子耗费是14，绿色起点右边的节点$G=10，H=30$,代表从起点到达这个节点的路径代价为$10$，从这个节点到目标点的路径代价为$30$（由于H是预估代价，而不是实际代价，这里可以忽视墙壁的影响）

5. 将F值最小的节点从OPEN表中删除，并将其添加到CLOSE表中
6. 通过当前节点搜索当前节点邻近的节点，如果当前节点所扩展的节点不在OPEN表中，则将这些节点添加进OPEN表中
7. 之后对添加到 OPEN 表中的结点进行排序，按照上述过程选出 F 值最小的结点，选出该结点作为当前结点，并扩展其邻近结点。
8. 如果所扩展的结点在 OPEN 表中，以当前结点为父结点，重新计算 G 值，并和之前的 G 值进行比较，从而找出最小的 G 值进行更新，并重新计算 F 值，再次进行排列。按照以上步骤循环，直至将目标点添加到 OPEN 表中，此时搜索算法结束。根据父结点一直找到起点，就得到搜索到的最佳路径。

如此，我们再来看下面的例子

在我们最初的 9 个方格中，还有 8 个在OPEN表中，起点被放入了CLOSE表中。在这些方格中，起点右边的格子的 F 值 40 最小，设这个格子为A，因此我们选择A作为下一个要处理的方格。A的外框用蓝线打亮。我们将A从OPEN表中删除，将其添加进CLOSE表。A右边上下三个都是墙, 所以忽略它们. 它左边是起点, 已经加入到CLOSE表中了, 也可以忽略. 所以它周围的候选方块就只剩下 4 个，设A下方的方块为B，设A上方的方块为C。B目前的G值是14, 如果通过A到达它的话, G值将会是20, 这比14要大，因此这不是最优的路径。直接从起点沿对角线移动到B比先右移到A再下移到B要好。

我们继续从OPEN表中找出F值最小的方格，B和C的F值都为54，因此我们选择哪一个都是可以的。这里我们选择B，将其边框用蓝线打亮。

B右边以及右上方的都是墙, 所以忽略,而B右下方的方格没有被添加进OPEN表中，因为如果不穿越墙角的话，你不能直接从B移动到那个方格。你需要先往下走，然后再移动到那个方格，这样来绕过墙角。（具体规则看程序是否允许设置这样走），再将新添加的方格的父节点设置成B，除了起点和A之外，B只剩下三个相邻的方格，而B下方的两个方格是新添加进来的，如此还剩下B左方的方格，检查如果用新的路径 (就是经过B的路径) 到达它的话, G值是否会更低一些, 如果新的G值更低, 那就把它的父节点改为目前选中的方格B, 然后重新计算它的 F 值和 G 值 (H 值不需要重新计算, 因为对于每个方块, H 值是不变的). 如果新的 G 值比较高, 就说明经过B再到达它不是一个明智的选择, 因为它需要更远的路

不断重复这个过程，直到把终点也加入到了OPEN表中，就说明路径搜索成功，此时如下图所示

注意，在起点下面 2 格的方格的父亲已经与前面不同了。之前它的 G 值是 28 并且指向它右上方的方格。现在它的 G 值为 20 ，并且指向它正上方的方格。这在寻路过程中的某处发生，使用新路径时 G 值经过检查并且变得更低，因此父节点被重新设置， G 和 F 值被重新计算。

找回路径

我们成功搜索到从起点到终点的最短路径之后就要找回路径，从终点开始，按着箭头向父节点移动，这样就回到了起点，这就是最终的路径。