精华内容
下载资源
问答
  • jps
    2020-09-12 08:29:09

    JVM Process Status Tool,显示指定系统内所有的HotSpot虚拟机进程

    命令格式

    jps [options] [hostid]

    option参数

    • -l : 输出主类全名或jar路径

    • -q : 只输出LVMID

    • -m : 输出JVM启动时传递给main()的参数

    • -v : 输出JVM启动时显示指定的JVM参数

    其中[option]、[hostid]参数也可以不写。

     案例:

      1.jps

    [root@localhost ~]# jps
    8515 RunJar
    8516 Jps
    8517 jar
    

      2. jps -l  输出主类或者jar的完全路径名

    [root@localhost ~]# jps -l
    8513 sun.tools.jps.Jps
    8512 web-1.1-SNAPSHOT.jar
    8517 com.inteelij.idea.Main
    

      3. jps -v 输出jvm参数

    [root@localhost ~]# jps -v
    8515 war -Xms200m -Xmx200m
    26115 Jps -Denv.class.path=.:/data/SoftWare/jdk1.8.0_171/lib/dt.jar:/data/SoftWare/jdk1.8.0_171/lib/tools.jar -Dapplication.home=/data/SoftWare/jdk1.8.0_171 -Xms8m
    8516 jar -Xms800m -Xmx800m -XX:SurvivorRatio=8 -XX:+UseConcMarkSweepGC -XX:CICompilerCount=4
    

      4. jps -q 只显示java进程号

    [root@localhost ~]# jps -q
    8515
    8516
    8517
    
    更多相关内容
  • 我们一定会写一个shell脚本去每一个节点上去jps,查看每个节点的进程情况。 原先以为shell很简单: #!/bin/bash #查看每个节点运行情况 for((host=101;host<108;host++));do echo -----------hadoop$host--------...
  • JPS_search_matlab-main.zip

    2021-09-03 20:37:28
    包含相同地图下(一共6种地图,10*10,20*24,40*40,60*60,80*80,100*100)A*算法与JPS算法的实现,以及两种算法的运行时间、占用内存以及路径长度的对比
  • jps(Java Virtual Machine Process Status Tool)是JDK 1.5提供的一个显示当前所有java进程pid的命令,简单实用,非常适合在linux/unix平台上简单察看当前java进程的一些简单情况。 使用 先执行jps –help 查看一下此...
  • 可以使用 3 种算法之一找到路径:A*、JPS 或 JSP+。Obstables 对结果路径没有影响。 精确 - 使用“墙壁追踪”在连续空间中工作 该方案来自游戏“Dota 2”。首先,您搜索到目标点的粗略路径,然后搜索从当前位置到...
  • JPS_JumpPointSearch

    2021-03-17 20:18:38
    JPS_JumpPointSearch
  • kotlin-jps-plugin.jar

    2022-03-21 10:52:28
    kotlin-jps-plugin.jar
  • JPS算法的实现!(C#版本)
  • JPS.zip,JPS,map.bmp,__pycache__,jps.cpython-35.pyc,jps.cpython-38.pyc,A_star.cpython-38.pyc,map2.bmp,Main.py,jps.py,map3.bmp
  • JumpPointSearch-master.zip,JumpPointSearch-master,mazes,mazebig.jpg,200 by 200 delta maze.png,6Kj2X.png,maze2_1_0640x0480.jpg,braid.gif,BigRound.jpg,src,.gitattributes,JPS,JPS.csproj,Pathfinder.cs,...
  • JPS-12计算机视觉排种器试验台的结构原理及使用.pdf
  • #jps-ds 这是一个简单的 MongoDB 数据源模块。 入门 在服务器上 安装模块: npm install jps-ds var DS = require('jps-ds').DS; 连接 要创建和配置新连接,请使用以下命令: var _ds = new DS( { //host: '...
  • MRSL跳转点搜索计划库v1.1 跳转点搜索可在2D和3D环境中进行路径规划。 原始跳点搜索算法在。 在提出了3D版本 。 此DMPlanner中还包括距离图计划器... && make -j4B)使用CATKIN $ mv jps3d ~ /catkin_ws/src$ cd ~ /c
  • javaFX-jps-plugin.jar

    2022-03-15 16:39:00
    javaFX-jps-plugin.jar
  • jps脚本 shell脚本

    2020-06-22 18:31:21
    在一个集群非常大的情况下,如果想要查看单个主机在运行哪些java进程。我们可以去到每个主机下,使用jps命令。可是这种方法太过低效。我们可以使用一个shell脚本来完成此命令。查看进程 jps脚本 提前配置免密
  • JPS型湿式混凝土喷射机机组能使混合料拌合均匀,水灰质量比能够准确控制,有利于水和水泥的水化,因而粉尘小,回弹小,混凝土均质性好,强度高,防尘降噪,减少环境污染。机器结构合理、性能稳定、操作维护方便、使用寿命长,...
  • servlet-jps-sample 演示以学习jsp和servlet
  • JPS算法

    千次阅读 2022-02-25 15:05:51
    在A*算法的基础上,推导JPS算法的规则、特点

    Jump Point Search算法(JPS算法)

    Jump Point Search算法的核心思想就是寻找到规划中的对称性Path并打破他们,从而避免扩展大量无用节点。

    在这里插入图片描述

    前向探索规则(Look Ahead Rule/ Pruning Rule)

    JPS的智能性体现在它遵循的Look Ahead规则,主要包含如下几条内容:

    裁剪邻居(Neighbor Pruning)

    此处,假定处于栅格地图(Grid-based Map)中,且采用八联通结构以及图内无障碍物。则由上一节点抵达当前节点的情况,分直行和对角两种进行分析。

    直行(straight)

    在这里插入图片描述

    假设当前从节点抵达下一个为直行(上图所示),如图当前节点为4号节点,下一个节点为x节点。则在考虑x节点的邻居节点时,可以仅仅考虑5号节点,而不考虑其余节点。

    上述遵循的筛选规则如下:

    • 摒弃劣性节点(Inferior Neighbours),也即图中灰色栅格区域的节点
    • 考虑自然节点(Natural Neighbours),也即图中白色栅格区域的节点

    所谓劣性节点是指:从父节点(4号节点)不经过当前节点(x节点) 而直接抵达所需代价,小于等于从父节点抵达当前节点(x节点),再抵达劣性节点所需代价的节点。
    i f C o s t ( 父 节 点 → 目 标 节 点 ( 不 经 过 当 前 节 点 ) ) ≤ C o s t ( 父 节 点 → 当 前 节 点 → 目 标 节 点 ) : n o d e = I n f e r i o r e l s e : n o d e = N a t u r a l \begin{aligned} &if\quad Cost(父节点\to目标节点(不经过当前节点))\leq Cost(父节点\to当前节点\to目标节点):\\ &\qquad node = Inferior\\ & else:\\ &\qquad node = Natural \end{aligned} ifCost()Cost():node=Inferiorelse:node=Natural
    举例说明:

    • 1号节点: 4 → 1 4\to1 41所需代价1; 4 → x → 1 4\to x\to1 4x1 4 → 1 4\to1 41所需代价 1 + 2 1+\sqrt2 1+2 ,劣性节点
    • 2号节点: 4 → 2 4\to2 42所需代价 2 \sqrt2 2 4 → x → 2 4\to x\to2 4x2所需代价2,劣性节点
    • 3号节点: 4 → 2 → 3 4\to2\to3 423所需代价 1 + 2 1+\sqrt2 1+2 4 → x → 3 4\to x\to3 4x3所需代价 1 + 2 1+\sqrt2 1+2 ,劣性节点
    • 5号节点:最短为 4 → x → 5 4\to x\to5 4x5,自然节点
    • 6号节点:对称等同于1号节点,劣性节点
    • 7号节点:对称等同于2号节点,劣性节点
    • 8号节点:对称等同于3号节点,劣性节点

    综上所述,由4号节点抵达x节点,在探索x的邻居节点时,只需要探索5号节点即可。

    对角(diagonal)

    在这里插入图片描述

    若如上图所示,由父节点(6号节点)抵达当前节点(x节点),则可认定节点1、4、7、8为劣性节点,其余为自然节点。

    分析如下:

    • 1号节点: 6 → 4 → 1 6\to4\to1 641所需代价2; 6 → x → 1 6\to x\to1 6x1所需代价为 2 2 2\sqrt2 22 ,劣性节点
    • 2号节点: 6 → 4 → 2 6\to4\to2 642所需代价 1 + 2 1+\sqrt2 1+2 6 → x → 2 6\to x\to2 6x2所需代价为 1 + 2 1+\sqrt2 1+2 ,自然节点
    • 3号节点:最短为 6 → x → 3 6\to x\to3 6x3,自然节点
    • 4号节点: 6 → 4 6\to4 64所需代价1; 6 → x → 4 6\to x\to4 6x4所需代价 1 + 2 1+\sqrt2 1+2
    • 5号节点:对称等同于2号节点,自然节点
    • 7号节点:对称等同于4号节点,劣性节点
    • 8号节点:对称等同于1号节点,劣性节点

    ***此处注意,博主所学教程中未解释为何2、5节点在等同的情况下为自然节点,而非劣性节点。***对此,也许对角情况下同直行不同,特意将等同条件判定为自然而非劣性。

    强迫邻居(Forced Neighbors)

    假设处于栅格地图环境中,且采用八联通结构并且存在障碍物情况下,依旧分直行和对角两种情况进行考虑。

    直行(straight)

    在这里插入图片描述

    如上图所示,在直行条件下,若2号节点所在栅格被障碍物占据,则3号节点的抵达无法通过 4 → 2 → 3 4\to2\to3 423进行,而必须采用 4 → x → 3 4\to x\to3 4x3进行。也即3号节点由劣性节点变为强迫节点,不能被抛弃。

    对角(diagonal)

    在这里插入图片描述

    如上图所示,在对角条件下,若4号节点所在栅格被障碍物占据,则1号节点的抵达无法通过 6 → 4 → 1 6\to4\to1 641进行,而必须采用 6 → x → 1 6\to x\to1 6x1进行。也即1号节点由劣性节点变为强迫节点,不能被抛弃。

    跳跃规则(Jumping Rules)

    对前向探索规则的学习,可知其满足如下规则:

    在这里插入图片描述

    则此时,若不断进行直行(straight pruning)或不断进行对角(diagonal pruning),则可采用跳跃规则(Jumping Rules)。

    直行跳跃(Jumping Straight)

    若机器人不断迭代执行直行前向规则(straight pruning rule),如下图所示:

    在这里插入图片描述

    则在前进过程中对邻居节点进行裁剪,直到抵达节点 y y y,此时针对障碍物所在位置,可知节点 z z z为节点 y y y的强迫邻居(Forced Neighbors),称节点 y y y为节点 x x x的关键节点(Jump Point Successor)。

    也即在对节点 x x x执行直行探索时,可直接跳跃至一个具有强迫邻居的关键节点 y y y上,对途中其余节点无需考虑探索。

    对角跳跃(Jumping Diagonally)

    对于任何一次跳跃,首先考虑直行跳跃(Jumping Straight),包括水平直行和垂直直行,其次再考虑对角跳跃(Jumping Diagonally)。如下图所示:

    在这里插入图片描述

    当由当前节点对角行至节点 x x x时,对其进行直行跳跃探索(图中红色虚线),由于未找到关键节点则忽略相关探索的节点,并使用对角跳跃规则至下一节点。

    同样对该节点进行直行跳跃探索,由于无关键节点而再次进行对角跳跃,直至抵达节点 y y y。此时对其进行水平直行跳跃,发现节点 z z z具有强迫邻居节点,则返回至发现节点 z z z的节点 y y y,标记其为节点 x x x的关键节点(Jump Point Successor)。

    优先级队列(Priority Queue)

    JPS算法的优先级队列内元素包含两类内容:使用跳跃规则发现的关键节点(Jump Point Successor);当前探索节点 x x x的强迫邻居节点(Forced Neighbors)。

    如上述对角跳跃中探索的示例图中,关键节点为 y y y、强迫邻居为 w w w,则同样将其加入优先级队列。

    完整跳跃演示

    第一次探索

    在这里插入图片描述

    当前节点(绿色节点)首先进行水平、垂直直行探索,未发现关键节点;进一步进行对角探索。

    第二次探索

    在这里插入图片描述

    对第一次探索得到的节点进行水平、垂直直行探索,未发现关键节点;进一步执行对角探索。

    第三次探索

    在这里插入图片描述
    同第二次探索情况。

    第四次探索

    在这里插入图片描述

    对第三次探索得到的节点执行水平直行探索时,发现一个关键节点(黄色节点),它具有强迫节点(紫色节点)。

    需要注意的是,从绿色节点无法一次直接跳跃至黄色节点,跳跃的规则为只能进行一次对角跳跃或直行跳跃。

    则弹出的关键节点应该为探索得到黄色节点的对角跳跃节点(下图蓝色节点)

    在这里插入图片描述

    JPS 算法流程

    JPS算法的伪代码同 A ∗ A^* A一样:
    L o o p i f   q u e u e   i s   e m p t y : r e t u r n   f a l s e ; b r e a k ; R e m o v e   t h e   n o d e   n   w i t h   t h e   l o w e s t   f ( n ) = g ( n ) + h ( n )   f r o m   t h e   p r i o r i t y   q u e u e M a r k   n o d e   n   a s   e x p a n d e d i f   t h e   n o d e   n   i s   t h e   g o a l   s t a t e : r e t u r n   t r u e ; b r e a k ; F o r   a l l   u n e x p a n d e d   n e i g h b o u r s   m   o f   n o d e   n : i f   g ( m ) = = i n f i n i t e : g ( m ) = g ( n ) + C o s t n m P u s h   n o d e   m   i n t o   t h e   q u e u e i f   g ( m ) > g ( n ) + C o s t n m g ( m ) = g ( n ) + C o s t n m e n d E n d   L o o p \begin{aligned} &Loop\\ &\qquad if\:queue\:is\:empty:\\ &\qquad\qquad return\:false;\\ &\qquad\qquad break;\\ &\qquad Remove\:the\:node\:n\:with\:the\:lowest\:f(n)=g(n)+h(n)\:from\:the\:priority\:queue\\ &\qquad Mark\:node\:n\:as\:expanded\\ &\qquad if\:the\:node\:n\:is\:the\:goal\:state:\\ &\qquad\qquad return\:true;\\ &\qquad\qquad break; \\ &\qquad For\:all\:unexpanded\:neighbours\:m\:of\:node\:n:\\ &\qquad\qquad if\:g(m)==infinite: \\ &\qquad\qquad\qquad g(m)=g(n)+Cost_{nm}\\ &\qquad\qquad\qquad Push\:node\:m\:into\:the\:queue\\ &\qquad\qquad if\:g(m)>g(n)+Cost_{nm} \\ &\qquad\qquad\qquad g(m)=g(n)+Cost_{nm}\\ &\qquad end\\ &End\:Loop \\ \end{aligned} Loopifqueueisempty:returnfalse;break;Removethenodenwiththelowestf(n)=g(n)+h(n)fromthepriorityqueueMarknodenasexpandedifthenodenisthegoalstate:returntrue;break;Forallunexpandedneighboursmofnoden:ifg(m)==infinite:g(m)=g(n)+CostnmPushnodemintothequeueifg(m)>g(n)+Costnmg(m)=g(n)+CostnmendEndLoop
    他们的不同在于邻居节点的定义不同:

    在这里插入图片描述
    A ∗ A^* A算法的邻居节点为几何意义上的邻居,而JPS算法的邻居节点为跳跃所得的邻居。

    JPS算法演示

    如下图,为一次JPS完整演示的问题描述:

    在这里插入图片描述
    从起点(绿色节点)到终点(红色节点),黑色节点为障碍物节点。

    第一个关键节点

    在这里插入图片描述
    此处省略推演(同上述完整跳跃演示),当探索至黄色节点时,对其进行水平直行探索:

    在这里插入图片描述
    发现关键节点(紫色节点)具有一个强迫邻居(蓝色节点),则认为黄色节点为第一个关键节点加入优先级队列。

    弹出绿色节点

    继续对黄色节点进行对角探索:
    在这里插入图片描述
    未发现任何关键节点且节点无法继续对角探索,则完成第一次探索。

    起点(绿色节点)弹出优先级队列,加入已经探索完毕的队列(Close List)中。

    第二个关键节点

    对上图中黄色节点进行探索,发现下一个关键节点(下图中黄色节点):
    在这里插入图片描述
    当前节点的探索完毕,加入Close List中。

    第三个关键节点

    对黄色节点进行直行、对角探索:

    在这里插入图片描述
    在这里插入图片描述

    两次探索后,发现目标点(红色节点)。JPS算法将目标点假定为强迫邻居节点,则判断当前节点为关键节点:
    在这里插入图片描述

    抵达目标点

    对黄色节点进行直行探索:
    在这里插入图片描述
    抵达终点,路径规划如下:
    在这里插入图片描述

    优先级队列的排序

    对于加入优先级队列的节点,同 A ∗ A^* A算法一样,对 f ( n ) f(n) f(n)进行排序,代价值小的先被弹出进行探索:

    在这里插入图片描述

    算法比较

    在复杂环境下,JPS算法的效果远远超过 A ∗ A^* A算法:

    在这里插入图片描述
    这是因为JPS算法能够减少加入Open List中的节点的个数,仅仅对关键节点进行探索。

    但是同样,JPS算法存在增添计算在探索是否存在障碍物上,如下图所示环境,JPS算法将优先想左边不断探索直至抵达边缘后在进行向右探索:
    在这里插入图片描述

    此外,JPS仅能应用于Uniform Grid Map中,也即两个相邻的节点边权重为1,对角为 2 \sqrt 2 2 的栅格地图中

    展开全文
  • 正频 JPS软件 调试 更改参数 电机自学习 中文
  • 搭建问题遇到的总结几点,便于找查问题 1)检查配置文件是否有问题 坑点一: zookeeper 配置文件 dataLogDir=/kafka/zookeeperlogs (记得不要写错单词) 坑点二: 在配置的dataDir 下创建myid文件,内容就是对应...
  • (转载)JPS JPS+算法

    千次阅读 2021-08-02 11:56:11
    JPS(jump point search)算法实际上是对A* 寻路算法的一个改进,因此在阅读本文之前需要先了解A算法。A 算法在扩展节点时会把节点所有邻居都考虑进去,这样openlist中点的数量会很多,搜索效率较慢。 例如在无遮挡...

    作者:KillerAery 出处:http://www.cnblogs.com/KillerAery/

    概念

    JPS(jump point search)算法实际上是对A* 寻路算法的一个改进,因此在阅读本文之前需要先了解A算法。A 算法在扩展节点时会把节点所有邻居都考虑进去,这样openlist中点的数量会很多,搜索效率较慢。

    例如在无遮挡情况下(往往会有多条等价路径),而我们希望起点到终点实际只取其中一条路径,而该路径外其它节点可以没必要放入openlist(不希望加入没必要的邻居)。
    在这里插入图片描述

    其次我们还希望直线方向上中途的点不用放入openlist,如果只放入每段直线子路径的起点和终点,那openlist又可以少放很多没必要的节点:
    在这里插入图片描述

    可以看到 JPS 算法搜到的节点总是“跳跃性”的,这是因为这些关键性的节点都是需要改变行走方向的拐点,因此这也是 Jump Point 命名的来历。

    在介绍JPS等算法具体实现前,我们必须先掌握下面的概念。

    强迫邻居(Forced Neighbour)

    强迫邻居:节点 x 的8个邻居中有障碍,且 x 的父节点 p 经过x 到达 n 的距离代价比不经过 x 到达的 n 的任意路径的距离代价小,则称 n 是 x 的强迫邻居。

    ( 转载者注:本人认为定义也不完全对,因为下图这样似乎x不算跳点,那么n也不算强迫邻居,大家怎么看呢?)
    在这里插入图片描述

    看定义也许十分晦涩难懂。直观来说,实际就是因为前进方向(父节点到 x 节点的方向为前进方向)的某一边的靠后位置有障碍物,因此想要到该边靠前的空位有最短的路径,就必须得经过过 x 节点。

    (转载者注:本人认为跳点最直观的理解就是:遇到障碍物或者靠近终点时,可以用来改变前进方向的点)

    可能的情况见图示,黑色为障碍,红圈即为强迫邻居:
    (转载者注:本人认为右图的1不一定是强迫邻居,但2一定是)
    在这里插入图片描述

    (左图为直线方向情况下的强迫邻居,右图为斜方向情况下的强迫邻居)

    跳点(Jump Point)

    跳点:当前点 x 满足以下三个条件之一:

    • 节点 x 是起点/终点。
    • 节点 x 至少有一个强迫邻居。
    • 如果父节点在斜方向(意味着这是斜向搜索),节点x的水平或垂直方向上有满足条件a,b的点。

    节点y的水平或垂直方向是斜向向量的拆解,比如向量d=(1,1),那么水平方向则是(1,0),并不会往左搜索,只会看右边,如果向量d=(-1,-1),那么水平方向是(-1,0),只会搜索左边,不看右边,其他同理。

    下图举个例子,由于黄色节点的父节点是在斜方向,其对应分解成向上和向右两个方向,因为在右方向发现一个蓝色跳点,因此黄色节点也应被判断为跳点:
    在这里插入图片描述

    JPS 寻路算法(Jump Point Search)

    实现原理
    JPS 算法和A* 算法非常相似,步骤大概如下:

    1. openlist取一个权值最低的节点,然后开始搜索。(这些和A*是一样的)
    2. 搜索时,先进行 直线搜索(4/8个方向,跳跃搜索),然后再
      斜向搜索(4个方向,只搜索一步)。如果期间某个方向搜索到跳点或者碰到障碍(或边界),则当前方向完成搜索,若有搜到跳点就添加进openlist。

    跳跃搜索是指沿直线方向一直搜下去(可能会搜到很多格),直到搜到跳点或者障碍(边界)。一开始从起点搜索,会有4个直线方向(上下左右),要是4个斜方向都前进了一步,此时直线方向会有8个。

    1. 若斜方向没完成搜索,则斜方向前进一步,重复上述过程。

    因为直线方向是跳跃式搜索,所以总是能完成搜索。

    1. 若所有方向已完成搜索,则认为当前节点搜索完毕,将当前节点移除于openlist,加入closelist。
    2. 重复取openlist权值最低节点搜索,直到openlist为空或者找到终点。

    下面结合图片更好说明过程2和3:首先我们从openlist取出绿色的节点,作为搜索的开始,先进行直线搜索,再斜向搜索,没有找到任何跳点。
    在这里插入图片描述

    斜方向前进一步后,重复直线搜索和斜向搜索过程,仍没发现跳点。

    在这里插入图片描述

    斜方向前进两步后,重复直线搜索和斜向搜索过程,仍没发现跳点。
    在这里插入图片描述

    斜方向前进了三步后(假设当前位置为 x),在水平直线搜索上发现了一个跳点(紫色节点为强迫邻居)。

    在这里插入图片描述

    于是 x 也被判断为跳点,添加进openlist。斜方向结束,绿色节点的搜索过程也就此结束,被移除于openlist,放入closelist。

    在这里插入图片描述

    示例过程

    下面展示JPS算法更加完整的过程:
    假设起点为绿色节点 ,终点为红色节点

    在这里插入图片描述

    重复直线搜索和斜向搜索过程,斜方向前进了3步。在第3步判断出黄色节点为跳点(依据是水平方向有其它跳点),将黄色跳点放入openlist,然后斜方向搜索完成,绿色节点移除于openlist,放入closelist。
    在这里插入图片描述

    对openlist下一个权值最低的节点(即黄色节点)开启搜索,在直线方向上发现了蓝色节点为跳点(依据是紫色节点为强迫邻居),类似地,放入openlist。
    在这里插入图片描述

    由于斜方向还没结束,继续前进一步。最后一次直线搜索和斜向搜索都碰到了边界,因此黄色节点搜索完成,移除于openlist,放入closelist。

    在这里插入图片描述

    对openlist下一个权值最低的节点(原为蓝色节点,下图变为黄色节点)开启搜索,直线搜索碰到边界,斜向搜索无果。斜方继续前进一步,仍然直线搜索碰到边界,斜向搜索无果。
    在这里插入图片描述

    由于斜方向还没结束,继续前进一步。
    在这里插入图片描述

    最终在直线方向上发现了红色节点为跳点,因此蓝色节点先被判断为跳点,只添加蓝色节点进openlist。斜方向完成,黄色节点搜索完成。
    在这里插入图片描述

    最后openlist取出的蓝色节点开启搜索,在水平方向上发现红色节点,判断为终点,算法完成。

    回忆起跳点的第三个判断条件(如果父节点在斜方向,节点x的水平或垂直方向上有满足条件a,b的点),会发现这个条件判断是最复杂的。在寻路过程中,它使寻路多次在水平节点上搜到跳点,也只能先添加它本身。其次,这也是算法中需要使用到递归的地方,是JPS算法性能瓶颈所在。

    转载者注:对于少走弯路的巡路,无优化的JPS较慢于无优化的A*。

    JPS+(Jump Point Search Plus)

    JPS+ 本质上也是 JPS寻路,只是加上了预处理来改进,从而使寻路更加快速。

    预处理

    我们首先对地图每个节点进行跳点判断,找出所有主要跳点:
    在这里插入图片描述

    然后对每个节点进行跳点的直线可达性判断,并记录好跳点直线可达性:
    在这里插入图片描述

    若可达还需记录号跳点直线距离:
    在这里插入图片描述

    类似地,我们对每个节点进行跳点斜向距离的记录:
    在这里插入图片描述

    剩余各个方向如果不可到达跳点的数据记为0或负数距离。如果在对应的方向上移动1步后碰到障碍(或边界)则记为0,如果移动n+1步后会碰到障碍(或边界)的数据记为负数距离-n

    最后每个节点的8个方向都记录完毕,我们便完成了JPS+的预处理过程:
    在这里插入图片描述

    以上预处理过程需要有一个数据结构存储地图上每个格子8个方向距离碰撞或跳点的距离。

    示例过程

    做好了地图的预处理之后,我们就可以使用JPS+算法了。大致思路与JPS算法相同,不过这次有了预处理的数据,我们可以更快的进行直线搜索和斜向搜索。

    在某个搜索方向上有:

    • 对于正数距离 n(意味着距离跳点 n 格),我们可以直接将n步远的节点作为跳点添加进openlist
    • 对于0距离(意味着一步都不可移动),我们无需在该方向搜索;
    • 对于负数距离 -n(意味着距离边界或障碍 n 格),我们直接将n步远的节点进行一次跳点判断(有可能满足跳点的第三条件,不过得益于预处理的数据,这步也可以很快完成)。

    如下图示,起始节点通过已记录的向上距离,直接将3步远的跳点添加进openlist,而不再像以前需要迭代三步(还每步都要判断是否跳点):
    在这里插入图片描述

    其它过程也是类似的:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    总结

    可以看到 JPS/JPS+ 算法里只有跳点才会被加入openlist里,排除了大量不必要的点,最后找出来的最短路径也是由跳点组成。这也是 JPS/JPS+ 高效的主要原因。

    JPS :

    • 绝大部分地图,使用 JPS 算法都会比 A* 算法更快,内存占用也更小(openlist里节点少了很多)。
    • JPS 在跳点判断上,要尽可能避免递归的深度过大(或者期待一下以后出现避免递归的算法),否则在超大型的地图里递归判断跳点可能会造成灾难。
    • JPS 也可以用于动态变化的地图,只是每次地图改变都需要再进行一次 JPS 搜索。
    • JPS 天生拥有合并节点(亦或者说是在一条直线里移除中间不必要节点)的功能,但是仍存在一些可以继续合并的地方。
    • JPS 只适用于 网格(grid)节点类型,不支持 Navmesh 或者路径点(Way Point)。

    JPS+ :

    • JPS+ 相比 JPS 算法又是更快上一个档次(特别是避免了过多层递归判断跳点),内存占用则是每个格子需要额外记录8个方向的距离数据。
    • JPS+ 算法由于包含预处理过程,这让它面对动态变化的地图有天生的劣势(几乎是不可以接受动态地图的),因此更适合用于静态地图。
    • JPS+ 预处理的复杂度为 O(n) ,n 代表地图格子数。
    算法性能内存占用支持动态地图预处理支持节点类型
    A*中等支持网格、Navmesh、路径点
    JPS偏小支持网格
    JPS+非常快中等不支持有,O(n)网格

    综上,JPS/JPS+ 是A算法的优秀替代者,绝大部分情况下更快和更小的内存占用已经足够诱人。在GDC 2015 关于 JPS+ 算法的演讲中,Steve Rabin 给出的数据甚至是比A 算法快70~350倍。

    展开全文
  • 变频器说明书大全系列-jps-PDS.rar
  • 变频器说明书系列-jps-PDS.DOC
  • 变频器说明书大全系列-jps-pda-pdh-pde.rar
  • JPS寻路算法优化思路

    2021-09-12 01:21:52
    当寻路算法成为瓶颈的时候,可以看看JPS算法是怎么解决寻路过程中的性能问题的

    A*算法

    简介

    A*算法,A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法,也是解决许多搜索问题的有效算法。通常用于游戏中的寻路,找到一个从初始点到终点的最短路径。
    要了解JPS算法,首先要了解A*算法,以及A*算法的不足,因为JPS算法是在A*算法上进行改进的。

    A*算法的一些概念

    current: 当前节点
    openset 开启节点集合,集合内节点有待进一步探索拓展
    closedset 关闭节点结合,集合内节点后续不再进行拓展
    neighbor 邻居,与当前节点相邻的节点
    parent(x) 节点 x 的父节点,即算法寻得的路径中节点 parent(x)的下一节点为 x
    G 值表示从起点到当前点路径耗费;
    H 值是一个期待值,当前点到终点的理论路径耗费;、
    F=G+H表示经过该节点到终点的路径耗费
    A*示意图
    如上图所示,中间高亮的绿色的格子,既是起始点,也是current,然后算法开始访问current的neighbor也就是周边的8个浅绿色的格子,current访问完成以后,周边可达的8点格子加入openset,current进入closedset,不再进行拓展了,parent(x)的父节点是谁拓展了该节点。

    算法流程

    Step 1. 将起始点 start 加入开启集合 openset
    Step 2. 重复以下工作:

    1. 当 openset 为空,则结束程序,此时没有路径。
    2. 寻找 openset 中 F 值最小的节点,设为当前点 current
    3. 从 openset 中移出当前点 current
    4. 关闭集合 closedset 中加入当前点 current
    5. 若 current 为目标点 goal,则结束程序,此时有路径生成,此时由 goal 节点开始逐级追溯路径上每一个节点 x 的上一级父节点 parent(x),直至回溯到开始节点 start,此时回溯的各节点即为路径。
    6. 对 current 的八个方向的每一个相邻点 neighbor
    7. 如果 neighbor 不可通过或者已经在 closedset 中,略过。
    8. 如果 neighbor 不在 openset 中,加入 openset 中
    9. 如果 neighbor 在 openset 中,G 值判定,若此路径 G 值比之前路径小,则 neighbor 的父节点为
      current,同时更新 G 与 F 值。反之,则保持原来的节点关系与 G、F 值。

    JPS 算法简介

    JPS 算法:JPS 又名跳点搜索算法(Jump Point Search),是由澳大利亚两位教授于 2011年提出的基于 Grid 格子的寻路算法。A*算法整体流程如下图所示,JPS算法在保留 A*算法的框架的同时,进一步优化了 A*算法寻找后继节点的操作。为了说明 JPS 在 A*基础上的具体优化策略,下图中给出 A*和 JPS的算法流程图对比。由图看出,JPS 与 A*算法主要区别在后继节点拓展策略上,不同于 A*算法中直接获取当前节点所有非关闭的可达邻居节点来进行拓展的策略,JPS 根据当前结点 current 的方向、并基于跳点的策略来扩展后继节点,遵循“两个定义、三个规则”(见表,两个定义确定强迫邻居、跳点,三个规则确定节点的拓展原则),具体流程如下:

    1. 若 current 当前方向是直线方向:
      (1)如果 current 左后方不可走且左方可走(即左方是强迫邻居),则沿 current左前方和左方寻找不在 closedset 的跳点;
      (2)如果 current 当前方向可走,则沿 current 当前方向寻找不在 closed 集合的跳点;
      (3)如果 current 右后方不可走且右方可走(右方是强迫邻居),则沿 current右前方和右方寻找不在 closedset 的跳点;
    2. 若 current 当前方向为对角线方向:
      (1)如果 current 当前方向的水平分量可走(例如 current 当前为东北方向,则水平分量为东),则沿 current 当前方向的水平分量寻找不在 closedset 的跳点;
      (2)如果 current 当前方向可走,则沿 current 当前方向寻找不在 closedset的跳点;
      (3)如果 current 当前方向的垂直分量可走(例如 current 当前为东北方向,则垂直分量为北),则沿 current 当前方向的垂直分量寻找不在 closedset 的跳点。.

    JPS 寻找跳点的过程有三种优化:一,位运算;二;预处理;三;剪枝中间跳点。
    图1

    JPS 算法的两条定义,三个规则

    定义一:强迫邻居(forced neighbour):如果点 n 是 x 的邻居,并且点 n 的邻居有阻挡(不可行走的格子),并且从 parent(x)、x、n 的路径长度比其他任何从 parent(x)到 n 且不经过 x 的路径短,其中parent(x)为路径中 x 的前一个点,则 n 为 x 的强迫邻居,x 为 n 的跳点),例如图 2 中,寻找从 S 到 E的路径时,K 为 I 的强迫邻居(I 为 K 的跳点)。这里不认为从 H 到 K 能走,因为对角线有阻挡(这点和论文不一致,但和代码一致,因为如果 H 到 K 能直接到达,会走进 H 右边的阻挡区,大部分的 JPS 开源代码根据论文都认为 H 到 K能走,所以存在穿越阻挡的情况),如果需要 H 到 K 可走,则 K 为 H的强迫邻居(H 为 K的跳点)。

    定义二:跳点(jump point)
    (1)如果点 y 是起点或目标点,则 y 是跳点,例如图 2 中,S 是起点也是跳点,E 是目标点也是跳点;(2)如果 y 有邻居且是强迫邻居则 y 是跳点, 例 如 I 是跳点,请注意此类跳点和强迫邻居是伴生系,从上文强迫邻居的定义来看 n 是强迫邻居,x 是跳点,二者的关系是伴生的,例如图 2 中 K 的邻居只有I 是跳点,M 虽然也是 K的邻居,但 M 不是跳点,因为 K 不是 M 的强迫邻居;(3)如果 parent(y)到 y 是对角线移动,并且 y 经过水平或垂直方向移动可以到达跳点,则 y 是跳点,例如图 2 中 G 是跳点,因为 parent(G)为 S,S 到 G 为对角线移动,从 G 到跳点 I 为垂直方向移动,I 是跳点,所以 G 也是跳点。

    规则一:JPS 搜索跳点的过程中,如果直线方向(为了和对角线区分,直线方向代表水平方向、垂直方向,下文所说的直线均为水平方向和垂直方向)、对角线方向都可以移动,则首先在直线方向搜索跳点,再在对角线方向搜索跳点。
    规则二:(1)如果从 parent(x)到 x 是直线移动,n 是 x 的邻居,若有从 parent(x)到 n 的路径不经过 x 且路径长度小于或等于从 parent(x)经过 x 到 n 的路径,则走到 x 后下一个点不会走到 n;(2)果从 parent(x)到 x 是对角线移动,n 是 x 的邻居,若有从 parent(x)到 n 的路径不经过 x 且路径长度小于从parent(x)经过 x 到 n 的路径,则走到 x 后下一个点不会走到 n(相关证明见论文)。
    规则三:只有跳点才会加入 openset,因为跳点会改变行走方向,而非跳点不会改变行走方向,最后寻找出来的路径点也只会是跳点集合的子集。

    JPS 算法举例

    图二
    下面举例说明 JPS 具体的寻路流程。问题示例如上图所示,5*5 的网格,黑色代表阻挡区,S 为起点,E 为终点。JPS 要寻找从 S 到 E 的最短路径,首先初始化将 S 加入 openset。从 openset 取出 F 值最小的点 S,并从 openset 删除,加入 closedset,S 的当前方向为空则沿八个方向寻找跳点,在该图中只有下、右、右下三个方向可走,但向下遇到边界,向右遇到阻挡,因此都没有找到跳点,然后沿右下方向寻找跳点,在 G 点,根据上文定义二的第(3)条parent(G)为 S,praent(G)到 S 为对角线移动,并且 G 经过垂直方向移动(向下移动)可以到达跳点 I,因此 G 为跳点 ,将 G 加入 openset。从 openset 取出F 值最小的点 G,并从 openset 删除,加入 closedset,因为 G 当前方向为对角线方向(从 S 到 G 的方向),因此在右、下、右下三个方向寻找跳点,在该图中只有向下可走,因此向下寻找跳点,根据上文定义二的第(2)条找到跳点 I,将I 加入 openset。从 openset 取出 F 值最小的点 I,并从 openset 删除,加入closedset,因为 I 的当前方向为直线方向(从 G 到 I 的方向),在 I 点时 I 的左后方不可走且左方可走,因此沿下、左、左下寻找跳点,但向下、左下都遇到边界,只有向左寻找到跳点 Q(根据上文定义二的第(2)条)),因此将 Q 加入openset。从openset取出F值最小的点Q,并从openset删除,加入closedset,因为 Q 的当前方向为直线方向,Q 的左后方不可走且左方可走,因此沿右、左、左上寻找跳点,但向右、左上都遇到边界,只有向左寻找到跳点 E(根据上文定义二的第(1)条)),因此将 E 加入 openset。从 openset 取出 F值最小的点E,因为 E 是目标点,因此寻路结束,路径是 S、G、I、Q、E。

    注意,本文不考虑从 H 能走到 K 的情况,因为对角线有阻挡(这点和论文不一致,但和代码一致,因为如果 H 到 K能直接到达,会走进 H 右边的阻挡区,大部分的 JPS 开源代码根据论文都认为 H 到 K 能直接到达,所以存在穿越阻挡的情况),如果需要 H 到 K 能走,则路径是 S、G、H、K、M、P、E,修改跳点的计算方法即可。

    上述的 JPS 寻路效率是明显快于 A*的,原因在于:在从 S 到 A 沿垂直方向寻路时,在 A 点,如果是 A*算法,会将 F、G、B、H 都加入 openset,但是在 JPS中这四个点都不会加入 openset。对 F、G、H 三点而言,因为从 S、A、F 的路径长度比 S、F 长,所以从 S 到 F 的最短路径不是 S、A、F 路径,同理 S、A、 G 也不是最短路径,根据上文规则二的第(1)条,走到 A 后不会走到 F、G,所以 F、G 不会加入 openset,虽然 S、A、H 是 S 到 H 的最短路径,但因为存在S、G、H 的最短路径且不经过 A,据上文规则二的第(1)条,从 S 走到 A 后,下一个走的点不会是 H,因此 H 也不会加入 openset;对 B 点而言,根据上文规则三,B 不是跳点,也不会加入 openset,直接走到 C 即可。

    如下表所示为 A*和 JPS 在寻路消耗中的对比,D. Age: Origins、D. Age 2、StarCraft 为三个游戏龙腾世纪:起源、、龙腾世纪 2、星际争霸的场景图集合,M.Time 表示操作 openset 和 closedset 的时间,G.Time 表示搜索后继节点的时间。可见 A*大约有 58%的时间在操作 openset 和 closedset,42%时间在搜索后继节点;而 JPS 大约 14%时间在操作 openset 和 closedset,86%时间在搜索后继节点。避免在 openset 中加入太多点,从而避免过多的维护最小堆是 JPS 比 A*快的原因((最小堆插入新元素时间复杂度 log(n),删除最小元素后调整堆,时间复杂度也为 log(n))),实际上在从 S 到 E 的寻路过程中,进入openset 的只有 S、G、I、Q、E。
    图三

    JPS 五个优化算法

    1.JPS-Bit:位运算优化

    图四

    利用位运算优化的 JPS-Bit 的关键优化思路在于利用位运算来优化 JPS 中节点拓展的效率。下面以上图中的场景示例说明如何将位运算融合于 JPS 算法中,其中黑色部分为阻挡,假设当前位置为 I(标蓝位置),当前方向为右,位运算中使用 1 代表不可走,0 代表可走,则 I 当前行 B 的八位可以用八个 bit:00000100 表示,I 上一行 B-的八位可以用八个 bit:00000000 表示,I 的下一行 B+的八位可以用八个 bit:00110000 表示。在当前行寻找阻挡的位置可以用
    CPU 的指令__builtin_clz(B)(返回前导 0 的个数),即当前阻挡在第 5 个位置(从 0 开始)。寻找当前行的跳点可以用__builtin_clz(((B->>1) && !😎 ||((B+>>1) && !B+)) 寻找,例如本例中(B+>>1) && !B+为:(00110000 >> 1) &&11001111,即 00001000,而(B->>1) &&!B 为 00000000,所以__builtin_clz(((B->>1) && !😎 ||((B+>>1) && !B+)) 为__builtin_clz(00001000)为 4,所以跳点为第 4 个位置 M(从 0 开始)。注意论文中使用_builtin_ffs(((B-<<1) && !😎 ||((B+<<1) && !B+)),__builtin_ffs(x)返回 x 的最后一位 1 是从后向前第几位,比如 7368(1110011001000)返回
    4,因为论文对格子的 bit 编码采用小端模式,而这里对格子的 bit 编码采用大端模式。

    由于 JPS-Bit 使用运算效率更高的位运算和 CPU 指令运算来优化原始 JPS 节点扩展过程中的遍历操作,JPS-Bit 的算法效率高于原始的 JPS,实测中 JPS-Bit 的寻路时间比 JPS 缩短 5 倍左右。

    2.JPS-BitPrune:位运算与剪枝优化

    利用位运算和剪枝优化的 JPS-BitPrune 在 JPS-Bit 的基础上进一步进行剪枝优化,剪掉不必要的中间跳点(见定义二第(3)条定义),根据定义二,中间跳点在节点拓展过程中只具有简单的“承接”作用,不具备拓展价值,将中间跳点放入 openset 会增大扩展的次数,因此 JPS-BitPrune 将中间跳点全部删除,将中间跳点后继跳点中的非中间跳点的父跳点改为中间跳点的父跳点,可以有效避免冗余的节点拓展运算。

    拐点获取:值得一提的是,JPS-BitPrune 由于删除了中间跳点,因此 JPS- BitPrune 需要在搜索到完整的路径之后以一定的策略在最后寻得的路径中加入中间拐点,使得每两个相邻的路径节点之间都是垂直、水平、对角线方向可达的。对此,JPS-BitPrune 采用的具体方法如下:假设目前搜索到的路径为 start(jp1)、jp2、jp3…jpk…end(jpn),对每两个相邻的跳点 jpi、jpi+1,

    1. 如果 jpi、jpi+1 的 x 坐标或者 y 坐标相等,说明这两个跳点在同一个水平方向或垂直方向,可以直线到达,无需在这两个跳点之间加入拐点;
    2. 如果 jpi、jpi+1 的 x 坐标和 y 坐标都不相等,进行后续3 4 的判断
    3. 如果 x 坐标的差 dx(即 jpi的 x 坐标减去 jpi+1 的 x 坐标)和 y 坐标的差 dy 的绝对值相等,说明这两个跳点在对角线方向,也可以直线到达,无需在这两个跳点之间加入拐点;
    4. 如果x 坐标的差 dx 和 y 坐标的差 dy 的绝对值不相等,说明这两个跳点不在对角线方向,并且有可能不能直线到达(因为跳点附近有阻挡),此时 jpi、jpi+1 之间只需要加入一个从 jpi 出发离 jpi+1 最近的对角线上的点即可(jpi、jpi+1 不能水平、垂直、对角线到达,说明 jpi、jpi+1 之间一定存在被剪枝的中间跳点,只需要补上离 jpi+1 最近的一个中间跳点充当拐点即可,该拐点即为 jpi 沿对角线方向走min(dx,dy)步到达的点)。
      图5
      下面以上图的问题场景示例 JPS-BitPrune 如何在剪枝的同时进行寻路。起点为 S(坐标为(1,1),即 S(1,1)),节点 1、4、6 均为中间跳点:因为节点 2、 3 是满足定义二第(2)条的跳点,所以节点 1 是为了到达节点 2、3 的中间跳点,同理节点 4、6 也为中间跳点。在剪枝中间跳点之前,要将中间跳点的后继节点的父节点调整为该中间跳点的父节点。例如图中,节点 1 的后继跳点为节点 2、3、4,其中节点 4 也为中间跳点,删掉中间跳点中的节点 1 后,节点2、3 的父跳点由节点 1 改为节点 S,删除中间跳点中的节点 4 后,节点 4 的后继跳点 5 的父跳点由节点 4 改为节点 S(节点 4 的父跳点为节点 1,但节点 1 已经被删掉,因此回溯到节点 S),删除中间跳点中的节点 6 后,节点 6 的后继跳点 7 的父跳点由节点 6 改为节点 S(节点 6 的父跳点为节点 4,但节点 4 被删,节点 4 的父跳点节点 1 也被删,因此回溯到节点 S)。

    上述过程是简化的逻辑描述,实际运行中的做法是从节点 S 寻找跳点,首先找到中间跳点节点 1,然后在水平方向和垂直方向寻找到跳点节点 2、3,将节点 2、 3 的父跳点设为节点 S;继续沿对角线方向寻找跳点,走到节点 4 后,沿水平方向和垂直方向寻找到跳点节点 5,将节点 5 的父跳点设为节点 S;继续沿对角线方向寻找跳点,走到节点 6 后,沿水平方向和垂直方向寻找到跳点 7,将跳点 7的父跳点设为节点 S。因此 JPS-BitPrune 获得路径 S(1,1) 、节点 7(4,6)。

    因为路径中 S(1,1)无法垂直、水平、对角线方向走到节点 7(4,6),需要加入中间拐点,根据上述的拐点添加策略,有 dx 为 3,dy 为 5,需要从 S 沿对角线走 3步,即节点 6(4,4)可作为中间拐点,因此,在上图的示例中,JPS-BitPrune最后构建的完整路径为 S(1,1) 、节点 6(4,4) 、节点 7(4,6)。

    下面通过对比剪枝前后的 JPS 节点拓展的情况来说明剪枝操作的优化效率:

    • 场景一(无剪枝)
      如果不对中间跳点进行剪枝,那么从节点 S 寻路到节点 7 将经历如下过程:
    1. 从节点 S 搜索跳点,找到跳点节点 1,openset 此时只有节点 1;
    2. 从 openset 取出 F 值最小跳点节点 1,并搜索节点 1 的后继跳点,水平方向和垂直方向找到跳点节点 2、3,对角线方向找到跳点节点 4,此时 openset 有节点 2、3、4;
    3. 从 openset 取出 F 值最小跳点节点 4,并搜索节点 4 的后继跳点,水平和垂直方向找到跳点节点 5,对角线方向找到跳点 6
    4. 此时 openset 有节点 2、3、5、 6;从 openset 取出 F 值最小跳点节点 6,垂直方向找到跳点 7,此时 openset有节点 2、3、5、7;
    5. 从 openset 取出 F 值最小的跳点节点 7,为目的点,搜索结束,因此完整路径为节点 S(1,1)、节点 1(2,2) 、节点 4(3,3) 、节点 6(4,4) 、节点 7(4,6)。JPS 在到达目的节点 7 之前,需要接连拓展中间跳点 1,4,6。
    • 场景二(剪枝中间跳点)
      在剪枝中间跳点之后,从节点 S 寻路到节点 7 的流程得到了明显简化:
    1. 从节点 S 寻找跳点,首先找到中间跳点节点 1,然后在水平方向和垂直方向寻找到跳点节点 2、3,将节点 2、3 的父跳点设为节点 S;继续沿对角线方向寻找跳点,走到节点 4 后,沿水平方向和垂直方向寻找到跳点节点 5,将节点 5 的父跳点设为节点 S;继续沿对角线方向寻找跳点,走到节点 6 后,沿水平方向和垂直方向寻找到跳点 7,将跳点 7 的父跳点设为节点 S;继续沿对角线方向寻找跳点,遇到阻挡,搜索终止,此时 openset 有节点 2、3、5、7;
    2. 从 openset 取出 F 值最小的跳点节点 7,为目的点,搜索结束,此时获得的路径为 S(1,1) 、节点 7(4,6)。不同于无剪枝的 JPS 需要拓展中间跳点 1、4、6, 在 JPS-BitPrune 中,节点 1、4、6 作为中间跳点均被剪枝,有效避免了冗余的节点拓展,寻路效率得到大大提升。

    3. JPS-BitPre:位运算与预处理

    本优化中的预处理在一些文章被称为 JPS+。JPS-BitPre 和 JPS-BitPrunePre 都不支持动态阻挡,因为动态阻挡的出现会导致八个方向最多能走的步数发生变化,从而导致预处理的结果不再准确。利用位运算和预处理的 JPS-BitPre 依旧采用JPS-Bit 中的位运算,而其中的预处理则是对每个点存储八个方向最多能走的步数 step,这个 step 值将影响 JPS 中节点的拓展顺序和拓展“跨度”,加快寻路效率。由于预处理版本的 JPS 需要存储八个方向最多能走多少步,如果地图大小是 NN,每个方向最多能走的步数用 16 位数表示,则需要存储空间NN816bit,如果 N 为 1024,则大概需要存储空间为 16M,存储空间占用较大,使用该版本 JPS 时需要权衡是否以空间换时间,另外预处理的时间对小10241024 个格子的图可以在 1 秒内处理完,但对于 20482048 个格子的图需要一小时左右处理完。
    图六

    其中,step 值由跳点、阻挡、边界等决定,如果遇到跳点,则 step 为走到跳点的步数;否则 step 为走到阻挡或边界的步数。
    例如对上图 中的 N 点,向北最多走到节点 8,即 2 步;
    向南最多走到节点 4,即 4 步;
    向西最多走到节点 6,即 3 步;
    向东最多走到节点 2(节点 2 是满足定义二第(2)条的跳点),即 5 步;
    西北最多走到节点 7,即 2 步;
    东北最多走到节点 1(节点为 1 是上文定义二第(3)条定义的跳点),即 1 步;
    西南最多走到节点 5,即 3 步;
    东南最多走到节点 3(节点 3 是上文定义二第(3)条定义的跳点),即 3 步。

    以上图中的场景为例,要寻找从节点 N 到节点 T 的路径,JPS-BitPre 的寻路流程如下:

    1. 从 openset 取出节点 N, 从 N 沿八个方向寻找跳点,根据预处理得到的各方向最远可走的 step 值,可以快速确定八个方向最远能到达的节点{1,2,3,4, 5,6,7,8},如图所示,其中,节点 1、2、3 均为满足定义二的跳点,直接加入 openset,对于节点 4、5、6、7、8,首先判断终点 T 位于以 N为中心的南、西南、西、西北、北的哪部分,因为 T 位于西南方向,只有节点 5位于西南方向,因此节点 4、6、7、8 直接略过,在从 N 到 5 的方向上,N 可走 3 步,而 N 和 T 的 x 坐标差绝对值 dx 为 1,y 坐标差绝对值 dy 为 2,因此将从节点 N 到节点 5 方向上走 min(dx,dy)步即节点 11,加入 openset;
    2. 从 openset 取出 F 值最小节点 11,垂直方向找到跳点 T,加入 openset;
    3. 从openset取出F值最小节点T,为目的点,搜索结束,此时获得的路径为N(4,5)、节点 11(3,4) 、节点 T(3,3)。

    为了说明 JPS-BitPre 寻路的准确性与高效率,这里给出原始 JPS-Bit 从 N 到 T的寻路流程作为对比:

    1. 从 openset 取出节点 N 后,需要沿八个方向寻找跳点,节点 1、3、11 为上文定义二第(3)条定义的跳点,加入 openset,节点 2 为上文定义二的第(2)条定义的跳点,加入 openset;
    2. 从 openset 取出 F 值最小节点 11,垂直方向找到跳点 T,加入 openset;.
    3. 从 openset 取出 F 值最小跳点 T,为目的点,搜索结束,此时获得的路径也为
      N(4,5)、节点 11(3,4) 、节点 T(3,3)。

    对比发现,经过预处理的 JPS-BitPre 和只使用位运算的 JPS-Bit 最后寻得的路径是一样的,然而,由于 JPS-BitPre 无需在每一步节点拓展过程中沿各方向寻找跳点,其可以根据预处理得到的 step 值快速确定 openset 的备选节点,从而大大提升寻路效率。

    4.连通性判断

    图七

    如上图所示,起点 S 不可到达终点 E,然而寻路算法仍然会花费时间去寻找 S、E 之间的路径,而且失败情况下寻路花费的时间远大于成功情况下寻路花费的时间,因为失败情况下需要遍历所有的路径,才能确定两点不可达。因此为了避免这种情况,在每次寻路之前,判断起点和终点是否可达:如果起点和终点在同一连通区域,则起点和终点可达,否则不可达。只有起点和终点可达,才需要去寻路。

    连通计算方法:
    Step1. 当前连通区域编号 num 初始化为 0
    Step2. 对 Grid 网格每个点 current 重复以下工作:

    1. num++。
    2. 如果 current 是阻挡点,跳过。
    3. 如果 current 被访问过,跳过。
    4. current 的连通区域编号记为 num,标记已访问过。
    5. 宽度优先搜索和 current 四连通的所有 Grid 网格点,连通区域编号均记为 num,
      并标记已访问过。

    首先计算 Grid 网格的连通区域,算法如上面介绍,只能采用宽度优先搜索,深度优先搜索的递归层次太深,会导致栈溢出。按照算法,示例的点 S、1、2 的连通区域编号均为 1,点 3、4、E 的连通区域编号均为 2,S、E 连通区域编号不同,因此 S、E 不在同一连通区域,不需要寻找路径。算法在程序启动时计算一次即可,算法复杂度为 O(N), N 为 Grid 网格数目,运行时只需要查询两点是否在同一连通区域,算法复杂度为 O(1)。

    5.空间换时间

    openset 采用最小堆实现,最小堆的底层数据结构是一个数组,从最小堆中插入、删除时间复杂度为 O(logn)。除了删除还需要查找操作,每次找到一个跳点,都需要判断在最小堆中是否有,如果有,则判断是否更新 G 值、F 值、父跳点等,如果没有,则加入 openset。在最小堆的中查找操作时间复杂度 O(n),因此需要优化。closedset 存的是已经从 openset 中弹出的跳点,实际只需要对每个跳点加个标记即可,如果跳点打上标记,则表示是 closedset 中跳点,否则不是。

    综合上述需求,针对 1km1km 的地图,构建 2k2k 的二维数组 matrix,数组每个元素 pnode 均为一个指针,指针的对象类型包括节点 id、是否扩展过expanded(即是否在 closedset 中)、G 值、F 值、父跳点指针 parent、在最小堆中的索引 index 等 12 个 byte。如果地图(x,y)处是搜索到的跳点,首先检查在二维数组 matrix 对应的(x,y)处指针 pnode 是否为空,如果为空,表示该跳点之前未搜索过,从内存池 new 出一个跳点,将指针加到最小堆 openset 中,并在执行 shift up、shift down 操作之后,记录在最小堆中的索引 index;如果不为空,则表示该跳点之前搜索过,首先检查 expand 标记,如果为真,则表示在closedset 中,直接跳过该跳点;否则表示在 openset 中,通过 matrix(x,y)记录的在 openset 中的索引 index 找到对应的指针,检查 matrix(x,y)和openset(index)的指针是否相等进行二次确认,然后检查判断是否需要更新 G值、F 值、父跳点等,采用空间换时间的方法可以将 openset 和 closedset 中查找操作降为 O(1)。游戏中有很多场景,无需为每个场景构建一个 matrix,以最大的场景的大小构建一个 matrix 即可。

    6. 多线程支持

    游戏服务器普遍采用单进程多线程架构,多线程下,不能对 JPS 寻路加锁,否则寻路串行化,失去了多线程的优势,为了支持多线程 JPS 寻路,需要将一些变量声明为线程独有 thread_local,例如上文提到的为了优化 openset 和 closedset的查找速度,构建的二维跳点指针数组 matrix。该数组必须为线程独有,否则,不同线程在寻路时,都修改 matrix 元素指向的跳点数据,例如 A 线程在扩展完跳点后,将 expanded 标记为真,B 线程再试图扩展该跳点时,发现已经扩展过,就直接跳过,导致寻路错误。

    JPS内存优化算法

    1.分层

    JPS 的地图格子粒度如果采用 0.5m0.5m,每个格子占 1bit,则 1km1km 的地图占用内存 2k2k/8 个 byte,即 0.5M;为了向上、向下也能通过取 32 位数获得向上、向下的 32 个格子阻挡信息,需要存将地图旋转 90 度后的阻挡信息;上文 JPS 优化之四:不可达两点提前判断,需要存连通信息,假设连通区数目最多 15 个,则需内存 2k2k/2 个 byte,即 2m,则内存为:原地图阻挡信息 0.5m、旋转地图阻挡信息 0.5m、连通区信息 2m,即 3m。另外,上文提到用空间换时间的方法,为了优化 openset 和 closedset 的查找速度,构建二维跳点指针数组 matrix。1km1km 的地图,格子粒度为 0.5m0.5m,构建出的 matrix 指针数组大小为 2k2k4byte 即为 8m,为了支持多线程,该 matrix 数组必须为thread_local,即线程独有,16 个线程共需内存 16*8m 即为 128m,内存空间太大,因此需要优化这部分内存。

    首先将 2k2k 分成 100100 的块,即 2020 个块,2020 个块为第一层数组firLayerMatrix,100100 为第二层数组 secLayerMatrix,firLayerMatrix 的400 个元素为 400 个指针,每个指针初始化为空,当遍历到的跳点属于firLayerMatrix 中 (x,y) 的 块 时 , 则 从 内 存 池 new 出 100100*4byte 的secLayerMatrix,secLayerMatrix 每个元素也是一个指针,指向一个从内存池new 出来的跳点。

    例如,搜索 2k2k 的地图时,在(231,671)位置找到一个跳点,首先检查firLayerMatrix 的(2,6)位置指针是否为空,如果为空,则 new 出 1001004byte的 secLayerMatrix,继续在 secLayerMatrix 查找(31,71)位置检查跳点的指针是否为空,如果为空,则从内存池 new 出来跳点,加入 openset,否则检查跳点的 expanded 标记,如果标记为真,表示在 closedset 中,直接跳过该点,否则表示在 openset 中,判断是否更新 G 值、F 值、父节点等。因为游戏中 NPC寻路均为短距离寻路,JPS 寻路区域最大为 8080,一个 secLayerMatrix 是100100 , 因 此 只 需要 一 个 secLayerMatrix ,则两层 matrix 大小为:20204byte+100100*4byte 即为 0.04m。

    所以 16 个线程下,总内存为:原地图阻挡信息 0.5m、旋转地图阻挡信息 0.5m、连通区信息 2m、两层 matrix0.04m*16,共 3.64M,游戏中场景最多不到 20个,所有场景 JPS 总内存为 72.8M。

    2.内存池

    在 JPS 搜索过程中,每次将一个跳点加入 openset,都需要 new 出对应的节点对象,节点对象中存节点 id、父节点、寻路消耗等共 12 个 byte,为了减少内存碎片,以及频繁 new 的时间消耗,需要自行管理内存池,每次 new 节点对象时,均从内存池中申请,内存池详解请见下文服务器内存优化,为了防止内存池增长过大,需要限制搜索步数.

    本文的内存池共有两个:
    一,跳点的内存池,初始大小为 800 个跳点,当 new 的跳点数目超出 800 个,即停止寻路,因为服务器用 JPS 进行 NPC 的寻路,NPC 不会进行长距离寻路,假设 NPC 寻路上限距离是 20m,则寻路区域面积是 40m40m,格子数 8080即 6400,经统计跳点数目占所有格子数目的比例不到 1/10, 即跳点数目少于640,因此 800 个跳点足够使用,800 个跳点共占内存 800byte12,即为 9.6k,忽略不计;
    二,secLayerMatrix 指向的 100
    1004byte 的内存池,因为每次寻路都需要至少一个 secLayerMatrix,如果每次寻路都重新申请,寻路完后再释放,会造成开销,因此 secLayerMatrix 指向的 100100*4byte 的空间也在内存池中,申请时,从内存池拿出,释放时,放回内存池即可,secLayerMatrix 内存池占内存0.04m。

    路径优化

    如下图所示,绿色格子为起点,红色格子为终点,灰色格子为跳点,蓝线 为 JPS 搜出来的路径,灰色虚线为搜索过程。可以看出,从绿色格子到红色格子可以直线到达,而 JPS 搜索出来的路径却需要转折一次,在游戏表现上,会显得比较奇怪。因此在 JPS 搜索出来路径后,需要对路径进行后处理。
    图九
    比如 JPS 搜出来的路径有 A、B、C、D、E、F、G、H 八个点,走到 A 时,需要采样检查 A、C 是否直线可达,如果 A、C 直线可达,再检查 A、D 是否直线可达,如果 A、D 直线可达,继续检查 A、E,如果 A、E 直线不可达,则路径优化为 A、D、E、F、G、H,走到 D 时,再检查 D、F 是否直线可达,如果 D、F 直线可达,继续检查 D、G,如果 D、G 直线不可达,则路径优化为 A、D、F、G、 H。依此类推,直到走到 H。因为采样检查的速度很快,大约占 JPS 寻路时间的1/5,而且只有当走到一个路点后,才采样检查该路点之后的路点是否可以合并,将采样的消耗平摊在行走的过程中,因此采样的消耗可以忽略。

    说明:此文参考《仙剑奇侠传 online》游戏后台优化。

    展开全文
  • JPS/JPS+ 寻路算法

    千次阅读 2020-09-01 16:38:05
    JPS 寻路算法(Jump Point Search) 实现原理 示例过程 JPS+(Jump Point Search Plus) 预处理 示例过程 总结 参考 概念 JPS(jump point search)算法实际上是对A* 寻路算法的一个改进,因此在...
  • 用于查询所有节点的jps或者集体执行某个命令,如关机,如重启,如删除文件
  • 1、我的 java 的 home 目录:/usr/local/java2、首先,我的环境变量配置是正确的,因为我使用 java -version 是可以看到我的实际使用的 java 环境的 3、但是我使用 jps 这个命令的时候就有问题: 4、网上给的说法...
  • 变频器说明书系列-jps-pda-pdh-pde.doc

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 83,446
精华内容 33,378
关键字:

jps