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

RudolphHamm 3年前

来自: 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引擎。