A*算法实现静态地图求最短路径 a*算法求最短路径原理

前段时间用C++简单的写了一个走迷宫的小游戏，但是一直没有实现求最短路径的算法，今天抽空看了一下A*算法，就简单的实现了一下，下面写一些代码的思路和实现的步骤。

迷宫demo

A*算法；A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。

其实总结就是根据每个节点的权值选最优，那么怎么计算权值呢？

权值 ：F = G + H；

移动距离：G(地图中水平垂直移动就+1，以此类推)

曼哈顿距离F：就是到终点的水平距离和垂直距离的和

计算曼哈顿距离

计算的权值怎么处理这些节点信息呢？

在A*算法中，设置了两个列表，一个是开启列表另一个是关闭列表，将遍历当前节点周围所有节点(计算F值)，并加入开启列表中，然后将当前节点放入关闭列表中。

怎么维护开启列表中的结点？

使用优先队列，C++中提供了priority_queue直接使用，要注意重载操作符

结点的定义

到此基本的思路有一个大概了，剩下的就是一些边边角角的处理，比如障碍的判断，是否超出范围以及对每一个访问过的结点visited数组的设置等。

下面有一张图体现A*算法搜索的方法（1为通路，起点(0,1) 终点(9, 19)）

A*搜索路径

可以发现每一次都会搜索附近的8个结点(忽略已标记的结点)

有需要源码的小伙伴可以在下方留下邮箱，有错误的欢迎指正交流，谢谢~