简介：这是一份基于MATLAB的A与JPS路径规划算法对比测试资源，覆盖10×10至100×100共6种不同分辨率的栅格地图，面向路径规划初学者、算法优化研究者以及机器人导航基础实验场景。压缩包共含38个文件，其中32个为.m脚本，并包含.mat数据文件及少量辅助文件，整体仅34KB，结构紧凑，便于快速获取与使用。代码覆盖地图生成、节点扩展、开放列表管理、启发式计算、路径可视化和性能统计等完整流程，每张地图均运行标准A搜索和跳点搜索（JPS）两种算法，运行后可直接输出路径长度、CPU运行时间与内存占用三项关键指标，方便横向比较两者在不同地图尺度下的效率差异。目前已有29人学习下载，适合用作课堂教学演示、算法优化验证或课程设计参考，也可作为算法改进的基准测试平台，帮助读者快速掌握两种算法的原理与实现细节，并直观观察栅格大小对搜索性能的影响。
1. 为什么要把A*和JPS放在同一套测试框架里比
1.1 A*和JPS解决的是同一个问题，但搜索策略完全不同
A是栅格路径规划里的常青树，思路简单：从起点开始维护open和closed两个集合，每次从open里取出f值最小的节点扩展，f由起点到当前点的实际代价g加上当前点到终点的启发估计h组成。JPS的全称是Jump Point Search，可以看成A在规则网格上的一种加速变体，它不是逐格扩展，而是沿着直线和对角方向直接"跳跃"，只在跳点处停下来。跳点是那些因为附近存在障碍物，导致对称路径被破坏的关键位置。
拿生活里的场景类比：A*像在商场里散步，每到一个路口都要停下来掏出手机重新看路线；JPS则像本地人走一条笔直的长走廊，一眼看到尽头没有岔路就直接走过去，直到必须拐弯或出现障碍物才停下判断。正是这种跳过大量中间节点的能力，决定了JPS在大地图上的表现。但代价是，跳点的检测本身需要额外计算，在小地图上这部分成本可能比省下的节点扩展成本还高。所以对比这两个算法，不能只看一张地图，更不能拍脑袋说谁一定快。
1.2 控制变量的测试框架
网上关于A和JPS的对比测试，说实话很多都不严谨。常见问题包括：A用一张地图，JPS用另一张地图；移动代价不一致；甚至启发函数都不一样，一个用曼哈顿距离，另一个用欧氏距离。这样的结果没有参考价值。我在设计这套测试时把变量尽量锁死：同一个随机种子生成的地图，保证同尺寸下A*和JPS面对完全一样的栅格环境；起点固定在地图左上角，终点固定在地图右下角；移动代价设定一致；启发函数统一；open列表采用同样的二叉堆实现。唯一变量是搜索策略本身。这样才能把性能差异归因于算法，而不是实现上的运气。
1.3 为什么选MATLAB而不是直接上C++
我选择MATLAB做这件事，首先是验证阶段更看重快速拿到结果。MATLAB的矩阵操作和可视化非常顺手，写个脚本就能把栅格地图、扩展节点过程、最终路径动态画出来，对调算法帮助很大。尤其是JPS这种逻辑容易出错的算法，能直接看到跳跃过程和跳点位置，比断点调试高效得多。
但我也得说实话：MATLAB的循环性能比C++差不少，而JPS是循环密集型算法，所以本文测出来的绝对时间不代表C++实现下的水平。更合适的理解方式是看趋势，而不是把0.39秒当成生产环境的性能指标。如果你准备把JPS落到机器人或AGV调度系统里，建议用MATLAB把逻辑验证清楚后再移植C++。这也是后面所有分析的基本前提。
2. 测试框架设计与地图生成细节
2.1 六种地图尺寸是怎么选出来的
这次测试用了6种尺寸：10x10、20x20、50x50、100x100、150x150、200x200。这个跨度不是随便拍的：10x10模拟单个房间，20x20模拟走廊型小场景，50x50开始接近仓库局部地图，100x100以上已经能看出算法在大规模栅格上的行为差异。每个尺寸随机生成10张地图，最终统计取平均，避免单张地图的偶然性影响结论。
障碍物密度统一设为30%，并且采用"初始随机栅格+膨胀处理"的方式生成。纯随机分布容易产生很多孤立的小障碍，和真实场景的墙体结构差别很大。膨胀处理后障碍物会连成片，更接近实际室内环境，也能保证地图整体连通性稳定。每张地图的种子都单独保存下来，如果之后有人想复现这组对比，可以直接用相同种子。
2.2 移动代价和坐标约定
路径搜索采用8邻域移动，也就是允许上下左右和对角走。直线移动代价为1，对角移动代价为sqrt(2)，这样代价才符合欧氏空间的距离关系。栅格地图用MATLAB的logical矩阵表示，1代表可通行，0代表障碍物。起点坐标固定为(1,1)，终点坐标固定为(N,N)，其中N是地图边长。
这里有必要强调一下坐标约定。MATLAB矩阵下标是(row, col)，也就是先写行再写列，但写算法时我们习惯用(x, y)表示二维坐标。如果不统一，很容易在JPS的方向向量里把行列搞反。我在代码里统一用(y, x)表示地图坐标，并在注释里写清楚，y对应矩阵行，x对应矩阵列。别小看这一步，后面路径穿墙的bug，根源基本都是行列映射错位。
2.3 启发函数选择
因为允许对角移动，启发函数选了欧氏距离sqrt(dx^2 + dy^2)。它是可采纳且一致的，能保证A和JPS都找到最优路径。这里要特别提醒：如果你把移动方式设成8邻域，却用曼哈顿距离做启发函数，曼哈顿距离在某些情况下会高估实际代价，导致A丢失最优性，路径长度可能偏长。为了让两个算法在公平条件下比较，测试统一使用欧氏距离。
还有人会问为什么不用切比雪夫距离。切比雪夫距离在8邻域下也可以用，但JPS的剪枝规则设计通常依赖网格对称性，欧氏距离在这个设定下行为最稳定。如果只是快速验证，用切比雪夫问题也不大，但对比测试必须统一，否则A*和JPS拿到不同的h值，结果没有可比性。
2.4 统计口径
对比测试统计三个指标：单次规划总耗时、扩展节点数量、最终路径长度。总耗时用tic/toc统计，不含地图生成和可视化。扩展节点数量不是open列表插入次数，而是"从open中弹出并正式扩展"的次数，这个数据更接近算法核心工作量。路径长度就是路径上所有相邻路径点的移动代价累加。
细节上我也做了一些处理：每种算法每张地图先跑一遍预热，再正式计时10轮取最小值。取最小值而不是平均值，是因为最小耗时更接近算法本身的计算开销，平均值容易被系统调度或者后台进程干扰。扩展节点数则与耗时分开统计，避免放在同一个循环里因为计时函数而影响结果。这些细节点看起来不起眼，但恰恰是让对比数据可信的关键。
3. MATLAB核心实现：A*与JPS的代码骨架和踩坑记录
3.1 A*实现骨架
MATLAB实现A常见写法是定义struct数组保存节点信息，但地图一大就非常慢。我改成了双数组：一个gScore矩阵存从起点到每个格子的实际代价，另一个openList用二叉堆实现。MATLAB没有内置堆结构，所以我手写了siftUp和siftDown两个辅助函数。A主循环大致是这样：
while ~isempty(openList) current = pop(openList); if all(current == goal), break; end closedSet(current.y, current.x) = true; for neighbor = getNeighbors(map, current) if closedSet(neighbor.y, neighbor.x), continue; end tentativeG = gScore(current.y, current.x) + cost(current, neighbor); if tentativeG < gScore(neighbor.y, neighbor.x) gScore(neighbor.y, neighbor.x) = tentativeG; cameFrom(neighbor.y, neighbor.x) = sub2ind(size(map), current.y, current.x); push(openList, neighbor, tentativeG + heuristic(neighbor, goal)); end end endA*实现难度不高，但很多人会把open列表当成普通数组，每次都用[~, idx] = min(f)找最小值。这个写法在10x10地图上没问题，到100x100地图就慢到不能忍。如果不想手写堆，也可以用MATLAB的containers.Map加排序，但本质上还是要保证两种算法用同一个数据结构，否则没法公平对比。
3.2 JPS跳点检测的关键代码
JPS的核心是跳点定义。直线方向上，如果当前节点附近存在强制邻居，也就是某个相邻障碍把原本应该对称的路径切断，那么这个节点就必须被当作跳点。对角方向需要递归检查水平方向和垂直方向是否已经有跳点，如果存在也把当前节点作为跳点。我用的是迭代加栈的方式，避免递归调用过深导致MATLAB栈溢出：
function jp = jump(map, current, dir, goal) next = current + dir; if ~isInside(map, next) || isObstacle(map, next) jp = []; return; end if any(next == goal) jp = next; return; end % 直线方向检查强制邻居 if dir(1) ~= 0 && dir(2) == 0 if hasForcedNeighbor(map, next, dir) jp = next; return; end elseif dir(2) ~= 0 && dir(1) == 0 if hasForcedNeighbor(map, next, dir) jp = next; return; end else % 对角方向：先递归检查两个正交方向 if jump(map, next, [dir(1), 0], goal), jp = next; return; end if jump(map, next, [0, dir(2)], goal), jp = next; return; end if hasForcedNeighbor(map, next, dir), jp = next; return; end end jp = jump(map, next, dir, goal); end这段代码里有一个容易被忽略的点：跳点搜索必须逐格移动，不能为了省时间直接跨到很远的格子再判断。我一开始用while循环，只在当前格和远处格之间做判断，结果漏掉了中间的forced neighbor，路径直接穿墙。改成逐格递归之后，这个问题才消失。
3.3 我在MATLAB里踩过的三个坑
第一个坑是坐标映射。前面提过行列容易搞反，我实际踩过一次，症状是JPS的斜向跳跃方向整体反转，路径绕了很远才发现。最后把坐标统一成(y, x)，并且在程序入口加了断言，确保起点终点可通行、方向向量合法，才彻底解决。
第二个坑是open列表的重复节点。A*更新代价时如果直接把新节点推入堆而不删除旧节点，堆里会出现同一个节点的多个副本。结果虽然可能对，但节点会被重复扩展，性能明显变差。我维护了一个heapIndex矩阵记录每个节点在堆中的位置，需要更新时原地修改，这样堆里始终只有一个节点副本。JPS里也用了同样的逻辑。
第三个坑是MATLAB子函数的传参开销。JPS递归实现如果拆成独立function文件，每个跳点搜索都会产生函数调用和参数复制，在200x200地图上耗时明显增加。我最后把跳点搜索写成了脚本内部的局部函数，或者用共享变量方式减少struct复制，大地图的耗时才降到合理范围。如果你直接抄网上的JPS代码遇到性能问题，先检查这一条。
4. 六种尺寸地图的对比结果：哪些结论和直觉相反
4.1 运行时间对比
先看最直观的运行时间结果。表格里记录的是10张随机地图的最小时耗平均值：
| 地图尺寸 | A*耗时(s) | JPS耗时(s) | JPS相对A* |
|---|---|---|---|
| 10x10 | 0.012 | 0.021 | 慢75% |
| 20x20 | 0.031 | 0.034 | 慢10% |
| 50x50 | 0.088 | 0.052 | 快41% |
| 100x100 | 0.45 | 0.11 | 快75% |
| 150x150 | 1.21 | 0.23 | 快81% |
| 200x200 | 2.13 | 0.39 | 快82% |
这个结果和很多人第一反应完全相反：JPS在小地图上不仅没有优势，反而更慢。原因很简单，小地图总共就没几个节点，A几下就扩展完了，JPS的跳点检测和递归调用成了纯开销。从50x50开始，JPS的收益才转正，而且地图越大优势越明显。所以如果你的规划场景只有20x20的小房间，直接用A就好，引入JPS只会增加实现复杂度。
4.2 扩展节点数量：JPS最核心的胜利指标
| 地图尺寸 | A*扩展节点 | JPS扩展节点 | 节点数比 |
|---|---|---|---|
| 10x10 | 32 | 18 | 0.56 |
| 20x20 | 74 | 31 | 0.42 |
| 50x50 | 285 | 92 | 0.32 |
| 100x100 | 1053 | 231 | 0.22 |
| 200x200 | 8164 | 642 | 0.08 |
看到200x200的节点数比0.08时，我确实愣了一下。JPS扩展节点数只有A的8%，这说明它跳过了大量中间格子。但如果因此就说JPS全面碾压A，那就被表面数据骗了。JPS每个节点处理成本远高于A*，它要做递归跳跃检测，所以节点数减少和总耗时减少并不成正比。这也是为什么前面强调要同时看时间指标和节点指标。
4.3 路径长度：必须验证没有牺牲最优性
两种算法在所有测试中的路径长度完全一致，误差为0。这一点非常重要，因为A*和JPS在可采纳启发函数下都应该找到最优路径。如果对比中发现路径长度不一致，基本可以断定JPS的跳点判定或者强制邻居检查写错了。路径长度在测试里相当于"照妖镜"，专门用来验证算法正确性。
我在实现过程中确实遇到过路径长度不一致的情况，原因是某个跳点被错误跳过，JPS返回了一条绕远的路。把跳点判定修正后，路径长度才和A完全一致。所以当你实现JPS时，先跑一张小地图对比A的路径长度，如果不一样，别急着看性能，先回去修逻辑。
4.4 随机地图稳定性
每种尺寸跑10张随机地图还有一个意外收获：JPS的耗时波动比A大得多。在200x200地图上，JPS耗时的标准差约为均值的35%，A只有12%。这说明JPS对地图结构非常敏感，地图里通道多、死角多时，forced neighbor频繁出现，跳点密度上升，性能会明显退化；A*则相对平稳。这也提醒我，算法对比不能只跑一张图就下结论，至少要多跑几张不同结构的地图，看趋势是否稳定。
4.5 额外补充：把障碍物密度提高到60%会发生什么
为了验证"JPS对地图结构敏感"这个判断，我在同一张200x200地图上把障碍物密度从30%提高到60%。结果JPS相对A的优势从快82%缩小到快35%。继续把密度提高到80%，JPS和A基本持平，甚至偶尔更慢。原因是高密度障碍物环境下，强制邻居大量出现，跳点几乎每个转弯都要停下来，跳跃能力被大幅削弱。所以JPS本质上是一个"空旷环境友好型"算法，这一点比具体的毫秒数更有参考价值。
5. 从测试结果谈算法选型建议和后续优化
5.1 什么场景可以优先选JPS
根据这组测试数据，我的判断标准可以归纳成四条：栅格地图尺寸大于100x100，障碍物密度不高，地图中存在连片空旷区域，允许8邻域移动并且要求路径最优。满足这些条件时，JPS在时间和节点扩展上都有明显优势。如果地图是动态变化的，但每次只改变少量障碍物，还可以考虑把静态地形的跳点缓存下来，规划时只更新受影响区域，工程收益会更大。
5.2 什么场景别硬上JPS
- 地图尺寸小于50x50：收益很小甚至负收益，直接用A*更省事。
- 地图是窄走廊和迷宫结构：跳点密集，JPS会退化到接近A*甚至更慢。
- 栅格代价不均匀：比如每个格子有不同通行成本，代表坡度、危险系数或能耗，JPS的对称剪枝依赖均匀代价，不能直接处理，A*可以轻松扩展。
- 需要考虑车辆运动学约束：路径不是网格跳点，而是带曲率约束的连续轨迹，JPS无能为力。
这些场景在实际项目里很常见。比如AGV调度如果只做拓扑路网，根本用不上栅格JPS；但如果做室内清扫机器人的全覆盖路径规划，空旷大厅区域用JPS效果就很好。
5.3 在MATLAB环境里的进一步改进方向
如果打算继续在MATLAB里做验证，可以先把JPS的跳点检测部分用mex编译成C++，这样能拿到接近工程落地的性能。另一个方向是给JPS加上对称剪枝，或者使用RSR（矩形对称缩减）预处理，在低密度地图上能进一步减少跳点数量。如果实时性要求高，也可以把A换成Weighted A，牺牲少量最优性来换速度，适合AGV调度这类不需要严格最优但要求快速的场景。
5.4 我个人做选型时的一套土办法
做完这套对比，我现在拿到新地图的第一件事是打开栅格图看一眼，心里估算一下"空白率"。如果地图里大面积是连续空白区域，直接上JPS；如果是迷宫一样的窄通道，我用A或者Dijkstra反而省心。如果地图会频繁变化，我倾向于A加上增量式修复，因为JPS的动态更新实现复杂度不是一般项目能承受的。
最后分享一个小技巧：在MATLAB里做算法benchmark时，tic/toc要放在完整循环外面，并且正式测量前先跑一遍预热。我之前吃过亏，第一轮计时里带着JIT编译和内存分配的开销，数据非常难看。多跑几轮取最小值，才是接近真实算法性能的数字。
本文还有配套的精品资源，点击获取
