简介这是一份面向游戏开发初学者与中级C程序员的实时战略RTS游戏路径规划算法实现资源聚焦于网格地图下的高效寻路问题涵盖A*、JPS跳点搜索、JPS及Wall-tracing墙追踪四类核心算法。资源共14个文件含7个头文件hpp定义算法接口与几何工具如Coord、geometry、PathFinder等5个源文件cpp实现各算法逻辑与路径优化流程另含LICENSE与README.md说明文档整体仅20KB轻量易集成。已有826人学习下载适合希望在自研引擎中快速嵌入工业级寻路能力的开发者。读者可直接复用其两阶段路径生成框架先以单元格中心为节点执行粗粒度全局寻路支持障碍物无关的JPS加速再通过连续空间中的墙追踪完成局部精确定位——该设计源自《Dota 2》实战机制兼顾性能与平滑性且适配最大65536×65536规模网格具备明确的工程落地参考价值。1. 项目概述与算法选型思路RTS游戏里最容易被玩家感知又最容易被开发者低估的模块就是寻路。玩家框选几十个作战单位下达一个移动指令整个队伍必须流畅地绕过基地建筑、穿过窄桥、避开战场上的残骸最终到达目标点。任何一个单位卡在墙角或者绕了远路玩家都会立刻察觉到“这AI好蠢”。所以寻路算法不是RTS里最炫酷的部分却是决定游戏手感下限的模块。这个项目要做的事情很明确用C实现三种寻路算法分别是A*、JPSJump Point Search、Wall-tracing并且把它们放进同一个RTS风格的地图框架里进行对比和实际使用。很多人会问既然A已经能解决问题为什么还要折腾JPS和Wall-tracing这是因为RTS场景极其复杂单张地图上几十上百个单位同时在寻路每个单位需要做的计算量直接决定了游戏帧率。A是通用解但不够快JPS在开阔地图上有数量级的性能提升但对障碍规则有要求Wall-tracing则是一种完全不同的思路适合迷宫型地图或者作为局部避障的辅助手段。三种算法各有适用位置放在同一个工程里做对照才能理解它们的本质差异。这篇内容适合三种人看正在做策略类小游戏却苦于寻路性能的同学对路径规划算法感兴趣但不想只看理论推导的C爱好者以及想学习如何对经典算法做工程化取舍的开发者。我会从地图数据结构讲起逐步拆解每个算法的实现要点最后给出真实代码结构、性能对比和排查经验。全程不会只贴一堆高深的理论公式而是尽量用RTS游戏的实际问题来说话。1.1 为什么RTS寻路不能只靠一种算法先直接说结论没有哪一种寻路算法能通吃所有RTS场景。A的优点是通用性和可预测性任何网格地图上它都能找到最短路径代价是它在开阔区域会展开大量节点。想象一张100x100的地图中间是大片空地A从左上角走到右下角会有接近上万次节点检查和堆操作哪怕用二叉堆优化单次寻路的开销也是不小的数字。而JPS不一样它利用“跳点”跳过了空旷区域里那些不重要的中间节点在开阔地图上的节点展开数可能只有A*的百分之几。但如果地图是密集的墙体和窄通道JPS的跳点搜索优势就会大幅缩水甚至因为递归跳跃逻辑产生额外开销。Wall-tracing就是另一条路了它不计算全局最短路径而是严格沿着障碍物的边沿走。这在迷宫地图里有奇效因为迷宫的本质是“墙构成了解空间”沿着墙走就能找到出口。但一旦地图变成RTS那种建筑林立但道路通畅的场景Wall-tracing就会陷入局部绕路的困境。我在项目里把三种算法一起实现目的不是证明谁替代谁而是让它们各司其职大部队跨地图移动用JPS复杂小区域精确寻路用A*单位在迷宫巷道里移动或者做局部沿墙绕障时用Wall-tracing。1.2 两种主流寻路流派在RTS中的分工如果从更高维度看寻路算法可以分成全局路径规划和局部避障两层。RTS游戏通常的做法是全局层用性能优秀的算法算出一条宏观路径单位沿着这条路径移动时再用短距离的局部算法处理临时出现的障碍和单位之间的相互避让。这个项目里的A*和JPS都属于全局层Wall-tracing则既可以用在全局寻路上处理迷宫型地图也可以拆出来作为局部避障时“沿着墙移动”的微调逻辑。我实际测试过的场景组合是这样的当玩家命令一个坦克集群从基地左端移动到地图右端的敌人据点时先对地图做分层解析把建筑区、道路区、开阔区标出来然后派出一个“领队单位”用JPS计算主路径后续单位通过队列跟随和局部偏移来跟随而不是让每个单位都做一次完整的JPS。到了敌方据点附近建筑密集、路径窄再切换A*做最终进点路径。而如果单位被卡在墙角触发Wall-tracing模式绕开墙壁继续前进。这个三层策略兼顾了性能、路径质量和实际游戏中的动态变化是我认为RTS寻路工程化的比较理想的形态。2. 地图表示与基础数据结构在讨论算法本身之前有一个关键前提必须说清楚地图怎么存。寻路算法的所有表现都建立在地图数据结构之上地图设计得不好后面全部白搭。RTS游戏的地图通常基于格子最常见的是正方形格子也有六边形格子但六边形格子实现的A*逻辑复杂度和计算开销都会高一些所以这个项目从正方形网格开始做起。2.1 格子地图与寻路层的设计细节我采用的方案是二维数组存地形每个格子用一个结构体描述。结构体包含以下几个核心字段地形类型空地、障碍、缓行、不可通行、移动代价系数、该格子的世界坐标、用于寻路的临时标记位。注意这个临时标记位非常关键因为寻路过程中每个格子需要记录g值、h值、父节点指针等状态如果不做隔离频繁创建对象会导致严重的内存抖动。我的做法是预分配一个size大小等于地图格数的状态数组每次寻路开始时重置版本号而不是清空整个数组。地图分层的思路也值得一说。RTS地图上通常有装饰层花草、岩石、单位层建筑、部队、逻辑层碰撞体积、移动区域。寻路只关心逻辑层所以在读取地图数据时要提前把它转换成一张只有“可行走”和“不可行走”的布尔网格。建筑占据多个格子的情况要把这些格子统一标记为不可行走。此外RTS里的单位大小不同大型单位无法穿过狭窄通道我在地图数据里为不同体型维护了不同版本的可行走层。这一块虽然简单但是在工程实现里极其容易坑人因为把地图数据直接从美术资源丢给寻路算法几乎是必错的做法。2.2 节点结构、开放列表与关闭列表的实现选择A*和JPS都离不开开放列表和关闭列表。开放列表存的是“当前已经发现但还没处理”的节点关闭列表存“已经处理完毕”的节点。许多教学代码用C的std::vector或者std::list来存这两类节点在小地图上没有问题但到了RTS地图上性能就不够看了。我在项目里做了三件事来优化这一点。第一关闭列表不单独建容器直接通过格子状态数组里的标记位判断一个格子是否已经关闭查一个布尔值就行不需要在容器里搜索。第二开放列表用的是std::priority_queue搭配自定义比较器比较的是f值也就是g值加h值。第三由于std::priority_queue不支持快速的“更新已存在节点的优先级”操作我采用了一种常见的工程技巧允许同一个节点被多次推入优先队列但只在取出时校验它是否为最新状态如果发现是过期数据就直接丢弃。这种方法叫“惰性删除”虽然队列里可能堆积少量旧节点但综合性能远高于每次更新都重新调整堆的方案。struct GridNode { int x, y; float g; float h; int version; // 用于状态数组隔离 int came_from; // 父节点索引可以用线性索引记录 bool is_closed; }; struct OpenNode { float f; int index; bool operator(const OpenNode other) const { return f other.f; } };这里index采用一维线性索引而不是二维坐标是为了减少寻路循环中的乘除运算。地图宽width高height坐标(x, y)转换成一维索引就是y * width x反过来是x index % width; y index / width。这个转换在C里开销很小但能有效减少结构体内存占用同时也让状态数组可以直接用std::vectorGridNode按索引访问不需要额外的哈希表。3. A*算法的核心实现与优化细节A是这个项目的主心骨也是所有路径规划算法的地基。它的核心思想说起来很简单维护一个优先队列每次取出当前代价最小的节点把它周围的邻居加入队列直到队列为空或者到达目标点。这里的“当前代价”包括两个部分一是从起点到当前节点的实际代价g二是从当前节点到终点的估算代价h两者之和f就是排序依据。A就像是一个经验丰富的向导既知道已经走了多远又能大致判断距离终点还有多远。3.1 启发式函数的选择与g值计算细节A*使用不同的启发式函数寻路效率差异巨大。在RTS正方形网格中最常见的选择是曼哈顿距离或者对角距离。曼哈顿距离是abs(x2 - x1) abs(y2 - y1)适合只能四方向移动的寻路。对角距离则是dx dy (sqrt(2) - 2) * min(dx, dy)适合八方向移动。项目的默认移动方式允许八方向所以我用对角距离作为启发式函数。但这里有一个很容易踩的坑g值的计算和启发式函数必须保持“一致”。假如你允许斜向移动g值里斜向移动的距离应该是sqrt(2)而不是1同时h函数也应该按八方向距离估算。如果h算法里按四方向g里却按八方向可能导致A*优先展开错误的节点最终路径质量下降。我在地图初始化阶段就把相邻格子的移动代价算好了水平垂直移动代价为1斜向移动代价固定为1.414。某些地形如沼泽、泥地会额外在g值基础上乘上地形系数这个系数存储在地图数据的地形类型中寻路过程中读取即可。3.2 邻节点生成与障碍判定A*的邻节点生成逻辑直接决定路径形态。八方向寻路时每从开放列表取一个节点要检查它的八个邻格。检查顺序我固定在方位数组里从正上开始顺时针排列。这样至少保证遍历顺序稳定后续调试时看到的行为是可预期的。障碍判定要注意斜向穿过墙角时是否允许穿过是游戏规则问题。有的游戏允许单位斜着挤过墙角有的不行。大部分RTS为了保证单位看起来不“穿模”都禁止斜穿墙角。实现上就是当目标邻格是斜角时不仅要检查该邻格是否可行走还要检查相邻的两个正交格是否都可行走。例如从当前节点走向右上角需要同时检查上方和右方的格子是否是障碍。如果其中一个是障碍斜向移动就不允许。3.3 优先队列的选择和惰性删除的细节std::priority_queue是我们项目首选因为它内部使用二叉堆插入和弹出都是O(log n)。但正如我前面提到的它不支持降低键值操作。所谓降低键值指的是寻路过程中碰到一个已经在开放列表里的节点但发现了一条新的、g值更小的路径这时候需要更新它的f值。标准教科书会建议用带decrease-key操作的斐波那契堆但这玩意工程实现复杂度高、常数大在大多数情况下并不比优先队列更快。我采用的惰性删除方案是每次找到更优路径时不修改旧节点在堆里的值而是直接再插入一个新节点记录新的f值并在节点状态数组里更新g值和父节点信息。等到堆里弹出某个节点时检查它的g值是否和状态数组里记录的一致如果不一致说明这是过期数据直接跳过。这样做的好处是代码简单不需要自己实现堆。坏处是堆里可能堆积一些无效节点但实测下来如果地图规模不超过500x500这个方案完全够用内存占用和CPU开销都能接受。float heuristic(int x1, int y1, int x2, int y2) { int dx std::abs(x2 - x1); int dy std::abs(y2 - y1); return dx dy (1.414f - 2.0f) * std::min(dx, dy); }这段代码里的1.414f是斜向移动的近似代价实际中可以用sqrt2常量但为了性能可以考虑预计算或者直接写成常量。RTS单位多的时候每一帧可能有几十次寻路调用每次调用里有几千次启发式函数调用如果这里都用sqrt函数算那肯定扛不住直接用常量是合理选择。4. JPS算法从A*到跳点搜索JPS是A的一种加速变体核心思想是在规则网格上许多节点之间是“对称”的它们对最终路径的影响完全一样因此可以跳过这些节点不展开。JPS通过预定义的规则把搜索限制在“跳点”上把开放列表的维护次数从A的O(节点数)降到接近O(路径长度)在开阔地图上效率提升非常明显。4.1 JPS的核心思想剪枝与跳点JPS里有一个概念叫“自然邻居”和“强迫邻居”。当从父节点p走到当前节点x时如果某个邻居n不是自然邻居并且n是可行走的那么n就是一个强迫邻居。强迫邻居的存在意味着x不能简单地被跳过必须停下来记录它作为一个跳点。换句话说JPS聪明的地方就在于当运动方向确定时绝大多数邻居节点都可以被“忽略”只有当出现强迫邻居或者到达目标点时才把它们加入开放列表。这个定义听起来有点绕但用大白话讲就是你沿一条路走前方的路笔直通到底那中途的所有格子都不用停下来评估只需要看路的尽头或者墙壁的转折点。这大大减少了搜索空间。我在实现过程中发现JPS的难点不在于规则本身而在于各种边界条件的处理尤其是地图边界、障碍物贴边、斜向运动的特殊情况。4.2 jump函数的实现要点JPS的核心函数只有一个jump(x, y, dx, dy)它接受当前节点和搜索方向递归地沿方向跳跃直到找到跳点、目标点、或者遇到地图边界和障碍物。我加上剪枝条件后跳跃逻辑表现出极高的效率但代码必须写得非常细致否则各种数组越界和方向判断错误会让人头疼。我给出的简化版思路是这样的沿水平或垂直方向跳跃时每次检查下一步的格子是否可行走如果不可行走则返回空检查当前格子是否有强迫邻居如果有则返回当前格子然后继续前进。沿对角线方向跳跃时需要同时检查水平和垂直两路的子跳跃如果水平或垂直方向找到跳点则当前格子也是跳点。int jump(int index, int dx, int dy) { int next index_to_xy(index) dx dy * width; // 1. 越界和障碍检查 // 2. 如果是目标点返回当前 // 3. 检查是否有强迫邻居 // 4. 沿当前方向继续递归跳跃 // 5. 如果是对角线方向尝试水平和垂直方向子跳跃 }注意JPS对障碍物的形状很敏感。如果地图上的障碍物是“针尖状”的单点障碍跳点会非常密集JPS的加速效果会大打折扣。而在建筑群或者大片连续障碍构成的RTS地图上跳点稀疏JPS的加速效果就比较理想。4.3 JPS的边界条件与优化心得我在项目里调试JPS时花了大量时间处理两个边界情况一个是地图的四个角落另一个是起点和终点附近的狭窄通道。有些实现里终点附近需要通过“目标点检测”来提前终止跳跃否则JPS可能直接跳过目标点导致找不到路径。我的处理方式是在jump函数的每一轮先做一次目标点检查如果下一个节点就是终点则直接返回终点索引。另一个优化心得是JPS可以无缝复用A的开放列表、关闭列表和节点状态结构只需要把“邻居生成”改成“跳点生成”。这样代码结构非常清晰维护起来也方便。我在改JPS实现时把A类里生成邻居的方法抽成了虚函数或者函数指针运行时切换成JPS的策略这样debug时只需要看差异部分不用重新梳理整个流程。5. Wall-tracing算法迷宫场景的独特解法Wall-tracing也叫墙追踪、Bug算法本质上是一种不同于A的搜索思路。它不需要维护开放列表也不需要启发式函数而是采用非常朴素的策略始终让单位贴着墙走直到到达目标。这个算法在最坏情况下的路径长度可能很长但它的计算量极小每步只做常数级判断所以在已知地图是迷宫型的时候它往往比A更快找到可行路径。5.1 墙追踪的原理与右手法则墙追踪的经典策略是“右手法则”站在迷宫入口处右手始终贴着墙手不离墙地往前走最终一定能够走出迷宫。这个法则基于一个拓扑学原理如果你始终沿着障碍物的边界走那么你实际上是在遍历某个连通区域的边界只要目标点和起点处于同一连通区域就一定能找到路径。将这个想法移植到网格地图上我的实现是规定单位当前朝一个方向移动当遇到前方有障碍时不断右转或者左转直到找到可行方向。算法循环执行“前进-检测-转向”三个动作每次转向都会检查当前格子是否有标记防止死循环。实际编码时我用方向编号0到7来表示八方向定义一个turn_right和turn_left操作。每当单位前方受阻就按固定方向旋转方向角。旋转的方式取决于选择左手法则还是右手法则。右手法则让单位沿障碍物右侧绕行左手法则则是沿左侧绕行。项目里默认用右手法则因为它的走动路径在大多数地图上更符合玩家的直觉。5.2 实现细节与循环检测Wall-tracing的最大风险是死循环。单位在天井型障碍物内部或者目标不可达时会陷入无限绕圈。所以必须加一个“步数上限”比如当前格子访问次数超过某个阈值就终止搜索。我常用的做法是维护一个访问计数器数组每进入一个格子就把计数器加一一旦某个格子的计数器超过可配置上限比如10次就判定寻路失败。另一个容易忽略的细节墙追踪算法对出发位置极度敏感。如果起点周围没有墙可贴算法会变成纯粹的“随机游走”所以一般要加一个前置检测先检查起点的八邻域里是否有障碍物如果完全没有算法就无法启动。这种情况就直接放弃Wall-tracing切回A*。这也是为什么在混合策略中Wall-tracing不能作为唯一寻路方案的原因。5.3 与A*、JPS结合的混合策略在RTS场景里纯粹的Wall-tracing只适合一种情况单位被卡在错综复杂的建筑群里而且目标点就在建筑群另一侧。此时如果再用A*虽然能找到路径但计算开销大如果单位数量多帧率会明显波动。而Wall-tracing的开销几乎可以忽略不计每个单位只需做几十次方向判断就能走出困境。我实现了一个简单的决策器当地图上单位所在位置“局部连通区域”面积很小比如单位周围8格内障碍物数量超过5个就进入Wall-tracing模式一旦单位脱离高密度障碍区域再重新用JPS计算全局路径。这种模式切换在实际运行中很有效单位在建筑迷宫里的绊住率明显降低。当然这不是说 A* 和 JPS 被替代它们仍然是全局寻路的骨架Wall-tracing只是那个在狭窄区域灵活调整方向的“急救员”。6. 性能对比与实战调优只把算法跑通是不够的RTS场景里必须做性能测试。我在100x100、200x200和300x300三种尺寸的随机地图上做了对比记录每次寻路的节点展开数和实际耗时。测试环境是Intel i5-10400无多线程优化单次寻路取平均值。6.1 三种算法的实测性能对比下表是部分测试数据地图障碍密度约30%起点在左上角终点在右下角算法地图尺寸节点展开数平均耗时(ms)A*100x10058601.27A*200x200231045.84A*300x3005201816.92JPS100x10010420.31JPS200x20041291.43JPS300x30095314.20Wall-tracing100x1004020.09Wall-tracing200x20017890.38Wall-tracing300x30041020.93从数据可以看出JPS在开阔地图上的节点展开数大约是A的六分之一到五分之一运行时间也有数量级优势。Wall-tracing虽然节点数更少但它的路径质量差路径长度通常比A长30%到50%所以不能一味追求速度。在RTS工程里最理想的配置依然是“JPS为主A*兜底Wall-tracing应急”。6.2 寻路结果的后处理路径平滑与分段算法算出来的路径本质上是一串格子坐标直接交给单位走看起来会非常生硬尤其在斜向移动时会有明显的锯齿感。实际项目中要做路径平滑。最简单的平滑方案是“视线检测”从当前路径点的第一个点开始尝试与后面的点做直线连接如果直线上的所有格子都是可行走的就可以删除中间点。这个过程叫“拉直线”虽然简单但对路径观感提升很大。更好的方案是漏斗算法它在A*路径的基础上进一步收缩走廊宽度把路径压缩到贴近障碍物的边缘可以让单位走曲线时更自然。不过漏斗算法实现稍复杂需要处理尖角情况。我对RTS单位的要求没有到丝般顺滑的程度所以采用了拉直线加二次贝塞尔插值的方式看起来效果也不错。还需要做分段处理RTS单位在移动过程中目标点可能发生偏移比如玩家频繁下达新命令如果把整条长路径一次性缓存起来一旦目标变化就要全量重算。我的做法是把路径按一定长度切成多个段单位每到达一个段终点再检查是否需要计算下一段路径。这样每个单位的单次计算量都不会太大也方便动态避障时做局部调整。6.3 动态地图下的缓存与失效策略RTS地图不是一成不变的建筑会新建、被摧毁单位会移动这些都会改变可通行状态。如果每次地图变化都把整个寻路缓存清空代价太大。我引入了一个“版本号”机制地图上的每个区域维护一个版本号单位每帧寻路时带上自己上次寻路时的版本号如果版本号不一致就说明路径可能失效需要重新寻路。这个机制实现起来很简单但是效果非常好。举个例子如果一支部队已经沿着路径走到一半突然有敌人建造了一个兵营挡在路上只有那一小片区域版本号变化其他区域的路径缓存依然有效。单位只需要在版本号变化的区域重新计算局部路径而不是全图重来。在动态RTS战场上这一项优化能节省大量CPU资源。7. 常见问题与排查技巧实录前面的内容偏框架和原理这一部分放实际开发中踩过的坑和处理经验。很多问题不是算法本身导致的而是集成进游戏引擎后出现的各种怪现象。7.1 路径抖动与奇怪绕路最常见的问题是单位移动时路径频繁抖动走几步就停一下看起来像“犹豫不决”。这种问题八成是因为每帧都在调用寻路而不是移动到本次路径终点后再重新计算。我踩过这个坑后做了调整单位每帧检查当前路径终点的可见性如果终点可见就不用重算继续走。只有终点不可见时才重新寻路。这样就把每帧重复寻路的问题解决掉了。另一个奇怪绕路的案例是单位明明可以直接穿过一条宽阔通道却选择绕一个大圈。后来排查发现是地图数据里的某个格子被错误标记成了不可行走但美术资源里看起来是空地。这类问题用“调试可视化”能轻松定位把可行走状态按颜色渲染到地图上一眼就能看出来哪里标记错了。7.2 大数据量下的性能瓶颈早期版本在300x300地图上同时让50个单位寻路时帧率掉到10以下。用profiler一测发现大多数时间耗在开放列表的堆操作上。后来我做了两个优化第一是启用JPS替代A*作为主算法节点数量直接少了一个数量级第二是为每个单位做了一个小的寻路请求队列避免同一帧内同时发起太多寻路请求。第二个优化背后的思路是多单位寻路时不要求每个单位都精确到最优路径而是分批次异步计算。例如一帧最多处理20个单位其他单位继续沿当前路径移动下一帧再处理剩下20个。这里还要提一个细节open list的初始容量不要太小。std::priority_queue在频繁插入时会多次扩容扩容时拷贝元素的开销在节点数达到几万时非常可观。实测中我给队列预留了地图格子数的四分之一作为初始容量效果不错。7.3 多单位寻路的去重与避让RTS里几十个单位同时走向同一个目标点时如果不做处理它们会挤在一起互相卡住。纯寻路算法解决不了这个问题这就到了“局部避让”和“单位去重”的范畴。我的方案是每个单位在移动时除了携带自己的全局路径还会在局部碰撞检测中检查前方是否有其他单位如果有则向两边让一步。这个让行逻辑并不依赖寻路算法但需要寻路算法提供“当前移动方向”和“可绕行方向”的信息。去重则更简单粗暴同一组命令单位的目标点可以设置为一个很小的偏移范围比如目标点中心周围随机偏移0.5格。这样每个单位的实际终点略微不同单位到达后会自然散开而不是所有人都挤在同一个格点。7.4 调试可视化技巧最后分享一个对效率有巨大提升的调试技巧把寻路过程可视化。我实现了一个简单的调试窗口把A*的g值分布、JPS的跳点位置、Wall-tracing的访问次数全部用颜色渲染出来。切换算法时不要只是打印日志而是要能直观看到“为什么这里会绕路”“为什么这个跳点被加入了”。在实际调试JPS时可视化帮了大忙。很多次我以为跳点生成逻辑正确但看到渲染结果后发现跳点出现在完全不该出现的位置这时候立即检查跳点生成函数问题很快就能定位。相比之下纯看调试日志排查路径问题的效率极低。任何寻路算法在RTS这种复杂环境中都必须配合可视化调试器才能保证正确性。如果让我再重做一次这个项目我会把单元测试补得更全一些尤其是针对各种迷宫地图、单点障碍地图和狭长通道地图的边界测试。这里也分享一个建议不要只测试“正常地图”多给算法喂一些极端形状的地图比如S形通道、螺旋图、大回字图。很多隐藏很深的array index越界和死循环问题都是在极端测例里才会暴露出来的。本文还有配套的精品资源点击获取 
长河君 · 2026/8/31 12:02:44 · 阅读 1.2k RTS寻路算法实战：C++实现A*、JPS与墙追踪的对比与优化
简介这是一份面向游戏开发初学者与中级C程序员的实时战略RTS游戏路径规划算法实现资源聚焦于网格地图下的高效寻路问题涵盖A*、JPS跳点搜索、JPS及Wall-tracing墙追踪四类核心算法。资源共14个文件含7个头文件hpp定义算法接口与几何工具如Coord、geometry、PathFinder等5个源文件cpp实现各算法逻辑与路径优化流程另含LICENSE与README.md说明文档整体仅20KB轻量易集成。已有826人学习下载适合希望在自研引擎中快速嵌入工业级寻路能力的开发者。读者可直接复用其两阶段路径生成框架先以单元格中心为节点执行粗粒度全局寻路支持障碍物无关的JPS加速再通过连续空间中的墙追踪完成局部精确定位——该设计源自《Dota 2》实战机制兼顾性能与平滑性且适配最大65536×65536规模网格具备明确的工程落地参考价值。1. 项目概述与算法选型思路RTS游戏里最容易被玩家感知又最容易被开发者低估的模块就是寻路。玩家框选几十个作战单位下达一个移动指令整个队伍必须流畅地绕过基地建筑、穿过窄桥、避开战场上的残骸最终到达目标点。任何一个单位卡在墙角或者绕了远路玩家都会立刻察觉到“这AI好蠢”。所以寻路算法不是RTS里最炫酷的部分却是决定游戏手感下限的模块。这个项目要做的事情很明确用C实现三种寻路算法分别是A*、JPSJump Point Search、Wall-tracing并且把它们放进同一个RTS风格的地图框架里进行对比和实际使用。很多人会问既然A已经能解决问题为什么还要折腾JPS和Wall-tracing这是因为RTS场景极其复杂单张地图上几十上百个单位同时在寻路每个单位需要做的计算量直接决定了游戏帧率。A是通用解但不够快JPS在开阔地图上有数量级的性能提升但对障碍规则有要求Wall-tracing则是一种完全不同的思路适合迷宫型地图或者作为局部避障的辅助手段。三种算法各有适用位置放在同一个工程里做对照才能理解它们的本质差异。这篇内容适合三种人看正在做策略类小游戏却苦于寻路性能的同学对路径规划算法感兴趣但不想只看理论推导的C爱好者以及想学习如何对经典算法做工程化取舍的开发者。我会从地图数据结构讲起逐步拆解每个算法的实现要点最后给出真实代码结构、性能对比和排查经验。全程不会只贴一堆高深的理论公式而是尽量用RTS游戏的实际问题来说话。1.1 为什么RTS寻路不能只靠一种算法先直接说结论没有哪一种寻路算法能通吃所有RTS场景。A的优点是通用性和可预测性任何网格地图上它都能找到最短路径代价是它在开阔区域会展开大量节点。想象一张100x100的地图中间是大片空地A从左上角走到右下角会有接近上万次节点检查和堆操作哪怕用二叉堆优化单次寻路的开销也是不小的数字。而JPS不一样它利用“跳点”跳过了空旷区域里那些不重要的中间节点在开阔地图上的节点展开数可能只有A*的百分之几。但如果地图是密集的墙体和窄通道JPS的跳点搜索优势就会大幅缩水甚至因为递归跳跃逻辑产生额外开销。Wall-tracing就是另一条路了它不计算全局最短路径而是严格沿着障碍物的边沿走。这在迷宫地图里有奇效因为迷宫的本质是“墙构成了解空间”沿着墙走就能找到出口。但一旦地图变成RTS那种建筑林立但道路通畅的场景Wall-tracing就会陷入局部绕路的困境。我在项目里把三种算法一起实现目的不是证明谁替代谁而是让它们各司其职大部队跨地图移动用JPS复杂小区域精确寻路用A*单位在迷宫巷道里移动或者做局部沿墙绕障时用Wall-tracing。1.2 两种主流寻路流派在RTS中的分工如果从更高维度看寻路算法可以分成全局路径规划和局部避障两层。RTS游戏通常的做法是全局层用性能优秀的算法算出一条宏观路径单位沿着这条路径移动时再用短距离的局部算法处理临时出现的障碍和单位之间的相互避让。这个项目里的A*和JPS都属于全局层Wall-tracing则既可以用在全局寻路上处理迷宫型地图也可以拆出来作为局部避障时“沿着墙移动”的微调逻辑。我实际测试过的场景组合是这样的当玩家命令一个坦克集群从基地左端移动到地图右端的敌人据点时先对地图做分层解析把建筑区、道路区、开阔区标出来然后派出一个“领队单位”用JPS计算主路径后续单位通过队列跟随和局部偏移来跟随而不是让每个单位都做一次完整的JPS。到了敌方据点附近建筑密集、路径窄再切换A*做最终进点路径。而如果单位被卡在墙角触发Wall-tracing模式绕开墙壁继续前进。这个三层策略兼顾了性能、路径质量和实际游戏中的动态变化是我认为RTS寻路工程化的比较理想的形态。2. 地图表示与基础数据结构在讨论算法本身之前有一个关键前提必须说清楚地图怎么存。寻路算法的所有表现都建立在地图数据结构之上地图设计得不好后面全部白搭。RTS游戏的地图通常基于格子最常见的是正方形格子也有六边形格子但六边形格子实现的A*逻辑复杂度和计算开销都会高一些所以这个项目从正方形网格开始做起。2.1 格子地图与寻路层的设计细节我采用的方案是二维数组存地形每个格子用一个结构体描述。结构体包含以下几个核心字段地形类型空地、障碍、缓行、不可通行、移动代价系数、该格子的世界坐标、用于寻路的临时标记位。注意这个临时标记位非常关键因为寻路过程中每个格子需要记录g值、h值、父节点指针等状态如果不做隔离频繁创建对象会导致严重的内存抖动。我的做法是预分配一个size大小等于地图格数的状态数组每次寻路开始时重置版本号而不是清空整个数组。地图分层的思路也值得一说。RTS地图上通常有装饰层花草、岩石、单位层建筑、部队、逻辑层碰撞体积、移动区域。寻路只关心逻辑层所以在读取地图数据时要提前把它转换成一张只有“可行走”和“不可行走”的布尔网格。建筑占据多个格子的情况要把这些格子统一标记为不可行走。此外RTS里的单位大小不同大型单位无法穿过狭窄通道我在地图数据里为不同体型维护了不同版本的可行走层。这一块虽然简单但是在工程实现里极其容易坑人因为把地图数据直接从美术资源丢给寻路算法几乎是必错的做法。2.2 节点结构、开放列表与关闭列表的实现选择A*和JPS都离不开开放列表和关闭列表。开放列表存的是“当前已经发现但还没处理”的节点关闭列表存“已经处理完毕”的节点。许多教学代码用C的std::vector或者std::list来存这两类节点在小地图上没有问题但到了RTS地图上性能就不够看了。我在项目里做了三件事来优化这一点。第一关闭列表不单独建容器直接通过格子状态数组里的标记位判断一个格子是否已经关闭查一个布尔值就行不需要在容器里搜索。第二开放列表用的是std::priority_queue搭配自定义比较器比较的是f值也就是g值加h值。第三由于std::priority_queue不支持快速的“更新已存在节点的优先级”操作我采用了一种常见的工程技巧允许同一个节点被多次推入优先队列但只在取出时校验它是否为最新状态如果发现是过期数据就直接丢弃。这种方法叫“惰性删除”虽然队列里可能堆积少量旧节点但综合性能远高于每次更新都重新调整堆的方案。struct GridNode { int x, y; float g; float h; int version; // 用于状态数组隔离 int came_from; // 父节点索引可以用线性索引记录 bool is_closed; }; struct OpenNode { float f; int index; bool operator(const OpenNode other) const { return f other.f; } };这里index采用一维线性索引而不是二维坐标是为了减少寻路循环中的乘除运算。地图宽width高height坐标(x, y)转换成一维索引就是y * width x反过来是x index % width; y index / width。这个转换在C里开销很小但能有效减少结构体内存占用同时也让状态数组可以直接用std::vectorGridNode按索引访问不需要额外的哈希表。3. A*算法的核心实现与优化细节A是这个项目的主心骨也是所有路径规划算法的地基。它的核心思想说起来很简单维护一个优先队列每次取出当前代价最小的节点把它周围的邻居加入队列直到队列为空或者到达目标点。这里的“当前代价”包括两个部分一是从起点到当前节点的实际代价g二是从当前节点到终点的估算代价h两者之和f就是排序依据。A就像是一个经验丰富的向导既知道已经走了多远又能大致判断距离终点还有多远。3.1 启发式函数的选择与g值计算细节A*使用不同的启发式函数寻路效率差异巨大。在RTS正方形网格中最常见的选择是曼哈顿距离或者对角距离。曼哈顿距离是abs(x2 - x1) abs(y2 - y1)适合只能四方向移动的寻路。对角距离则是dx dy (sqrt(2) - 2) * min(dx, dy)适合八方向移动。项目的默认移动方式允许八方向所以我用对角距离作为启发式函数。但这里有一个很容易踩的坑g值的计算和启发式函数必须保持“一致”。假如你允许斜向移动g值里斜向移动的距离应该是sqrt(2)而不是1同时h函数也应该按八方向距离估算。如果h算法里按四方向g里却按八方向可能导致A*优先展开错误的节点最终路径质量下降。我在地图初始化阶段就把相邻格子的移动代价算好了水平垂直移动代价为1斜向移动代价固定为1.414。某些地形如沼泽、泥地会额外在g值基础上乘上地形系数这个系数存储在地图数据的地形类型中寻路过程中读取即可。3.2 邻节点生成与障碍判定A*的邻节点生成逻辑直接决定路径形态。八方向寻路时每从开放列表取一个节点要检查它的八个邻格。检查顺序我固定在方位数组里从正上开始顺时针排列。这样至少保证遍历顺序稳定后续调试时看到的行为是可预期的。障碍判定要注意斜向穿过墙角时是否允许穿过是游戏规则问题。有的游戏允许单位斜着挤过墙角有的不行。大部分RTS为了保证单位看起来不“穿模”都禁止斜穿墙角。实现上就是当目标邻格是斜角时不仅要检查该邻格是否可行走还要检查相邻的两个正交格是否都可行走。例如从当前节点走向右上角需要同时检查上方和右方的格子是否是障碍。如果其中一个是障碍斜向移动就不允许。3.3 优先队列的选择和惰性删除的细节std::priority_queue是我们项目首选因为它内部使用二叉堆插入和弹出都是O(log n)。但正如我前面提到的它不支持降低键值操作。所谓降低键值指的是寻路过程中碰到一个已经在开放列表里的节点但发现了一条新的、g值更小的路径这时候需要更新它的f值。标准教科书会建议用带decrease-key操作的斐波那契堆但这玩意工程实现复杂度高、常数大在大多数情况下并不比优先队列更快。我采用的惰性删除方案是每次找到更优路径时不修改旧节点在堆里的值而是直接再插入一个新节点记录新的f值并在节点状态数组里更新g值和父节点信息。等到堆里弹出某个节点时检查它的g值是否和状态数组里记录的一致如果不一致说明这是过期数据直接跳过。这样做的好处是代码简单不需要自己实现堆。坏处是堆里可能堆积一些无效节点但实测下来如果地图规模不超过500x500这个方案完全够用内存占用和CPU开销都能接受。float heuristic(int x1, int y1, int x2, int y2) { int dx std::abs(x2 - x1); int dy std::abs(y2 - y1); return dx dy (1.414f - 2.0f) * std::min(dx, dy); }这段代码里的1.414f是斜向移动的近似代价实际中可以用sqrt2常量但为了性能可以考虑预计算或者直接写成常量。RTS单位多的时候每一帧可能有几十次寻路调用每次调用里有几千次启发式函数调用如果这里都用sqrt函数算那肯定扛不住直接用常量是合理选择。4. JPS算法从A*到跳点搜索JPS是A的一种加速变体核心思想是在规则网格上许多节点之间是“对称”的它们对最终路径的影响完全一样因此可以跳过这些节点不展开。JPS通过预定义的规则把搜索限制在“跳点”上把开放列表的维护次数从A的O(节点数)降到接近O(路径长度)在开阔地图上效率提升非常明显。4.1 JPS的核心思想剪枝与跳点JPS里有一个概念叫“自然邻居”和“强迫邻居”。当从父节点p走到当前节点x时如果某个邻居n不是自然邻居并且n是可行走的那么n就是一个强迫邻居。强迫邻居的存在意味着x不能简单地被跳过必须停下来记录它作为一个跳点。换句话说JPS聪明的地方就在于当运动方向确定时绝大多数邻居节点都可以被“忽略”只有当出现强迫邻居或者到达目标点时才把它们加入开放列表。这个定义听起来有点绕但用大白话讲就是你沿一条路走前方的路笔直通到底那中途的所有格子都不用停下来评估只需要看路的尽头或者墙壁的转折点。这大大减少了搜索空间。我在实现过程中发现JPS的难点不在于规则本身而在于各种边界条件的处理尤其是地图边界、障碍物贴边、斜向运动的特殊情况。4.2 jump函数的实现要点JPS的核心函数只有一个jump(x, y, dx, dy)它接受当前节点和搜索方向递归地沿方向跳跃直到找到跳点、目标点、或者遇到地图边界和障碍物。我加上剪枝条件后跳跃逻辑表现出极高的效率但代码必须写得非常细致否则各种数组越界和方向判断错误会让人头疼。我给出的简化版思路是这样的沿水平或垂直方向跳跃时每次检查下一步的格子是否可行走如果不可行走则返回空检查当前格子是否有强迫邻居如果有则返回当前格子然后继续前进。沿对角线方向跳跃时需要同时检查水平和垂直两路的子跳跃如果水平或垂直方向找到跳点则当前格子也是跳点。int jump(int index, int dx, int dy) { int next index_to_xy(index) dx dy * width; // 1. 越界和障碍检查 // 2. 如果是目标点返回当前 // 3. 检查是否有强迫邻居 // 4. 沿当前方向继续递归跳跃 // 5. 如果是对角线方向尝试水平和垂直方向子跳跃 }注意JPS对障碍物的形状很敏感。如果地图上的障碍物是“针尖状”的单点障碍跳点会非常密集JPS的加速效果会大打折扣。而在建筑群或者大片连续障碍构成的RTS地图上跳点稀疏JPS的加速效果就比较理想。4.3 JPS的边界条件与优化心得我在项目里调试JPS时花了大量时间处理两个边界情况一个是地图的四个角落另一个是起点和终点附近的狭窄通道。有些实现里终点附近需要通过“目标点检测”来提前终止跳跃否则JPS可能直接跳过目标点导致找不到路径。我的处理方式是在jump函数的每一轮先做一次目标点检查如果下一个节点就是终点则直接返回终点索引。另一个优化心得是JPS可以无缝复用A的开放列表、关闭列表和节点状态结构只需要把“邻居生成”改成“跳点生成”。这样代码结构非常清晰维护起来也方便。我在改JPS实现时把A类里生成邻居的方法抽成了虚函数或者函数指针运行时切换成JPS的策略这样debug时只需要看差异部分不用重新梳理整个流程。5. Wall-tracing算法迷宫场景的独特解法Wall-tracing也叫墙追踪、Bug算法本质上是一种不同于A的搜索思路。它不需要维护开放列表也不需要启发式函数而是采用非常朴素的策略始终让单位贴着墙走直到到达目标。这个算法在最坏情况下的路径长度可能很长但它的计算量极小每步只做常数级判断所以在已知地图是迷宫型的时候它往往比A更快找到可行路径。5.1 墙追踪的原理与右手法则墙追踪的经典策略是“右手法则”站在迷宫入口处右手始终贴着墙手不离墙地往前走最终一定能够走出迷宫。这个法则基于一个拓扑学原理如果你始终沿着障碍物的边界走那么你实际上是在遍历某个连通区域的边界只要目标点和起点处于同一连通区域就一定能找到路径。将这个想法移植到网格地图上我的实现是规定单位当前朝一个方向移动当遇到前方有障碍时不断右转或者左转直到找到可行方向。算法循环执行“前进-检测-转向”三个动作每次转向都会检查当前格子是否有标记防止死循环。实际编码时我用方向编号0到7来表示八方向定义一个turn_right和turn_left操作。每当单位前方受阻就按固定方向旋转方向角。旋转的方式取决于选择左手法则还是右手法则。右手法则让单位沿障碍物右侧绕行左手法则则是沿左侧绕行。项目里默认用右手法则因为它的走动路径在大多数地图上更符合玩家的直觉。5.2 实现细节与循环检测Wall-tracing的最大风险是死循环。单位在天井型障碍物内部或者目标不可达时会陷入无限绕圈。所以必须加一个“步数上限”比如当前格子访问次数超过某个阈值就终止搜索。我常用的做法是维护一个访问计数器数组每进入一个格子就把计数器加一一旦某个格子的计数器超过可配置上限比如10次就判定寻路失败。另一个容易忽略的细节墙追踪算法对出发位置极度敏感。如果起点周围没有墙可贴算法会变成纯粹的“随机游走”所以一般要加一个前置检测先检查起点的八邻域里是否有障碍物如果完全没有算法就无法启动。这种情况就直接放弃Wall-tracing切回A*。这也是为什么在混合策略中Wall-tracing不能作为唯一寻路方案的原因。5.3 与A*、JPS结合的混合策略在RTS场景里纯粹的Wall-tracing只适合一种情况单位被卡在错综复杂的建筑群里而且目标点就在建筑群另一侧。此时如果再用A*虽然能找到路径但计算开销大如果单位数量多帧率会明显波动。而Wall-tracing的开销几乎可以忽略不计每个单位只需做几十次方向判断就能走出困境。我实现了一个简单的决策器当地图上单位所在位置“局部连通区域”面积很小比如单位周围8格内障碍物数量超过5个就进入Wall-tracing模式一旦单位脱离高密度障碍区域再重新用JPS计算全局路径。这种模式切换在实际运行中很有效单位在建筑迷宫里的绊住率明显降低。当然这不是说 A* 和 JPS 被替代它们仍然是全局寻路的骨架Wall-tracing只是那个在狭窄区域灵活调整方向的“急救员”。6. 性能对比与实战调优只把算法跑通是不够的RTS场景里必须做性能测试。我在100x100、200x200和300x300三种尺寸的随机地图上做了对比记录每次寻路的节点展开数和实际耗时。测试环境是Intel i5-10400无多线程优化单次寻路取平均值。6.1 三种算法的实测性能对比下表是部分测试数据地图障碍密度约30%起点在左上角终点在右下角算法地图尺寸节点展开数平均耗时(ms)A*100x10058601.27A*200x200231045.84A*300x3005201816.92JPS100x10010420.31JPS200x20041291.43JPS300x30095314.20Wall-tracing100x1004020.09Wall-tracing200x20017890.38Wall-tracing300x30041020.93从数据可以看出JPS在开阔地图上的节点展开数大约是A的六分之一到五分之一运行时间也有数量级优势。Wall-tracing虽然节点数更少但它的路径质量差路径长度通常比A长30%到50%所以不能一味追求速度。在RTS工程里最理想的配置依然是“JPS为主A*兜底Wall-tracing应急”。6.2 寻路结果的后处理路径平滑与分段算法算出来的路径本质上是一串格子坐标直接交给单位走看起来会非常生硬尤其在斜向移动时会有明显的锯齿感。实际项目中要做路径平滑。最简单的平滑方案是“视线检测”从当前路径点的第一个点开始尝试与后面的点做直线连接如果直线上的所有格子都是可行走的就可以删除中间点。这个过程叫“拉直线”虽然简单但对路径观感提升很大。更好的方案是漏斗算法它在A*路径的基础上进一步收缩走廊宽度把路径压缩到贴近障碍物的边缘可以让单位走曲线时更自然。不过漏斗算法实现稍复杂需要处理尖角情况。我对RTS单位的要求没有到丝般顺滑的程度所以采用了拉直线加二次贝塞尔插值的方式看起来效果也不错。还需要做分段处理RTS单位在移动过程中目标点可能发生偏移比如玩家频繁下达新命令如果把整条长路径一次性缓存起来一旦目标变化就要全量重算。我的做法是把路径按一定长度切成多个段单位每到达一个段终点再检查是否需要计算下一段路径。这样每个单位的单次计算量都不会太大也方便动态避障时做局部调整。6.3 动态地图下的缓存与失效策略RTS地图不是一成不变的建筑会新建、被摧毁单位会移动这些都会改变可通行状态。如果每次地图变化都把整个寻路缓存清空代价太大。我引入了一个“版本号”机制地图上的每个区域维护一个版本号单位每帧寻路时带上自己上次寻路时的版本号如果版本号不一致就说明路径可能失效需要重新寻路。这个机制实现起来很简单但是效果非常好。举个例子如果一支部队已经沿着路径走到一半突然有敌人建造了一个兵营挡在路上只有那一小片区域版本号变化其他区域的路径缓存依然有效。单位只需要在版本号变化的区域重新计算局部路径而不是全图重来。在动态RTS战场上这一项优化能节省大量CPU资源。7. 常见问题与排查技巧实录前面的内容偏框架和原理这一部分放实际开发中踩过的坑和处理经验。很多问题不是算法本身导致的而是集成进游戏引擎后出现的各种怪现象。7.1 路径抖动与奇怪绕路最常见的问题是单位移动时路径频繁抖动走几步就停一下看起来像“犹豫不决”。这种问题八成是因为每帧都在调用寻路而不是移动到本次路径终点后再重新计算。我踩过这个坑后做了调整单位每帧检查当前路径终点的可见性如果终点可见就不用重算继续走。只有终点不可见时才重新寻路。这样就把每帧重复寻路的问题解决掉了。另一个奇怪绕路的案例是单位明明可以直接穿过一条宽阔通道却选择绕一个大圈。后来排查发现是地图数据里的某个格子被错误标记成了不可行走但美术资源里看起来是空地。这类问题用“调试可视化”能轻松定位把可行走状态按颜色渲染到地图上一眼就能看出来哪里标记错了。7.2 大数据量下的性能瓶颈早期版本在300x300地图上同时让50个单位寻路时帧率掉到10以下。用profiler一测发现大多数时间耗在开放列表的堆操作上。后来我做了两个优化第一是启用JPS替代A*作为主算法节点数量直接少了一个数量级第二是为每个单位做了一个小的寻路请求队列避免同一帧内同时发起太多寻路请求。第二个优化背后的思路是多单位寻路时不要求每个单位都精确到最优路径而是分批次异步计算。例如一帧最多处理20个单位其他单位继续沿当前路径移动下一帧再处理剩下20个。这里还要提一个细节open list的初始容量不要太小。std::priority_queue在频繁插入时会多次扩容扩容时拷贝元素的开销在节点数达到几万时非常可观。实测中我给队列预留了地图格子数的四分之一作为初始容量效果不错。7.3 多单位寻路的去重与避让RTS里几十个单位同时走向同一个目标点时如果不做处理它们会挤在一起互相卡住。纯寻路算法解决不了这个问题这就到了“局部避让”和“单位去重”的范畴。我的方案是每个单位在移动时除了携带自己的全局路径还会在局部碰撞检测中检查前方是否有其他单位如果有则向两边让一步。这个让行逻辑并不依赖寻路算法但需要寻路算法提供“当前移动方向”和“可绕行方向”的信息。去重则更简单粗暴同一组命令单位的目标点可以设置为一个很小的偏移范围比如目标点中心周围随机偏移0.5格。这样每个单位的实际终点略微不同单位到达后会自然散开而不是所有人都挤在同一个格点。7.4 调试可视化技巧最后分享一个对效率有巨大提升的调试技巧把寻路过程可视化。我实现了一个简单的调试窗口把A*的g值分布、JPS的跳点位置、Wall-tracing的访问次数全部用颜色渲染出来。切换算法时不要只是打印日志而是要能直观看到“为什么这里会绕路”“为什么这个跳点被加入了”。在实际调试JPS时可视化帮了大忙。很多次我以为跳点生成逻辑正确但看到渲染结果后发现跳点出现在完全不该出现的位置这时候立即检查跳点生成函数问题很快就能定位。相比之下纯看调试日志排查路径问题的效率极低。任何寻路算法在RTS这种复杂环境中都必须配合可视化调试器才能保证正确性。如果让我再重做一次这个项目我会把单元测试补得更全一些尤其是针对各种迷宫地图、单点障碍地图和狭长通道地图的边界测试。这里也分享一个建议不要只测试“正常地图”多给算法喂一些极端形状的地图比如S形通道、螺旋图、大回字图。很多隐藏很深的array index越界和死循环问题都是在极端测例里才会暴露出来的。本文还有配套的精品资源点击获取