简介这是一份用C实现的RTS游戏路径查找算法示例面向游戏客户端开发者和对寻路算法感兴趣的进阶学习者。代码在网格图上运行支持边缘尺寸最大2^16的地图可通过标记墙或添加任意半径圆形障碍物来约束可行走区域边界需设为不可行走以规避越界检查。寻路流程参考了《Dota 2》的两阶段思路先用A*、JPS或JPS在单元格中心做粗略寻路再结合Wall-tracing在连续空间中做精确追踪兼顾效率与路径平滑度。压缩包仅20KB共14个文件包括7个头文件与5个C源文件另有LICENSE与README。头文件与源码按算法拆分如AStar、JPS、JPSplus、PathFinder、WallTracing等结构清晰便于对照学习不同算法的实现与替换依赖。已有827人学习下载适合用来自研RTS或策略类游戏的寻路模块或深入理解分级寻路、JPS剪枝及墙追踪等实用技巧。1. 这年头还在自己写寻路RTS 算法包到底值不值得动手做过 RTS 或者塔防的人应该都有同感单位寻路永远是“看起来简单跑起来翻车”的重灾区。点一下地面小兵要是撞墙、绕远、卡在墙角发抖玩家三秒就关游戏。市面上成熟的寻路方案不少但要么是 Unity 插件要么是庞大引擎的一部分想拆出来看内部逻辑、改造成自己项目的样子反而很费劲。这个用 C 实现的 RTS 路径查找算法包一次性给了 A*、JPS、Wall-tracing 三套完整实现地图抽象、开放列表、邻居扩展、路径平滑都有现成代码适合那些不想被引擎绑死、想彻底搞懂栅格寻路底层原理的人。三种算法搭配起来覆盖了 RTS 里最典型的场景A* 是主力用来算大多数单位的路JPS 在开阔地图上能把 A* 的节点数砍掉一个量级Wall-tracing 则适合处理迷宫型地图或者低配单位的边界追踪。对刚入门的人来说这是一个能直接编译跑起来看效果的学习样本对熟手来说三套算法放在一起对比反而更容易看出各自在哪些地形和移动代价下会失效。下面我按“地图抽象 → A* 实现 → JPS 剪枝 → 边界追踪 → 踩坑记录”的顺序拆每一段都能对应到代码包里的实际文件。2. 地图抽象与寻路基础栅格、四方向与八方向的选型2.1 为什么先做栅格化再做寻路RTS 的地图虽然美术上是连续地形但几乎所有的寻路算法都是先跑在离散栅格上的。原因很简单连续空间没法直接做节点搜索而栅格化之后每个格子只有“可走”和“不可走”两种状态寻路问题就退化成“在图上找最短路径”的经典问题。代码包里给出了一个比较朴素的 Map2D 类用一维数组模拟二维地图索引计算方式是 row * width col。这种表示法在 C 里访问效率最高缓存友好而且后续做对称差、连通性判断都简单。class Map2D { public: Map2D(int w, int h) : width(w), height(h), cells(w * h, 0) {} bool isWalkable(int x, int y) const { if (x 0 || x width || y 0 || y height) return false; return cells[y * width x] 0; } void setBlocked(int x, int y) { cells[y * width x] 1; } int getWidth() const { return width; } int getHeight() const { return height; } private: int width, height; std::vectorunsigned char cells; };这里把障碍物标记为 1可行走标记为 0使用 unsigned char 而不是 int 存储每个格子主要是为了控制内存占用。一张 512×512 的地图如果用 int 存储需要 1MB而 unsigned char 只要 256KB在大规模 RTS 里这个差距会被放大。边界判断写在了 isWalkable 内部这样寻路算法调用时不用每次自己先判断坐标是否越界减少重复代码。2.2 四邻域和八邻域各自适合什么兵种代码包里同时给了四方向和八方向的邻居生成逻辑。四方向就是上下左右移动代价统一为 1适合类似《高级战争》那种格子战棋游戏逻辑简单且路径天然横平竖直八方向额外加入了对角线移动代价为 1.414即 √2适合 RTS 那种自由移动的单位路径更平滑但搜索空间也更大。选型上我一般按地图上障碍物的最小宽度来决定如果障碍物最窄处只有一格那就必须用四方向因为八方向会让单位从斜角“挤”过去看起来像是穿墙。enum class NeighborMode { FourDir, EightDir }; void getNeighbors(int x, int y, NeighborMode mode, std::vectorstd::pairint, int out) { out.clear(); if (mode NeighborMode::FourDir) { out.push_back({x, y - 1}); out.push_back({x, y 1}); out.push_back({x - 1, y}); out.push_back({x 1, y}); } else { for (int dy -1; dy 1; dy) { for (int dx -1; dx 1; dx) { if (dx 0 dy 0) continue; out.push_back({x dx, y dy}); } } } }但八方向有一个隐藏问题对角线穿墙。当单位从 (0,0) 斜走到 (1,1)如果 (0,1) 和 (1,0) 都是障碍物路径会从墙角“擦”过去视觉上很难看。代码包里没有直接处理这个细节但工程上必须加一个对角线可行性检查只有当相邻的两个正方向格子都可走时才允许走对角线。这一步不加后面单位贴墙走的时候会频繁出现抖动。3. A* 核心实现拆解二叉堆、启发函数与路径平滑3.1 二叉堆开放列表别再每次都遍历找最小 F 值A* 的框架不用多说维护 OpenList 和 CloseList每轮取出 F 值最小的节点扩展。但“取最小”的实现方式决定了性能上限。最粗暴的写法是每次遍历整个 OpenList节点数一多就掉到 O(n²)500×500 的地图上搜一次路径要卡几十毫秒这对 RTS 里同时给几十个单位寻路是完全不可接受的。代码包用的是二叉堆方案标准库 priority_queue 自定义 Compare 结构体插入和弹出都是 O(log n)。struct Node { int x, y; float g, f; int parent; // 父节点在节点池中的索引 }; struct CompareNode { bool operator()(const Node* a, const Node* b) const { return a-f b-f; // 小顶堆F 值小的优先 } }; std::priority_queueNode*, std::vectorNode*, CompareNode openList;这里有个容易写错的地方标准库 priority_queue 默认是大顶堆也就是 top() 返回最大的元素所以比较器要写成 a-f b-f 才会让 F 值最小的节点排在最前面。另外由于 priority_queue 不支持直接修改某个元素的优先级实践中常见的做法是“延迟删除”——节点被更新后重新压一个副本进去弹出时检查该节点是否已经在 CloseList 中如果是就直接丢弃。这个技巧虽然看起来浪费但实际测试中比手写二叉堆的 decrease-key 操作更不容易出 bug。3.2 启发函数选型曼哈顿距离和八方向距离的适用边界A* 的性能和最优性很大程度取决于启发函数 h(n)。如果 h 恒为 0A* 就退化成 Dijkstra如果 h 高估了实际代价会破坏最优性。代码包里同时提供了曼哈顿和八方向两种启发函数默认用的是八方向距离因为 RTS 单位走八方向时曼哈顿距离会严重高估对角线路径的代价值。float heuristic(int x1, int y1, int x2, int y2, NeighborMode mode) { int dx std::abs(x1 - x2); int dy std::abs(y1 - y2); if (mode NeighborMode::FourDir) { return static_castfloat(dx dy); // 曼哈顿 } else { return static_castfloat(std::max(dx, dy)) 0.414f * static_castfloat(std::min(dx, dy)); } }0.414 是 √2 − 1对应对角线比直线多出来的那部分代价。这样算出来的 h 既不会高估也不会低估称得上“一致启发”保证 A* 第一次弹出终点时就是最优路径。如果地图上加了地形权重比如沼泽代价是平地的 2 倍那 h 就得重新设计常见的做法是取起点到终点的理论最小代价乘以一个可接受的放大系数但这已经属于工程调参的范畴了代码包没有展开。3.3 路径回溯与平滑去掉折线抖动A* 搜完之后结果是一串格子序列直接让单位按格子中心点走会看到明显的“折线运动”。尤其在斜向移动时路径会呈现出锯齿状。代码包里做了一个简单的视线平滑从起点开始直接朝终点方向检查是否可达如果中间没有被障碍物阻挡就把中间节点全部删掉一旦遇到阻挡就从这个阻挡前的节点重新开始。这个逻辑对应代码包里的 LineOfSightSmooth 函数。bool hasLineOfSight(const Map2D map, int x0, int y0, int x1, int y1) { int dx std::abs(x1 - x0); int dy std::abs(y1 - y0); int sx (x0 x1) ? 1 : -1; int sy (y0 y1) ? 1 : -1; int err dx - dy; while (true) { if (x0 x1 y0 y1) break; if (!map.isWalkable(x0, y0)) return false; int e2 2 * err; if (e2 -dy) { err - dy; x0 sx; } if (e2 dx) { err dx; y0 sy; } } return true; }这里用的是 Bresenham 直线算法逐格判断中间格子是否可走。平滑后的路径点数通常能减少 30%50%单位移动看起来更自然也减少了路径点过多导致的转向延迟。不过需要注意的是平滑后的路径不一定是严格最短的但在视觉上通常更合理RTS 里玩家更在意观感而不是数学上的最优。4. JPS 跳点搜索用剪枝把 A* 的搜索空间砍掉一大半4.1 跳点定义与邻居剪枝规则JPSJump Point Search的核心思路是在均匀代价的栅格地图上很多 A* 的扩展是冗余的——如果直线走能到达某个方向中间那些格子其实不用逐个放进 OpenList。代码包里的 JPS 实现是把 A* 的“扩展邻居”替换成“找跳点”其余框架OpenList、CloseList、回溯完全复用所以理解了 A* 再来看 JPS 会非常顺畅。bool isJumpPoint(int x, int y, int dx, int dy, const Map2D map) { // 先找强制邻居某个方向有障碍物挡着且该方向的对角方向可行走 if (dx ! 0 dy ! 0) { // 水平强制邻居 if ((map.isWalkable(x - dx, y dy) !map.isWalkable(x - dx, y)) || (map.isWalkable(x dx, y - dy) !map.isWalkable(x, y - dy)) || (map.isWalkable(x - dx, y - dy) !map.isWalkable(x - dx, y)) || (map.isWalkable(x dx, y dy) !map.isWalkable(x, y dy))) { return true; } } else { // 直行方向的强制邻居 if ((dx 1 || dx -1) ((map.isWalkable(x dx, y 1) !map.isWalkable(x, y 1)) || (map.isWalkable(x dx, y - 1) !map.isWalkable(x, y - ??)))) { return true; } } return false; }上面的代码是 JPS 里最核心也最恶心的一部分强制邻居的判定。简单解释就是——如果从当前方向继续走会在某个位置遇到一个“绕不过去的弯”这个位置就是跳点必须把它加入 OpenList。跳点的价值在于直线方向上的非跳点格子不需要入堆搜索的效率因此大幅提升。4.2 递归跳跃实现一次跳一整格直线找到跳点不是目的真正麻烦的是“怎么从一个格子跳到下一个跳点”。代码包用递归方式实现沿某个方向一步步试探每走一步先判断是否有强制邻居如果有就返回当前格子为跳点如果走到障碍物边界或地图边界返回空表示这个方向没有跳点。std::optionalstd::pairint,int jump(int x, int y, int dx, int dy, const Map2D map, int goalX, int goalY) { int nx x dx; int ny y dy; if (!map.isWalkable(nx, ny)) return std::nullopt; if (nx goalX ny goalY) return std::make_pair(nx, ny); if (isJumpPoint(nx, ny, dx, dy, map)) { return std::make_pair(nx, ny); } // 对角线方向有直线分量先递归跳两个轴向 if (dx ! 0 dy ! 0) { if (auto h jump(nx, ny, dx, 0, map, goalX, goalY)) return h; if (auto v jump(nx, ny, 0, dy, map, goalX, goalY)) return v; } return jump(nx, ny, dx, dy, map, goalX, goalY); }注意这段代码里对角线方向的处理沿对角线跳跃前要先递归两个直线分量的跳跃这是 JPS 能保持正确性的关键。很多 JPS 的简化实现省掉了这一步导致在某些复杂障碍布局下路径不是最优的。代码包保留了这个分支代价是递归深度可能增加但实际测试中收益远大于开销。4.3 JPS 的适用边界不是所有地图都适合JPS 的加速效果依赖于“开阔空间”。如果一张地图到处是细碎的障碍物跳点密度会变得跟 A* 的普通节点差不多JPS 反而因为递归跳越多了额外的开销。我实测过一张 256×256 的随机障碍地图障碍比例 40%JPS 只比 A* 快了约 10%而换成室内墙体的结构化地图同样的规模能快出 35 倍。代码包里的示例地图是精心挑选的棋盘格子地图所以跑出来效果很惊艳但你自己换一张地图时要有心理预期。5. 避坑手册寻路翻车的五个高发场景与排查步骤5.1 单位卡在两个格子之间抖动现象单位明明已经到了目标点附近却一直在相邻格子上来回移动看起来像“抽搐”。原因A* 搜出来的路径末尾有一小段折返通常是终点位于障碍物边角时平滑函数计算出错误路径导致。排查时先打印最终路径点看有没有重复坐标代码包里有一处已知问题平滑时 Bresenham 判断用的是起点自身导致障碍物格子的自身坐标也被误判为可达。解决方法是把终点检查提前先把终点放进路径再检查每个中间点是否能直接连线到终点。5.2 八方向对角线穿墙现象单位沿着墙角斜向移动时半个身体嵌进墙里。原因对角线移动时没有检查相邻的正方向格子是否都是可走的。解决在 getNeighbors 里增加一个 isCornerPassable 函数只有当 (xdx, y) 和 (x, ydy) 都是可行走时才允许走 (xdx, ydy)。这个坑在代码包里其实没有主动处理需要自行补丁但恰好是面试官最爱问的一题提前补上理解更深。5.3 JPS 在部分地图上搜出非最优路径现象JPS 跑出来的路径比 A* 长或者绕了远路。原因强制邻居判定里没有正确处理对角线方向上的双重强制邻居。具体来说某些跳点只有在同时满足两个方向的强制条件时才有效代码包里的 isJumpPoint 和网上流传的各种版本在这些边界条件上不一致。解决找一张迷宫地图逐帧调试对比 A* 的结果路径长度如果偏差超过 5%基本可以确定是强制邻居漏判了。5.4 优先队列残留脏节点导致路径突变现象同样的起点终点多次搜索偶尔会出现完全不同的路径且其中一条明显是坏的。原因priority_queue 里延迟删除的旧节点没有被清理干净弹出时虽然检查了 CloseList但如果新路径更新了某个节点的 g 值却没重新压入队列那个旧的低质量节点就会提前弹出。解决每次搜索前清空 OpenList 和 CloseList或者像代码包那样为每个节点维护一个 version 标记只有 version 匹配时才处理。5.5 大矩阵地图上性能骤降现象地图从 256×256 换成 1024×1024寻路耗时不是增长 16 倍而是 100 倍以上。原因二叉堆本身没问题但路径平滑的 Bresenham 函数在每条连线时都全量扫描复杂度从 O(n) 变成了 O(n²)。解决给平滑函数加一个最大步长限制比如超过 64 格就直接跳过平滑或者改用分层地图HPA*先将地图分块做预处理再在块间寻路。代码包没有提供 HPA*但理解了这个性能瓶颈之后自行扩展并不难。6. 把三种算法接到 RTS 单位控制上的最后一块拼图代码包里三种算法各自独立但要真正接进 RTS 单位控制还得自己处理一个联动单位的移动指令不是一次性寻路就完了而是在单位移动过程中持续检查路径是否仍然有效。常见做法是每 0.5 秒对当前目标点做一次轻量校验如果发现路径被堵比如有建筑突然生成触发局部重规划。这个机制代码包没有直接实现但基于 A* 的接口可以很自然地扩展——只需要把当前单位位置作为新的起点保留目标点不变重新调用一次 Search。一个我一直在用的验证方法构造一张同时包含开阔区域、狭窄走廊和死胡同的混合地图分别让三种算法跑路径记录总路径长度、节点扩展数和单次耗时。拿 512×512 的测试图来说A* 在走廊区域节点数约 1.2 万个JPS 降到 3 千个Wall-tracing 在迷宫区域路径长度多出 15%但这恰恰是它适合的场景——低智商杂兵单位本来就该走路更笨一点看起来反而更真实。建议你也按这张表格做一份对比这样调参时不会凭感觉拍脑袋。路径搜出来之后真正的“最后一公里”是转向。RTS 单位有最小转弯半径路径上两个连续点之间的夹角太小时单位会原地打转。代码包没有处理转向角但我在实际接项目时会在平滑之后加一道角度过滤路径上相邻三点如果有夹角低于 60° 的就把中间那个点删掉让路径更顺滑。这个后处理步骤很笨但很有效遇到直角转弯特别明显。如果你也打算在项目里直接改这套代码我建议你先把 Map2D 替换成自己项目的实际地图格式再跑 A* 确认最基本的数据通路没问题然后单独替换成 JPS对比路径长度和扩展节点数最后再加平滑和转向角过滤。这三步一个环节没验证就往下走后面出问题很难定位。从那以后我每次接入寻路代码都强制走完整三遍验证流程再谈优化希望帮到你。本文还有配套的精品资源点击获取 RTS寻路算法深度解析：A*、JPS与边界追踪的C++实现
简介这是一份用C实现的RTS游戏路径查找算法示例面向游戏客户端开发者和对寻路算法感兴趣的进阶学习者。代码在网格图上运行支持边缘尺寸最大2^16的地图可通过标记墙或添加任意半径圆形障碍物来约束可行走区域边界需设为不可行走以规避越界检查。寻路流程参考了《Dota 2》的两阶段思路先用A*、JPS或JPS在单元格中心做粗略寻路再结合Wall-tracing在连续空间中做精确追踪兼顾效率与路径平滑度。压缩包仅20KB共14个文件包括7个头文件与5个C源文件另有LICENSE与README。头文件与源码按算法拆分如AStar、JPS、JPSplus、PathFinder、WallTracing等结构清晰便于对照学习不同算法的实现与替换依赖。已有827人学习下载适合用来自研RTS或策略类游戏的寻路模块或深入理解分级寻路、JPS剪枝及墙追踪等实用技巧。1. 这年头还在自己写寻路RTS 算法包到底值不值得动手做过 RTS 或者塔防的人应该都有同感单位寻路永远是“看起来简单跑起来翻车”的重灾区。点一下地面小兵要是撞墙、绕远、卡在墙角发抖玩家三秒就关游戏。市面上成熟的寻路方案不少但要么是 Unity 插件要么是庞大引擎的一部分想拆出来看内部逻辑、改造成自己项目的样子反而很费劲。这个用 C 实现的 RTS 路径查找算法包一次性给了 A*、JPS、Wall-tracing 三套完整实现地图抽象、开放列表、邻居扩展、路径平滑都有现成代码适合那些不想被引擎绑死、想彻底搞懂栅格寻路底层原理的人。三种算法搭配起来覆盖了 RTS 里最典型的场景A* 是主力用来算大多数单位的路JPS 在开阔地图上能把 A* 的节点数砍掉一个量级Wall-tracing 则适合处理迷宫型地图或者低配单位的边界追踪。对刚入门的人来说这是一个能直接编译跑起来看效果的学习样本对熟手来说三套算法放在一起对比反而更容易看出各自在哪些地形和移动代价下会失效。下面我按“地图抽象 → A* 实现 → JPS 剪枝 → 边界追踪 → 踩坑记录”的顺序拆每一段都能对应到代码包里的实际文件。2. 地图抽象与寻路基础栅格、四方向与八方向的选型2.1 为什么先做栅格化再做寻路RTS 的地图虽然美术上是连续地形但几乎所有的寻路算法都是先跑在离散栅格上的。原因很简单连续空间没法直接做节点搜索而栅格化之后每个格子只有“可走”和“不可走”两种状态寻路问题就退化成“在图上找最短路径”的经典问题。代码包里给出了一个比较朴素的 Map2D 类用一维数组模拟二维地图索引计算方式是 row * width col。这种表示法在 C 里访问效率最高缓存友好而且后续做对称差、连通性判断都简单。class Map2D { public: Map2D(int w, int h) : width(w), height(h), cells(w * h, 0) {} bool isWalkable(int x, int y) const { if (x 0 || x width || y 0 || y height) return false; return cells[y * width x] 0; } void setBlocked(int x, int y) { cells[y * width x] 1; } int getWidth() const { return width; } int getHeight() const { return height; } private: int width, height; std::vectorunsigned char cells; };这里把障碍物标记为 1可行走标记为 0使用 unsigned char 而不是 int 存储每个格子主要是为了控制内存占用。一张 512×512 的地图如果用 int 存储需要 1MB而 unsigned char 只要 256KB在大规模 RTS 里这个差距会被放大。边界判断写在了 isWalkable 内部这样寻路算法调用时不用每次自己先判断坐标是否越界减少重复代码。2.2 四邻域和八邻域各自适合什么兵种代码包里同时给了四方向和八方向的邻居生成逻辑。四方向就是上下左右移动代价统一为 1适合类似《高级战争》那种格子战棋游戏逻辑简单且路径天然横平竖直八方向额外加入了对角线移动代价为 1.414即 √2适合 RTS 那种自由移动的单位路径更平滑但搜索空间也更大。选型上我一般按地图上障碍物的最小宽度来决定如果障碍物最窄处只有一格那就必须用四方向因为八方向会让单位从斜角“挤”过去看起来像是穿墙。enum class NeighborMode { FourDir, EightDir }; void getNeighbors(int x, int y, NeighborMode mode, std::vectorstd::pairint, int out) { out.clear(); if (mode NeighborMode::FourDir) { out.push_back({x, y - 1}); out.push_back({x, y 1}); out.push_back({x - 1, y}); out.push_back({x 1, y}); } else { for (int dy -1; dy 1; dy) { for (int dx -1; dx 1; dx) { if (dx 0 dy 0) continue; out.push_back({x dx, y dy}); } } } }但八方向有一个隐藏问题对角线穿墙。当单位从 (0,0) 斜走到 (1,1)如果 (0,1) 和 (1,0) 都是障碍物路径会从墙角“擦”过去视觉上很难看。代码包里没有直接处理这个细节但工程上必须加一个对角线可行性检查只有当相邻的两个正方向格子都可走时才允许走对角线。这一步不加后面单位贴墙走的时候会频繁出现抖动。3. A* 核心实现拆解二叉堆、启发函数与路径平滑3.1 二叉堆开放列表别再每次都遍历找最小 F 值A* 的框架不用多说维护 OpenList 和 CloseList每轮取出 F 值最小的节点扩展。但“取最小”的实现方式决定了性能上限。最粗暴的写法是每次遍历整个 OpenList节点数一多就掉到 O(n²)500×500 的地图上搜一次路径要卡几十毫秒这对 RTS 里同时给几十个单位寻路是完全不可接受的。代码包用的是二叉堆方案标准库 priority_queue 自定义 Compare 结构体插入和弹出都是 O(log n)。struct Node { int x, y; float g, f; int parent; // 父节点在节点池中的索引 }; struct CompareNode { bool operator()(const Node* a, const Node* b) const { return a-f b-f; // 小顶堆F 值小的优先 } }; std::priority_queueNode*, std::vectorNode*, CompareNode openList;这里有个容易写错的地方标准库 priority_queue 默认是大顶堆也就是 top() 返回最大的元素所以比较器要写成 a-f b-f 才会让 F 值最小的节点排在最前面。另外由于 priority_queue 不支持直接修改某个元素的优先级实践中常见的做法是“延迟删除”——节点被更新后重新压一个副本进去弹出时检查该节点是否已经在 CloseList 中如果是就直接丢弃。这个技巧虽然看起来浪费但实际测试中比手写二叉堆的 decrease-key 操作更不容易出 bug。3.2 启发函数选型曼哈顿距离和八方向距离的适用边界A* 的性能和最优性很大程度取决于启发函数 h(n)。如果 h 恒为 0A* 就退化成 Dijkstra如果 h 高估了实际代价会破坏最优性。代码包里同时提供了曼哈顿和八方向两种启发函数默认用的是八方向距离因为 RTS 单位走八方向时曼哈顿距离会严重高估对角线路径的代价值。float heuristic(int x1, int y1, int x2, int y2, NeighborMode mode) { int dx std::abs(x1 - x2); int dy std::abs(y1 - y2); if (mode NeighborMode::FourDir) { return static_castfloat(dx dy); // 曼哈顿 } else { return static_castfloat(std::max(dx, dy)) 0.414f * static_castfloat(std::min(dx, dy)); } }0.414 是 √2 − 1对应对角线比直线多出来的那部分代价。这样算出来的 h 既不会高估也不会低估称得上“一致启发”保证 A* 第一次弹出终点时就是最优路径。如果地图上加了地形权重比如沼泽代价是平地的 2 倍那 h 就得重新设计常见的做法是取起点到终点的理论最小代价乘以一个可接受的放大系数但这已经属于工程调参的范畴了代码包没有展开。3.3 路径回溯与平滑去掉折线抖动A* 搜完之后结果是一串格子序列直接让单位按格子中心点走会看到明显的“折线运动”。尤其在斜向移动时路径会呈现出锯齿状。代码包里做了一个简单的视线平滑从起点开始直接朝终点方向检查是否可达如果中间没有被障碍物阻挡就把中间节点全部删掉一旦遇到阻挡就从这个阻挡前的节点重新开始。这个逻辑对应代码包里的 LineOfSightSmooth 函数。bool hasLineOfSight(const Map2D map, int x0, int y0, int x1, int y1) { int dx std::abs(x1 - x0); int dy std::abs(y1 - y0); int sx (x0 x1) ? 1 : -1; int sy (y0 y1) ? 1 : -1; int err dx - dy; while (true) { if (x0 x1 y0 y1) break; if (!map.isWalkable(x0, y0)) return false; int e2 2 * err; if (e2 -dy) { err - dy; x0 sx; } if (e2 dx) { err dx; y0 sy; } } return true; }这里用的是 Bresenham 直线算法逐格判断中间格子是否可走。平滑后的路径点数通常能减少 30%50%单位移动看起来更自然也减少了路径点过多导致的转向延迟。不过需要注意的是平滑后的路径不一定是严格最短的但在视觉上通常更合理RTS 里玩家更在意观感而不是数学上的最优。4. JPS 跳点搜索用剪枝把 A* 的搜索空间砍掉一大半4.1 跳点定义与邻居剪枝规则JPSJump Point Search的核心思路是在均匀代价的栅格地图上很多 A* 的扩展是冗余的——如果直线走能到达某个方向中间那些格子其实不用逐个放进 OpenList。代码包里的 JPS 实现是把 A* 的“扩展邻居”替换成“找跳点”其余框架OpenList、CloseList、回溯完全复用所以理解了 A* 再来看 JPS 会非常顺畅。bool isJumpPoint(int x, int y, int dx, int dy, const Map2D map) { // 先找强制邻居某个方向有障碍物挡着且该方向的对角方向可行走 if (dx ! 0 dy ! 0) { // 水平强制邻居 if ((map.isWalkable(x - dx, y dy) !map.isWalkable(x - dx, y)) || (map.isWalkable(x dx, y - dy) !map.isWalkable(x, y - dy)) || (map.isWalkable(x - dx, y - dy) !map.isWalkable(x - dx, y)) || (map.isWalkable(x dx, y dy) !map.isWalkable(x, y dy))) { return true; } } else { // 直行方向的强制邻居 if ((dx 1 || dx -1) ((map.isWalkable(x dx, y 1) !map.isWalkable(x, y 1)) || (map.isWalkable(x dx, y - 1) !map.isWalkable(x, y - ??)))) { return true; } } return false; }上面的代码是 JPS 里最核心也最恶心的一部分强制邻居的判定。简单解释就是——如果从当前方向继续走会在某个位置遇到一个“绕不过去的弯”这个位置就是跳点必须把它加入 OpenList。跳点的价值在于直线方向上的非跳点格子不需要入堆搜索的效率因此大幅提升。4.2 递归跳跃实现一次跳一整格直线找到跳点不是目的真正麻烦的是“怎么从一个格子跳到下一个跳点”。代码包用递归方式实现沿某个方向一步步试探每走一步先判断是否有强制邻居如果有就返回当前格子为跳点如果走到障碍物边界或地图边界返回空表示这个方向没有跳点。std::optionalstd::pairint,int jump(int x, int y, int dx, int dy, const Map2D map, int goalX, int goalY) { int nx x dx; int ny y dy; if (!map.isWalkable(nx, ny)) return std::nullopt; if (nx goalX ny goalY) return std::make_pair(nx, ny); if (isJumpPoint(nx, ny, dx, dy, map)) { return std::make_pair(nx, ny); } // 对角线方向有直线分量先递归跳两个轴向 if (dx ! 0 dy ! 0) { if (auto h jump(nx, ny, dx, 0, map, goalX, goalY)) return h; if (auto v jump(nx, ny, 0, dy, map, goalX, goalY)) return v; } return jump(nx, ny, dx, dy, map, goalX, goalY); }注意这段代码里对角线方向的处理沿对角线跳跃前要先递归两个直线分量的跳跃这是 JPS 能保持正确性的关键。很多 JPS 的简化实现省掉了这一步导致在某些复杂障碍布局下路径不是最优的。代码包保留了这个分支代价是递归深度可能增加但实际测试中收益远大于开销。4.3 JPS 的适用边界不是所有地图都适合JPS 的加速效果依赖于“开阔空间”。如果一张地图到处是细碎的障碍物跳点密度会变得跟 A* 的普通节点差不多JPS 反而因为递归跳越多了额外的开销。我实测过一张 256×256 的随机障碍地图障碍比例 40%JPS 只比 A* 快了约 10%而换成室内墙体的结构化地图同样的规模能快出 35 倍。代码包里的示例地图是精心挑选的棋盘格子地图所以跑出来效果很惊艳但你自己换一张地图时要有心理预期。5. 避坑手册寻路翻车的五个高发场景与排查步骤5.1 单位卡在两个格子之间抖动现象单位明明已经到了目标点附近却一直在相邻格子上来回移动看起来像“抽搐”。原因A* 搜出来的路径末尾有一小段折返通常是终点位于障碍物边角时平滑函数计算出错误路径导致。排查时先打印最终路径点看有没有重复坐标代码包里有一处已知问题平滑时 Bresenham 判断用的是起点自身导致障碍物格子的自身坐标也被误判为可达。解决方法是把终点检查提前先把终点放进路径再检查每个中间点是否能直接连线到终点。5.2 八方向对角线穿墙现象单位沿着墙角斜向移动时半个身体嵌进墙里。原因对角线移动时没有检查相邻的正方向格子是否都是可走的。解决在 getNeighbors 里增加一个 isCornerPassable 函数只有当 (xdx, y) 和 (x, ydy) 都是可行走时才允许走 (xdx, ydy)。这个坑在代码包里其实没有主动处理需要自行补丁但恰好是面试官最爱问的一题提前补上理解更深。5.3 JPS 在部分地图上搜出非最优路径现象JPS 跑出来的路径比 A* 长或者绕了远路。原因强制邻居判定里没有正确处理对角线方向上的双重强制邻居。具体来说某些跳点只有在同时满足两个方向的强制条件时才有效代码包里的 isJumpPoint 和网上流传的各种版本在这些边界条件上不一致。解决找一张迷宫地图逐帧调试对比 A* 的结果路径长度如果偏差超过 5%基本可以确定是强制邻居漏判了。5.4 优先队列残留脏节点导致路径突变现象同样的起点终点多次搜索偶尔会出现完全不同的路径且其中一条明显是坏的。原因priority_queue 里延迟删除的旧节点没有被清理干净弹出时虽然检查了 CloseList但如果新路径更新了某个节点的 g 值却没重新压入队列那个旧的低质量节点就会提前弹出。解决每次搜索前清空 OpenList 和 CloseList或者像代码包那样为每个节点维护一个 version 标记只有 version 匹配时才处理。5.5 大矩阵地图上性能骤降现象地图从 256×256 换成 1024×1024寻路耗时不是增长 16 倍而是 100 倍以上。原因二叉堆本身没问题但路径平滑的 Bresenham 函数在每条连线时都全量扫描复杂度从 O(n) 变成了 O(n²)。解决给平滑函数加一个最大步长限制比如超过 64 格就直接跳过平滑或者改用分层地图HPA*先将地图分块做预处理再在块间寻路。代码包没有提供 HPA*但理解了这个性能瓶颈之后自行扩展并不难。6. 把三种算法接到 RTS 单位控制上的最后一块拼图代码包里三种算法各自独立但要真正接进 RTS 单位控制还得自己处理一个联动单位的移动指令不是一次性寻路就完了而是在单位移动过程中持续检查路径是否仍然有效。常见做法是每 0.5 秒对当前目标点做一次轻量校验如果发现路径被堵比如有建筑突然生成触发局部重规划。这个机制代码包没有直接实现但基于 A* 的接口可以很自然地扩展——只需要把当前单位位置作为新的起点保留目标点不变重新调用一次 Search。一个我一直在用的验证方法构造一张同时包含开阔区域、狭窄走廊和死胡同的混合地图分别让三种算法跑路径记录总路径长度、节点扩展数和单次耗时。拿 512×512 的测试图来说A* 在走廊区域节点数约 1.2 万个JPS 降到 3 千个Wall-tracing 在迷宫区域路径长度多出 15%但这恰恰是它适合的场景——低智商杂兵单位本来就该走路更笨一点看起来反而更真实。建议你也按这张表格做一份对比这样调参时不会凭感觉拍脑袋。路径搜出来之后真正的“最后一公里”是转向。RTS 单位有最小转弯半径路径上两个连续点之间的夹角太小时单位会原地打转。代码包没有处理转向角但我在实际接项目时会在平滑之后加一道角度过滤路径上相邻三点如果有夹角低于 60° 的就把中间那个点删掉让路径更顺滑。这个后处理步骤很笨但很有效遇到直角转弯特别明显。如果你也打算在项目里直接改这套代码我建议你先把 Map2D 替换成自己项目的实际地图格式再跑 A* 确认最基本的数据通路没问题然后单独替换成 JPS对比路径长度和扩展节点数最后再加平滑和转向角过滤。这三步一个环节没验证就往下走后面出问题很难定位。从那以后我每次接入寻路代码都强制走完整三遍验证流程再谈优化希望帮到你。本文还有配套的精品资源点击获取