A* 算法（A星算法）是一种启发式搜索方法，通过路径评估函数动态确定最佳路径，与暴力广度搜索不同。

基本思想

算法维护两个列表：open 列表和 close 列表。open 列表存放待搜索周围节点的节点，close 列表记录不需要继续搜索的节点。

启发式函数定义为：

f = g + h
  • f：该路径的总代价
  • g：从起点到当前节点的实际路径代价
  • h：从当前节点到终点的估计代价

h 的估计值越接近当前节点到终点的实际最短路径，A* 搜索的结果就越接近真正的最短路径。从这个角度看，A* 是时间与精度之间的权衡——它是对广度搜索的改进。当 h 值始终为 0 时，算法退化为广度搜索（没有估值，f 的计算全部依赖实际值，变成暴力广度搜索）。

性能测试

经过测试，A* 算法大约牺牲了 10% 的精度，换来了约 10 倍的速度提升。

上图为 h 值为 0 时，算法退化为广度搜索的效果。

上图为曼哈顿估值法（即横向距离与纵向距离之和）的效果。

上图为距离估值法的效果。

上图为随机化地图遮挡下的寻路结果。

搜索流程

每次搜索都从 open 列表中取出代价最小的节点进行扩展。搜索当前节点时，若周围节点已存在于 open 列表中，则需要重新计算 f 值和 g 值——判断经过当前节点到达该周围节点是否路径更短。重新计算后 open 列表重新排序，下一轮继续从 f 值最小的节点开始搜索。

下篇主要介绍性能优化：AStar寻路2-性能优化