Home » Flash相关 » 未分类 » 利用跳点搜索算法,优化A星寻路

利用跳点搜索算法,优化A星寻路

在游戏中寻路是无处不在的。最著名的寻找最短路径算法莫过与A*算法,实现方式有很多中,重要的是我们要掌握其原理。

在本教程中,我们将介绍一种相对较新的方法搜索——基于网格的世界的跳点的搜索,可以加速A*寻路算法。效率提升那是大大的。

我假设读者已经明白A*算法的原理。如果你对A星寻路还不是很了解的话,我推荐你去看下这篇十分简单明了的教程,了解A星算法原理,猛戳这里

好的,下面进入正题,开始讲解Jump Point Search!(以下简称JPS)

先来看个Demo,做个对比实验

 首先让我们来看下老外用AS开发的一个Demo。Demo中黑色部分为不可行走区域,鼠标放到场景中任何个点,都会进行寻路算法,左上角的文本会提示寻路算法平均花费时间。

按【空格】键可以切换寻路算法模式为普通A*算法和JPS优化后的A*算法。

按【A】键可以添加NPC(貌似瓢虫的动物)

按【R】键可以移除NPC

下面开始讲解原理

常规A*算法,是向相邻的格子中搜索可能的“最近节点”,然后把所有的“最近节点”连接起来,既为最终解。至于说怎样的节点才是“最近节点”,本篇不做介绍,因为我前面已经设定了读者是已经明白A*算法的原理的了。

问题的关键,就在于,我们一定要逐格逐格的去搜索吗?随着格子密集度提升,时间复杂度也将大幅提升。

那么我们如何去优化呢?

很简单,对于大片的可行走区域,他们之间的任何一点都是可联通的,我们可以省去这部分格子的“最近节点”搜索,这将是很大一部分的搜索的运算了。我们只需要找出一些相关的控制点,然后通过控制点之间的连通,省去大部分无谓的“寻找最近节点”的运算。

具体思路如下:

1 生成/摆放好 凸多边形障碍物

2 “扩展”多边形 扩展的大小取决于 寻路者的大小

3 将地图中所有联通点(以扩展后的多边形为主)构成一张”图”

4 将寻路者的起点和目标点作为”临时节点”加入到3)中生成的图里

5 在图中寻路. 寻路后将之前的起点移除.

下面我们举个例子:

1、有如下一张地图,途中黑色填充为不可行走区
jsp2
2、 “扩展”多边形 扩展的大小取决于 寻路者的大小,如图中细线部

jsp2

3、将地图中所有联通点(以扩展后的多边形为主)构成一张”图”
jsp2

4 、将寻路者的起点和目标点作为”临时节点”加入到3)中生成的图里
jsp2

5、基于图中的“控制点” ,在图中寻路.

5.1、寻路第一步,将起始点作为搜索点,在与其相邻的控制点中,找到可能的“最近节点”,如图所示,最粗的两条线的交点,就是我们要找的“最近节点”,因为其深绿色线段+浅绿色线段的长度之和,是最短的。这也是A*寻路的基本思路。
jsp2

5.2、寻路第二步,把上一步寻找到的“最近节点”,作为新的搜索点,然后重复同样的判断,找到新的新的“最近节点”,如图所示,红色的点,就是我们要找的新的“最近节点”
jsp2

5.3、寻路第N步,重复同样的算法,寻找新的可能的“最近节点”,直到找到“终点”。如下图,深绿色的路线,就是我们寻路结果。
jsp2

总结:

看到这里,我想大家一定都懂了,也肯定明白了,为什么利用JPS算法能够大大提高A*寻路的效率。因为它省去了一些无谓的判断节点。当然它是需要在寻路之前,开销一些空间和时间去进行地图的预处理。不过这点开销,在后面寻路算法中又大大地赚了回来。

附录:

在这里提供一个HTML5写的Demo,需使用兼容HTML5的高富帅浏览器,方能运行,屌丝IE6请绕道。猛戳这里。可以更加清晰的体现Jump Point Search算法的轮廓。

我的微博:@我就叫向佳        

感谢@大城小胖

    分享到: