简介这份资源面向路径规划初学者、机器人导航方向的学生与算法验证人员提供MATLAB环境下A与JPS跳点搜索两种算法的横向对比测试方案用于解决不同分辨率栅格地图下搜索效率差异难以直观量化的问题。压缩包共38个文件约34KB以32个m脚本为核心辅以mat数据文件与少量工程配置类文件涵盖地图生成、节点扩展、开放列表管理、启发式计算、路径可视化及性能统计等完整模块并针对A与JPS分别给出独立实现。资源内置10×10至100×100共6组栅格地图每张地图均运行两种算法输出路径长度、CPU运行时间与内存占用三项指标便于直接对比效率差异。目前已有31人学习。读者可将其用于教学演示、算法优化验证或机器人导航基础实验通过现成脚本快速复现实验、观察JPS相对A*的加速效果并在此基础上修改地图与启发函数开展进一步探究。1. 从一张 200×200 的栅格地图说起A* 和 JPS 到底差在哪如果你做过移动机器人或者游戏寻路大概率写过 A*。它逻辑清晰、扩展性好几乎成了路径规划的入门必修课。但当你把地图尺寸从 50×50 拉到 200×200甚至更大A* 的 open list 会迅速膨胀搜索时间肉眼可见地变长。这时候很多人会听到另一个名字JPSJump Point Search跳点搜索。它号称在规则栅格地图上能把 A* 的搜索节点数砍掉一个数量级速度提升几倍到几十倍。但“号称”和“实测”是两回事。这份 MATLAB 资源做的事情很直接在同一套栅格地图生成逻辑下分别实现 A* 和 JPS用 6 种不同尺寸的栅格地图做对比测试输出路径长度、搜索节点数、耗时等指标。它适合两类人一是正在选型、想知道 JPS 到底值不值得换的工程师二是已经会用 A*但想搞清楚 JPS 的“跳点”机制在代码层面怎么落地的人。下面我按“先跑通、再拆解、后避坑”的顺序把这份资源拆开讲。2. 环境准备与地图生成6 种尺寸怎么切、障碍率怎么控2.1 MATLAB 版本与目录结构这份资源对 MATLAB 版本要求不算苛刻R2018b 及以上都能跑因为用到的核心函数是zeros、inf、find、sortrows这类基础操作没有依赖工具箱。如果你用的是更老的版本主要检查两点containers.Map是否可用JPS 里用来做节点去重以及tic/toc计时精度是否够用。拿到资源后建议先按下面结构整理目录避免路径混乱project_root/ ├── main_compare.m % 主入口跑 6 种尺寸对比 ├── generate_map.m % 栅格地图生成 ├── astar_plan.m % A* 实现 ├── jps_plan.m % JPS 实现 ├── heuristic.m % 启发函数 └── utils/ ├── reconstruct_path.m % 回溯路径 └── plot_map.m % 可视化主入口只做三件事循环尺寸、调用两种算法、收集指标。这样拆的好处是你改地图生成逻辑时不会动到算法本体排查问题时能快速定位是“地图变了”还是“算法错了”。2.2 栅格地图生成的三个关键参数6 种尺寸通常取 50、80、100、150、200、300形成从小到大的梯度。地图生成的核心参数有三个尺寸N、障碍率obs_ratio、起点终点坐标。障碍率一般取 0.2 到 0.3太低没有区分度太高容易无解。function map generate_map(N, obs_ratio, seed) % N: 栅格边长 % obs_ratio: 障碍物占比 % seed: 随机种子保证可复现 rng(seed); map zeros(N, N); % 0 表示自由空间 obs_num round(N * N * obs_ratio); idx randperm(N * N, obs_num); map(idx) 1; % 1 表示障碍 map(1,1) 0; % 强制起点自由 map(N,N) 0; % 强制终点自由 end这里有个容易忽略的点randperm生成的障碍是均匀分布的但真实场景里障碍往往成簇。如果你想让测试更有说服力可以再加一个“障碍膨胀”步骤把随机障碍按一定概率向邻域扩散模拟连续墙体。不过要注意JPS 在成簇障碍下的优势比均匀障碍更明显因为跳点更容易跳过整片自由区域。提示固定seed是复现的前提。不同 seed 下 A* 和 JPS 的相对关系可能波动建议每个尺寸跑 5 到 10 个 seed 取平均而不是只看一次结果。2.3 起点终点的选取与对角线移动开关起点终点默认取左上角和右下角这是最远对角能充分暴露搜索空间差异。但如果你只关心局部避障可以把终点设在中间区域。另一个关键开关是“是否允许对角线移动”。允许对角线时A* 的启发函数要用对角距离也叫切比雪夫距离的变体JPS 的跳点规则也要相应调整。% 允许对角线移动时的启发函数 function h heuristic(node, goal, allow_diag) dx abs(node(1) - goal(1)); dy abs(node(2) - goal(2)); if allow_diag h (dx dy) (sqrt(2) - 2) * min(dx, dy); % 对角距离 else h dx dy; % 曼哈顿距离 end end参数allow_diag必须在地图生成、A*、JPS 三处保持一致否则对比就失去意义。我见过有人 A* 开了对角、JPS 没开结果 JPS 路径更长然后得出“JPS 不行”的结论这是典型的配置不一致翻车。3. A* 实现拆解open list 用数组还是优先队列3.1 节点结构与代价定义A* 的节点至少存四个字段坐标pos、g 值起点到当前实际代价、h 值当前到终点估计、父节点parent。MATLAB 里用结构体数组或者containers.Map都行但结构体数组在频繁增删时性能一般。常见做法是用一个N×N的矩阵存 g 值另一个矩阵存父节点索引open list 单独用一个动态数组维护。function [path, nodes_expanded, elapsed] astar_plan(map, start_pos, goal_pos, allow_diag) tic; [N, ~] size(map); g inf(N, N); g(start_pos(1), start_pos(2)) 0; parent zeros(N, N, 2); % 存父节点坐标 open [start_pos, heuristic(start_pos, goal_pos, allow_diag)]; closed false(N, N); nodes_expanded 0; while ~isempty(open) [~, idx] min(open(:,3)); % 取 f 最小 current open(idx, 1:2); open(idx, :) []; if closed(current(1), current(2)) continue; end closed(current(1), current(2)) true; nodes_expanded nodes_expanded 1; if isequal(current, goal_pos) break; end % 邻居扩展见下节 end elapsed toc; path reconstruct_path(parent, start_pos, goal_pos); endnodes_expanded是核心指标之一它直接反映搜索效率。A* 的nodes_expanded通常远大于 JPS因为 A* 会扩展大量“看起来有希望但最终没走”的节点。3.2 邻居扩展与代价更新邻居扩展是 A* 最耗时的部分。8 邻域下每个节点最多检查 8 个邻居。对角移动时要注意“切角”问题如果对角方向的两个正交邻居都是障碍则不允许走对角否则路径会穿墙。dirs [ -1 0; 1 0; 0 -1; 0 1 ]; if allow_diag dirs [dirs; -1 -1; -1 1; 1 -1; 1 1]; end for d 1:size(dirs, 1) nb current dirs(d, :); if nb(1) 1 || nb(1) N || nb(2) 1 || nb(2) N continue; end if map(nb(1), nb(2)) 1 || closed(nb(1), nb(2)) continue; end % 切角检查 if abs(dirs(d,1)) 1 abs(dirs(d,2)) 1 if map(current(1)dirs(d,1), current(2)) 1 || ... map(current(1), current(2)dirs(d,2)) 1 continue; end end step_cost norm(dirs(d, :)); tentative_g g(current(1), current(2)) step_cost; if tentative_g g(nb(1), nb(2)) g(nb(1), nb(2)) tentative_g; parent(nb(1), nb(2), :) current; f tentative_g heuristic(nb, goal_pos, allow_diag); open [open; nb, f]; end end这段代码里open用数组拼接每次插入都重新分配内存尺寸大了会明显拖慢。如果你要跑 300×300 以上建议改成预分配数组加指针或者用 MATLAB 的priorityqueue如果版本支持。不过对于这份资源的对比目的数组方式足够暴露 A* 和 JPS 的差距。3.3 路径回溯与可视化回溯就是从终点沿parent一路走到起点然后翻转。可视化时把地图、障碍、路径、扩展节点分别用不同颜色画出来能直观看到 A* 的“扇形”搜索区域和 JPS 的“跳跃”轨迹。function path reconstruct_path(parent, start_pos, goal_pos) path goal_pos; current goal_pos; while ~isequal(current, start_pos) p squeeze(parent(current(1), current(2), :)); if all(p 0) path []; % 无解 return; end path [p; path]; current p; end end可视化不是装饰它是排查“为什么这条路这么绕”的第一手段。很多时候你看一眼扩展节点的分布就知道启发函数是不是设得太保守了。4. JPS 实现拆解跳点规则与强制邻居怎么落地4.1 JPS 的核心思想只扩展“跳点”JPS 和 A* 最大的区别在于A* 扩展当前节点的所有合法邻居JPS 只扩展“跳点”。跳点的定义是沿某个方向一直走直到遇到障碍、边界或者出现“强制邻居”才停下来。强制邻居是指如果当前节点不拐弯就会错过一条更优路径的那个邻居。这个机制让 JPS 在开阔区域可以一步跳过几十个格子而不是逐格扩展。代价是实现复杂度上升尤其是强制邻居的判断逻辑写错一个条件就会导致路径不是最优甚至无解。4.2 水平与垂直方向的跳点搜索先看最简单的水平方向。从当前节点向右走如果遇到障碍或边界就停如果途中某个节点的上方或下方是障碍而斜上方或斜下方是自由空间那这个节点就是跳点。function jp jump_horizontal(map, current, dir, goal_pos) N size(map, 1); jp []; next current [0, dir]; while next(1) 1 next(1) N next(2) 1 next(2) N if map(next(1), next(2)) 1 return; end if isequal(next, goal_pos) jp next; return; end % 检查强制邻居上方或下方有障碍且斜向可走 if (next(1)-1 1 map(next(1)-1, next(2)) 1 ... next(2)dir 1 next(2)dir N map(next(1)-1, next(2)dir) 0) || ... (next(1)1 N map(next(1)1, next(2)) 1 ... next(2)dir 1 next(2)dir N map(next(1)1, next(2)dir) 0) jp next; return; end next next [0, dir]; end end垂直方向同理只是把行列互换。这两个函数是 JPS 的基础写完后要单独测试在一张只有边界障碍的空地图上从起点向右跳应该直接跳到终点所在列或边界。4.3 对角方向的跳点与递归检查对角方向最复杂。沿对角走一步后要分别检查水平和垂直方向是否能跳出跳点。如果能当前对角节点就是跳点否则继续对角走。function jp jump_diagonal(map, current, dir, goal_pos) N size(map, 1); jp []; next current dir; while next(1) 1 next(1) N next(2) 1 next(2) N if map(next(1), next(2)) 1 return; end if isequal(next, goal_pos) jp next; return; end % 对角节点的水平和垂直方向有跳点则当前节点是跳点 if ~isempty(jump_horizontal(map, next, dir(2), goal_pos)) || ... ~isempty(jump_vertical(map, next, dir(1), goal_pos)) jp next; return; end % 强制邻居检查 if (map(next(1)-dir(1), next(2)) 1 map(next(1)-dir(1), next(2)dir(2)) 0) || ... (map(next(1), next(2)-dir(2)) 1 map(next(1)dir(1), next(2)-dir(2)) 0) jp next; return; end next next dir; end end递归调用是 JPS 的性能关键也是 MATLAB 里最容易栈溢出的地方。如果地图很大且障碍稀疏对角跳跃会递归很多层。常见做法是加一个最大跳跃步数限制超过就强制返回避免卡死。4.4 JPS 主循环与 open list 维护JPS 主循环和 A* 类似区别在于邻居不是直接取 8 邻域而是对每个方向调用jump函数只有返回跳点才加入 open list。while ~isempty(open) [~, idx] min(open(:,3)); current open(idx, 1:2); open(idx, :) []; if closed(current(1), current(2)) continue; end closed(current(1), current(2)) true; nodes_expanded nodes_expanded 1; if isequal(current, goal_pos) break; end dirs get_dirs(current, parent, allow_diag); % 根据父节点方向裁剪 for d 1:size(dirs, 1) jp jump(map, current, dirs(d,:), goal_pos); if ~isempty(jp) ~closed(jp(1), jp(2)) tentative_g g(current(1), current(2)) norm(jp - current); if tentative_g g(jp(1), jp(2)) g(jp(1), jp(2)) tentative_g; parent(jp(1), jp(2), :) current; f tentative_g heuristic(jp, goal_pos, allow_diag); open [open; jp, f]; end end end endget_dirs是 JPS 的另一个关键它根据当前节点相对父节点的方向裁剪掉不可能产生最优路径的方向。比如你从左边走到当前节点那继续向左走没有意义因为那是回头路。这个裁剪能进一步减少跳点搜索次数。5. 对比测试与避坑为什么你的 JPS 有时比 A* 还慢5.1 指标采集与结果解读主入口跑完 6 种尺寸后至少收集四个指标路径长度、扩展节点数、耗时、是否找到路径。路径长度用欧氏距离累加扩展节点数直接读nodes_expanded耗时用toc。建议每个尺寸跑 10 次取中位数避免单次抖动。尺寸A* 节点数JPS 节点数A* 耗时(ms)JPS 耗时(ms)路径长度比50约 800约 1201281.00100约 3200约 30055221.00200约 13000约 700240651.00300约 29000约 11005801301.00路径长度比接近 1 说明两者都找到了最优路径在相同启发函数下。如果 JPS 路径明显更长大概率是跳点规则写漏了强制邻居导致某些方向提前停止。5.2 避坑JPS 常见的四个翻车点现象一JPS 找不到路径但 A能。* 原因通常是强制邻居判断条件写反了把“斜向可走”写成了“斜向是障碍”。解决方法是拿一张只有单个障碍的地图手动推演跳点应该出现在哪然后打印jump函数的返回值逐个比对。现象二JPS 路径比 A长。* 原因可能是对角跳跃时没有递归检查水平和垂直跳点导致漏掉了更优的拐点。检查jump_diagonal里是否同时调用了jump_horizontal和jump_vertical并且方向参数正确。现象三JPS 耗时反而比 A大。* 在小地图50×50 以下或者障碍极密的地图上JPS 的跳点搜索开销可能超过 A* 的逐格扩展。这不是 bug是特性。JPS 的优势在开阔大图地图越小、障碍越密优势越不明显。现象四MATLAB 递归栈溢出。对角跳跃在空旷区域会递归很多层。解决办法是给jump函数加一个max_jump参数比如 200 步超过就返回空让主循环继续从其他方向找。注意对比测试时一定要固定随机种子和障碍率。不同种子下 JPS 的节点数波动可能达到 30%只看一次结果容易得出错误结论。5.3 启发函数权重对两者的影响差异A* 和 JPS 都对启发函数敏感但敏感程度不同。把启发函数乘以一个大于 1 的权重加权 A*A* 的节点数会明显下降但路径可能次优。JPS 在加权后节点数下降幅度较小因为它本身已经跳过了大量节点。如果你追求实时性加权 A* 在中等地图上可能比标准 JPS 更划算如果你追求最优路径且地图很大JPS 更稳。% 加权启发weight 1 时偏向速度 h weight * heuristic(node, goal_pos, allow_diag);权重一般取 1.0 到 1.5超过 2.0 路径会明显绕远。建议在 100×100 和 200×200 两张图上分别试 1.0、1.2、1.5 三档看节点数和路径长度的权衡曲线。6. 进阶技巧把对比测试变成可复用的评估脚本跑通一次对比不难难的是每次改了算法或地图后能快速复现整套评估。我的习惯是把主入口改成一个函数输入是尺寸列表、障碍率列表、种子列表输出是一张汇总表。这样你换任何参数组合一行命令就能重跑。function results run_benchmark(sizes, obs_ratios, seeds) % sizes: 如 [50 80 100 150 200 300] % obs_ratios: 如 [0.2 0.3] % seeds: 如 1:10 results []; for N sizes for or obs_ratios for s seeds map generate_map(N, or, s); [~, n1, t1] astar_plan(map, [1 1], [N N], true); [~, n2, t2] jps_plan(map, [1 1], [N N], true); results [results; N, or, s, n1, t1, n2, t2]; end end end results array2table(results, VariableNames, ... {Size,ObsRatio,Seed,AstarNodes,AstarTime,JPSNodes,JPSTime}); end这个脚本跑完你可以直接用groupsummary按尺寸和障碍率聚合看平均节点数和平均耗时。如果 JPS 在某个尺寸下节点数突然跳变大概率是那个种子的地图出现了长走廊或大面积空旷区导致跳点搜索路径变长。这时候不要急着改算法先可视化那张地图确认是不是地图本身的问题。另一个实用技巧是加一个“路径平滑度”指标统计路径中拐点的数量。JPS 的路径拐点通常比 A* 少因为跳点天然倾向于走直线。如果你做的是机器人运动规划拐点少意味着更少的减速和转向实际执行时间可能比纯搜索时间更有优势。从那以后我每次做算法对比都强制先跑一遍固定种子的基准再换随机种子看波动范围。基准不稳后面的结论都是空中楼阁。希望这份拆解能帮你少走点弯路把 A* 和 JPS 的边界摸清楚再决定用哪个。本文还有配套的精品资源点击获取 
长河君 · 2026/10/18 17:21:18 · 阅读 1.2k A*与JPS路径规划对比：MATLAB实现与性能实测
简介这份资源面向路径规划初学者、机器人导航方向的学生与算法验证人员提供MATLAB环境下A与JPS跳点搜索两种算法的横向对比测试方案用于解决不同分辨率栅格地图下搜索效率差异难以直观量化的问题。压缩包共38个文件约34KB以32个m脚本为核心辅以mat数据文件与少量工程配置类文件涵盖地图生成、节点扩展、开放列表管理、启发式计算、路径可视化及性能统计等完整模块并针对A与JPS分别给出独立实现。资源内置10×10至100×100共6组栅格地图每张地图均运行两种算法输出路径长度、CPU运行时间与内存占用三项指标便于直接对比效率差异。目前已有31人学习。读者可将其用于教学演示、算法优化验证或机器人导航基础实验通过现成脚本快速复现实验、观察JPS相对A*的加速效果并在此基础上修改地图与启发函数开展进一步探究。1. 从一张 200×200 的栅格地图说起A* 和 JPS 到底差在哪如果你做过移动机器人或者游戏寻路大概率写过 A*。它逻辑清晰、扩展性好几乎成了路径规划的入门必修课。但当你把地图尺寸从 50×50 拉到 200×200甚至更大A* 的 open list 会迅速膨胀搜索时间肉眼可见地变长。这时候很多人会听到另一个名字JPSJump Point Search跳点搜索。它号称在规则栅格地图上能把 A* 的搜索节点数砍掉一个数量级速度提升几倍到几十倍。但“号称”和“实测”是两回事。这份 MATLAB 资源做的事情很直接在同一套栅格地图生成逻辑下分别实现 A* 和 JPS用 6 种不同尺寸的栅格地图做对比测试输出路径长度、搜索节点数、耗时等指标。它适合两类人一是正在选型、想知道 JPS 到底值不值得换的工程师二是已经会用 A*但想搞清楚 JPS 的“跳点”机制在代码层面怎么落地的人。下面我按“先跑通、再拆解、后避坑”的顺序把这份资源拆开讲。2. 环境准备与地图生成6 种尺寸怎么切、障碍率怎么控2.1 MATLAB 版本与目录结构这份资源对 MATLAB 版本要求不算苛刻R2018b 及以上都能跑因为用到的核心函数是zeros、inf、find、sortrows这类基础操作没有依赖工具箱。如果你用的是更老的版本主要检查两点containers.Map是否可用JPS 里用来做节点去重以及tic/toc计时精度是否够用。拿到资源后建议先按下面结构整理目录避免路径混乱project_root/ ├── main_compare.m % 主入口跑 6 种尺寸对比 ├── generate_map.m % 栅格地图生成 ├── astar_plan.m % A* 实现 ├── jps_plan.m % JPS 实现 ├── heuristic.m % 启发函数 └── utils/ ├── reconstruct_path.m % 回溯路径 └── plot_map.m % 可视化主入口只做三件事循环尺寸、调用两种算法、收集指标。这样拆的好处是你改地图生成逻辑时不会动到算法本体排查问题时能快速定位是“地图变了”还是“算法错了”。2.2 栅格地图生成的三个关键参数6 种尺寸通常取 50、80、100、150、200、300形成从小到大的梯度。地图生成的核心参数有三个尺寸N、障碍率obs_ratio、起点终点坐标。障碍率一般取 0.2 到 0.3太低没有区分度太高容易无解。function map generate_map(N, obs_ratio, seed) % N: 栅格边长 % obs_ratio: 障碍物占比 % seed: 随机种子保证可复现 rng(seed); map zeros(N, N); % 0 表示自由空间 obs_num round(N * N * obs_ratio); idx randperm(N * N, obs_num); map(idx) 1; % 1 表示障碍 map(1,1) 0; % 强制起点自由 map(N,N) 0; % 强制终点自由 end这里有个容易忽略的点randperm生成的障碍是均匀分布的但真实场景里障碍往往成簇。如果你想让测试更有说服力可以再加一个“障碍膨胀”步骤把随机障碍按一定概率向邻域扩散模拟连续墙体。不过要注意JPS 在成簇障碍下的优势比均匀障碍更明显因为跳点更容易跳过整片自由区域。提示固定seed是复现的前提。不同 seed 下 A* 和 JPS 的相对关系可能波动建议每个尺寸跑 5 到 10 个 seed 取平均而不是只看一次结果。2.3 起点终点的选取与对角线移动开关起点终点默认取左上角和右下角这是最远对角能充分暴露搜索空间差异。但如果你只关心局部避障可以把终点设在中间区域。另一个关键开关是“是否允许对角线移动”。允许对角线时A* 的启发函数要用对角距离也叫切比雪夫距离的变体JPS 的跳点规则也要相应调整。% 允许对角线移动时的启发函数 function h heuristic(node, goal, allow_diag) dx abs(node(1) - goal(1)); dy abs(node(2) - goal(2)); if allow_diag h (dx dy) (sqrt(2) - 2) * min(dx, dy); % 对角距离 else h dx dy; % 曼哈顿距离 end end参数allow_diag必须在地图生成、A*、JPS 三处保持一致否则对比就失去意义。我见过有人 A* 开了对角、JPS 没开结果 JPS 路径更长然后得出“JPS 不行”的结论这是典型的配置不一致翻车。3. A* 实现拆解open list 用数组还是优先队列3.1 节点结构与代价定义A* 的节点至少存四个字段坐标pos、g 值起点到当前实际代价、h 值当前到终点估计、父节点parent。MATLAB 里用结构体数组或者containers.Map都行但结构体数组在频繁增删时性能一般。常见做法是用一个N×N的矩阵存 g 值另一个矩阵存父节点索引open list 单独用一个动态数组维护。function [path, nodes_expanded, elapsed] astar_plan(map, start_pos, goal_pos, allow_diag) tic; [N, ~] size(map); g inf(N, N); g(start_pos(1), start_pos(2)) 0; parent zeros(N, N, 2); % 存父节点坐标 open [start_pos, heuristic(start_pos, goal_pos, allow_diag)]; closed false(N, N); nodes_expanded 0; while ~isempty(open) [~, idx] min(open(:,3)); % 取 f 最小 current open(idx, 1:2); open(idx, :) []; if closed(current(1), current(2)) continue; end closed(current(1), current(2)) true; nodes_expanded nodes_expanded 1; if isequal(current, goal_pos) break; end % 邻居扩展见下节 end elapsed toc; path reconstruct_path(parent, start_pos, goal_pos); endnodes_expanded是核心指标之一它直接反映搜索效率。A* 的nodes_expanded通常远大于 JPS因为 A* 会扩展大量“看起来有希望但最终没走”的节点。3.2 邻居扩展与代价更新邻居扩展是 A* 最耗时的部分。8 邻域下每个节点最多检查 8 个邻居。对角移动时要注意“切角”问题如果对角方向的两个正交邻居都是障碍则不允许走对角否则路径会穿墙。dirs [ -1 0; 1 0; 0 -1; 0 1 ]; if allow_diag dirs [dirs; -1 -1; -1 1; 1 -1; 1 1]; end for d 1:size(dirs, 1) nb current dirs(d, :); if nb(1) 1 || nb(1) N || nb(2) 1 || nb(2) N continue; end if map(nb(1), nb(2)) 1 || closed(nb(1), nb(2)) continue; end % 切角检查 if abs(dirs(d,1)) 1 abs(dirs(d,2)) 1 if map(current(1)dirs(d,1), current(2)) 1 || ... map(current(1), current(2)dirs(d,2)) 1 continue; end end step_cost norm(dirs(d, :)); tentative_g g(current(1), current(2)) step_cost; if tentative_g g(nb(1), nb(2)) g(nb(1), nb(2)) tentative_g; parent(nb(1), nb(2), :) current; f tentative_g heuristic(nb, goal_pos, allow_diag); open [open; nb, f]; end end这段代码里open用数组拼接每次插入都重新分配内存尺寸大了会明显拖慢。如果你要跑 300×300 以上建议改成预分配数组加指针或者用 MATLAB 的priorityqueue如果版本支持。不过对于这份资源的对比目的数组方式足够暴露 A* 和 JPS 的差距。3.3 路径回溯与可视化回溯就是从终点沿parent一路走到起点然后翻转。可视化时把地图、障碍、路径、扩展节点分别用不同颜色画出来能直观看到 A* 的“扇形”搜索区域和 JPS 的“跳跃”轨迹。function path reconstruct_path(parent, start_pos, goal_pos) path goal_pos; current goal_pos; while ~isequal(current, start_pos) p squeeze(parent(current(1), current(2), :)); if all(p 0) path []; % 无解 return; end path [p; path]; current p; end end可视化不是装饰它是排查“为什么这条路这么绕”的第一手段。很多时候你看一眼扩展节点的分布就知道启发函数是不是设得太保守了。4. JPS 实现拆解跳点规则与强制邻居怎么落地4.1 JPS 的核心思想只扩展“跳点”JPS 和 A* 最大的区别在于A* 扩展当前节点的所有合法邻居JPS 只扩展“跳点”。跳点的定义是沿某个方向一直走直到遇到障碍、边界或者出现“强制邻居”才停下来。强制邻居是指如果当前节点不拐弯就会错过一条更优路径的那个邻居。这个机制让 JPS 在开阔区域可以一步跳过几十个格子而不是逐格扩展。代价是实现复杂度上升尤其是强制邻居的判断逻辑写错一个条件就会导致路径不是最优甚至无解。4.2 水平与垂直方向的跳点搜索先看最简单的水平方向。从当前节点向右走如果遇到障碍或边界就停如果途中某个节点的上方或下方是障碍而斜上方或斜下方是自由空间那这个节点就是跳点。function jp jump_horizontal(map, current, dir, goal_pos) N size(map, 1); jp []; next current [0, dir]; while next(1) 1 next(1) N next(2) 1 next(2) N if map(next(1), next(2)) 1 return; end if isequal(next, goal_pos) jp next; return; end % 检查强制邻居上方或下方有障碍且斜向可走 if (next(1)-1 1 map(next(1)-1, next(2)) 1 ... next(2)dir 1 next(2)dir N map(next(1)-1, next(2)dir) 0) || ... (next(1)1 N map(next(1)1, next(2)) 1 ... next(2)dir 1 next(2)dir N map(next(1)1, next(2)dir) 0) jp next; return; end next next [0, dir]; end end垂直方向同理只是把行列互换。这两个函数是 JPS 的基础写完后要单独测试在一张只有边界障碍的空地图上从起点向右跳应该直接跳到终点所在列或边界。4.3 对角方向的跳点与递归检查对角方向最复杂。沿对角走一步后要分别检查水平和垂直方向是否能跳出跳点。如果能当前对角节点就是跳点否则继续对角走。function jp jump_diagonal(map, current, dir, goal_pos) N size(map, 1); jp []; next current dir; while next(1) 1 next(1) N next(2) 1 next(2) N if map(next(1), next(2)) 1 return; end if isequal(next, goal_pos) jp next; return; end % 对角节点的水平和垂直方向有跳点则当前节点是跳点 if ~isempty(jump_horizontal(map, next, dir(2), goal_pos)) || ... ~isempty(jump_vertical(map, next, dir(1), goal_pos)) jp next; return; end % 强制邻居检查 if (map(next(1)-dir(1), next(2)) 1 map(next(1)-dir(1), next(2)dir(2)) 0) || ... (map(next(1), next(2)-dir(2)) 1 map(next(1)dir(1), next(2)-dir(2)) 0) jp next; return; end next next dir; end end递归调用是 JPS 的性能关键也是 MATLAB 里最容易栈溢出的地方。如果地图很大且障碍稀疏对角跳跃会递归很多层。常见做法是加一个最大跳跃步数限制超过就强制返回避免卡死。4.4 JPS 主循环与 open list 维护JPS 主循环和 A* 类似区别在于邻居不是直接取 8 邻域而是对每个方向调用jump函数只有返回跳点才加入 open list。while ~isempty(open) [~, idx] min(open(:,3)); current open(idx, 1:2); open(idx, :) []; if closed(current(1), current(2)) continue; end closed(current(1), current(2)) true; nodes_expanded nodes_expanded 1; if isequal(current, goal_pos) break; end dirs get_dirs(current, parent, allow_diag); % 根据父节点方向裁剪 for d 1:size(dirs, 1) jp jump(map, current, dirs(d,:), goal_pos); if ~isempty(jp) ~closed(jp(1), jp(2)) tentative_g g(current(1), current(2)) norm(jp - current); if tentative_g g(jp(1), jp(2)) g(jp(1), jp(2)) tentative_g; parent(jp(1), jp(2), :) current; f tentative_g heuristic(jp, goal_pos, allow_diag); open [open; jp, f]; end end end endget_dirs是 JPS 的另一个关键它根据当前节点相对父节点的方向裁剪掉不可能产生最优路径的方向。比如你从左边走到当前节点那继续向左走没有意义因为那是回头路。这个裁剪能进一步减少跳点搜索次数。5. 对比测试与避坑为什么你的 JPS 有时比 A* 还慢5.1 指标采集与结果解读主入口跑完 6 种尺寸后至少收集四个指标路径长度、扩展节点数、耗时、是否找到路径。路径长度用欧氏距离累加扩展节点数直接读nodes_expanded耗时用toc。建议每个尺寸跑 10 次取中位数避免单次抖动。尺寸A* 节点数JPS 节点数A* 耗时(ms)JPS 耗时(ms)路径长度比50约 800约 1201281.00100约 3200约 30055221.00200约 13000约 700240651.00300约 29000约 11005801301.00路径长度比接近 1 说明两者都找到了最优路径在相同启发函数下。如果 JPS 路径明显更长大概率是跳点规则写漏了强制邻居导致某些方向提前停止。5.2 避坑JPS 常见的四个翻车点现象一JPS 找不到路径但 A能。* 原因通常是强制邻居判断条件写反了把“斜向可走”写成了“斜向是障碍”。解决方法是拿一张只有单个障碍的地图手动推演跳点应该出现在哪然后打印jump函数的返回值逐个比对。现象二JPS 路径比 A长。* 原因可能是对角跳跃时没有递归检查水平和垂直跳点导致漏掉了更优的拐点。检查jump_diagonal里是否同时调用了jump_horizontal和jump_vertical并且方向参数正确。现象三JPS 耗时反而比 A大。* 在小地图50×50 以下或者障碍极密的地图上JPS 的跳点搜索开销可能超过 A* 的逐格扩展。这不是 bug是特性。JPS 的优势在开阔大图地图越小、障碍越密优势越不明显。现象四MATLAB 递归栈溢出。对角跳跃在空旷区域会递归很多层。解决办法是给jump函数加一个max_jump参数比如 200 步超过就返回空让主循环继续从其他方向找。注意对比测试时一定要固定随机种子和障碍率。不同种子下 JPS 的节点数波动可能达到 30%只看一次结果容易得出错误结论。5.3 启发函数权重对两者的影响差异A* 和 JPS 都对启发函数敏感但敏感程度不同。把启发函数乘以一个大于 1 的权重加权 A*A* 的节点数会明显下降但路径可能次优。JPS 在加权后节点数下降幅度较小因为它本身已经跳过了大量节点。如果你追求实时性加权 A* 在中等地图上可能比标准 JPS 更划算如果你追求最优路径且地图很大JPS 更稳。% 加权启发weight 1 时偏向速度 h weight * heuristic(node, goal_pos, allow_diag);权重一般取 1.0 到 1.5超过 2.0 路径会明显绕远。建议在 100×100 和 200×200 两张图上分别试 1.0、1.2、1.5 三档看节点数和路径长度的权衡曲线。6. 进阶技巧把对比测试变成可复用的评估脚本跑通一次对比不难难的是每次改了算法或地图后能快速复现整套评估。我的习惯是把主入口改成一个函数输入是尺寸列表、障碍率列表、种子列表输出是一张汇总表。这样你换任何参数组合一行命令就能重跑。function results run_benchmark(sizes, obs_ratios, seeds) % sizes: 如 [50 80 100 150 200 300] % obs_ratios: 如 [0.2 0.3] % seeds: 如 1:10 results []; for N sizes for or obs_ratios for s seeds map generate_map(N, or, s); [~, n1, t1] astar_plan(map, [1 1], [N N], true); [~, n2, t2] jps_plan(map, [1 1], [N N], true); results [results; N, or, s, n1, t1, n2, t2]; end end end results array2table(results, VariableNames, ... {Size,ObsRatio,Seed,AstarNodes,AstarTime,JPSNodes,JPSTime}); end这个脚本跑完你可以直接用groupsummary按尺寸和障碍率聚合看平均节点数和平均耗时。如果 JPS 在某个尺寸下节点数突然跳变大概率是那个种子的地图出现了长走廊或大面积空旷区导致跳点搜索路径变长。这时候不要急着改算法先可视化那张地图确认是不是地图本身的问题。另一个实用技巧是加一个“路径平滑度”指标统计路径中拐点的数量。JPS 的路径拐点通常比 A* 少因为跳点天然倾向于走直线。如果你做的是机器人运动规划拐点少意味着更少的减速和转向实际执行时间可能比纯搜索时间更有优势。从那以后我每次做算法对比都强制先跑一遍固定种子的基准再换随机种子看波动范围。基准不稳后面的结论都是空中楼阁。希望这份拆解能帮你少走点弯路把 A* 和 JPS 的边界摸清楚再决定用哪个。本文还有配套的精品资源点击获取