A星算法是一种启发式的搜索方法,通过一个路径评估函数,来动态确定最佳路径。这点和广度搜索不同。
基本思想是有2个列表,open和close,
open列表里面的节点表示待搜索周围点的节点,close列表里面记录着不需要搜索的节点。
启发式函数f=g+h;
f表示该路径的代价,g表示起点到搜索的点的该条路径的实际值,h表示该搜索的点到终点的估计值。h的估计值越接近当前点到终点的最短路径的实际值那么A星搜索出来的路径就越接近实际的最短路径,从这点来看A星是时间和精度的一个权衡改进的广度搜索算法。h值始终为0的话,那退化为广度搜索了(没有了估值,f的计算都是实际值,因此变为了暴力的广度搜索)。
进过以下测试,大约牺牲了10%的精度换来了10倍的速度。
上图为h值为0,退化为广度搜索。
上图为曼哈顿估值法(即横向和纵向距离之和),
上图为距离估值法。
上图为随机化地图遮挡的结果,
每次搜索都从open表中找出代价最小的节点进行搜索,在搜索当前点时,如果周围点已经存在于open列表中,那么就要重新计算f和g值,表示进过当前点到达 周围点会不会更近,重新计算后open列表将会重新排序,下个轮回再次从f值最小的开始广度搜索。
下篇主要是优化性能 AStar寻路2-性能优化