简介：本资源面向路径规划初学者、机器人导航方向学生及算法教学人员，提供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 是直走代价（通常取 1），D2 是对角代价（通常取 √2）。这个启发式是可采纳的（admissible），也就是永远不会高估真实代价，所以 A* 找到的路径一定最优。很多人图省事用曼哈顿距离，在允许对角走的八邻域里会高估，路径就不再最优——这是第一个容易翻车的地方。

A* 的伪代码结构很简单：开放列表用最小堆按 f 排序，每次弹出 f 最小的节点，扩展它的 8 个邻居，如果邻居可走且新 g 更小就更新。问题在于，开阔区域里每个格子都会被扩展一次，地图越大，开放列表越大，内存和时间都线性上涨。

2.2 JPS 的跳点是怎么「跳」出来的

JPS（Jump 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 次取平均。下面是一组典型结果（单位：节点数）：

趋势很清楚：地图越大，JPS 的扩展节点数增长越慢，比值越大。原因是 A* 扩展面积随地图面积线性增长，而 JPS 扩展节点数主要跟路径长度和强制邻居数量相关，增长接近线性于边长。但注意，这是密度 0.25 的结果，密度一高，强制邻居变多，JPS 的跳点会变密，比值会下降。

4.2 耗时对比：为什么 JPS 不是永远快

扩展节点数少不代表耗时一定少。JPS 每个跳点要做递归跳点检测，单节点开销比 A* 高。在 50×50 小地图上，JPS 的耗时优势可能只有 2 到 3 倍，甚至因为 MATLAB 递归开销大，偶尔出现 JPS 比 A* 慢的情况。到 500×500，JPS 耗时优势才拉开到 10 倍以上。下面是一组耗时对比（单位：秒）：

这个表说明一个工程结论：小地图上 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) 走到 (r+1,c+1)，如果 (r+1,c) 或 (r,c+1) 是障碍，实际路径会擦着障碍角穿过去，物理上不可行。

解决：在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，结果一个强制邻居判断写反，跑了半小时才发现路径全是错的，血泪经验。希望帮到你。

本文还有配套的精品资源，点击获取