闲来无事,这里我写一篇关于jps寻路的文章,希望帮助大家理解jps,也是帮我自己留一个历史的脚印吧!
首先需要了解的两个概念:
- forced neighbors
- jump point
forced neighbors
forced neighbors中文意思是被迫邻居,有两种情况的被迫邻居。
第一种
对角线情况 - 为被迫邻居
x + +
x n +
p x -
第二种
直线情况 - 为被迫邻居
x x -
p n +
x x -
jump point
jump point中文意思是跳跃点,上面两种情况中的n就代表的是jump point ,我们从起始点寻到目标点,就是一个个jump point 这样寻找过去。
成为jump point 有两个条件
: 1、这个点有被迫邻居
: 2、这个点是目标点
demo
说完两个概念,我们直接上个demo讲解下jps寻路过程。(这个demo从s开始寻找到e)
|
|
|
|
|
|
|
|
b |
b |
b |
b |
b |
b |
b |
b |
+ |
s |
+ |
b |
e |
b |
b |
+ |
+ |
j1 |
j2 |
+ |
b |
b |
+ |
+ |
+ |
+ |
+ |
b |
b |
b |
b |
b |
b |
b |
b |
图中的
- s(start)
起始点
- b(block)
阻碍点
- e(end)
目标点
- j(jump point)
跳跃点
在这个简单的例子中,要从s寻路到e,我们的jps寻路过程是这样。
1、 把起始点s压入openlist。
2、 从openlist中弹出一个点,以这个点为当前节点。
3、 获得当前点附近可以走的所有点,(获得的点)我用了加粗表示。
4、 先在这5个点中的3个正方向上的点上寻找jump point。很明显,这3个正方向上都找不到jump point。
5、 在5个点中的2个斜方向上的点上寻找jump point。这里需要注意的是,如果寻找方向上的点不是阻碍点也不是jump point的话,那么会"继续搜索"下去。但要注意的是,如果是协方向, 这个"继续搜索"会先对在正方向进行搜索,也就是上下左右,如果没有找到jump point再从协方向搜索。这里很明显,上下左都会遇到阻碍点,但我们向右走的时候会遇到jump point(j2),而在这种情况下遇到的jump point ,那么我们当前的点( j1 )就会被当做jump point返回。
6、 设置j1的父节点为s,然后把j1压入openlist。
7、 我们继续重复上面的操2-6的操作,就可以找到下一个jump point(这里是j2,因为j2满足jump point的条件)。
8、 我们在找到j2的情况下,再重复2-6,就会发现我们找到了我们的目标点。(如果未完成,继续重复第7步操作,直接找到e点)。
- 9、
最后我们找到e点之后,可以根据每个对应节点的父节点,从后往前推导,整理出一条路径出来。任务完成。
好了, jump point search 搜索的过程其实就这些,接下来,各位同学去找个实际的代码demo看下,加深下理解吧!go !
博主github上有个path_finding项目,是实现了erlang版本的jps,需要的可以看下。