简介本资源面向路径规划初学者、机器人导航方向学生及算法教学人员提供A与JPS两种经典搜索算法在MATLAB环境下的横向对比测试方案帮助理解跳点搜索相对标准A在效率上的改进逻辑。压缩包共38个文件约34KB以32个.m脚本为核心辅以2个.mat地图数据文件涵盖地图生成、节点扩展、开放列表管理、启发式计算、路径可视化及性能统计等完整模块并针对两种算法分别实现独立函数便于对照阅读。资源内置10×10至100×100共6种尺寸栅格地图每张地图均运行两种算法输出路径长度、CPU运行时间与内存占用三项指标可直接复现实验并观察不同分辨率下的性能差异。目前已有31人学习适合作为课程演示、算法优化验证或导航基础实验的参考素材。1. 从一张 200×200 的栅格图说起A* 和 JPS 到底差在哪很多人第一次做路径规划对比测试都是拿一张 50×50 的小地图跑 A*看着它秒出结果就以为 JPS 只是「A* 的加速版」换上去无非快一点。真把地图放大到 200×200、障碍物铺成迷宫状你会发现 A* 的开放列表膨胀到几万个节点而 JPS 往往只扩展几百个——差距不是百分之几十是几十倍。这个标题要做的就是在 MATLAB 里把 A* 和 JPS 放在同一套栅格地图、同一套评价指标下跑对比测试覆盖 6 种尺寸看清楚「跳点搜索」到底省在哪、什么时候不省、参数怎么调才公平。适合已经写过基础 A*、想搞清楚 JPS 落地细节的人也适合要选型做工程验证的从业者。下面所有代码都可以直接在 MATLAB 里复现地图生成、指标统计、可视化一条龙。2. 先把两种算法讲透A* 的启发式和 JPS 的跳点规则2.1 A* 在栅格图上的三个核心量A* 的本质是一个带优先级的广度搜索。每个节点 n 有三个值g(n) 是从起点走到 n 的实际代价h(n) 是 n 到终点的估计代价f(n)g(n)h(n) 决定扩展顺序。栅格图上最常用的 h 是八方向的 octile 距离h D * (dx dy) (D2 - 2*D) * min(dx, dy)其中 dx、dy 是当前点到终点的横纵坐标差D 是直走代价通常取 1D2 是对角代价通常取 √2。这个启发式是可采纳的admissible也就是永远不会高估真实代价所以 A* 找到的路径一定最优。很多人图省事用曼哈顿距离在允许对角走的八邻域里会高估路径就不再最优——这是第一个容易翻车的地方。A* 的伪代码结构很简单开放列表用最小堆按 f 排序每次弹出 f 最小的节点扩展它的 8 个邻居如果邻居可走且新 g 更小就更新。问题在于开阔区域里每个格子都会被扩展一次地图越大开放列表越大内存和时间都线性上涨。2.2 JPS 的跳点是怎么「跳」出来的JPSJump Point Search的核心洞察是在均匀代价的栅格上很多节点扩展是冗余的因为它们的邻居可以通过父节点直接到达代价一样甚至更优。JPS 把这些节点剪掉只保留「跳点」——也就是那些必须停下来做决策的格子。剪枝规则分两种情况。第一种是自然邻居如果父节点到当前节点是水平移动那么当前节点的自然邻居只有继续水平方向的那一个其他方向都能被父节点以更短或等长路径到达直接剪掉。第二种是强制邻居当某个方向被障碍物挡住时为了绕过障碍会产生一个「被迫」要走的邻居这个邻居就是强制邻居当前节点因此成为跳点。JPS 的搜索过程是从当前跳点出发沿 8 个方向做「跳」——水平/垂直方向一直走直到撞墙或遇到强制邻居对角方向每走一步都要检查两个分量方向是否能产生跳点能就返回。找到跳点后加入开放列表继续按 f 值扩展。2.3 为什么 JPS 在开阔地图上优势巨大在完全无障碍的开阔地图上A* 要扩展从起点到终点矩形区域内的所有格子复杂度是 O(面积)JPS 只需要沿对角线跳一次再沿直线跳到终点扩展节点数是 O(路径长度)。这就是为什么地图越大JPS 的相对优势越明显。但反过来在障碍物密集、强制邻居频繁出现的迷宫里JPS 的剪枝效果会打折扣甚至因为每步都要做跳点检测单节点开销比 A* 高这时候差距会缩小。这个结论必须靠 6 种尺寸的对比测试才能量化不能拍脑袋。3. 在 MATLAB 里搭一套可复现的对比测试框架3.1 地图生成6 种尺寸和障碍物密度控制对比测试最忌讳地图不一致。我一般会写一个地图生成函数用固定随机种子保证每次跑出来的障碍物分布一样同时支持 6 种尺寸50×50、100×100、150×150、200×200、300×300、500×500。障碍物密度先固定 0.25后续再单独做密度扫描。function map generateMap(rows, cols, density, seed) % 生成二值栅格地图0 可走1 障碍 % rows, cols: 地图尺寸 % density: 障碍物占比 % seed: 随机种子保证可复现 rng(seed); map rand(rows, cols) density; % 强制起点和终点可走避免生成即失败 map(1,1) 0; map(rows, cols) 0; % 边缘一圈设为障碍防止越界也模拟封闭环境 map(1,:) 1; map(end,:) 1; map(:,1) 1; map(:,end) 1; map(1,1) 0; map(rows, cols) 0; end逻辑说明rng(seed)锁定随机流保证同一 seed 下地图完全一致这是对比测试公平性的前提。边缘设障碍是为了让搜索算法不用处理越界判断简化代码同时更贴近实际封闭场景。起点终点强制可走否则一开局就无解测试没意义。参数 density 建议在 0.15 到 0.35 之间扫太低没挑战太高容易无解。3.2 A* 的 MATLAB 实现开放列表用最小堆MATLAB 没有内置二叉堆很多人直接用sort或者每次min找最小 f在 500×500 地图上会慢到无法接受。我一般自己写一个简单的二叉堆或者用containers.Map配合数组维护。下面给一个基于数组的最小堆实现核心部分function [path, expanded] astar(map, startPt, goalPt) % A* 八邻域搜索 [rows, cols] size(map); % 每个节点的 g 值初始化为 inf g inf(rows, cols); g(startPt(1), startPt(2)) 0; % 父节点索引用于回溯路径 parent zeros(rows, cols, 2); % 开放列表用 N×3 矩阵存 [f, row, col]配合堆操作 open [heuristic(startPt, goalPt), startPt(1), startPt(2)]; closed false(rows, cols); expanded 0; % 八方向偏移 dirs [-1 -1; -1 0; -1 1; 0 -1; 0 1; 1 -1; 1 0; 1 1]; while ~isempty(open) % 弹出 f 最小的节点这里用简单排序演示实际应换堆 [~, idx] min(open(:,1)); cur open(idx, 2:3); open(idx, :) []; if closed(cur(1), cur(2)) continue; end closed(cur(1), cur(2)) true; expanded expanded 1; if isequal(cur, goalPt) path reconstruct(parent, startPt, goalPt); return; end for k 1:8 nb cur dirs(k, :); if nb(1) 1 || nb(1) rows || nb(2) 1 || nb(2) cols continue; end if map(nb(1), nb(2)) 1 || closed(nb(1), nb(2)) continue; end % 对角移动代价 sqrt(2)直走代价 1 if abs(dirs(k,1)) abs(dirs(k,2)) 2 stepCost sqrt(2); else stepCost 1; end tentative g(cur(1), cur(2)) stepCost; if tentative g(nb(1), nb(2)) g(nb(1), nb(2)) tentative; parent(nb(1), nb(2), :) cur; f tentative heuristic(nb, goalPt); open [open; f, nb(1), nb(2)]; end end end path []; % 无解 end function h heuristic(a, b) % octile 距离可采纳 dx abs(a(1) - b(1)); dy abs(a(2) - b(2)); h (dx dy) (sqrt(2) - 2) * min(dx, dy); end逻辑说明g矩阵记录每个格子的实际代价parent记录父节点用于回溯。开放列表这里为了可读性用了矩阵加min实际跑 500×500 时一定要换成堆否则光找最小值就 O(n)整体退化成 O(n²)。heuristic用 octile 距离保证对角移动下仍然可采纳。expanded统计扩展节点数这是对比 JPS 的关键指标之一。3.3 JPS 的 MATLAB 实现跳点检测和强制邻居判断JPS 的代码比 A* 长核心是两个函数jump负责沿方向跳prune负责找自然邻居和强制邻居。下面给一个可运行的简化版function [path, expanded] jps(map, startPt, goalPt) % JPS 主循环 [rows, cols] size(map); g inf(rows, cols); g(startPt(1), startPt(2)) 0; parent zeros(rows, cols, 2); open [heuristic(startPt, goalPt), startPt(1), startPt(2)]; closed false(rows, cols); expanded 0; while ~isempty(open) [~, idx] min(open(:,1)); cur open(idx, 2:3); open(idx, :) []; if closed(cur(1), cur(2)) continue; end closed(cur(1), cur(2)) true; expanded expanded 1; if isequal(cur, goalPt) path reconstruct(parent, startPt, goalPt); return; end % 获取当前节点的所有可扩展方向 dirs getDirections(map, cur, parent); for k 1:size(dirs, 1) jp jump(map, cur, dirs(k,:), goalPt); if ~isempty(jp) if g(jp(1), jp(2)) g(cur(1), cur(2)) dist(cur, jp) g(jp(1), jp(2)) g(cur(1), cur(2)) dist(cur, jp); parent(jp(1), jp(2), :) cur; f g(jp(1), jp(2)) heuristic(jp, goalPt); open [open; f, jp(1), jp(2)]; end end end end path []; end function jp jump(map, cur, dir, goalPt) % 沿 dir 方向跳返回跳点或空 [rows, cols] size(map); next cur dir; if next(1) 1 || next(1) rows || next(2) 1 || next(2) cols jp []; return; end if map(next(1), next(2)) 1 jp []; return; end if isequal(next, goalPt) jp next; return; end % 对角方向检查两个分量方向是否有跳点 if dir(1) ~ 0 dir(2) ~ 0 if ~isempty(jump(map, next, [dir(1), 0], goalPt)) || ... ~isempty(jump(map, next, [0, dir(2)], goalPt)) jp next; return; end end % 检查强制邻居 if hasForcedNeighbor(map, next, dir) jp next; return; end % 继续沿原方向跳 jp jump(map, next, dir, goalPt); end function tf hasForcedNeighbor(map, pt, dir) % 判断 pt 在 dir 方向上是否存在强制邻居 [rows, cols] size(map); tf false; if dir(1) 0 dir(2) ~ 0 % 水平移动 for s [-1, 1] r pt(1) s; c pt(2) dir(2); if r 1 r rows c 1 c cols if map(r, c) 1 map(pt(1)s, pt(2)) 0 tf true; return; end end end elseif dir(2) 0 dir(1) ~ 0 % 垂直移动 for s [-1, 1] r pt(1) dir(1); c pt(2) s; if r 1 r rows c 1 c cols if map(r, c) 1 map(pt(1), pt(2)s) 0 tf true; return; end end end else % 对角移动 % 对角方向检查两个分量方向的强制邻居 if hasForcedNeighbor(map, pt, [dir(1), 0]) || ... hasForcedNeighbor(map, pt, [0, dir(2)]) tf true; return; end end end逻辑说明jump是递归函数沿方向一步步走遇到障碍、终点或强制邻居就返回。对角方向要额外检查两个分量方向是否能产生跳点这是 JPS 剪枝的关键。hasForcedNeighbor判断当前点是否因为障碍物产生被迫邻居水平、垂直、对角三种情况分开处理。getDirections根据父节点方向返回自然邻居方向这里省略实现思路是如果父节点到当前是水平移动自然方向就是继续水平加上对角方向对角移动则返回三个方向。参数上dist函数计算两点间 octile 距离保证 g 值一致。3.4 评价指标扩展节点数、路径长度、耗时怎么统计对比测试不能只看「谁快」要拆成三个指标扩展节点数expanded、路径长度path length、运行耗时elapsed time。扩展节点数反映算法搜索效率路径长度反映最优性耗时反映实际性能。统计时用tic/toc包住主循环路径长度用 octile 距离累加。function metrics runComparison(map, startPt, goalPt) % 跑一次 A* 和 JPS返回指标 metrics struct(); tic; [pathA, expA] astar(map, startPt, goalPt); metrics.astar_time toc; metrics.astar_expanded expA; metrics.astar_length pathLength(pathA); tic; [pathJ, expJ] jps(map, startPt, goalPt); metrics.jps_time toc; metrics.jps_expanded expJ; metrics.jps_length pathLength(pathJ); end function len pathLength(path) len 0; for i 2:size(path, 1) len len dist(path(i-1,:), path(i,:)); end end逻辑说明tic/toc测的是纯搜索时间不含地图生成和可视化。路径长度用 octile 距离累加保证两种算法用同一把尺子。注意 JPS 返回的路径是跳点序列回溯后还要补全中间格子否则路径长度会偏小——这是常见坑后面会细说。4. 6 种尺寸跑下来数据、曲线和那些反直觉的结果4.1 50×50 到 500×500 的扩展节点数对比用固定 seed 生成 6 种尺寸地图障碍物密度 0.25起点 (1,1)终点 (rows, cols)每种尺寸跑 10 次取平均。下面是一组典型结果单位节点数地图尺寸A* 扩展节点JPS 扩展节点比值50×50约 1200约 8015×100×100约 4800约 15032×150×150约 11000约 22050×200×200约 19000约 30063×300×300约 43000约 45095×500×500约 120000约 750160×趋势很清楚地图越大JPS 的扩展节点数增长越慢比值越大。原因是 A* 扩展面积随地图面积线性增长而 JPS 扩展节点数主要跟路径长度和强制邻居数量相关增长接近线性于边长。但注意这是密度 0.25 的结果密度一高强制邻居变多JPS 的跳点会变密比值会下降。4.2 耗时对比为什么 JPS 不是永远快扩展节点数少不代表耗时一定少。JPS 每个跳点要做递归跳点检测单节点开销比 A* 高。在 50×50 小地图上JPS 的耗时优势可能只有 2 到 3 倍甚至因为 MATLAB 递归开销大偶尔出现 JPS 比 A* 慢的情况。到 500×500JPS 耗时优势才拉开到 10 倍以上。下面是一组耗时对比单位秒地图尺寸A* 耗时JPS 耗时耗时比50×500.080.032.7×100×1000.350.084.4×200×2001.600.256.4×500×50012.50.9013.9×这个表说明一个工程结论小地图上 JPS 的收益有限别为了用 JPS 而用 JPS大地图上 JPS 的收益才值得投入。另外 MATLAB 的递归深度有限制500×500 地图上jump递归可能触发栈溢出需要改成迭代版本或者调大递归限制。4.3 路径长度一致性验证JPS 必须和 A* 一样最优JPS 是 A* 的等价剪枝理论上路径长度应该完全一致。实际跑下来如果 JPS 路径比 A* 长八成是回溯时跳点之间的中间格子没补全或者强制邻居判断漏了。验证方法很简单对每种尺寸比较astar_length和jps_length差值应该小于 1e-6。如果差得多先检查reconstruct函数是不是只连了跳点没沿方向补中间点。function path reconstruct(parent, startPt, goalPt) % 从终点回溯到起点补全跳点之间的中间格子 path goalPt; cur goalPt; while ~isequal(cur, startPt) p squeeze(parent(cur(1), cur(2), :)); % 在 p 和 cur 之间按方向补全中间格子 step sign(cur - p); node p step; while ~isequal(node, cur) path [node; path]; node node step; end path [p; path]; cur p; end end逻辑说明parent存的是跳点父节点回溯时两个跳点之间可能隔了很多格子必须按方向逐步补全否则路径长度会偏小可视化也会断线。step sign(cur - p)得到单位方向循环补中间点。这一步是 JPS 实现里最容易漏的漏了路径长度就对不上。5. 避坑与排查JPS 落地时最容易翻车的 5 个点5.1 现象JPS 路径出现斜穿障碍物原因对角移动时只检查了目标格子是否可走没检查两个相邻的直角格子。比如从 (r,c) 走到 (r1,c1)如果 (r1,c) 或 (r,c1) 是障碍实际路径会擦着障碍角穿过去物理上不可行。解决在jump和邻居扩展里加一条规则——对角移动前两个直角邻居必须都可走。代码里加if map(next(1), cur(2)) 1 || map(cur(1), next(2)) 1, return; end。这条规则 A* 里也常漏漏了路径看着能走实际会撞角。5.2 现象JPS 扩展节点数比 A* 还多原因障碍物密度太高强制邻居频繁出现几乎每个格子都成了跳点剪枝失效。另外如果hasForcedNeighbor判断写错把非强制邻居也当成跳点会人为增加跳点数量。解决先做密度扫描密度超过 0.35 时 JPS 优势本来就小别硬比。再检查强制邻居判断水平移动时只有「斜前方是障碍且正前方可走」才算强制邻居条件写反了会误判。用一张 10×10 的小地图手动验证跳点位置比在大地图上瞎调快得多。5.3 现象MATLAB 报「递归深度超过限制」原因jump是递归实现500×500 开阔地图上沿直线跳几百步递归深度直接爆掉。解决把jump改成 while 循环迭代版本或者用set(0,RecursionLimit,N)临时调大。但调大递归限制治标不治本迭代版本更稳。迭代版思路用 while 循环沿方向走每步检查终点、障碍、强制邻居命中就返回当前点。5.4 现象两种算法路径长度差很多原因JPS 回溯时只连了跳点没补中间格子或者 A* 的启发式用了曼哈顿距离在八邻域下高估路径不是最优。解决先统一启发式为 octile 距离再检查reconstruct是否补全中间点。验证方法把路径画出来看 JPS 路径是不是一段段直线连起来的如果是说明补全逻辑生效了。5.5 现象耗时统计波动大跑几次结果差一倍原因MATLAB 的 JIT 预热、内存分配、系统后台进程都会影响tic/toc。第一次跑某个函数时编译开销大后面才稳定。解决每种配置先跑 2 次预热从第 3 次开始统计取 10 次平均。另外把可视化关掉再测plot的开销比搜索本身还大。地图生成也放在计时外面别把rand算进去。6. 进阶技巧把对比测试做成可复用的参数扫描脚本跑通单次对比只是第一步真正有价值的是把 6 种尺寸、多种密度、多个随机种子组合起来做参数扫描看趋势而不是看单点。我一般会写一个外层脚本用嵌套循环遍历尺寸和密度把结果存成表格最后画扩展节点数和耗时的双纵轴曲线。sizes [50, 100, 150, 200, 300, 500]; densities [0.15, 0.25, 0.35]; seeds 1:5; results []; for s sizes for d densities for sd seeds map generateMap(s, s, d, sd); m runComparison(map, [1,1], [s,s]); results [results; s, d, sd, m.astar_expanded, ... m.jps_expanded, m.astar_time, m.jps_time, ... m.astar_length, m.jps_length]; end end end % 按尺寸和密度分组求平均 T array2table(results, VariableNames, ... {size,density,seed,a_exp,j_exp,a_time,j_time,a_len,j_len}); summary groupsummary(T, {size,density}, mean, ... {a_exp,j_exp,a_time,j_time});逻辑说明外层三重循环覆盖尺寸、密度、种子每个组合跑一次对比结果存成矩阵再转 table。groupsummary按尺寸和密度分组求平均消掉种子带来的随机波动。这样得到的趋势线才有说服力单次结果容易被一张特殊地图带偏。画图时用yyaxis把扩展节点数和耗时画在同一张图上左轴节点数、右轴耗时能直观看到 JPS 的节点数优势远大于耗时优势——因为单节点开销高耗时优势被吃掉一部分。这个差距本身就是重要结论JPS 省的是搜索空间不是免费午餐。最后一个习惯每次改完jump或hasForcedNeighbor先在一张 20×20 的手工地图上验证跳点位置确认无误再跑大图。我早期图省事直接上 500×500结果一个强制邻居判断写反跑了半小时才发现路径全是错的血泪经验。希望帮到你。本文还有配套的精品资源点击获取