A* 搜寻算法，俗称 A 星算法，作为启发式搜索算法中的一种，这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。

A*算法

在 A* 算法中，使用了两个状态表，分别称为 Open 表和 Closed 表。Open 表由待考察的节点组成，Closed 表由已经考察过的节点组成。

公式表示为： F(n) = G(n) + H(n)
F(n) 是从初始状态经由状态 n 到目标状态的代价估计
G(n) 是在状态空间中从初始状态到状态 n 的实际代价（通常相邻节点上下左右的 G 值为 10，斜线的 G 值为 14）
H(n) 是从状态 n 到目标状态的最佳路径的估计代价，估算代价通常采用哈曼顿距离

H(n) = D * (abs ( n.x – goal.x ) + abs ( n.y – goal.y ) ) D 是移动到相邻位置的最小代价值

开始时，Closed 表为空，Open 表仅包括起始节点，每次迭代中，A* 算法将 Open 表中具有最小代价的节点进行检查，如果这个节点不是目标节点，那么考虑该节点的所有 8 个相邻节点。对于每个相邻节点按下列规则处理；

1. 如果相邻节点既不在 Open 表中，又不在 Closed 表中，则将它加入 Open 表中；
2. 如果相邻节点已经在 Open 表中，并且新的路径具有更低的代价值，则更新它的代价值跟父节点；
3. 如果相邻节点已经在 Closed 表中，那么需要检查新的路径是否具有更低的代价值，如果是，那么将它从 Closed 表中移出，加入到 Open 表中并且更新节点信息，否则忽略。

重复上述步骤，直到到达目标节点。如果在到达目标之前，Open 表就已经变空，则意味着在起始位置和目标位置之间没有可达的路径。

a*搜索算法动态演示分析

A*算法优化

1. Open 表后期很大，可以选择有参照性的数据结构，如优先队列（大/小根堆）的方式。
2. Close 表使用二维表（二维数组），由于障碍物列表和 Close 表仅用来检测是否能通过，所以我们可以使用 bool 二维表来存放。有某个点(Xa, Yb)，可以通过 if(barrierList[Xa][Yb] && closeList[Xa][Yb]) 来判断。因为二维表用下标访问，效率很高，但是耗空间比较多。
3. 深度限制，有时要搜的路径非常长，利用 A* 算法搜一次付出的代价很高，那么为了保证每次搜索不会超过一定代价，可以设置深度限制，每搜一次则深度 +1，搜到一定深度限制还没搜到终点，则返还失败值。
4. 导航图辅助寻路，我们可以预先通过给每个房子的门口设置一个导航点，如果起点或终点在某个房子里，那么必定经过该房子对应的导航点，那么可以从起点搜到第一个导航点，然后往下搜索到每个导航点，最后一个导航点搜到终点。相比直接从起点搜索到终点，这种做法，减少了大量不必要开启搜索的点，效率明显的高。即长寻路变成短寻路。