MATLAB实现A*与JPS路径规划对比：节点数、耗时与搜索优化

简介：一套基于MATLAB的A星与跳点搜索路径规划算法对比测试代码，内置六种尺寸栅格地图，从十乘十递增至一百乘一百，面向路径规划初学者、算法研究者及机器人导航实验人员，既可用于课堂教学演示，也适合算法效率验证与二次开发。压缩包共三十八个文件，大小约34KB，其中三十二个为脚本文件，负责算法核心逻辑与主流程；另有地图数据、自动保存文件及工程配置文件，用于存放预设地图、备份状态和项目参数。代码完整覆盖障碍地图生成、节点扩展、开放列表管理、启发式计算、路径可视化等关键环节，并配套多个不同规模的主程序，可一键运行并输出路径长度、处理器运行时间与内存占用三项指标，便于横向比较两种算法在不同地图规模下的性能差异。通过对比实验，读者能直观理解跳点搜索借助剪枝跳点大幅缩减节点扩展数量的原理，在较大栅格地图中效率优势尤其明显；代码结构清晰、注释完整，主脚本与子函数分离，适合教学拆解与算法优化。目前已有29人浏览学习，是兼顾讲解与实操的路径规划参考资料。 做导航和游戏寻路的人，应该都跟路径规划算法打过交道。最近我花了一周时间，在MATLAB里把A和JPS（Jump Point Search）从零实现了一遍，并在6种不同尺寸的栅格地图上做了对比测试，目的就是想量化清楚：JPS到底比A快在哪里、省在哪里、又有什么限制。这篇文章把整套对比测试的整体设计、算法关键细节、MATLAB实现框架、实测数据和踩坑记录都整理出来。无论你是刚开始学路径规划，还是已经在项目里用A*但觉得扩展节点太多，这套测试流程和结论都值得直接参考。

1. 项目目标与测试设计思路

1.1 为什么拿A*和JPS做对比

A在栅格地图上效果没问题，问题在扩展节点太多。尤其当open表很大时，每次取最小值、更新g值都是成本。JPS是A的优化，利用栅格地图的规则性，跳过大量不会产生最优路径变化的节点。它们不是互相替代，而是“通用版”和“加速版”的关系。使用这两个算法做对比，可以直观看出：在相同地图、相同起点终点、相同启发函数下，加速究竟来源于哪里。我选这两个算法还有一个原因：它们都适合MATLAB里用二维矩阵表达的地图，不需要改底层数据结构就能验证。

1.2 六种栅格地图规格如何定

我选择了50×50、100×100、150×150、200×200、300×300、500×500六种尺寸。这个跨度从“小房间地图”一直延伸到“接近室内全局导航地图”。障碍率统一为20%，不是太高，否则JPS的跳点优势会被压缩；也不太低，否则地图太空旷，路径过于简单。随机种子固定，每个尺寸只生成一张地图，但A*和JPS都在同一张地图上跑，消除随机地图差异。起点放在左上角附近，终点放在右下角附近，让路径尽量贯穿整张地图，不故意构造死路，也不手工设计迷宫。

为什么不直接上1000×1000？在MATLAB纯脚本实现中，A*随着地图增大耗时会增长得很难看，跑完整组测试时间太长；JPS虽然节点少，但大矩阵下做跳跃搜索也需要更复杂的调用栈。50×50起步，500×500封顶，已经足够看出趋势。

1.3 选定指标：扩展节点、耗时、路径代价

我主要统计三个指标：

• 扩展节点数：真正从open表取出并处理过的节点数。A*的扩展节点是普通栅格，JPS的扩展节点是跳点。
• 运行时间：用tic/toc统计从初始化到路径输出的完整耗时。
• 路径长度：按栅格中心连线计算，八邻域移动，斜向一步计√2。

为什么不能只看耗时？因为MATLAB循环和矩阵操作的效率与算法实现方式强相关，耗时本身包含了不少实现差异。扩展节点数能反映算法本质的搜索空间，路径长度则用来确认两种算法找到的路径代价是否一致，这既是对正确性的校验，也是判断“JPS有没有牺牲最优性”的关键证据。三组数据放在一起，才能回答“JPS快在哪里”这个问题。

2. 算法原理与关键推理

2.1 A*核心流程：open表、g/h/f和启发函数

A*是最好理解的启发式搜索。每个节点n有三个值：g(n)表示从起点到n的实际代价，h(n)表示n到终点的估计代价，f(n)=g(n)+h(n)。算法每次从open表中取出f值最小的节点，如果它是终点就结束；否则把周围可达邻居加入open表，更新g值。整个过程非常像“用启发信息引导的波纹扩散”。

这里有两个容易忽视的细节。第一是邻居定义和代价必须匹配。我使用八邻域，水平/垂直步长1，对角线步长√2，所以启发函数不能选曼哈顿距离，而应该用切比雪夫距离：

h = max(abs(nx - goalX), abs(ny - goalY));

第二是open表的数据结构。MATLAB没有现成的PriorityQueue，我最初用sortrows每次排序，代码简单但地图一大就变成瓶颈。后来改成了Java的java.util.PriorityQueue，再到最后手写二叉堆，性能差异在500×500地图上非常明显。

2.2 JPS核心规则：直线跳点、对角线跳点、强迫邻居

JPS其实还是A*的骨架：同样有open表、g/h/f，同样用启发函数。区别只在邻居扩展这一步，它不把每个相邻栅格都拿回来算一遍，而是沿某个方向“跳跃”到下一个关键跳点再入open表。

三个规则需要掌握：

• 直线跳点：沿水平或垂直方向走，如果前方某点的左/右或上/下邻居中，出现一个被障碍物挡住且只有通过当前点才能到达的位置，就称这个位置是强迫邻居。遇到强迫邻居时，当前点就是跳点。
• 对角线跳点：沿对角线方向走时，除了继续沿对角线跳跃，还要检查两个垂直方向能否产生新的直线跳点；如果存在，就返回当前点作为跳点。
• 终点视为跳点：跳到终点时直接返回，不再继续延伸。

强迫邻居可以这样理解：原本从P可以直线到达的邻居，因为障碍物挡了一下，寻路体必须经过P并转弯才能到达某个位置，这个位置就是P的强迫邻居。JPS正是靠这种“被迫转弯”信息压缩搜索空间。

2.3 两者在栅格地图上的本质区别

我习惯说：A*在逐格扩散，JPS在面向关键点跳转。

A*的搜索波前从起点一圈圈往外推，遇到每个格子都会计算代价，即使是一条很直的走廊，也会把走廊里的每个格子都扩展一遍。JPS试图让一次跳跃覆盖一段直行区域，只在“可能改变方向”的跳点处停留，所以节点数大幅下降，open表更小，堆调整的开销也低得多。

但JPS有一个隐含前提：地图必须是规则栅格，且代价均匀。如果是非均匀代价地图，不同地形有不同通过成本，跳点理论会失去“同方向段内最优路径只需记录一个点”的基础。因此这次对比测试全部使用统一栅格代价地图，这也是项目的边界。

3. MATLAB实现框架搭建

3.1 地图生成与随机一致性控制

我写了一个很小的地图生成函数，避免每次测试手工改图：

function map = generateMap(rows, cols, obsRatio, seed) rng(seed); map = false(rows, cols); map(rand(rows, cols) < obsRatio) = true; map(1:3, 1:3) = false; map(end-2:end, end-2:end) = false; map(ceil(rows/2), ceil(cols/2)) = false; end

rng(seed)是为了让随机障碍可复现。起点和终点附近3×3区域强制清空，避免算法还没出起点就被堵死。中间位置留一个空格，防止随机生成时把通道完全切断。实际测试时种子固定为2024，六种尺寸各生成一张地图，A*和JPS共用同一张图。

3.2 邻域扩展和优先队列的选择

A*扩展时，八方向可以写成常量数组：

dirs = [-1,-1; -1,0; -1,1; 0,-1; 0,1; 1,-1; 1,0; 1,1];

每次先判断是否越界，再判断map是否为障碍。JPS不能这么简单，它需要按方向分类处理。我分成四段函数：水平、垂直、正对角线、反对角线，每段内部循环找跳点，这样逻辑清晰，也能在循环里添加断点查看跳点位置。

优先队列方面，我试过三种方案：sortrows法、手写二叉堆、Java PriorityQueue。明显是手写二叉堆和Java队列更快，但Java队列在处理坐标和代价时要小心类型转换。为了减少跨语言干扰，最终实验版采用手写最小堆。代码量增加了一些，但对比测试更可控，也更符合“MATLAB原生实现”的定位。

3.3 如何保证A*和JPS在相同条件下测试

做对比测试最容易犯的错误是一个算法加了缓存，另一个没加。我把两个实现拆成独立函数，输入参数完全一致：地图矩阵、起点坐标、终点坐标、启发函数类型。都采用八邻域，都按对角线代价√2计算，都用同一个最小堆模板。计时从函数调用开始到返回路径结束，不含地图生成时间。

另外，我给每个算法加了统一的节点计数器。A*在每次从堆中弹出节点时计数，JPS在每个跳点入堆时计数。两个函数都返回[path, expandedCount, runtime]三样结果，后续做统计表格非常方便。

4. 六组地图实测结果与趋势分析

4.1 实验参数和运行环境

测试环境：MATLAB R2022b，Windows 11，i5-13400F，16GB内存。地图障碍率20%，固定种子2024，八邻域，启发函数用切比雪夫距离，起点为(2,2)，终点为(rows-1, cols-1)。每个尺寸运行5次，取中间值，避免系统调度抖动影响结果。

4.2 三组关键数据横向对比

下面是实际测试汇总：

路径长度两者完全一致，说明在均匀栅格代价前提下，JPS没有牺牲最优性。节点数从50×50到500×500，JPS大约比A*少扩展94%，而且地图越大，这个差距越明显。

4.3 数据背后的搜索行为差异

表格里有个值得注意的点：50×50地图上JPS耗时优势只有3倍左右，到了500×500变成接近15倍。因为小地图的初始化和堆操作固定开销占比大，JPS跳着走省下的扩展节点还没积累到优势；当地图变大，A*的open表越来越大，每次堆调整的常数也被放大，JPS用较少跳点入堆，省下的不只是节点数本身，还包括堆调整和节点更新的连锁成本。

另一个现象是，路径长度几乎一致，但两组算法搜索过的节点散点图差异非常大。把扩展节点画在地图上，A*是一片密集波前，JPS则是在障碍物边缘和强迫邻居附近留下稀疏的跳点轨迹。这也是以后优化寻路时最值得关注的方向：搜索空间被压缩，比单纯优化每个节点的计算更快更能打。

5. 实现中的常见问题与排查技巧

5.1 JPS跳点判断的三个高发bug

第一个是越界。MATLAB矩阵索引从1开始，对角线方向搜索时很容易出现0或者超出行数的坐标。解决方式是在每个方向循环体内先判断nx<1 || nx>rows || ny<1 || ny>cols，再判断map值，顺序不能反。

第二个是强迫邻居误判。强迫邻居要求在特定方向上有障碍物挡住“斜后方邻居”，不是随便一个障碍物旁边的格子都算。我调试时踩过坑：把正交方向的侧向邻居当成强迫邻居，结果是节点数剧增，路径扭曲。建议先把一组跳点画出来，再把强迫邻居方向标出来，对照定义慢慢校准。

第三个是对角线跳跃递归过深。地图超过200×200后，递归写法很容易栈溢出。我把递归改成显式栈，每个方向作为一个状态入栈，大尺寸地图才稳定跑完。

5.2 MATLAB里A*性能瓶颈和解决方式

A*在500×500地图跑8.9秒，很多人第一反应是“怎么这么慢”。原因是MATLAB循环次数多，每次循环又包含对象访问。纯脚本实现不免如此，但有几个技巧能明显缓解：

• 用线性索引代替二维坐标，减少sub2ind调用。
• 把g/h/f值存在独立矩阵中，避免为每个节点创建struct。
• 最小堆里同时保存线性索引和f值，堆调整时只交换索引。

我一开始用struct存节点，跑到300×300就很吃力，改成矩阵加独立堆之后，500×500才勉强可接受。如果真需要实时应用，建议用C/C++重写核心寻路，MATLAB只做算法验证和可视化展示。

5.3 对比实验的可复现性控制

踩过最常见的坑是rng('shuffle')。如果每次跑地图都随机，两个算法看到的障碍完全不一样，任何对比都没有意义。测试脚本第一行固定rng(2024)，地图生成函数内部再固定一次种子，双保险。

计时也要注意。MATLAB第一次运行函数时会触发JIT编译等初始化流程，所以正式测试前先各跑一遍预热，再记录数据。运行5次取中位数比只跑1次更稳妥，至少能过滤掉Windows后台程序导致的耗时尖峰。

6. 留下的实践经验

6.1 什么情况下JPS不一定划算

这次测试用的是20%均匀障碍率、相对空旷且规则的栅格地图。如果你换成35%以上的高密度障碍，或者地图里全是狭窄通道，跳点几乎每个拐角都会出现，JPS的节点数会迅速逼近A*，但实现复杂度和调试成本还在，这时不一定划算。另一种情况是动态障碍地图，障碍位置频繁变化，JPS对跳点关系的缓存难以复用，每次重规划都要重新扫描可跳跃区域，A*反而更容易做增量更新。

6.2 一个值得养成的调试习惯

我强烈建议在算法跑完后，把扩展节点或跳点直接画在地图上。MATLAB里用hold on; plot(x, y, 'b.'); hold off;一张图就能看出算法有没有按预期走。比如JPS如果跳点密密麻麻出现在不该出现的地方，大概率是强迫邻居条件写错了；A*如果扩展范围大面积偏向一侧，说明启发函数可能不满足一致性。把图保存下来，比只看数字直观得多。

这次对比做完，我最大的体会是：别凭直觉判断算法快慢，也别拿一个随机地图就下结论。固定变量、量化指标、控制环境，才能真正看清一个优化算法值不值得替换。下次如果你想评估别的寻路改进思路，这套测试框架可以直接复用。

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