前阵子在做园区低速物流车的全局路径模块甲方给过来的需求很直接在几百米见方的栅格地图上从库房门口到充电桩要能快速出一条不绕远、不震荡的路径同时嵌入式板卡上的CPU预算不高不能把核都吃满。最早用A*跑结果在开阔区域里节点扩张得让人头疼open list一度堆到几万个虽然最终路径能出来但每次重规划都肉眼可见地卡一下。后来把算法换成跳点搜索Jump Point Search行业里常叫JPS之后同样的地图、同样的起终点扩展节点数量直接少了两个数量级重规划从几百毫秒降到几十毫秒。这篇文章就把跳点搜索从原理、实现到优化的完整过程以及它在泊车路径规划和无人机路径规划这两类典型场景里的落地经验一次性讲透。这篇内容适合刚接触栅格路径规划的工程师、做机器人或无人驾驶决策模块的同学以及想把自己A代码升级一版但又不想引入复杂图搜索框架的人。你要是已经会A但觉得它在大地图上不够快或者你只听过“JPS快”但不知道它为什么快、怎么正确地把它写出来那接下来的内容应该能帮你省不少时间。1. 跳点搜索到底解决了一个什么问题1.1 A* 的冗余在哪里先用一句话回顾A*它维护一个open list从起点开始不断取f值最小的节点扩展f g hg是已经走过的实际代价h是从当前节点到终点的估计代价。在栅格地图里相邻网格的移动代价通常都相等于是问题就来了——当你在一个没有障碍的“大平原”上从左上往右下搜索时实际上有大量路径的代价是完全相同的。我举个直观的例子。假设从点(0,0)到点(5,5)只允许上下左右走那么任何一条“先向下走几步、再向右走几步”的排列组合只要步数相同代价就一样。A*只会机械地根据f值大小逐个扩展节点它并不知道“这条路走到中间换一下走的顺序其实和另一条路完全等价”。于是它就会把大量等价节点都塞进open list逐个评估、逐个弹出浪费在无意义的比较上。更麻烦的是地图越大、空旷区域占比越高这种冗余就越严重。我在一块800x600的随机障碍地图上测试过用经典A*搜索一条跨越约500个栅格的路径open list的峰值可以到三万以上这个过程产生的内存分配和优先队列调整开销直接成为性能瓶颈。1.2 对称性假设是JPS能省时间的根本JPS的出发点和A*完全不同既然在空旷区域里存在大量等代价路径那为什么还要把每一条都展开不如把那些“具有相同走向、只差前后顺序”的节点合并成一段直线只保留方向发生改变、或者被迫转弯的点这些点就叫“跳点”jump point。JPS依赖一个核心前提地图是网格化的并且每个格的移动代价一致否则“对称性”就不存在跳点剪枝也就不成立。所以它不是对A*的简单修补而是从问题本身的几何特性出发去掉了大量冗余搜索。正是这种“少扩展节点”的思路让JPS在高分辨率城市道路栅格、室内结构化环境、矿区平面图这类规则网格上有非常大的优势。它解决的不是“能不能找到路”而是“能不能在有限算力下更快地找到那条路”。1.3 它的适用边界和“不适合”的场合但也有必要把丑话说在前头。JPS并不是万能的。它适合的是“静态或半静态、网格规则、代价均一”的搜索空间。如果地图里障碍物频繁动态变化比如仓储机器人实时感知到行人不断移动那每次都要重新做JPS搜索这时候可以考虑JPS做预处理或者直接用D* Lite这类增量算法如果地图本身不是栅格比如自动驾驶里常用的道路级路网图那A*、Dijkstra反而更直接。另外JPS虽然收敛快但单次“跳跃”要检查很长的直线段上是否有障碍和强迫邻居在某些地图上跳跃检查的次数并不少。如果你地图很小、节点不多比如只有几十乘几十的局部规划A*已经够用就不必为了秀技术强行换JPS。2. 跳点搜索算法的核心原理拆解2.1 邻居定义和裁剪理解JPS前必须先建立一个概念每个节点在展开时都有一个“父节点方向”也就是它从哪个方向被走过来。基于这个方向可以把当前节点的邻居分成两类自然邻居和被剪枝邻居。这样说比较抽象我配合实际场景描述。假设你正沿着一个方向向东搜索走到某个栅格时你自然应该继续往东看同时如果东南或东北方向没有障碍阻挡也可以顺带看一下因为这些邻居不需要额外绕路。但在你身后方向的节点或者需要“折返”才能访问的邻居在对称等价路径的意义下就不必再考虑了直接裁剪掉。这就是JPS的“邻居裁剪”沿着来路的方向尽量少扩展把搜索精力集中在那些真正可能导致路径分叉的节点上。你可能觉得这有点像人为加了方向偏好但它的正确性依赖于对称性证明被裁掉的邻居总能通过某些等价路径以相同代价到达不会导致漏解。2.2 强迫邻居与跳点的判别如果只是裁剪邻居那JPS就退化成带方向约束的贪心搜索了它必须有办法知道“什么时候路径不能再继续直线走下去了”。这个关键角色叫强迫邻居forced neighbor。强迫邻居的定义用白话讲当前节点x沿着父节点方向继续前进时如果它的某个非自然邻居n由于另一侧存在障碍物导致你如果想去n最优路径必须经过x而不能从x的旁边绕过去那么n就是x的强迫邻居。一旦出现强迫邻居x就不再是一个可以被“跳过”的普通中间点而必须作为一个跳点加入open list。举一个最小例子你正从西往东走当前节点北侧是墙而东北方向那个格子在墙后面是可走的。那么你想从当前行的北侧绕到墙后面去只能先走到当前节点然后向东北方向切过去。这种情况下当前节点会产生一个强迫邻居搜索必须停下来把它记下来否则路径会漏。2.3 直线跳跃与对角线跳跃规则JPS的跳跃过程分两种沿直线方向跳跃和沿对角线方向跳跃。先看直线。如果从当前节点向西移动那就沿西方向逐格前进途中遇到两种情况需要停下来一是到达终点二是当前格子存在强迫邻居。还有一种情况是遇到障碍或越界那就返回空表示这个方向没有跳点。这里要注意直线跳跃不是真的要“看到整条线”而是每一步检查当前位置左右两侧是否有障碍导致强迫邻居这个过程本身要花点代价但远小于扩张节点。再看对角线。当父节点方向是斜向时要更复杂一些。比如从西南往东北方向斜着走那么理论上可以同时影响向北和向东两条直线方向。所以对角线跳跃在每前进一步时要先尝试沿水平分量方向跳跃如果找到了跳点或终点说明当前点需要被记为跳点相同的逻辑再检查垂直分量方向。只要两个直线分量里有任何一个找到有效跳点说明当前点就是对角线路径上的必经跳点。这一段逻辑是JPS最容易写错的地方。很多网上代码把对角线跳跃简化成单纯“斜着走到底”结果会漏掉大量必须拐弯的跳点导致路径并非最短。正确做法是先做两个分量的直线跳跃检查再决定是否继续向前斜走。3. 完整实现流程和关键代码逻辑3.1 地图表示和节点数据结构正式写代码之前先说清楚底层数据结构。JPS对地图的访问非常频繁所以地图表示强烈建议用一维数组而不是二维vector套vector。原因有两个一是内存连续对cache更友好二是坐标换算简单idx y * width x。检查一个格子的可通行状态时直接在数组里取bool速度比查两层容器快很多。节点的数据结构至少包含坐标、g值、f值、父节点指针以及从父节点进入当前节点的方向。我的做法是把方向用x和y两个int表示取值范围为{-1,0,1}这样方向和坐标就能统一计算。这里有个值得注意的小点JPS扩展一个跳点时往往会从多个父方向扫描到同一个跳点这会导致这个跳点的g值可能被多次更新。为了保持算法完整性我在实现中会让节点在g值被更优路径更新时重新加入open list哪怕它之前已经被弹出过。这一点和经典A*的“closed不放回”策略略有不同实测下来它对保证最优性有帮助代价是极低的重开比例。3.2 主搜索循环的伪代码级实现下面我把核心搜索流程按伪代码写到直接可看懂的程度。假设open是一个以f值为键的最小堆。function JpsSearch(start, goal): start.g 0 open.push(start) while open is not empty: cur open.popMinF() if cur goal: return reconstructPath(cur) // 不把cur塞closed而是用g值做节流 // 如果cur已经不是当前最优g就跳过 if cur.g bestG[cur.id]: continue expand(cur) function expand(cur): // 获取从父节点方向出发需要检查的方向集 directions getDirectionsByParent(cur) for direction in directions: jp jump(cur, direction, goal) if jp ! null: newG cur.g octileDistance(cur, jp) if newG bestG[jp.id]: bestG[jp.id] newG jp.parent cur open.push(jp)对应的跳跃函数是function jump(node, direction, goal): // 先尝试移动一步 next node direction if not walkable(next) or outOfBounds(next): return null if next goal: return next if hasForcedNeighbor(next, direction): return next if isDiagonal(direction): // 水平分量和垂直分量上分别寻找跳点 if jump(next, direction.x, 0) ! null: return next if jump(next, 0, direction.y) ! null: return next return jump(next, direction, goal)上面这段伪代码有一个工程细节要留意递归在搜索直线很长的时候会占用较多栈空间虽然多数地图问题不大但在嵌入式环境或超大栅格里最好改成循环式跳跃。我个人的做法是写成while循环并用一个局部变量保存当前位置判断到跳点或边界就退出。3.3 实测数据与肉眼可见的提速为了让你对“到底快多少”有个体感我在自己的台式机上跑了一组测试地图尺寸800x600障碍密度约10%起终点均在地图空旷区域搜索距离约500格。A*和JPS都用相同的最小堆和启发函数只比较路径搜索消耗和扩展节点数。数据只代表我的软硬件环境但数量级差异在大多数测试里都稳定。指标经典A*JPS备注扩展节点总数约28000约650有转折的跳点也要计入open list峰值约3000约80内存占用差异巨大单次搜索耗时约320ms约25msCO2编译路径长度876格876格两者一致均为最优路径长度完全一致这件事并不意外因为JPS保证不破坏A的最优性真正改变的是搜索过程中的计算量。在比较宽阔的区域里JPS经常连续跳几十格才停下来而A要一格一格地扩展在走廊型地图里两者的差距会被拉小因为走廊本身没有太多对称路径可以剪掉但JPS通常还是不会比A*差。4. 工程里真正能用到的几类优化4.1 提前终止和带权启发带权启发算是A*系算法里最省事的加速手段。在启发函数h前面乘一个大于1的系数ε会让算法更“贪心”更早地朝终点方向靠拢代价是路径可能不是严格最优。实际操作中ε取1.2到1.5时路径长度通常只增加百分之几但扩展节点能再少一半以上这种权衡在泊车和无人机场景里很有用因为后续还要做平滑甚至轨迹优化路径略微次优并不致命。JPS还有一个天然的提前终止条件当从open list中弹出的节点是终点时可以直接结束搜索不需要再处理队列里剩余节点。理论上为了保证最优性应该等待open list里最小的f值都不小于终点g值时才停止但我的实测结果是直接弹出终点就停绝大多数情况下得到的路径仍然是原问题最优解。因为JPS已经通过跳跃把大量后续路径压缩成了直线“跳点段”不太会出现那种“先撞见一条绕远路径、然后再发现更短路径”的情况。当然如果你追求严格的证明级最优可以保留f值对比判断多写几行代码而已。4.2 JPS 预处理思路与适用条件JPS在搜索时每次跳跃都要沿途扫描节点、检查强迫邻居这个扫描过程也有开销。如果能提前把每个节点朝各个方向“最远能跳到哪里”的信息离线算好搜索时就能O(1)拿到跳跃结果这就是JPS的思路。JPS的预处理会为每个节点存储四个主要方向上、下、左、右的跳跃距离以及对角线方向的跳跃距离。搜索过程中只需要查表就能知道沿当前方向能跳到哪个坐标不再需要逐格扫描。这样一来真正的在线搜索阶段快得惊人有时候扩展一个跳点只要几次查表和比较。但JPS有一个硬伤它极度依赖地图是静态的。一旦障碍物发生变化预处理表就必须局部甚至全部重建。对于泊车这种感知地图每次刷新都可能变化的场景JPS不能直接套用它更适合那种“地图固定不变、需要反复查询不同起终点”的应用比如楼宇内固定布局的AGV路径查询、或者游戏关卡里的离线寻路。4.3 数据结构、缓存和数据布局层面微调这段是工程细节但它们累加起来的效果往往比算法层面的优化更明显。第一个是open list的实现。std::priority_queue可以用但插入和弹出都会做堆调整如果地图上节点数量很大频繁调用会造成不小的开销。我自己比较喜欢用配对堆或者4-way heap并在节点数组上保存堆索引实现O(1)的“减小键值”操作。不过这是进阶优化初版先用优先队列跑通再考虑替换也不迟。第二个是判重和取g值。不要每次都用std::unordered_map存节点状态map的哈希计算和内存随机访问在底层是无形的坑。更快的办法是把地图尺寸作为固定大小数组每个栅格存自己的g值、bestG值以及当前是否在堆中。因为JPS的节点是可以和栅格位置一一对应的直接以坐标作为下标索引效率最高。第三个是方向枚举和内联。跳跃函数里会频繁调用isDiagonal、forcedNeighbor判断把这些函数写成inline或者在头文件里定义编译优化后效果非常可观。我曾在同样的地图上把编译器从O0切到O2后整体耗时下降了近4倍所以别小看“基础工程素养”。5. 在泊车路径规划里的落地经验5.1 从车位场景看栅格化和膨胀泊车路径规划通常需要先建立局部栅格图把超声波雷达或视觉感知到的障碍物投影到网格里。这里第一个关键问题是栅格分辨率。分辨率太高地图维度爆炸分辨率太低车辆宽度在栅格中没法准确表示。我在实际项目里常用的原则是栅格尺寸取车辆宽度的四分之一到五分之一。以一辆车宽约1.8m的小型车为例栅格边长可以取0.4m左右这样在转弯时既能保留足够精度又不至于让地图太大。当然如果做的是近距离揉库级别的精细规划分辨率需要提升到0.1m对应地图尺寸就要好好优化数据结构了。膨胀环节是另一个容易踩坑点。不能简单把车辆画成一个矩形然后栅格化因为车在旋转时扫过的外廓比直线行驶时要宽。一个稳妥的做法是取车辆半宽加最小安全距离作为膨胀半径然后对每个障碍格做圆形膨胀。JPS搜索出的路径自然就不会贴着墙根走给后续的运动控制留出纠偏空间。5.2 全局粗路径与运动学细规划的配合很多人以为泊车规划里把JPS的结果直接给执行器就行实际根本不行。JPS生成的是折线路径不满足车辆的非完整约束车不能原地转向更不可能走那个直角转弯。真正成熟的架构是两层规划上游用JPS在栅格地图上算出一条通行走廊或参考路径下游用Hybrid A*或者Reeds-Shepp曲线在走廊附近做运动学可行的精细轨迹搜索。JPS在这里的角色我更愿意叫它“可通行性预筛选器”。它花很短时间就告诉你“从车位出口到目标车位宏观上能不能过去、大概走什么路线”下游精细化算法只需在这条走廊附近搜索避免对整个地图做高维运动学搜索。算力节省非常明显尤其在一个大的地下车库场景里起终点相距一两百米时没有粗规划就直接上Hybrid A*会把CPU吃满。5.3 泊车场景里的陷阱和规避方案泊车感知地图有个明显特点动态障碍多车位边缘线和锥桶经常会在几秒内出现在不同位置。JPS本身不具备动态处理能力所以我的建议是给地图加一个“时间戳版本号”每次感知刷新后只对变化区域做局部栅格更新。如果变化区域不在当前粗路径的走廊范围就不需要触发全局重规划如果正好挡住了关键跳点就触发一次带权重的JPS重规划再把新的粗路径交给下游。另一个容易被忽略的问题是对称车位和通道的判别。在某些空旷的地下停车场JPS会发现大量对称可走路径导致它随机选择其中一条看似合理但出入不方便的路径。解决办法是在代价函数里加一项“靠近参考线”的软约束或者在下游Hybrid A*时用“终点朝向”做硬约束让最终轨迹的车头朝向符合实际泊入需求。单纯依赖JPS的几何最优并不等于驾驶习惯上的最优。6. 在无人机路径规划里的应用变形6.1 三维空间切成多层二维还是直接3D JPS无人机路径规划表面上是把JPS从二维搬到三维栅格但直接这么做会遇到几个麻烦三维对角方向数量暴涨从二维的8邻域变成三维的26邻域甚至更多剪枝规则变得非常复杂很多空域其实是“2.5维”不同高度层的可通行区域形态差异不大为两层之间的差异专门做三维跳跃性价比不高。因此我看到更多实用方案是“分层JPS”把空域按高度切层每一层都建立二维栅格在二维层面用JPS找到当前层的候选路径再用跨越层间的连接点把各层路径串起来。这样既保留了JPS快速搜索的优势又把复杂的三维空间分解成了若干个可管理的二维问题。如果飞行高度固定比如固定翼巡航那就几乎完全退化成二维规划JPS可以直接使用。当然如果做的是城市峡谷、楼宇间低空穿行这种强三维约束场景2.5维就不够用了。这时候可以尝试把三维体素地图按“水平投影高度连续性”规则压缩成带高度属性的二维地图规划出水平路径后再对每一段做高度升降可行性检查。这种方案在实现复杂度上比完全三维的JPS低很多也更稳定。6.2 航迹平滑和动力学约束二次处理不管是二维还是分层JPS出来的路径都是“走栅格中心连线”的折线无人机不能直接按它飞。每段航向突变点都需要平滑处理否则转弯时过载会超限姿态也容易被甩偏。我常用的做法是先用JPS输出关键航点然后用B样条或者贝塞尔曲线做几何平滑。平滑时需要对曲线加一个最大曲率约束保证转弯半径不小于无人机在该速度下的最小转弯半径。真正执行时再给飞控的轨迹跟踪模块下发带速度剖面的航点序列让每个航段的速度和转弯半径匹配。一个容易忽略的坑是平滑后的航迹可能被拉回到障碍物附近甚至穿过原本躲开的障碍边缘。所以平滑之后一定要做碰撞检测如果检测到穿障碍可以在该航段附近插入新的中间点或者把它标记为不可行让上层重新规划这一段。JPS的速度足够快这一段重规划的代价通常可以接受。6.3 动态障碍时的重新规划策略无人机在空中经常会遇到同一高度上突然出现的障碍物比如其他飞行器、突发的施工塔吊遮挡等。由于JPS没有A*那种增量更新能力一旦环境变化通常只能整个重来。好在JPS的重规划很快实际任务中可以采用“定时重规划事件触发重规划”的组合策略。定时重规划可以设在1到2秒一次因为飞行时走廊环境相对稳定事件触发则用于检测到前方规划路径被阻塞或当前位置偏离参考路径超过阈值时。事件触发时需要注意不要频繁地在同一个障碍附近反复重规划导致路径振荡可以在检测到同一障碍触发次数超过设定值后把该区域直接标记为临时禁飞区改变目标绕行方向。重规划的衔接也讲究度。不要每次重规划都把整条路径换掉而是保留当前正在执行的局部路径只对当前位置之后的部分做重规划再与剩余原路径做平滑融合。这个思路能显著减少无人机在空中的晃动我在地面仿真里的效果要比整条路径全换好得多。7. 常见问题与排查技巧实录7.1 算法跑挂、跑偏、跑得慢怎么办先说说跑挂。JPS最常见的情况就是递归跳跃没有正确判边界导致索引越界。我就犯过一次把越界判断放在可通行判断之后结果访问了非法内存程序在调试版不报错发布版随机崩排查了很久。建议所有跳跃函数第一步就做边界和可通行检查顺序不要颠倒。再说跑偏。路径明明存在但JPS绕了一个大圈。这种情况八成是强迫邻居的判定条件写错或者把对角线跳跃的分量检查漏掉了。可以在少量简单地图上手动画几组已知最优路径用断言把路径长度卡住这样回归测试能很快暴露规则和预期不符的问题。最后说跑得慢。如果JPS效率没有比A*提升通常有两个可能一是open list实现得特别差每次查找最小f都是线性扫描二是跳点被反复加入造成大量重复计算。你可以在调试模式打印扩展节点数和open list峰值如果扩展节点数明显多于地图中实际跳点数量就需要检查是否有方向集合计算方法的问题。7.2 一张查阅方便的排查参考表症状可能原因解决办法跳跃递归栈溢出地图过大、递归层次太深改用循环跳跃设置迭代上限路径明显绕路强迫邻居判定少考虑了斜向障碍按3x3局部对照规则自查补全方向集找不到终点但A*能找到跳点检查漏掉了终点判断在跳跃每一步都判断是否到达goal结果路径与A*的最优长度不一致带权启发系数过大将权重设回1.0验证工程场景保留1.1以下动态障碍更新后仍然穿过障碍栅格地图未正确更新或膨胀失效检查地图更新范围和膨胀代码调用时机扩展节点数反而超A*方向集未做裁剪几乎变成“无方向限制A*”严格实现父方向分析逐条对照JPS规则长时间卡顿后无结果起点或终点被困在障碍内部搜索前做起终点合法性检查找到最近可行点这张表是我调试JPS时最有用的一个东西。碰到问题先不用翻论文对着症状找原因基本能定位到百分之八九十的坑。还有一个排查技巧值得特别分享在开发阶段把JPS每轮找到的跳点都可视化出来并用箭头画出它们之间的跳跃关系。相比只看最终规划的曲线观察跳点树能让问题暴露得更加直接。哪一段多跳了、哪一段跳到了死角视觉上一眼就能看出来。8. 测试复盘与落地建议8.1 调参与验收的我的习惯如果你现在准备在自己的项目里引入JPS我的建议是不要一上来就追求花哨的优化。先实现一个“正确但朴素”的版本也就是严格按照论文的四个方向和对角线规则实现不做带权启发不搞JPS拿到一组可复现的测试数据比如地图尺寸、起终点坐标、障碍物种子记录下每轮搜索的扩展节点数和耗时作为后续优化的基准。基准测试非常重要。我自己曾因为直接加了带权启发导致路径长度与最优值偏差超过预期却完全察觉不到。后来回退对比才发现原因就藏在权重系数上。后续每次改动之后把“扩展节点数”“路径长度”“搜索耗时”三条曲线和基准版本对比很快就能判断改动是利是弊。8.2 几条真实教训第一JPS的“快”是建立在能够安全剪枝的条件上的。如果你把地图改成八邻域代价不一致或者允许斜穿障碍物夹角那对称性会被破坏跳点剪枝就不再成立。千万别为了省事让JPS走“捷径”穿过墙角路径安全性和算法正确性都会出问题。第二不要在主路径规划线程里做JPS重规划。即使JPS已经很快它仍然是计算密集型任务在嵌入式平台上可能会阻塞其他控制任务。我在项目中会用单独的规划进程配合共享内存传递最新地图和结果这样即使规划偶发超时也不会让车或无人机立刻失控。最后一条也是最想提醒你的JPS适合解决“从A走到B”的静态几何寻路它不能解决“怎么走更符合运动学”的问题更不能替代控制层的避障。合理的设计是让它作为规划链路里速度最快的第一环把粗路径快速算出来再交给更精细、更慢的算法。把不同算法的优势组合起来整个系统的效果才会真正落地。我个人在实际操作中体会最深的一点是JPS本身并不复杂多数失败都出在对“强迫邻居”这一个定义的理解上。你只要耐住性子把3x3的局部场景一个个画出来把所有方向情况列一遍代码自然就写对了。写完后再跑一遍最优长度验证之后想怎么优化、怎么加速都只是在往一个正确的地基上添砖加瓦。