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*、JPS（Jump 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::vector<GridNode>按索引访问，不需要额外的哈希表。

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%，起点在左上角，终点在右下角）：

从数据可以看出，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越界和死循环问题，都是在极端测例里才会暴露出来的。

本文还有配套的精品资源，点击获取