自动寻路里面的说的最多的就是A星寻路了,但是网上找了些博客大家写的有点简略,导致对于刚接触的人来说理解的不够清楚。在这里我将用大量的图片一步一步地列出A星算法的寻路过程。A星算法对于大地图的效率不高,大地图的寻路算法可以尝试用导航网络处理,如果想了解大地图的算法,可以来这里看下http://www.zhihu.com/question/20298134(知乎里面的高票回答)
A*算法原理
- A*算法属于状态空间搜索范畴,一般分为两种策略:盲目搜索策略和启发式搜索策略。前者是数据结构里面讲过的深度优先搜索以及广度优先搜索,后者里面其中的一种就是A*算法。
- 启发式搜索就是在搜索中加入了与问题有关的启发性信息,用以指导搜索朝着最有希望的方向进行,从而加速问题的求解过程并找到最优解。具体到自动寻路可以通俗地这样讲,你从南京到北京要走最短距离,根据北京在南京的北方,我们会朝着南京北方的方向找到北京的最短距离,而不是没有目的的东南西北四个方向找。目的地提供的信息就是,最短路径在北方。下面尽量简化地介绍A*算法,以我的理解。
假设把游戏的地图分成网格状,每个格子代表一步,玩家只能上下左右四个方向移动,绿色方块的是玩家,红色方块是要到达的地点,蓝色方块是障碍。
A*算法里面的估价函数: f(x) = g(x) + h(x),其中f(x)为评估值函数,g(x)为搜索图中的节点深度函数,h(x)为启发式函数(A*算法能否顺利使用,重点是如何表达该函数,表达的函数很多,但该函数必须遵循单调非递减原则)。在这里我们把h(x)设置为当前方块到目标方块的最短方块数(忽略任何障碍),g(x)函数为探索的深度,即从出发方块到当前方块走过的方块数,f(x)就是他们的和。关于算法的实现,我们需要用到两个队列列表,一个是开列表,一个是闭列表,其中开列表有序的,闭列表无要求下图是运行的第一步。
首先把当前方块放入开列表,图中绿色方块为开始方块,上下左右分四个方向计算相邻方块的估价函数,拿右边方块来说,h的值就是6,即忽略障碍从该方块到红色方块最少要走6个方格,g值是从开始方块到该方块移动的一个格子,f值为他们的和,其他三个方向同样如此计算。在计算这些之前我们还要将当前方块放入到闭列表中,并且把当前方块从开列表中移除掉。或许有困惑,当前方块刚放进开列表就移除掉,是多此一举,因为这是开始循环前的第一步,计算出的相邻方块还要按f值有序加入到开列表中,然后再从中一个一个拿出来遍历(如果还是不太明白,请继续往下看,下面还会提到,或者看后续博文里的程序流程图,会更加直观)。
计算完后把四个方向的方块的父节点指向当前方块,就如图中箭头表示一样,当找到最短路径后我们要根据父亲节点来找到相对的路径,然后就可以用cocos2dx的动作函数实现人物的移动了。
f值小的即最短路径可能出现的方向,但是图中出现了两个f值为7的方块,这个时候该如何选择呢?方法很简单就是自己设置个固定的优先方向,这里我设置为下左上右(不用担心,有可靠的理论支撑,无论自己设置什么固定的优先方向最后都能找到最短路径)。设置好顺序后,要把这四个方块加入到有序的开列表,加入的原则是按照f值由小到大,如果f值相等则按照设置的优先顺序加入列表,这里的加入顺序是下边-左边-上边-右边,在开列表中的排序是右边-下边-左边-上边,因为开列表的添加这按相同的f值方块,后加入的排在先加入的前面规则进行的。下图红色数字表示方块在开列表中的位置
所以,在下一次从开列表中取方块的时候,选择了右边f值为7的方块,如下图。
把刚选择的方块,作为当前方块。
重复上面的步骤,计算四个方向相邻方块的f、h和g值,但是对于障碍方块和已经在闭列表中的方块不做任何处理,所以只计算上下两个方块并把他们加入到有顺序的开列表中,如下图,红色数字表示他们在开列表中的顺序
下面要说的是我感觉在别的博文中讲的不够清楚的地方(也可能是我理解能力不行)。启发式搜索有全局的也有局部的,A星用的是全局的,就是说在开列表中的所有方块中,取f值最小的为下一步搜索的方块。上图中可以看出有两个f值为7的方块,但是在这里取开列表中的第一个元素为当前点,然后在开列表中移除它,并把它加入到闭列表中。如下图。
同样计算四个方向相邻的方块,这里又又新的不同点出现了。当前点的下边正常计算,右边障碍点和上边已经加入闭列表的方块不用计算,特殊的是左边的已经在开列表的方块。对于该方块的计算是这样的,如果当前方块的g值加上到左边方块的移动值大于左边方块的g值,那么就把左边的g值设置为前者,即当前方块的g值2+1 > 左边的g值1,故把左边的g值1变为3,f值也要随着改变。如下图。
改变f值后的这个方块,要重新按有序加入到开列表中,所以现在在开列表中的方块顺序,如下图
想在开列表中所有的方块f值都为9,取红色数字为1方块(开列表的第一个方块),用它来做下一步探索的方块,把它从开列表中拿出,放入到闭列表,如下图。
选择开列表中的第一个方块,即下图中红色数字为1的方块。
计算它相邻的方块,结果如下图。
注意,这次只计算了当前方块下边的方块,坐标方块在开列表中,但是左边方块的g值不小于当前方块g值加1(1是当前方块移动到相邻方块经过的路径长度,即一个方块为一个单位长度),所以左边方块保持不变。再看下这个方块在开列表中的顺序,如下图。
f值为9的方块在开列表的排序好理解,因为开列表中取出了一个f值为9的方块,所以后面的方块在开列表中的顺序都减1。值得注意的是f值为11的方块在列表中的顺序,原先的两个方块顺序没有变,而最新计算出来的f值为11的方块排到了他们前面。这就是开始时说的,新方块插入列表的原则,即f值相等时,后插入的排在之前插入的前面。如下图所示,程序是当找到第一个f值为11的方块时,就把它插入到该位置的前面。
取开列表第一个方块,把它加入到闭列表,计算它相邻方块,注意它左边的方块要重新计算g值,因为2+1 > 1,如下图。
开列表中方块的顺序,注意,重新计算g值的左边方块要重新加入开列表,所以左边的方块排第三,如下图。
重复以上 *** 作
这里注意列表顺序,要选择当前方块上边方块。
最后一个方格搜索到了红色目标方块,然后根据之前我们设置的父节点,从红色方块开始一步一步地就可以找到这条最短路径了。
至此A星算法的运算过程大致已经讲完,关于代码实现的部分会在后续的博文中,还有整个程序的流程图,帮助大家理解A星算法。
花了一天时间写的,转载记得说明出处!如果哪里没有讲清楚欢迎留言。
总结以上是内存溢出为你收集整理的cocos2dx 3.x 实现 A星(A*)(A-star)算法自动寻路(一)全部内容,希望文章能够帮你解决cocos2dx 3.x 实现 A星(A*)(A-star)算法自动寻路(一)所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)