25+ years of pathfinding problems with C++

TL;DR：《帝国时代》系列25年来的C++寻路系统深受动态地图机制、遗留代码断代、以及SIMD指令集取代x87 80位扩展精度所引发的浮点误差影响，导致单位“穿墙”等经典问题难以彻底根除。 ## 背景与社区反馈 我是Ry，Forgotten Empires的工程总监，也是《帝国时代》的长期粉丝。我的日常工作主要围绕比我自己年龄还大的代码库展开，参与了大部分经典作品的复刻以及《帝国时代4》的部分开发。本文内容主要聚焦于《帝国时代2》及其复刻/高清版本。 在寻路问题上，社区反馈几乎全是负面的，但这情有可原。有价值的反馈通常包含与原版或旧版本的对比，这能帮助我们快速定位回归问题。如果玩家能提供重现案例则更为理想。《帝国时代》采用确定性模拟，支持录像回放功能。当玩家提供录像并明确指出问题发生的时间点时，我们就能获得完美的重现环境，极大降低调试成本。 ## 《帝国时代》寻路的特殊复杂性 《帝国时代》的寻路系统并不走寻常路。单位在移动中会与其他单位碰撞、停止并重新寻路，系统严格禁止推挤或重叠（编队内的友军重叠除外）。编队系统引入了第二套运动逻辑，两套系统交互大幅增加了复杂度。此外，地图完全随机且动态变化，任何建筑或地形都可能随时改变。系统部分基于网格：单位不固定在格子上，但建筑和水域等障碍物严格网格对齐。 ## 为何不直接借鉴《星际争霸2》？ 《星际争霸2》的寻路广受好评，主要得益于暴雪对问题的简化：采用固定地图、引入转向行为（Steering Behaviors）、允许单位轻微重叠并相互滑过。这种设计视觉流畅且玩家体验更佳。 然而，《帝国时代》团队无法直接照搬该方案。我们开发的是复刻与重制版，而非全新游戏。适配《星际争霸2》的寻路逻辑需要重写绝大多数底层游戏代码。在《神话时代：重述版》中，我们曾尝试引入Boy's algorithm，但效果喜忧参半。更重要的是，社区虽然抱怨寻路，却也依赖其衍生的独特战术玩法。例如，有玩家曾用手柄模拟鼠标操作，在骑士冲锋的最后一刻精准移动渔船卡住路线完成防守。若采用更“平滑”的寻路逻辑，这类精彩的微操瞬间将不复存在。 ## 跨越25年的代码与知识流失 该C++代码库已有25年以上历史。原版开发人员已全部离开团队，仅留下部分网络文章、代码注释和日志记录。以遗留代码的标准来看，文档状况尚可，但开发跨度长达二十多年，多个团队经手，寻路系统被反复修改。更棘手的是，我们在接管代码时丢失了源代码变更历史，无法追溯早期的修改意图。 社区曾通过反编译可执行文件、直接修改汇编代码的方式优化过寻路，并被玩家视为“黄金标准”。但由于该补丁开发者销声匿迹，我们未能获取相关改动，起步便处于劣势。内部开发也常陷入“修复一个Bug，引入三个回归”的循环。此外，代码中存在大量无文档记录的“仪式性编程”：某些函数必须按特定顺序调用，否则关联系统会静默失效，只能依靠开发者死记硬背。 ## 短距离寻路算法揭秘 整个寻路系统极为庞大，此处仅拆解占比约10%的短距离寻路算法。该算法无正式文档，但在1999年的硬件上运行高效，且大部分时间有效。其核心流程如下： 1. **收集障碍物**：在起点A与终点B之间划定矩形搜索区域，提取所有轴对齐矩形障碍物。 2. **空间收缩**：将寻路单位收缩为一个点，并将收缩的体积叠加到所有障碍物上，将矩形避障简化为点避障。 3. **构建凸壳**：使用礼品包装算法（Gift Wrapping Algorithm）围绕障碍物生成一个或多个凸壳。 4. **逃离与射线探测**：若起点与终点不在同一凸壳内，系统从起点向四个正轴方向发射射线。若射线命中障碍物，则向侧面反弹，直至逃出当前凸壳。 5. **沿边行进**：逃出后，单位沿凸壳边缘移动。在每个顶点处向目标发射射线，若被阻挡则重复沿边移动与射线探测，直至抵达目标。 6. **路径平滑**：通过暴力测试移除冗余路径点，确保新路径不与障碍物重叠。 **边界情况处理**：若起点终点在同一凸壳或不同凸壳内，系统采用类似双向寻路的策略，分别从两端发射射线逃出凸壳后连接路径。若凸壳超出搜索区域，则扩大区域重试。若单位被完全包围（无路径），系统会扩大搜索范围并在数组边界内随机尝试，最多执行64次迭代或耗尽未尝试顶点。 长距离寻路则采用基于中间导航点的A*算法（早期分层寻路雏形），速度极快，是当年保障整体性能的关键。 ## 浮点精度灾难与“穿墙”Bug 该算法存在一个经典缺陷：单位偶尔会直接穿过墙壁或建筑。这是几何精度误差的教科书案例。礼品包装算法在构建凸壳时，需判断三个点是“左转”还是“右转”。当点距极近或几乎共线时，浮点精度不足会导致判断错误。错误结果会使凸壳未能完全包裹障碍物，反而切入内部，导致生成的路径直接穿墙。 《帝国时代2》《帝国时代3》和《神话时代》均受此困扰，且近期触发频率莫名上升。原版开发者曾尝试移除距离过近的点，但未能覆盖所有情况。《帝国时代3：决定版》开发期间，有开发者将`float`升级为`double`（64位），虽提高了精度、降低了Bug重现率，但仍未根除问题。其他采用类似几何算法的游戏也普遍遭遇过同类穿墙现象。 ## SIMD指令集与80位扩展精度的取舍 在调试《神话时代：扩展版》时，我手动关闭了编译器优化选项，意外禁用了SIMD指令集，使编译器回退至IA32指令集。令人惊讶的是，穿墙Bug彻底消失了。 根本原因在于**80位浮点扩展精度**。早期的x87 FPU硬件在中间计算时会使用超宽寄存器保留额外精度。随着SIMD技术普及，架构设计选择牺牲扩展精度以换取性能。这一取舍导致精度状态变得不可预测：一旦中间结果存入临时变量或寄存器耗尽，精度就会瞬间丢失。对于极度依赖共线判断的礼品包装算法而言，这种微小的精度波动足以引发左转/右转误判，进而导致凸壳计算错误。 当年开发者转向SIMD追求性能时，可能并未意识到精度牺牲对几何算法的深远影响。这也是为何许多老游戏在现代编译器或架构下会重现古老Bug的原因。寻路问题不仅是算法设计的挑战，更是硬件演进、编译器行为与二十多年代码债务交织的缩影。 Source: https://www.youtube.com/watch?v=lEBQveBCtKY