游戏算法实践——A星寻路

来自： https://segmentfault.com/a/1190000004503119

先展示效果图：

如图中亮绿色点为起点，蓝点为终点，白色为墙体不可行走。黄色点区域为被试探到的位置，绿色的路径为最后的最短路径。其中这里移动规则是只能上下左右移动。

关于A星算法，大家可以去google。这里展一下本项目A星算法的部分（思路）：

+ 创建一个open集合，一个close集合  + 把起点加入close集合，并把它设为Current节点  + 重复如下过程：    + 查找Current节点的相邻节点（上下左右）    + 如果节点不是墙也不在close集合并且也不在open集合的，计算G值H值，设置Parent为Current节点，然后加入到open集合    + 如果已经加入了open集合，那么查找一下是不是从Current节点到这个节点G值更小，如果是那么改变这个节点的G值为更小值，Parent指针指向Current节点    + 如果节点是终点，那么跳出循环    + 遍历open集合，查找F值最小的节点（F=G+H）    + 如果找到了，把这个节点移到close集合    + 如果没有找到，并且open表又为空了，那么表示找不到路径了，跳出循环  + 循环后如果没找不到路径，那么结束  + 如果找到路径，那么从终点开始，在close表中通过parent指针来寻找路径，直到起点

大家可以通过github来参考具体代码。

工程实现了编辑地图，保存地图（为下次打开使用）功能。工程使用cocos2d-x3.x引擎。