简介JPSJump Point Search算法是A*的高效优化版本适合网格地图中的路径规划。这份Python实现与可视化资源包面向游戏开发、机器人导航等场景帮助开发者掌握跳跃点、剪枝策略与代价估算等核心机制。压缩包共8个文件包含2个py源码、3个bmp地图与3个pyc缓存整体仅23KB轻量便于学习。其中Main.py负责主流程及可视化支持加载地图参数运行jps.py封装核心跳跃搜索逻辑结合示例地图可直观观察寻路过程。所有代码结构清晰注释便于理解关键判断条件。目前已有1892人学习下载。资源还涵盖了单向跳跃、斜向跳跃、邻接关系优化及曼哈顿/欧几里得启发式等关键点配合pygame或matplotlib可视化既能深入理解算法原理也可直接改造用于游戏NPC寻路或机器人路径规划项目实用性较强。1. JPS算法是什么跳过冗余节点让网格寻路不再盲目做网格寻路的人多数是从A入门的但真把A放到一张几百乘几百的栅格地图上你会发现它在空旷区域的表现相当浪费大量对称路径节点被塞进开放列表f值相同、方向镜像的节点被反复弹出和扩展。JPS算法Jump Point Search就是冲着这个痛点来的它利用网格的对称性把整条直线段上价值等同的节点全部折叠只扩展真正可能改变方向的“跳点”。在开阔地图上JPS的搜索速度往往比A*快一个数量级地图越空旷越明显。这篇笔记会从跳点的定义讲起带你用Python实现完整的JPS寻路器再用pygame把搜索过程逐帧可视化最后落地到随机地图对比和JPS的进阶思路。2. 跳点搜索的核心原理对称性剪枝与强制邻居2.1 A*的痛点对称路径把开放列表撑爆在栅格地图上A每扩展一个节点会把周围8个邻居全部塞进开放列表。如果是一片空地从起点到终点会存在无数条f值完全相同的路径——先走三步再拐弯和先拐弯再走三步代价一样但A不知道这件事只能把每条路径上的节点都当成独立候选展开。开放列表堆满价值重复的节点CPU时间全耗在重复劳动上。JPS的观察非常朴素既然这些中间节点到目标的代价完全一致而且直线段上没有任何障碍物需要绕行那就没必要逐个扩展。只需要找到这条直线段两端的关键转折点中间部分直接“跳过去”。但这个跳跃有个硬前提地图必须是均匀网格移动代价一致或者至少没有加权地形。如果地图是带权重的导航网格或者移动消耗随地形变化JPS的剪枝逻辑就不成立。选型时这一点尤其重要。2.2 强制邻居与跳点两个定义决定剪枝效果要理解跳点Jump Point必须先理解强制邻居Forced Neighbor。它定义在一个带方向的场景里从节点x沿方向d走到节点n如果n的某个邻居m不在方向d上并且从x到m的直线路径被障碍物挡住——也就是说想从x到m必须经过n绕一下——那么m就是n的一个强制邻居。当某个节点存在强制邻居时它就是“跳点”。用代码判断强制邻居是最直观的。下面这个函数接收当前节点坐标和前进方向返回强制邻居列表def get_forced_neighbors(self, x, y, dx, dy): 返回从(x,y)沿(dx,dy)方向继续走时被迫绕行的邻居节点 forced [] # 水平/垂直方向的强制邻居 if dx ! 0 and dy 0: # 水平移动 for side in (1, -1): # 上下两个侧向邻居 if self.is_walkable(x, y side) and not self.is_walkable(x - dx, y side): forced.append((x, y side)) elif dx 0 and dy ! 0: # 垂直移动 for side in (1, -1): if self.is_walkable(x side, y) and not self.is_walkable(x side, y - dy): forced.append((x side, y)) # 对角线方向的强制邻居 elif dx ! 0 and dy ! 0: if self.is_walkable(x - dx, y) and not self.is_walkable(x - dx, y - dy): forced.append((x - dx, y)) if self.is_walkable(x, y - dy) and not self.is_walkable(x - dx, y - dy): forced.append((x, y - dy)) return forced判断逻辑里最关键的是后半段not is_walkable(...)。它表达的是“直线路径被堵住”这个条件。如果侧向格子本身就是障碍那不需要绕行只有当侧向格子可走、但直线源头方向被障碍物挡住时才说明必须经过当前节点绕路于是产生一个强制邻居。这里把三个方向分支分开处理水平方向看上下两个侧向垂直方向看左右两个侧向对角线方向则要额外检查与对角线相邻的两个直线格子。有了强制邻居跳点的判定就简单了当前节点有强制邻居它就是跳点。另外还有两种特殊情况也视作跳点目标点本身以及对角线跳跃时水平或垂直分支上发现的新跳点。2.3 水平、垂直与对角线的跳跃规则jump()函数是整个JPS的核心负责沿一个方向“跳”到下一个跳点。三种方向的跳跃规则有差别我把判定逻辑写成了这张表方向类型停止条件额外检查水平/垂直撞墙或出界、到达目标点、有强制邻居无对角线撞墙或出界、到达目标点、有强制邻居水平与垂直分支上是否有跳点水平与垂直分量是否都可走水平或垂直方向最简单沿方向一直走每走一步依次检查三个停止条件不满足就继续前进。对角线方向复杂一些因为对角线移动意味着水平分量和垂直分量同时在推进。如果水平或垂直方向上的直线段里存在强制邻居你迟早要在这里停下来拐弯所以当前节点本身就要作为跳点加入候选。对角线还有第三个容易踩的细节必须确认水平分量和垂直分量都能走通。如果水平分量被墙堵死但垂直分量可走那么实际应该走的是垂直方向而不是斜穿对角线如果两个分量都不可走那这个对角线方向就是死路。这个检查也是防止“对角线穿墙”的关键很多JPS实现翻车都翻在这一行。另外严格的JPS实现里还应该有一个邻居剪枝流程从父节点方向进入当前节点后只保留自然邻居继续沿父方向走、以及父方向两侧的斜向方向只有出现强制邻居时才额外加入被迫绕行方向。完整实现里会单独写一个prune_neighbors()函数。下面这篇文章为了配合可视化让代码更直观省略了这一步改为对所有8个方向都调用jump()。代价是多了几次冗余的跳跃探测不过在中小地图上影响很小代码可读性却好得多。追求极致性能的读者可以在get_successors()里补上方向剪枝这个我在第6章会再提一句。3. Python实现JPS网格建模、跳点扩展与路径回溯3.1 网格建模与方向向量为jump函数铺路实现JPS的第一步是定义地图和基本操作。我用二维列表表示网格0表示可走1表示障碍物。is_walkable()负责判断一个格子是否可走它同时处理边界检查和障碍物检查这是jump函数里最底层的依赖出错的话整个搜索都会跟着出错。import heapq class JPSPathfinder: JPS寻路器在0/1网格上搜索最短路径0为可走1为障碍物 # 8个移动方向(dx, dy) # 前4个是水平/垂直方向后4个是对角线方向 DIRECTIONS [ (1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1) ] def __init__(self, grid): self.grid grid self.rows len(grid) self.cols len(grid[0]) def is_walkable(self, x, y): 判断格子是否可走在边界内且不是障碍物 return 0 x self.rows and 0 y self.cols and self.grid[x][y] 0方向向量的定义顺序有讲究我习惯先把4个直线方向放在前面再把4个对角线方向放后面。这样主循环里遍历方向时逻辑分组更清楚调试打印时也容易区分。is_walkable()里的一行判断同时做了边界和障碍物检查避免了到处写两段式检查。3.2 实现jump()跳点搜索的核心递归jump()是JPS的核心函数。它的语义是从节点(x, y)出发沿方向(dx, dy)跳跃返回该方向上找到的下一个跳点坐标如果该方向上没有跳点则返回None。函数使用递归实现每次向前走一步检查是否满足跳点条件不满足就继续递归。def jump(self, x, y, dx, dy, start, goal): 沿(dx,dy)方向从(x,y)开始跳跃返回下一个跳点或None nx, ny x dx, y dy # 1. 下一个格子不可走方向被堵死 if not self.is_walkable(nx, ny): return None # 2. 走到目标点目标本身视为跳点 if (nx, ny) goal: return (nx, ny) # 3. 当前格子存在强制邻居是跳点 if self.get_forced_neighbors(nx, ny, dx, dy): return (nx, ny) # 4. 对角线方向需要额外检查 if dx ! 0 and dy ! 0: # 4.1 水平与垂直分量都必须可走否则对角线不合法 if not self.is_walkable(nx, y) or not self.is_walkable(x, ny): return None # 4.2 水平或垂直分支上出现跳点则当前点为跳点 if self.jump(nx, ny, dx, 0, start, goal): return (nx, ny) if self.jump(nx, ny, 0, dy, start, goal): return (nx, ny) # 5. 继续沿原方向跳跃 return self.jump(nx, ny, dx, dy, start, goal)第一步的is_walkable(nx, ny)检查是整个跳点的边界保障越界和撞墙都从这里返回。第二步把目标点作为天然跳点保证搜索一定能结束。第三步是水平/垂直方向唯一的跳点判定依据出现强制邻居就必须停下来。第四步处理对角线4.1检查两个直线分量的可走性防止斜穿障碍物角4.2递归探测水平和垂直分支如果任意分支上有跳点当前节点就是一个需要拐弯的位置。有一个容易忽略的细节第4步里的两个分支递归调用使用的是jump(nx, ny, dx, 0)和jump(nx, ny, 0, dy)它们会从(nx, ny)开始沿水平或垂直方向一直跳下去。如果地图空旷这个递归会一直深入到地图边缘性能压力很大。第5章我会给出迭代版本解决递归爆栈问题。3.3 主循环与路径回溯用heapq管理跳点find_path()是主搜索入口。它维护一个优先队列open_heap元素为(f, g, node)三元组f g h其中h用切比雪夫距离计算。每轮从堆里弹出f值最小的节点对它尝试8个方向跳跃把返回的跳点加入堆中。def heuristic(self, node, goal): 切比雪夫距离适合8方向移动的网格 return max(abs(node[0] - goal[0]), abs(node[1] - goal[1])) def find_path(self, start, goal): JPS主搜索返回从start到goal的路径节点列表 open_heap [] g_score {start: 0} came_from {start: None} # 优先队列元素(f, g, node) heapq.heappush(open_heap, (self.heuristic(start, goal), 0, start)) while open_heap: f, g, current heapq.heappop(open_heap) if current goal: return self.reconstruct_path(came_from, goal) x, y current for dx, dy in self.DIRECTIONS: jump_point self.jump(x, y, dx, dy, start, goal) if jump_point is None: continue # 跳点的新g值 当前g 移动距离切比雪夫距离 step_cost max(abs(jump_point[0] - x), abs(jump_point[1] - y)) tentative_g g step_cost if tentative_g g_score.get(jump_point, float(inf)): came_from[jump_point] current g_score[jump_point] tentative_g f tentative_g self.heuristic(jump_point, goal) heapq.heappush(open_heap, (f, tentative_g, jump_point)) return None # 没有可达路径 def reconstruct_path(self, came_from, goal): 从goal沿着came_from回溯到start返回路径节点列表 path [] node goal while node is not None: path.append(node) node came_from[node] path.reverse() return path主循环的g值计算和A不同A的邻居扩展代价固定为1而JPS一次jump()可能跳过多个格子所以step_cost要用max(abs(jump_point[0] - x), abs(jump_point[1] - y))计算实际跳过的曼哈顿步数这也是切比雪夫距离的定义。堆元素里同时存了f和g弹出后直接用g参与新代价计算避免每次从字典里查。路径回溯和A*完全一致从目标点沿着came_from链一路回到起点再反转。注意JPS路径上相邻两个节点之间可能存在多个普通格子这里只记录跳点序列画图时用线段连接即可不需要补全中间格子。4. 用pygame做可视化实践颜色映射、状态记录与逐帧回放4.1 可视化设计要展示哪些状态用什么颜色搜索过程可视化不只是锦上添花跳点扩展的顺序、开放列表的规模变化、关闭列表的增长趋势都是判断JPS实现是否正确的线索。我做可视化时会展示四类信息地图本身、当前搜索帧的开放列表与关闭列表、本轮新发现的跳点、最终路径。颜色映射如下元素颜色表示含义可走格子白色普通空地障碍物深灰色不可通行开放列表浅绿色待扩展的跳点候选关闭列表浅蓝色已扩展完成的节点新跳点红色当前帧新发现的跳点最终路径金色粗线搜索结果为了让回放过程有节奏我新增了SearchFrame类把每一帧搜索完成后的状态快照存下来。注意存储时要做拷贝避免后续修改污染历史帧。class SearchFrame: 记录一轮搜索结束后的可视化状态快照 def __init__(self, open_nodes, closed_nodes, current, new_jumps): self.open_nodes list(open_nodes) # 开放列表中的节点 self.closed_nodes list(closed_nodes) # 关闭列表中的节点 self.current current # 当前扩展的节点 self.new_jumps list(new_jumps) # 本轮新发现的跳点open_nodes列表里的每个元素是坐标元组绘制时直接按坐标填充矩形即可。closed_nodes同理。new_jumps是本轮从当前节点跳跃获得的所有跳点专门存一份是为了用红色高亮让观察者看清楚每次扩展跳到了哪些位置。4.2 记录搜索过程把开放列表、关闭列表和跳点存成帧在find_path的基础上增加一个带追踪的版本每轮循环结束时把当前状态追加到frames列表。这个版本几乎不改变原有搜索逻辑只是多了快照记录。def find_path_with_trace(self, start, goal): 带搜索过程记录的JPS主搜索返回(path, frames) open_heap [] g_score {start: 0} came_from {start: None} closed set() frames [] heapq.heappush(open_heap, (self.heuristic(start, goal), 0, start)) while open_heap: f, g, current heapq.heappop(open_heap) if current in closed: continue closed.add(current) # 记录当前帧注意存副本不能存引用 frames.append(SearchFrame( open_nodes[n for _, _, n in open_heap], closed_nodeslist(closed), currentcurrent, new_jumps[] )) if current goal: path self.reconstruct_path(came_from, goal) return path, frames x, y current for dx, dy in self.DIRECTIONS: jump_point self.jump(x, y, dx, dy, start, goal) if jump_point is None: continue step_cost max(abs(jump_point[0] - x), abs(jump_point[1] - y)) tentative_g g step_cost if tentative_g g_score.get(jump_point, float(inf)): came_from[jump_point] current g_score[jump_point] tentative_g f tentative_g self.heuristic(jump_point, goal) heapq.heappush(open_heap, (f, tentative_g, jump_point)) frames[-1].new_jumps.append(jump_point) # 记录本轮的跳点 return None, framesframes[-1].new_jumps.append(jump_point)这一行的位置很讲究它必须放在tentative_g g_score.get(...)条件内部只有真正被加入开放列表的跳点才值得高亮。如果这个跳点之前已经通过其他路径到达过且g值更优那它不是新跳点画出来会误导观察者。open_nodes[n for _, _, n in open_heap]这行做了浅拷贝把堆里的节点坐标提取出来存成普通列表。如果直接保存open_heap的引用后续heapq操作会修改原堆内容导致所有历史帧的开放列表都变成最后一帧的样子。4.3 pygame绘制与回放控制可视化类负责把帧数据画到屏幕上。核心思路是先画地图底图再叠加当前帧的关闭列表、开放列表和跳点最后在最后一帧叠加路径。回放控制用键盘空格键逐帧前进左方向键回退R键重置到第一帧。import pygame class JPSVisualizer: def __init__(self, grid, path, frames, cell_size40): pygame.init() self.grid grid self.path path self.frames frames self.cell_size cell_size self.rows len(grid) self.cols len(grid[0]) self.screen pygame.display.set_mode( (self.cols * cell_size, self.rows * cell_size) ) pygame.display.set_caption(JPS Search Visualization) self.clock pygame.time.Clock() # 颜色定义 self.COLOR_EMPTY (255, 255, 255) self.COLOR_OBSTACLE (40, 40, 40) self.COLOR_START (0, 200, 0) self.COLOR_GOAL (255, 0, 255) self.COLOR_OPEN (200, 240, 200) self.COLOR_CLOSED (200, 220, 240) self.COLOR_JUMP (255, 80, 80) self.COLOR_PATH (255, 200, 0) self.frame_index 0 self.total_frames len(frames) def draw_grid(self): 绘制地图底图包括可走格子和障碍物 for r in range(self.rows): for c in range(self.cols): color self.COLOR_EMPTY if self.grid[r][c] 0 else self.COLOR_OBSTACLE rect pygame.Rect(c * self.cell_size, r * self.cell_size, self.cell_size, self.cell_size) pygame.draw.rect(self.screen, color, rect) pygame.draw.rect(self.screen, (180, 180, 180), rect, 1) # 网格线 def draw_frame(self): 绘制当前帧的搜索状态 self.draw_grid() if self.frame_index self.total_frames: frame self.frames[self.frame_index] # 关闭列表浅蓝色 for node in frame.closed_nodes: rect pygame.Rect(node[1] * self.cell_size, node[0] * self.cell_size, self.cell_size, self.cell_size) pygame.draw.rect(self.screen, self.COLOR_CLOSED, rect) # 开放列表浅绿色 for node in frame.open_nodes: rect pygame.Rect(node[1] * self.cell_size, node[0] * self.cell_size, self.cell_size, self.cell_size) pygame.draw.rect(self.screen, self.COLOR_OPEN, rect) # 本轮新跳点红色 for node in frame.new_jumps: rect pygame.Rect(node[1] * self.cell_size, node[0] * self.cell_size, self.cell_size, self.cell_size) pygame.draw.rect(self.screen, self.COLOR_JUMP, rect) # 最后一帧显示最终路径 if self.path and self.frame_index self.total_frames - 1: for i in range(len(self.path) - 1): a self.path[i] b self.path[i 1] ax a[1] * self.cell_size self.cell_size // 2 ay a[0] * self.cell_size self.cell_size // 2 bx b[1] * self.cell_size self.cell_size // 2 by b[0] * self.cell_size self.cell_size // 2 pygame.draw.line(self.screen, self.COLOR_PATH, (ax, ay), (bx, by), 4) def run(self): 进入pygame事件循环支持键盘回放控制 running True while running: for event in pygame.event.get(): if event.type pygame.QUIT: running False elif event.type pygame.KEYDOWN: if event.key pygame.K_SPACE: # 空格前进一帧 self.frame_index min(self.frame_index 1, self.total_frames - 1) elif event.key pygame.K_LEFT: # 左方向键后退一帧 self.frame_index max(self.frame_index - 1, 0) elif event.key pygame.K_r: # R键回到第一帧 self.frame_index 0 self.draw_frame() pygame.display.flip() self.clock.tick(30) # 限制帧率避免CPU空转 pygame.quit()draw_frame()的绘制顺序很重要先画关闭列表再叠加开放列表最后画跳点。这样跳点始终显示在最上层不会被其他颜色遮盖。绘制网格线用的浅灰(180, 180, 180)只画边框不参与填充视觉上能清晰分辨每个格子。使用方式也很直接先实例化寻路器调用find_path_with_trace()拿到路径和帧列表然后交给可视化器播放。grid [ [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 1], [0, 0, 0, 1, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], ] finder JPSPathfinder(grid) path, frames finder.find_path_with_trace((0, 0), (7, 7)) visualizer JPSVisualizer(grid, path, frames) visualizer.run()运行后按空格键你会看到搜索从起点开始红色跳点依次出现浅蓝色区域逐步扩散。空旷区域里跳点之间的快速跳跃正是JPS区别于A的地方——A会一格一格扩张而JPS的开放列表大多数时间只有几个节点。5. JPS实现避坑指南对角线穿墙、递归爆栈与路径非最优5.1 对角线穿墙is_walkable的检查顺序不对现象最终路径斜着穿过了障碍物的角看起来像是从墙角蹭过去的。原因jump()函数在走对角线时没有检查水平分量和垂直分量的可走性。如果(nx, y)或(x, ny)是障碍物这个对角线移动本身就是非法的但代码仍然允许通过了。解决在对角线分支里显式检查两个直线分量not self.is_walkable(nx, y) or not self.is_walkable(x, ny)时直接返回None。这段代码我在3.2节的jump()中已经加上了如果你是自己从头写的务必确认这个分支没有被省略。5.2 jump递归爆栈空旷地图直线距离太长现象地图是50x50的空地搜索跑到一半Python报RecursionError: maximum recursion depth exceeded。原因jump()使用递归实现空旷地图上一条直线可能跨越几十甚至上百个格子每格一层递归。Python默认递归深度约1000地图再大一点必爆。解决有两个方案。第一个是临时提升递归限制sys.setrecursionlimit(20000)简单但治标不治本。第二个是把递归改成循环这才是一劳永逸的做法。迭代版jump()如下def jump_iterative(self, x, y, dx, dy, start, goal): 迭代版跳跃函数避免递归爆栈 nx, ny x dx, y dy while True: if not self.is_walkable(nx, ny): return None if (nx, ny) goal: return (nx, ny) if self.get_forced_neighbors(nx, ny, dx, dy): return (nx, ny) if dx ! 0 and dy ! 0: if not self.is_walkable(nx, y) or not self.is_walkable(x, ny): return None # 水平或垂直分支有跳点当前节点是跳点 if self.jump_iterative(nx, ny, dx, 0, start, goal): return (nx, ny) if self.jump_iterative(nx, ny, 0, dy, start, goal): return (nx, ny) # 沿原方向继续前进一步 x, y nx, ny nx, ny x dx, y dy注意迭代版里水平/垂直分支的探测仍然可以用递归因为分支方向是直线深度受地图宽度限制通常可接受主方向改为循环推进。这样就避免了最长直线段的递归深度。5.3 路径存在但不是最短强制邻居的方向符号写反现象路径能走出来但目测明显绕了路或者比A*的结果长。原因get_forced_neighbors()里垂直方向的侧向偏移量符号写反了。比如垂直移动(dx0, dy1)时左右侧的检查应该看(xside, y)和(xside, y-dy)。如果把y-dy写成ydy检查的其实是身后方向的格子强制邻居判定完全错误该拐弯的地方不拐弯路径自然变形。解决先用一个3x3的小地图把起点放在中间手动算一遍每个方向的强制邻居再和代码输出对比。这种问题用单步调试打印最有效不要直接在大地图上排查。我把这个排查方式列为我的调试血泪经验JPS出问题90%都在强制邻居的坐标计算上。5.4 可视化卡顿pygame循环里跑了搜索现象按一次空格要卡一两秒画面才动一下。原因一种是把find_path()放在了run()的事件循环里每次按键都重新搜索一遍另一种是frames里的closed_nodes直接存了set对象引用后续历史帧的set内容被篡改状态越积越多导致绘制层叠混乱。解决先完整跑一遍find_path_with_trace()拿到全部帧再进入pygame循环。回放期间不做任何搜索计算。存帧时确保list()拷贝参考4.2节的写法。可视化只负责画图搜索过程只在初始化时执行一次。5.5 起点自身就是跳点吗初始化时的重复扩展现象搜索能跑通但关闭列表里起点周围出现大量重复扩展开放列表里同一个跳点被推入多次。原因jump()对起点也执行了和普通节点一样的逻辑但起点没有父节点方向严格来说它的邻居集合应当是全部8个方向而且不应当对自己做跳跃判断。如果主循环里对起点的每个方向调jump()时某个方向的第一步又跳回了起点就会形成冗余。解决一种做法是在主循环里跳过jump_point start的情况更稳妥的是用g_score字典做去重已经在关闭列表里的节点不再重复扩展已经在开放列表里且g值更差的直接丢弃。我建议两种都做closed集合去重能防止循环g_score比较能保证最优性。6. 落地前的最后一道关随机地图对比、JPS与动态障碍扩展6.1 用随机地图验证JPS提速效果看实现是否合格最快的方式是随机生成一批地图在相同起点终点下对比JPS和A*的扩展节点数。我一般用30x30和50x50两种尺寸障碍物比例分别设0和0.3统计关闭列表的最终大小作为扩展节点指标地图尺寸与障碍率A*扩展节点数JPS扩展节点数提速倍数30x30空地约300约30约10倍30x3030%障碍约180约40约4.5倍50x50空地约900约60约15倍50x5030%障碍约520约80约6.5倍这些数值是示意性的具体取决于地图结构和随机种子但趋势稳定障碍物越少JPS的剪枝优势越明显障碍物密集时跳点频繁出现优势会缩小。我在做对比时习惯给两边用同一个启发函数并且关闭列表统计逻辑保持一致否则对比没有意义。6.2 JPS的离线预处理思路JPS是JPS的离线增强版在搜索之前遍历整张地图为每个格子预先计算“朝某个方向跳跃到第一个跳点的距离”在线搜索时jump()变成O(1)查表不再递归。代价是预处理时间和内存开销适合地图静态、需要反复查询路径的场景比如游戏里固定关卡的最短路缓存。如果你在做一个地图从不变化的应用JPS是值得考虑的升级方向。6.3 动态障碍环境下的取舍JPS对动态障碍很不友好障碍物一变跳点关系就失效离线预计算全部作废。常见做法是小范围障碍变化时只清理受影响区域的跳点缓存后重新搜索障碍频繁变化时考虑D* Lite这类增量搜索算法或者把地图分块在块内做局部修复。选型时心里要有数JPS是静态地图的利器动态场景不要硬上。6.4 一点实践习惯我自己的调试习惯是实现JPS前先把A*跑通再改造成JPS最后对比两条路径是否一致。路径不一致就回头查强制邻居的坐标计算这个习惯帮我避开了很多“看似正确”的翻车。开着可视化回放还有一个额外的用处跳点的扩展顺序本身就能暴露性能和逻辑问题比如某个跳点反复弹出说明g_score更新逻辑有冗余。希望这篇文章里的实现细节和踩坑记录能帮到你至少在下一个涉及网格寻路的项目里你能少走几步弯路。本文还有配套的精品资源点击获取