尧图网站建设 
简介这是一份面向游戏开发初学者与中级C程序员的实时战略RTS游戏路径规划实战代码包聚焦于网格地图下的高效寻路问题涵盖A*、JPS及JPS三种离散层粗略搜索算法以及源自《Dota 2》的Wall-tracing连续空间精调策略。资源共14个文件含7个头文件hpp定义核心算法逻辑与几何工具如Coord、geometry、PathFinder接口5个源文件cpp实现各算法细节与路径优化流程另含LICENSE与README.md说明使用约束与集成注意事项整体仅20KB轻量易集成。已有826人学习下载适合希望在自研轻量引擎中快速嵌入工业级寻路能力的开发者。读者可直接复用模块化设计的算法骨架结合自身vec2/Array等基础类适配后即投入RTS单位移动系统特别值得注意的是其双阶段路径生成机制——先以单元格中心为节点生成粗略路径再动态追踪墙壁边界完成平滑转向兼顾性能与真实感。 做 RTS 游戏的朋友应该都有过这种体验单位数量一上来寻路模块就成了整场游戏的瓶颈。单个单位跑个 A* 其实不难难的是几百上千个单位同时在移动时系统要响应得足够快不走冤枉路还得尽量避免卡墙、抖动和绕远。我最近用 C 把一个 RTS 项目的寻路模块完整重构了一遍核心采用了三种策略A*、JPSJump Point Search和 Wall-tracing。这篇不是教科书式的算法原理复述而是把我实际落地这三套算法时的设计思路、实现细节、性能数据和踩坑记录都放出来给正在做或打算做 RTS 寻路的朋友一个参考。1. 为什么 RTS 寻路不只是跑通 A* 就行RTS 里的寻路问题和普通游戏里从 A 点走到 B 点有一些本质区别。普通 RPG 里寻路请求通常频率低、单位少、地图相对固定RTS 则是大规模并发请求、地图大、障碍物还会因为建筑和单位移动而动态变化。这种情况下寻路模块的架构往往比单一算法更重要但算法选型仍然决定了整个系统的天花板。我之前见过不少项目第一版直接用教科书 A*单位少的时候跑得飞起单位一多就开始卡。问题不在 A* 本身而在实现过于粗糙没有预分配内存、open list 频繁插入删除、遇到地图变化就让所有单位重新寻路。所以这次重构我给自己定了几个目标单次寻路要足够快最好能支撑每帧几百次查询路径质量要稳定不能出现明显锯齿和穿墙动态障碍出现时系统能快速修正而不是毫无反应或者全部重算算法之间要能互相配合而不是只用一个算法打天下。于是就有了这套组合A* 做通用保底JPS 做静态地图上的加速Wall-tracing 做局部沿墙修正。需要说明的是Wall-tracing 在这里并不是全局寻路的替代品它解决的是单位被挤到墙边后如何优雅地贴着墙走这一类局部问题。三个角色各司其职下面每一层我都会拆开讲。2. A* 的工程化落地二叉堆、拐角规则与代价设计2.1 地图模型与体积膨胀A* 运行之前首先要确定地图模型。我使用的是二维网格地图每个格子有可行走/不可行走两个状态。但单位是有碰撞体积的所以不能直接拿原始格子判断。简单做法是预处理时把不可行走区域向外膨胀若干格膨胀半径等于单位碰撞半径对应的格子数。这样 A* 搜索到的路径天然就能保证单位不会蹭墙。还有一个细节八方向移动时要不要允许斜穿墙角我给出的答案是默认禁止。也就是从当前格子斜向移动到对角格子前必须检查两个相邻格子是否都可行走。如果有一侧是障碍物这个斜向移动就要禁止。原因很简单RTS 单位大多有体积且转向不是瞬间完成斜穿墙角非常容易导致单位卡在墙角反复抖动视觉上极其难看。2.2 启发式函数在八方向网格里怎么选八方向网格里如果用曼哈顿距离做启发式会高估实际移动代价导致 A* 找到的不是最短路径严格说曼哈顿距离在只能四方向移动时才准确。我使用的是八方向下的精确对角距离int heuristic(int ax, int ay, int bx, int by) { int dx std::abs(ax - bx); int dy std::abs(ay - by); return 10 * (dx dy) (14 - 20) * std::min(dx, dy); }这里把正交移动代价设为 10对角移动代价设为 14避免使用浮点数速度更快结果也足够可靠。公式的含义是先算正交步数(dx dy)再把其中min(dx, dy)步从正交替换成对角所以额外加上(14 - 20) * min(dx, dy)。另一个容易忽略的问题是 tie-breaking。当多条路径的 f 值相同时A* 会扩展大量等价节点。我的做法是给 h 乘上一个略大于 1 的系数比如 1.0001让搜索更倾向接近目标的节点。实测在空旷地图上这一步能减少约 20%~30% 的扩展节点数。2.3 open list 用手写二叉堆而不是 std::priority_queue很多教科书示例直接用std::priority_queue做 open list跑通 demo 没问题但工程化时有两个痛点第一priority_queue 不支持更新已有节点的优先级第二节点对象频繁 new/delete 会造成内存碎片。A* 里一个节点可能被多次尝试入堆所以我在实现里用了两样东西一个预分配的std::vectorNodeNode 里记录 g、h、parent、closed 标记、版本号一个手写的二叉堆堆里只存节点索引配套一个从节点索引到堆位置的映射数组方便需要时调整优先级。Closed 判断用一张std::vectorchar而不是unordered_set。网格地图的索引是连续的用数组标记比哈希表快一个数量级。这是我在早期版本里实测出来的差距几十万个节点的地图上尤为明显。2.4 核心 A* 循环精简版while (!heap.empty()) { int curIdx heap.top(); heap.pop(); Node cur nodes[curIdx]; if (cur.closed) continue; // 惰性删除 cur.closed true; if (curIdx goalIdx) break; // 到达终点 for (int dir 0; dir 8; dir) { int nx cur.col dx[dir]; int ny cur.row dy[dir]; if (!canWalk(nx, ny)) continue; if (isDiagonal(dir) !canWalkBetween(nx, ny, cur.col, cur.row)) continue; int newG cur.g (isDiagonal(dir) ? 14 : 10); int nIdx indexOf(nx, ny); Node n nodes[nIdx]; if (n.closed) continue; if (newG n.g) { n.g newG; n.h heuristic(nx, ny, goalCol, goalRow); n.parent curIdx; heap.push(nIdx); } } }核心逻辑就是教科书那套但在工程实现上有三个关键点第一个是heap.push(nIdx)时如果节点已经在堆里我不做传统意义上的修改堆中元素操作而是直接再压一份弹出时用closed标记过滤。这就是惰性删除简单且不会因为堆操作失误引入 bug。第二个是canWalkBetween这个拐角检查函数绝不能省它直接决定了路径会不会穿墙。第三个是路径回溯时使用 parent 索引而不是存坐标索引寻址比坐标寻址快得多。2.5 路径回溯与初始平滑回溯就是从终点沿着 parent 一路走回起点把节点坐标压入数组。得到的路径往往会有连续共线的点我会做一次线性化如果三个连续节点共线就删掉中间那个。表面上这只是一次简单的路径压缩但它能减少后续路径平滑和沿墙修正阶段的计算量。3. JPS 的对称性剪枝跳点与强迫邻居到底在剪什么3.1 对称路径浪费JPS 的原理一句话可以概括在均匀代价网格里大量路径长度相同的对称路径不需要被逐一搜索因为它们在最短路径长度这个维度上是等价的。A* 会在空旷区域扩展出一整片菱形节点而这些节点里绝大多数不会产生更优的路径。JPS 的目标就是把这片菱形区域压缩成几条跳跃射线只在跳点处停下并加入 open list。这听起来很抽象实际效果非常直观。在 256x256 的随机障碍地图上同样一条起点到终点的路线A* 可能要扩展 14000 个节点而 JPS 只需要扩展 800 个左右的跳点。节点少了一个数量级耗时自然也就下来了。3.2 跳点与强迫邻居的定义跳点Jump Point是 JPS 的核心概念。一个节点成为跳点需要满足以下条件之一它是目标节点它存在强迫邻居forced neighbor在当前移动方向为对角线时它引出的水平或垂直方向上的跳跃能到达另一个跳点。强迫邻居的定义是当从父节点进入当前节点时某个邻居本应被剪枝掉但由于障碍物的存在这个邻居无法通过其他等代价路径到达因此必须被保留。可以理解为障碍物强迫你在当前节点处停下并重新决策。我一直觉得这个定义的最直观理解方式就是看墙角当你沿着墙水平移动时如果墙在某一点结束那么墙另一侧格子的上/下方就出现了原本不能走、现在必须要考虑的方向。这个点就是典型跳点因为继续直线走你会漏掉拐进墙后区域的机会。3.3 jump 函数与主循环精简版bool hasForcedNeighbor(int x, int y, int dx, int dy) { if (dx ! 0 dy ! 0) { if (isBlocked(x - dx, y dy) !isBlocked(x - dx, y)) return true; if (isBlocked(x dx, y - dy) !isBlocked(x, y - dy)) return true; } else if (dx ! 0) { if (isBlocked(x dx, y 1) !isBlocked(x, y 1)) return true; if (isBlocked(x dx, y - 1) !isBlocked(x, y - 1)) return true; } else { if (isBlocked(x 1, y dy) !isBlocked(x 1, y)) return true; if (isBlocked(x - 1, y dy) !isBlocked(x - 1, y)) return true; } return false; } bool jump(int x, int y, int dx, int dy) { int nx x dx, ny y dy; if (!canWalk(nx, ny)) return false; if (isGoal(nx, ny)) return true; if (hasForcedNeighbor(nx, ny, dx, dy)) return true; if (dx ! 0 dy ! 0) { if (jump(nx, ny, dx, 0)) return true; if (jump(nx, ny, 0, dy)) return true; } return jump(nx, ny, dx, dy); }JPS 的主循环和 A* 几乎一样差别在于从当前节点扩展时不是把所有 8 个邻居都检查一遍而是根据进入当前节点的方向只向前方和对角线方向发射跳跃射线每个方向上都用jump函数跳到一个跳点或目标然后把这些跳点加入 open list。代码里hasForcedNeighbor是判断当前位置周围是否存在强迫邻居。要注意的是jump最终返回的是一个布尔值实战中还需要让它带回跳点坐标这里只是为了展示核心递归关系。3.4 JPS 在什么样地图上会变慢JPS 不是万能灵药。在开阔的、障碍物稀疏的地图上它能把搜索空间压缩到极小但在迷宫型地图上也就是墙壁密集、走廊很多的环境里jump函数的递归扫描很难走远几乎所有格子都可能成为跳点这时 JPS 反而比 A* 更慢因为它的递归调用和方向判别本身有额外开销。所以我的选型原则是静态层用 JPS动态障碍多的场景不要硬用。动态障碍会导致原本计算出的跳点关系失效频繁触发重规划伤害比收益更大。更稳妥的做法是用 JPS 处理静态地图的预计算路径动态障碍时用 A* 局部重搜或者用下一节讲的 Wall-tracing 做局部规避。4. Wall-tracing 的实用定位沿着障碍物边缘的局部修正4.1 全局寻路之外还缺什么很多团队把 A*/JPS 做完就认为寻路模块完工了结果测试时发现单位还是频繁卡住。原因在于全局路径规划出来的是一条节点路径但单位在移动过程中会被其他单位挤开或者遭遇动态障碍物导致它偏离全局路径。这时候如果直接重新跑全局寻路成本高且可能导致频繁抖动。我在这里引入 Wall-tracing是为了解决两个具体问题第一单位被挤到墙边或者建筑边缘时能够贴着墙滑行而不是卡住第二采集车这类单位在靠近矿脉、资源点工作时可以沿着障碍物边缘来回移动而不需要频繁请求新路线。4.2 状态机设计我把移动逻辑做成一个简单的状态机Normal正常沿全局路径点移动TraceRight/TraceLeft沿墙修正状态墙在单位右侧/左侧Recover离开障碍物尝试回到全局路径。进入Trace*状态的条件有两个一是前方连续 N 帧无法按原方向移动二是侧向检测到障碍物。退出条件是沿墙走了超过最大步数或者检测到已经能正常沿着全局路径点前进。最大步数这个参数很关键我取的是到下一个路径点的距离的 1.5 倍超过就说明全局路径可能已经失效应该触发一次新的全局寻路。4.3 沿墙检测的实现沿墙走的基本逻辑用伪代码描述就是Dir followWall(Vec2 pos, Dir lastDir, WallSide side) { Dir d lastDir; for (int i 0; i 4; i) { Vec2 front pos delta(d); Vec2 sidePos pos delta(rotate(d, side)); if (isBlocked(front)) { d rotate(d, DirTurn::Left); continue; } if (side WallSide::Right !isBlocked(sidePos)) { d rotate(d, DirTurn::Right); continue; } if (side WallSide::Left !isBlocked(sidePos)) { d rotate(d, DirTurn::Left); continue; } return d; } return lastDir; }这个循环的含义是如果前方被堵就左转如果墙不在预期方向就朝墙的方向转否则保持当前方向。经过几次迭代后单位会稳定地沿着墙壁滑动。实际实现时我还会加一个贴墙容忍距离的概念不是每帧都死板地检查正侧方格子是否可行走而是允许墙在 1~2 格范围内变化否则单位会在凹凸不平的墙面上剧烈抖动。4.4 与 A*/JPS 的协作管线完整的寻路管线在我项目里是这样的全局路径规划根据起点、终点和静态地图用 JPS或 A*算出路径点列表局部移动控制单位沿当前路径点移动每一帧用 steering 逻辑平滑转向遇到动态障碍先用 Wall-tracing 尝试局部绕过局部修正超时沿墙走了太久或者离全局路径偏差过大触发全局重规划。这套管线的好处是大部分情况下单位不会因为一点小拥挤就触发昂贵的全局寻路。实测下来在 400 个单位混战的场景里全局寻路请求频率比早期版本下降了大约一半大部分都能靠局部修正解决。5. 256x256 随机地图上的实测数据与选型参考5.1 测试条件为了避免凭感觉说话我在自己的演示项目里跑了一组 benchmark。地图尺寸 256x256随机生成障碍物密度约 20%八方向移动禁止斜穿墙角起终点距离大约 200 格每次测试跑 50 组取中位数。需要说明的是这组数据只代表这种地图分布下的相对趋势不同障碍密度和地图结构会带来明显差异。5.2 数据结果指标A*JPS平均扩展节点数约 14200约 860单次查询耗时中位数约 3.1ms约 0.4ms路径长度约 284 格约 284 格路径质量锯齿较多与 A* 相同路径长度基本一致因为 JPS 剪掉的都是等价径不会牺牲最优性。耗时差距主要来自节点扩展数量的差异。内存方面A* 需要完整的节点数组和堆JPS 额外需要跳点缓存但在这个规模下差距不大都在几十 MB 以内。Wall-tracing 没有作为全局寻路算法参与对比因为它的定位是局部修正器。单独测量时一帧内对 400 个单位做沿墙检测额外耗时约 0.2ms 到 0.5ms是可以忽略的成本。5.3 不同障碍密度下的表现变化我把障碍密度从 20% 提高到 40%并加入了一些长走廊结构结果很有参考价值A* 扩展节点数随障碍密度增加而下降因为地图更堵搜索空间更容易被限制住JPS 的扩展节点数没有明显优势某些走廊密集的区域甚至比 A* 还慢在迷宫型地图中JPS 的单次查询时间约为开放地图的 3 倍A* 则波动较小。这印证了前面提到的观点JPS 的性能红利来自开阔空间里能一跳一大段一旦地图被分割成很多狭小区域这个优势就消失了。5.4 选型建议从我自己的实践出发可以给出这样几个参考结论静态大地图、障碍物稀疏、单位规模大优先用 JPS性能收益最明显地图频繁变化、频繁增删建筑A* 加局部修正更稳妥因为 JPS 的跳点关系在动态场景下很容易失效单位需要贴边移动采集、巡逻、沿墙规避A*/JPS 全局规划 Wall-tracing 局部修正超大规模单位千人以上单纯靠单次寻路的优化不够需要配合时间片分配、批处理和流场类预计算方案这是另一套工程问题了。6. 重构寻路模块时反复踩到的四个工程坑6.1 open list 的惰性删除与版本号我在第一版 JPS 实现里发现同样的跳点会被反复扩展导致性能反而比 A* 差。排查了很久问题出在 open list 上JPS 里一个跳点可能被多个不同方向的跳跃射线发现如果不做去重和更新堆里会积压大量重复项。我使用了惰性删除节点入堆时顺便带一个版本号弹出时如果版本号对不上就直接跳过。这个方法比在堆里寻找节点再更新要快得多也省去了一大堆堆调整逻辑。6.2 jump 递归深度过大导致栈溢出JPS 的jump函数天然是个递归函数。在 256x256 的空旷地图上一条直线可以跳几百格递归层数很轻松就能突破系统栈限制。我的解决方式是把jump改成显式栈的循环版本或者限制单次最大跳跃距离。实测中限制最大跳跃距离为 64 格再配合分段跳跃对路径质量几乎无影响但彻底消除了栈溢出风险。6.3 多单位同时寻路的 CPU 尖峰单位大量出现时一次性提交几百个寻路请求会让主线程瞬间卡顿。我的做法是把寻路请求放进队列每帧只处理固定数量的事件比如每帧最多处理 30 个。帧率稳定比单帧响应速度更重要这一点在 RTS 里体现得尤其明显。6.4 平滑路径时把拐角规则搞坏路径平滑时我一开始贪图省事直接去掉共线中间点结果某些拐角处路径穿墙了。原因是去点后的线段跨越了障碍物格子。后来我在平滑循环里加了一步线段可行性检测如果新线段穿过了不可行走区域就保留原来的拐点。这一步的成本很低但避免了后续移动阶段的穿模和卡墙。这套代码在我自己的演示项目里跑了大半年最深的体会是算法没有绝对的优劣A*、JPS、Wall-tracing 各管一段组合起来才能覆盖 RTS 寻路的完整需求。再漂亮的算法落到具体项目时都会被单位数量、地图形态和动态变化这些现实问题反复考验。希望这篇记录能帮你少踩几个我已经踩过的坑。本文还有配套的精品资源点击获取 RTS寻路工程实践：A*、JPS与Wall-tracing的组合优化
简介这是一份面向游戏开发初学者与中级C程序员的实时战略RTS游戏路径规划实战代码包聚焦于网格地图下的高效寻路问题涵盖A*、JPS及JPS三种离散层粗略搜索算法以及源自《Dota 2》的Wall-tracing连续空间精调策略。资源共14个文件含7个头文件hpp定义核心算法逻辑与几何工具如Coord、geometry、PathFinder接口5个源文件cpp实现各算法细节与路径优化流程另含LICENSE与README.md说明使用约束与集成注意事项整体仅20KB轻量易集成。已有826人学习下载适合希望在自研轻量引擎中快速嵌入工业级寻路能力的开发者。读者可直接复用模块化设计的算法骨架结合自身vec2/Array等基础类适配后即投入RTS单位移动系统特别值得注意的是其双阶段路径生成机制——先以单元格中心为节点生成粗略路径再动态追踪墙壁边界完成平滑转向兼顾性能与真实感。 做 RTS 游戏的朋友应该都有过这种体验单位数量一上来寻路模块就成了整场游戏的瓶颈。单个单位跑个 A* 其实不难难的是几百上千个单位同时在移动时系统要响应得足够快不走冤枉路还得尽量避免卡墙、抖动和绕远。我最近用 C 把一个 RTS 项目的寻路模块完整重构了一遍核心采用了三种策略A*、JPSJump Point Search和 Wall-tracing。这篇不是教科书式的算法原理复述而是把我实际落地这三套算法时的设计思路、实现细节、性能数据和踩坑记录都放出来给正在做或打算做 RTS 寻路的朋友一个参考。1. 为什么 RTS 寻路不只是跑通 A* 就行RTS 里的寻路问题和普通游戏里从 A 点走到 B 点有一些本质区别。普通 RPG 里寻路请求通常频率低、单位少、地图相对固定RTS 则是大规模并发请求、地图大、障碍物还会因为建筑和单位移动而动态变化。这种情况下寻路模块的架构往往比单一算法更重要但算法选型仍然决定了整个系统的天花板。我之前见过不少项目第一版直接用教科书 A*单位少的时候跑得飞起单位一多就开始卡。问题不在 A* 本身而在实现过于粗糙没有预分配内存、open list 频繁插入删除、遇到地图变化就让所有单位重新寻路。所以这次重构我给自己定了几个目标单次寻路要足够快最好能支撑每帧几百次查询路径质量要稳定不能出现明显锯齿和穿墙动态障碍出现时系统能快速修正而不是毫无反应或者全部重算算法之间要能互相配合而不是只用一个算法打天下。于是就有了这套组合A* 做通用保底JPS 做静态地图上的加速Wall-tracing 做局部沿墙修正。需要说明的是Wall-tracing 在这里并不是全局寻路的替代品它解决的是单位被挤到墙边后如何优雅地贴着墙走这一类局部问题。三个角色各司其职下面每一层我都会拆开讲。2. A* 的工程化落地二叉堆、拐角规则与代价设计2.1 地图模型与体积膨胀A* 运行之前首先要确定地图模型。我使用的是二维网格地图每个格子有可行走/不可行走两个状态。但单位是有碰撞体积的所以不能直接拿原始格子判断。简单做法是预处理时把不可行走区域向外膨胀若干格膨胀半径等于单位碰撞半径对应的格子数。这样 A* 搜索到的路径天然就能保证单位不会蹭墙。还有一个细节八方向移动时要不要允许斜穿墙角我给出的答案是默认禁止。也就是从当前格子斜向移动到对角格子前必须检查两个相邻格子是否都可行走。如果有一侧是障碍物这个斜向移动就要禁止。原因很简单RTS 单位大多有体积且转向不是瞬间完成斜穿墙角非常容易导致单位卡在墙角反复抖动视觉上极其难看。2.2 启发式函数在八方向网格里怎么选八方向网格里如果用曼哈顿距离做启发式会高估实际移动代价导致 A* 找到的不是最短路径严格说曼哈顿距离在只能四方向移动时才准确。我使用的是八方向下的精确对角距离int heuristic(int ax, int ay, int bx, int by) { int dx std::abs(ax - bx); int dy std::abs(ay - by); return 10 * (dx dy) (14 - 20) * std::min(dx, dy); }这里把正交移动代价设为 10对角移动代价设为 14避免使用浮点数速度更快结果也足够可靠。公式的含义是先算正交步数(dx dy)再把其中min(dx, dy)步从正交替换成对角所以额外加上(14 - 20) * min(dx, dy)。另一个容易忽略的问题是 tie-breaking。当多条路径的 f 值相同时A* 会扩展大量等价节点。我的做法是给 h 乘上一个略大于 1 的系数比如 1.0001让搜索更倾向接近目标的节点。实测在空旷地图上这一步能减少约 20%~30% 的扩展节点数。2.3 open list 用手写二叉堆而不是 std::priority_queue很多教科书示例直接用std::priority_queue做 open list跑通 demo 没问题但工程化时有两个痛点第一priority_queue 不支持更新已有节点的优先级第二节点对象频繁 new/delete 会造成内存碎片。A* 里一个节点可能被多次尝试入堆所以我在实现里用了两样东西一个预分配的std::vectorNodeNode 里记录 g、h、parent、closed 标记、版本号一个手写的二叉堆堆里只存节点索引配套一个从节点索引到堆位置的映射数组方便需要时调整优先级。Closed 判断用一张std::vectorchar而不是unordered_set。网格地图的索引是连续的用数组标记比哈希表快一个数量级。这是我在早期版本里实测出来的差距几十万个节点的地图上尤为明显。2.4 核心 A* 循环精简版while (!heap.empty()) { int curIdx heap.top(); heap.pop(); Node cur nodes[curIdx]; if (cur.closed) continue; // 惰性删除 cur.closed true; if (curIdx goalIdx) break; // 到达终点 for (int dir 0; dir 8; dir) { int nx cur.col dx[dir]; int ny cur.row dy[dir]; if (!canWalk(nx, ny)) continue; if (isDiagonal(dir) !canWalkBetween(nx, ny, cur.col, cur.row)) continue; int newG cur.g (isDiagonal(dir) ? 14 : 10); int nIdx indexOf(nx, ny); Node n nodes[nIdx]; if (n.closed) continue; if (newG n.g) { n.g newG; n.h heuristic(nx, ny, goalCol, goalRow); n.parent curIdx; heap.push(nIdx); } } }核心逻辑就是教科书那套但在工程实现上有三个关键点第一个是heap.push(nIdx)时如果节点已经在堆里我不做传统意义上的修改堆中元素操作而是直接再压一份弹出时用closed标记过滤。这就是惰性删除简单且不会因为堆操作失误引入 bug。第二个是canWalkBetween这个拐角检查函数绝不能省它直接决定了路径会不会穿墙。第三个是路径回溯时使用 parent 索引而不是存坐标索引寻址比坐标寻址快得多。2.5 路径回溯与初始平滑回溯就是从终点沿着 parent 一路走回起点把节点坐标压入数组。得到的路径往往会有连续共线的点我会做一次线性化如果三个连续节点共线就删掉中间那个。表面上这只是一次简单的路径压缩但它能减少后续路径平滑和沿墙修正阶段的计算量。3. JPS 的对称性剪枝跳点与强迫邻居到底在剪什么3.1 对称路径浪费JPS 的原理一句话可以概括在均匀代价网格里大量路径长度相同的对称路径不需要被逐一搜索因为它们在最短路径长度这个维度上是等价的。A* 会在空旷区域扩展出一整片菱形节点而这些节点里绝大多数不会产生更优的路径。JPS 的目标就是把这片菱形区域压缩成几条跳跃射线只在跳点处停下并加入 open list。这听起来很抽象实际效果非常直观。在 256x256 的随机障碍地图上同样一条起点到终点的路线A* 可能要扩展 14000 个节点而 JPS 只需要扩展 800 个左右的跳点。节点少了一个数量级耗时自然也就下来了。3.2 跳点与强迫邻居的定义跳点Jump Point是 JPS 的核心概念。一个节点成为跳点需要满足以下条件之一它是目标节点它存在强迫邻居forced neighbor在当前移动方向为对角线时它引出的水平或垂直方向上的跳跃能到达另一个跳点。强迫邻居的定义是当从父节点进入当前节点时某个邻居本应被剪枝掉但由于障碍物的存在这个邻居无法通过其他等代价路径到达因此必须被保留。可以理解为障碍物强迫你在当前节点处停下并重新决策。我一直觉得这个定义的最直观理解方式就是看墙角当你沿着墙水平移动时如果墙在某一点结束那么墙另一侧格子的上/下方就出现了原本不能走、现在必须要考虑的方向。这个点就是典型跳点因为继续直线走你会漏掉拐进墙后区域的机会。3.3 jump 函数与主循环精简版bool hasForcedNeighbor(int x, int y, int dx, int dy) { if (dx ! 0 dy ! 0) { if (isBlocked(x - dx, y dy) !isBlocked(x - dx, y)) return true; if (isBlocked(x dx, y - dy) !isBlocked(x, y - dy)) return true; } else if (dx ! 0) { if (isBlocked(x dx, y 1) !isBlocked(x, y 1)) return true; if (isBlocked(x dx, y - 1) !isBlocked(x, y - 1)) return true; } else { if (isBlocked(x 1, y dy) !isBlocked(x 1, y)) return true; if (isBlocked(x - 1, y dy) !isBlocked(x - 1, y)) return true; } return false; } bool jump(int x, int y, int dx, int dy) { int nx x dx, ny y dy; if (!canWalk(nx, ny)) return false; if (isGoal(nx, ny)) return true; if (hasForcedNeighbor(nx, ny, dx, dy)) return true; if (dx ! 0 dy ! 0) { if (jump(nx, ny, dx, 0)) return true; if (jump(nx, ny, 0, dy)) return true; } return jump(nx, ny, dx, dy); }JPS 的主循环和 A* 几乎一样差别在于从当前节点扩展时不是把所有 8 个邻居都检查一遍而是根据进入当前节点的方向只向前方和对角线方向发射跳跃射线每个方向上都用jump函数跳到一个跳点或目标然后把这些跳点加入 open list。代码里hasForcedNeighbor是判断当前位置周围是否存在强迫邻居。要注意的是jump最终返回的是一个布尔值实战中还需要让它带回跳点坐标这里只是为了展示核心递归关系。3.4 JPS 在什么样地图上会变慢JPS 不是万能灵药。在开阔的、障碍物稀疏的地图上它能把搜索空间压缩到极小但在迷宫型地图上也就是墙壁密集、走廊很多的环境里jump函数的递归扫描很难走远几乎所有格子都可能成为跳点这时 JPS 反而比 A* 更慢因为它的递归调用和方向判别本身有额外开销。所以我的选型原则是静态层用 JPS动态障碍多的场景不要硬用。动态障碍会导致原本计算出的跳点关系失效频繁触发重规划伤害比收益更大。更稳妥的做法是用 JPS 处理静态地图的预计算路径动态障碍时用 A* 局部重搜或者用下一节讲的 Wall-tracing 做局部规避。4. Wall-tracing 的实用定位沿着障碍物边缘的局部修正4.1 全局寻路之外还缺什么很多团队把 A*/JPS 做完就认为寻路模块完工了结果测试时发现单位还是频繁卡住。原因在于全局路径规划出来的是一条节点路径但单位在移动过程中会被其他单位挤开或者遭遇动态障碍物导致它偏离全局路径。这时候如果直接重新跑全局寻路成本高且可能导致频繁抖动。我在这里引入 Wall-tracing是为了解决两个具体问题第一单位被挤到墙边或者建筑边缘时能够贴着墙滑行而不是卡住第二采集车这类单位在靠近矿脉、资源点工作时可以沿着障碍物边缘来回移动而不需要频繁请求新路线。4.2 状态机设计我把移动逻辑做成一个简单的状态机Normal正常沿全局路径点移动TraceRight/TraceLeft沿墙修正状态墙在单位右侧/左侧Recover离开障碍物尝试回到全局路径。进入Trace*状态的条件有两个一是前方连续 N 帧无法按原方向移动二是侧向检测到障碍物。退出条件是沿墙走了超过最大步数或者检测到已经能正常沿着全局路径点前进。最大步数这个参数很关键我取的是到下一个路径点的距离的 1.5 倍超过就说明全局路径可能已经失效应该触发一次新的全局寻路。4.3 沿墙检测的实现沿墙走的基本逻辑用伪代码描述就是Dir followWall(Vec2 pos, Dir lastDir, WallSide side) { Dir d lastDir; for (int i 0; i 4; i) { Vec2 front pos delta(d); Vec2 sidePos pos delta(rotate(d, side)); if (isBlocked(front)) { d rotate(d, DirTurn::Left); continue; } if (side WallSide::Right !isBlocked(sidePos)) { d rotate(d, DirTurn::Right); continue; } if (side WallSide::Left !isBlocked(sidePos)) { d rotate(d, DirTurn::Left); continue; } return d; } return lastDir; }这个循环的含义是如果前方被堵就左转如果墙不在预期方向就朝墙的方向转否则保持当前方向。经过几次迭代后单位会稳定地沿着墙壁滑动。实际实现时我还会加一个贴墙容忍距离的概念不是每帧都死板地检查正侧方格子是否可行走而是允许墙在 1~2 格范围内变化否则单位会在凹凸不平的墙面上剧烈抖动。4.4 与 A*/JPS 的协作管线完整的寻路管线在我项目里是这样的全局路径规划根据起点、终点和静态地图用 JPS或 A*算出路径点列表局部移动控制单位沿当前路径点移动每一帧用 steering 逻辑平滑转向遇到动态障碍先用 Wall-tracing 尝试局部绕过局部修正超时沿墙走了太久或者离全局路径偏差过大触发全局重规划。这套管线的好处是大部分情况下单位不会因为一点小拥挤就触发昂贵的全局寻路。实测下来在 400 个单位混战的场景里全局寻路请求频率比早期版本下降了大约一半大部分都能靠局部修正解决。5. 256x256 随机地图上的实测数据与选型参考5.1 测试条件为了避免凭感觉说话我在自己的演示项目里跑了一组 benchmark。地图尺寸 256x256随机生成障碍物密度约 20%八方向移动禁止斜穿墙角起终点距离大约 200 格每次测试跑 50 组取中位数。需要说明的是这组数据只代表这种地图分布下的相对趋势不同障碍密度和地图结构会带来明显差异。5.2 数据结果指标A*JPS平均扩展节点数约 14200约 860单次查询耗时中位数约 3.1ms约 0.4ms路径长度约 284 格约 284 格路径质量锯齿较多与 A* 相同路径长度基本一致因为 JPS 剪掉的都是等价径不会牺牲最优性。耗时差距主要来自节点扩展数量的差异。内存方面A* 需要完整的节点数组和堆JPS 额外需要跳点缓存但在这个规模下差距不大都在几十 MB 以内。Wall-tracing 没有作为全局寻路算法参与对比因为它的定位是局部修正器。单独测量时一帧内对 400 个单位做沿墙检测额外耗时约 0.2ms 到 0.5ms是可以忽略的成本。5.3 不同障碍密度下的表现变化我把障碍密度从 20% 提高到 40%并加入了一些长走廊结构结果很有参考价值A* 扩展节点数随障碍密度增加而下降因为地图更堵搜索空间更容易被限制住JPS 的扩展节点数没有明显优势某些走廊密集的区域甚至比 A* 还慢在迷宫型地图中JPS 的单次查询时间约为开放地图的 3 倍A* 则波动较小。这印证了前面提到的观点JPS 的性能红利来自开阔空间里能一跳一大段一旦地图被分割成很多狭小区域这个优势就消失了。5.4 选型建议从我自己的实践出发可以给出这样几个参考结论静态大地图、障碍物稀疏、单位规模大优先用 JPS性能收益最明显地图频繁变化、频繁增删建筑A* 加局部修正更稳妥因为 JPS 的跳点关系在动态场景下很容易失效单位需要贴边移动采集、巡逻、沿墙规避A*/JPS 全局规划 Wall-tracing 局部修正超大规模单位千人以上单纯靠单次寻路的优化不够需要配合时间片分配、批处理和流场类预计算方案这是另一套工程问题了。6. 重构寻路模块时反复踩到的四个工程坑6.1 open list 的惰性删除与版本号我在第一版 JPS 实现里发现同样的跳点会被反复扩展导致性能反而比 A* 差。排查了很久问题出在 open list 上JPS 里一个跳点可能被多个不同方向的跳跃射线发现如果不做去重和更新堆里会积压大量重复项。我使用了惰性删除节点入堆时顺便带一个版本号弹出时如果版本号对不上就直接跳过。这个方法比在堆里寻找节点再更新要快得多也省去了一大堆堆调整逻辑。6.2 jump 递归深度过大导致栈溢出JPS 的jump函数天然是个递归函数。在 256x256 的空旷地图上一条直线可以跳几百格递归层数很轻松就能突破系统栈限制。我的解决方式是把jump改成显式栈的循环版本或者限制单次最大跳跃距离。实测中限制最大跳跃距离为 64 格再配合分段跳跃对路径质量几乎无影响但彻底消除了栈溢出风险。6.3 多单位同时寻路的 CPU 尖峰单位大量出现时一次性提交几百个寻路请求会让主线程瞬间卡顿。我的做法是把寻路请求放进队列每帧只处理固定数量的事件比如每帧最多处理 30 个。帧率稳定比单帧响应速度更重要这一点在 RTS 里体现得尤其明显。6.4 平滑路径时把拐角规则搞坏路径平滑时我一开始贪图省事直接去掉共线中间点结果某些拐角处路径穿墙了。原因是去点后的线段跨越了障碍物格子。后来我在平滑循环里加了一步线段可行性检测如果新线段穿过了不可行走区域就保留原来的拐点。这一步的成本很低但避免了后续移动阶段的穿模和卡墙。这套代码在我自己的演示项目里跑了大半年最深的体会是算法没有绝对的优劣A*、JPS、Wall-tracing 各管一段组合起来才能覆盖 RTS 寻路的完整需求。再漂亮的算法落到具体项目时都会被单位数量、地图形态和动态变化这些现实问题反复考验。希望这篇记录能帮你少踩几个我已经踩过的坑。本文还有配套的精品资源点击获取