• A*与JPS寻路算法的实现关闭
  • 雪峰 发表于 2016年9月28日
  • 最近正好在研究unity3d的AI人工智能的一些算法,主要是借阅了学校图书馆的一本叫做《unity3d人工智能编程精粹》的书,里面涉及方面不是很多,但每个例子都讲得非常的细致,刚好可以作为入门书籍看看。里面有一章就讲到了导航寻路,提到了A*算法。虽说u3d里有个A*的插件,但我还是想自己实现一遍。

    借着前几天在canvas实现的几个光栅画线的模板,这次也想用网格在canvas上做个简单的A*的动态寻路的例子。其实思路是比较简单的:

    1.  将每个格子(方块)看做一个节点,然后计算并记录该点到目标节点(即终点)的估计距离(我采用简单的曼哈顿距离)h,及离出发节点的代价值(这里我采用对角线方向为1.414,其余为1)g,最后总代价值f = g + h,并记录父节点(即前一节点);

    2. 首先从出发点开始(出发点g=0,无父节点),将其加入open表(open list),开始迭代。

    3. 检查open表是否为空,不为空则进行迭代;取出open表中总代价f最小的节点,若为目标节点则停止迭代,否则进行相邻节点(可以是4个节点,也可以是8个节点,有点类似于4联通和8联通)的检查。

    4. 检查节点:如果既不在open表也不在closed表中,则加入open表中;如果在open表中,则检查新的节点f是否小于旧节点的f值,若小于则更新旧节点为新节点;如果在closed表中,也要检查新节点的f值,若小于旧节点的f值,则把旧节点从closed表中移除,并把新节点加入到open表中。

    5. 一次迭代结束后,将此前最小节点加入到closed表中,开始下一次迭代(重复3,4)直到找到目标点或者是open表为空(即无法达到目标点)。

    注:在第3步进行检查的时候还要进行必要的碰撞检测,即检查是否为障碍物,不能将障碍点加入到表中,也不能直接穿过障碍物。

    优点:这个算法的优点就是一般可以找到最优路线,而且可以进行动态改变。

    缺点:缺点也是很明显,这个算法的迭代和循环遍历的次数比较多,只要地图上的节点数一多,所需的时间也会大量增加。并且在无法找到目标点时会迭代地图上所有节点,很浪费时间。

    baidu-ime_2016-9-28_22-44-16

    baidu-ime_2016-9-28_22-43-25

    从上图可以看出,当像素块大小为30时进行的一个环形障碍物测试所需时间为3855ms,而在像素块大小为20时在相似位置做相似的测试所需的时间为8211ms。很明显,随着节点的增多,所需的时间也大大地增加了。

    说明:由于是用js语言实现的,而这个算法的效率与数据结构有很大的关系,在js中像队列,栈,哈希表都没有支持,而且连动态的二维数组都不支持!!!我在这里仅使用一维数组储存数据,仅仅是最原始的A*算法实现,所以效率大打折扣,估计用java或者c++这些语言实现会好很多。我在网上看了一位大神写的A*的Demo(PathFinding.js),那可是ms级的啊。而且很多地方还可以进行优化,比如需要进行遍历的地方尽量换成不要遍历的方法,open表和close表的结构也可以优化。总之,可以改进的地方有很多,这方面的优化网上也有许多,日后可以深究一下。

     

    更新(2016-10-3)


     

    这里要更正一下,之前在js上运行效率之所以会这么低不是由于js数据结构的原因,而是我自己在循环体中使用了大量的自定义函数,而那个自定义函数比较耗时(大概一次循环会耗时10ms左右)。经测试本身的for循环大概不到1ms,所以程序正常耗时应该也就是几十ms到几百ms之间。

    还有,昨天刚好看了一篇关于A*算法的优化的文章(地址没保存,所以忘了),里面提到了close表存在的必要性说道closed表完全不必要(或者说是不需要进行遍历判断再更新),于是乎我就把close表去掉,将探索完后的节点进行标记;然后以节点的x,y作为数组的索引,将所有的数组(标记,障碍物,open表)转为一维数组,因此只剩下一处地方有遍历——取得当前open表代价最小节点。然后效率就刷刷的上来了,一以下是一些环形障碍测试:

    当像素块大小为30时,耗时为92ms:

    baidu-ime_2016-10-3_13-50-54

    当像素块大小为20时,耗时为366ms:

    baidu-ime_2016-10-3_13-54-6

    我还试了一下丧心病狂的像素块大小为10时,耗时为3901ms:

    baidu-ime_2016-10-3_13-57-15

    当然,这仅仅是一点小小的优化,真正的优化还是对最小代价节点的取舍以及对数据结构的优化方面。

     

    更新(2016-10-8)


    由于在网上看到一个比A*算法效率高很多的算法——JPS(Jump Point Search),所以没忍住也给实现了一遍,耗费了国庆的一天假期。说实话,在一般情况下这个算法的效率简直不是比A*star算法好了一丁点,基本上都快了几十到几百甚至上千倍,而且得到的也是最短路径。所以看到效果时我都吓了一跳,不过实现过程比较艰辛,国内关于此算法的介绍有限,去国外看的英文文章有点费劲,不过好在那篇文章(Jump Point Search Explained)提供了大量的步骤图,还有个demo可以随时调试。然后我就左试右试,把每种情况基本都摸清楚了,步骤也搞明白了,算是基本成型了吧?(原算法那篇论文有点看不明白,里面也没有提到具体节点的代价怎么计算,所以我还是沿用了A*算法的模式)还有一个问题没解决,就是被迫邻居节点可能同时一个方向出现两个,而我只处理了一个。

    这个算法比较精妙,它直接跳过那些空白的(也就是直线方向没有障碍物的)点,大大减少了open表处理的数据,称之为跳跃点,跳跃点根据情况不同而有不同确定方法。其中最复杂的部分就是对于被迫邻居节点(forced neighbor)的处理了,由于没图不太好说,还是推荐去我之前提到过的那个网站(http://zerowidth.com/2013/05/05/jump-point-search-explained.html)看看比较好,一目了然。

    我还试着做个流程图,感觉不太像。

    jps%e7%ae%97%e6%b3%95%e6%b5%81%e7%a8%8b

    给个效果图:

    baidu-ime_2016-10-8_12-40-1

    后话:在实现过程中,还碰到了一个奇怪的“bug”,就是一部分数组的最后一个元素没办法得到,length也是少了1,但是打印出来的数组却是对的,找了好久原因也没找到,这个问题也影响了部分效率。结果去知乎上问,居然还被关闭了。

    baidu-ime_2016-10-4_14-59-44

    查看介绍

    A*与JPS寻路算法的实现