Cocos2d-x 寻路算法解析(二): 离目的地的距离优先

发表于2015-12-15
评论0 450浏览

想免费获取内部独家PPT资料库?观看行业大牛直播?点击加入腾讯游戏学院游戏程序行业精英群

711501594
接上一篇《Cocos2d-x 寻路算法解析(一): 距离优先》


  看这个图,我们发现这个寻路算法有点傻,明明终点在右侧却每个方向都找。难道没有其他办法了吗?从现实生活中我们知道东西如果在东边,当然是往东边搜索才是最好的办法。

Figure 2


  计算机中如何表示离目标近呢? 用图来解释就是这样的,目标在右上角,我们往右走,从X轴的角度来说离目标又近了一步,同理往上走是在Y轴上里目标近一步。最好的一步应该是图中-2的点,X轴和Y轴同时离目标近了一步。简单地转换成代码就是下面的这样:

000

  扔到heap的比较条件中我们轻易地就实现了按照离目标距离优先的寻路算法,startPathFinding整个方法都不要改,只需要传进去上面提到的比较方法就行了。

-000

  离目的地的距离优先效果图:

Figure3


  我们惊奇地发现似乎我们成功了,就用了9步就找到了目的地!

  算法改进

  从图2中我们用的是X轴和Y轴上的相对距离,并不是真正的物理距离,意识到这个问题我们马上修改了比较函数。物理距离当然容易算了,公式如下:


  换成C++函数就是下面的样子:

000

  演示了下发现没有什么变化。但我们知道我们变的更好了。

  该算法存在的问题

  1.很容易想到的一个问题是,它没有考虑权重!如果目标在右侧,而右侧是一条非常难走的路,那么这个算法将毫无顾虑地走过去,丝毫不考虑就在不远处有条非常轻松的路。下面这个图就可以说明这个问题。


  2.还有个问题,即使没有权重Cell的存在,只有可通过和不可通过Cell的存在,这个算法也有问题,我们可以人为地制造一个陷阱,虽然目标在起点的下方,但是上面有条更近的路,这个算法应该会愚蠢地在往下找吧,这个就跟人一样,有时候目光短浅。下图是演示结果。


  对比之前的算法发现其实上面的这条路更好的,虽然它查询了大量的Cell才发现这点(人家很努力的好不好)。


  看看还有什么更好的办法没有?期待下篇的寻路算法吧。

原文链接

著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引

游戏学院公众号二维码
腾讯游戏学院
微信公众号

提供更专业的游戏知识学习平台