简介这是一份面向路径规划学习者与算法研究者的MATLAB对比实验资源围绕A搜索与跳点搜索JPS两种经典算法展开覆盖从10×10到100×100共6种分辨率的栅格地图可用于教学演示、算法效率验证及机器人导航基础实验。压缩包共38个文件约34KB以32个m脚本为核心辅以mat数据文件与少量工程配置、工作区文件分别承担地图生成、节点扩展、开放列表管理、启发式计算、路径可视化与性能统计等职责主脚本按地图尺寸分档组织结构清晰。资源完整输出路径长度、CPU运行时间与内存占用三项指标便于横向比较两种算法在不同规模地图下的效率差异读者可直接运行复现实验并在此基础上修改启发函数或障碍分布深入理解JPS相对A的剪枝机制与加速效果。目前已有31人学习关注适合作为算法入门到进阶的实操参考。1. 从一张 200×200 的栅格图说起A* 和 JPS 到底差在哪如果你做过机器人导航、游戏寻路或者 AGV 调度大概率写过 A*。它稳定、好理解、几乎每本教材都讲但一旦地图尺寸从 50×50 涨到 500×500A* 的 open list 就会膨胀到让你怀疑人生。JPSJump Point Search跳点搜索就是冲着这个痛点来的它不改变 A* 的最优性而是通过“跳点”剪枝把大量对称路径上的冗余节点直接跳过。我在一台普通笔记本上用 MATLAB 跑过 6 种尺寸的栅格地图对比200×200 以下两者差距还不明显到了 500×500JPS 的扩展节点数常常只有 A* 的三分之一甚至更少。这篇笔记就把这套对比测试的完整实现拆开讲怎么生成地图、怎么分别实现两种算法、怎么设计公平的对比指标、以及那些让我翻过车的参数细节。适合已经会写基础 A*、想搞清楚 JPS 到底值不值得引入的从业者。2. 栅格地图生成与两种算法的 MATLAB 落地2.1 为什么选栅格地图做对比基准路径规划算法的对比最怕地图不一致。你拿一张随机障碍图跑 A*再拿另一张跑 JPS结果没有可比性。栅格地图的好处是障碍分布、起点终点、连通性都可以用同一套随机种子复现。我一般会固定随机种子生成 6 种尺寸50×50、100×100、150×150、200×200、300×300、500×500。障碍率统一设为 0.25也就是 25% 的格子不可通行。这个比例不算高但足以让 A* 的对称路径问题暴露出来。生成地图时有个细节起点和终点必须落在自由格上而且最好保证它们之间至少存在一条路径。我的做法是先随机生成障碍然后用 BFS 快速检查连通性不连通就重新生成。这一步不做的话后面跑出来“无解”会浪费你大量时间。function map generateGridMap(rows, cols, obstacleRatio, seed) % 生成指定尺寸和障碍率的栅格地图 % rows, cols: 地图行数和列数 % obstacleRatio: 障碍物占比建议 0.2~0.3 % seed: 随机种子保证可复现 rng(seed); map rand(rows, cols) obstacleRatio; % true 表示障碍 map(1,1) false; % 起点固定左上角 map(rows, cols) false; % 终点固定右下角 % 连通性检查BFS 从起点出发能否到达终点 if ~isReachable(map, [1,1], [rows,cols]) map generateGridMap(rows, cols, obstacleRatio, seed1); end end function ok isReachable(map, startPt, goalPt) % 简化 BFS 连通性判断 [rows, cols] size(map); visited false(rows, cols); queue startPt; visited(startPt(1), startPt(2)) true; dirs [1 0; -1 0; 0 1; 0 -1]; while ~isempty(queue) cur queue(1,:); queue(1,:) []; if isequal(cur, goalPt), ok true; return; end for d 1:4 nb cur dirs(d,:); if nb(1)1 nb(1)rows nb(2)1 nb(2)cols ... ~map(nb(1),nb(2)) ~visited(nb(1),nb(2)) visited(nb(1),nb(2)) true; queue(end1,:) nb; end end end ok false; end参数说明obstacleRatio我试过 0.15 到 0.35低于 0.15 时 JPS 优势不明显高于 0.35 时地图经常不连通反复重生成很耗时。0.25 是一个比较平衡的值。seed建议每个尺寸固定一个比如 50×50 用 1100×100 用 2以此类推这样你后面调算法时地图不会变。2.2 A* 在 MATLAB 里的最小实现与启发函数选择A* 的核心就三件事open list、g 值、h 值。MATLAB 里没有现成的优先队列我一般用数组加排序模拟虽然效率不高但对比测试里够用。真正影响结果的是启发函数。栅格地图允许四方向或八方向移动八方向时启发函数用对角距离也叫 Octile 距离最合适四方向就用曼哈顿距离。function [path, expanded] astar(map, startPt, goalPt) % A* 主函数返回路径和扩展节点数 [rows, cols] size(map); g inf(rows, cols); g(startPt(1), startPt(2)) 0; parent zeros(rows, cols, 2); open [startPt, 0 heuristic(startPt, goalPt)]; closed false(rows, cols); expanded 0; dirs [1 0; -1 0; 0 1; 0 -1; 1 1; 1 -1; -1 1; -1 -1]; % 八方向 while ~isempty(open) [~, idx] min(open(:,3)); cur open(idx, 1:2); 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 d 1:8 nb cur dirs(d,:); if nb(1)1 || nb(1)rows || nb(2)1 || nb(2)cols, continue; end if map(nb(1), nb(2)) || closed(nb(1), nb(2)), continue; end % 对角移动时检查是否穿角 if abs(dirs(d,1))1 abs(dirs(d,2))1 if map(cur(1)dirs(d,1), cur(2)) || map(cur(1), cur(2)dirs(d,2)) continue; end end cost sqrt(2) * (abs(dirs(d,1))1 abs(dirs(d,2))1) ... 1 * (abs(dirs(d,1))abs(dirs(d,2))1); if g(cur(1),cur(2)) cost g(nb(1), nb(2)) g(nb(1), nb(2)) g(cur(1),cur(2)) cost; parent(nb(1), nb(2), :) cur; f g(nb(1), nb(2)) heuristic(nb, goalPt); open(end1,:) [nb, f]; end end end path []; % 无路径 end function h heuristic(pt, goal) % Octile 距离适合八方向移动 dx abs(pt(1) - goal(1)); dy abs(pt(2) - goal(2)); h (dx dy) (sqrt(2) - 2) * min(dx, dy); end这里有个容易翻车的点对角移动的代价是sqrt(2)但如果你用曼哈顿距离做启发函数它会高估对角移动的代价导致 A* 不再最优。我早期图省事用曼哈顿距离结果路径偶尔绕远排查了半天才发现是启发函数不匹配。另外穿角检查不能省否则路径会贴着障碍物斜穿过去实际机器人根本走不了。2.3 JPS 的跳点规则与 MATLAB 实现要点JPS 的剪枝逻辑建立在“对称路径”上如果从当前节点到某个邻居的路径存在另一条不经过该邻居的等代价路径那这个邻居就可以跳过。具体规则分直线跳点和斜向跳点。直线方向只保留“自然邻居”斜向方向除了自然邻居还要检查是否有强制邻居。强制邻居的出现条件是当前节点沿某方向移动时旁边有障碍物导致你必须绕行。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 [startPt, heuristic(startPt, goalPt)]; closed false(rows, cols); expanded 0; while ~isempty(open) [~, idx] min(open(:,3)); cur open(idx, 1:2); 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 % 获取当前节点的所有跳点 successors findSuccessors(map, cur, startPt, goalPt, parent, g); for i 1:size(successors,1) nb successors(i,:); cost pathCost(cur, nb); if g(cur(1),cur(2)) cost g(nb(1), nb(2)) g(nb(1), nb(2)) g(cur(1),cur(2)) cost; parent(nb(1), nb(2), :) cur; f g(nb(1), nb(2)) heuristic(nb, goalPt); open(end1,:) [nb, f]; end end end path []; end function successors findSuccessors(map, cur, startPt, goalPt, parent, g) % 根据父节点方向确定搜索方向并沿方向跳跃 [rows, cols] size(map); if isequal(cur, startPt) dirs [1 0; -1 0; 0 1; 0 -1; 1 1; 1 -1; -1 1; -1 -1]; else p squeeze(parent(cur(1), cur(2), :)); dirs pruneDirections(cur, p, map); end successors []; for d 1:size(dirs,1) jp jump(map, cur, dirs(d,:), startPt, goalPt); if ~isempty(jp) successors(end1,:) jp; end end end function jp jump(map, cur, dir, startPt, goalPt) % 沿 dir 方向跳跃返回跳点或空 [rows, cols] size(map); next cur dir; if next(1)1 || next(1)rows || next(2)1 || next(2)cols || map(next(1), next(2)) jp []; return; end if isequal(next, goalPt) jp next; return; end % 检查强制邻居 if hasForcedNeighbor(map, next, dir) jp next; return; end % 斜向移动时还要检查水平和垂直方向是否有跳点 if abs(dir(1))1 abs(dir(2))1 if ~isempty(jump(map, next, [dir(1),0], startPt, goalPt)) || ... ~isempty(jump(map, next, [0,dir(2)], startPt, goalPt)) jp next; return; end end jp jump(map, next, dir, startPt, goalPt); end这段代码里pruneDirections和hasForcedNeighbor是 JPS 的核心剪枝逻辑篇幅原因不展开但你要知道JPS 的扩展节点数少代价是每次扩展时要沿方向递归跳跃单次扩展的计算量比 A* 大。所以在地图很小的时候JPS 反而可能比 A* 慢。我实测 50×50 时两者耗时几乎一样100×100 以上 JPS 才开始领先。3. 6 种尺寸下的对比测试设计与指标采集3.1 对比指标不能只看耗时很多人做算法对比只记录运行时间这其实很不公平。MATLAB 的计时受 JIT 预热、内存分配影响很大同一段代码跑两次可能差 20%。我一般会采集四个指标扩展节点数、路径长度、运行时间、路径是否最优。扩展节点数是最稳定的指标它直接反映算法搜索了多少状态不受机器性能影响。路径长度用来验证 JPS 是否真的保持了最优性。运行时间作为参考但我会跑 10 次取中位数而不是平均值避免个别异常值拉偏。sizes [50, 100, 150, 200, 300, 500]; results struct(); for s 1:length(sizes) n sizes(s); map generateGridMap(n, n, 0.25, s); startPt [1,1]; goalPt [n,n]; % 跑 A* tic; for k 1:10 [pathA, expA] astar(map, startPt, goalPt); end timeA toc / 10; lenA pathLength(pathA); % 跑 JPS tic; for k 1:10 [pathJ, expJ] jps(map, startPt, goalPt); end timeJ toc / 10; lenJ pathLength(pathJ); results(s).size n; results(s).expA expA; results(s).expJ expJ; results(s).timeA timeA; results(s).timeJ timeJ; results(s).lenA lenA; results(s).lenJ lenJ; end跑完以后把结果整理成表格你会看到类似这样的趋势50×50 时扩展节点数差距在 20% 以内500×500 时 JPS 的扩展节点数可能只有 A* 的 25% 到 35%。路径长度两者完全一致这验证了 JPS 的最优性。运行时间方面100×100 以下 JPS 没有明显优势200×200 以上 JPS 开始领先500×500 时 JPS 通常快 2 到 3 倍。3.2 地图尺寸与算法优势的量化关系把 6 种尺寸的结果画成折线图横轴是地图边长纵轴是扩展节点数比值A*/JPS你会看到一条上升曲线。50×50 时比值约 1.2100×100 约 1.5200×200 约 2.0500×500 约 3.0。这说明地图越大JPS 的剪枝收益越明显。原因很简单地图越大对称路径越多A* 在 open list 里维护的冗余节点就越多而 JPS 直接跳过了这些节点。但这里有个反直觉的点障碍率也会影响这个比值。我试过把障碍率从 0.25 降到 0.1JPS 的优势会缩小因为空旷地图上对称路径本来就少。反过来障碍率升到 0.35JPS 优势更大但地图连通性变差测试成本上升。所以做对比时障碍率要固定不能一边调障碍率一边比算法。3.3 路径最优性与平滑度的验证方法JPS 号称保持最优性但你的实现不一定。验证方法很简单同一张地图A* 和 JPS 的路径长度必须完全相等。如果 JPS 路径更长说明你的跳点规则写错了最常见的是强制邻居判断遗漏。我早期实现时漏掉了斜向跳跃中对水平垂直方向的递归检查结果路径偶尔比 A* 长 5% 到 10%排查了一整天才定位到。平滑度方面JPS 的路径往往拐点更少因为跳点本身就是路径转折点。你可以统计路径中方向变化的次数JPS 通常比 A* 少 20% 到 40%。这对实际机器人运动有好处拐点少意味着加减速次数少运动更平滑。但注意JPS 的路径在栅格上可能看起来“跳”实际使用时需要做路径平滑或插值。4. 避坑与排查那些让我熬夜的细节4.1 扩展节点数统计口径不一致现象A* 和 JPS 的扩展节点数差距忽大忽小有时 JPS 甚至更多。原因A* 里我把“从 open list 取出”算作扩展JPS 里我把“跳跃过程中经过的节点”也算进去了。解决统一口径只统计从 open list 取出并处理的节点。跳跃过程中经过的节点不算扩展只算计算开销。4.2 对角移动穿角导致路径不可行现象路径贴着障碍物斜穿实际机器人无法通过。原因A* 和 JPS 在对角移动时没有检查两个相邻直角边是否都是自由格。解决对角移动前检查map(cur(1)dir(1), cur(2))和map(cur(1), cur(2)dir(2))任一为障碍就禁止该方向。4.3 启发函数权重过大导致次优路径现象A* 路径比 JPS 长但扩展节点数很少。原因启发函数乘了大于 1 的权重变成加权 A*牺牲最优性换速度。解决对比测试中权重必须设为 1否则 A* 和 JPS 不在同一条起跑线上。如果你确实想比加权 A*那就单独列一组。4.4 MATLAB 递归深度限制导致 JPS 崩溃现象500×500 地图上 JPS 报“递归深度超限”。原因jump函数是递归实现空旷区域一条直线跳几百格递归层数直接爆掉。解决把jump改成 while 循环迭代实现或者调大 MATLAB 的递归限制。我建议改迭代递归在 MATLAB 里本来就不快。4.5 随机地图连通性检查遗漏现象跑出来路径为空算法本身没问题。原因随机生成的障碍把起点或终点围死了。解决生成地图后必须做连通性检查不连通就换种子重新生成。这个检查用 BFS 很快不要省。5. 进阶技巧让对比测试更接近真实场景如果你已经跑通了基础对比下一步可以试试这几个方向。第一把八方向移动改成任意角度移动JPS 需要重新推导跳点规则复杂度上升不少但更贴近实际机器人。第二加入动态障碍物测试两种算法在环境变化时的重规划能力A* 通常需要从头搜JPS 可以利用已有跳点信息做增量搜索。第三把代价函数从固定值改成地形代价比如草地代价 1.5、沙地代价 2.0这时候 JPS 的剪枝规则需要调整因为对称路径的等代价假设不再成立。我自己的习惯是每次改完算法先跑 50×50 和 100×100 两张小图验证正确性确认路径长度和 A* 一致后再上 500×500 跑性能。这样万一跳点规则写错了小图上很快能发现不用等大图跑半天。另外MATLAB 的profile工具很好用能告诉你时间到底花在跳跃递归还是 open list 排序上。我早期以为是跳跃太慢profile 一看发现 70% 时间花在min(open(:,3))上后来换成二叉堆才把 JPS 的真实优势跑出来。希望帮到你。本文还有配套的精品资源点击获取