25+ years of pathfinding problems with C++

TL;DR: The C++ pathfinding system in the 25-year-old *Age of Empires* series is deeply affected by dynamic map mechanics, lost knowledge in legacy code, and floating-point precision errors arising from SIMD instruction sets replacing the 80-bit x87 extended precision. These issues make classic problems like units clipping through walls extremely hard to fully eliminate. ## Background and Community Feedback I'm Ry, Engineering Director at Forgotten Empires and a long-time fan of *Age of Empires*. My daily work largely revolves around a codebase older than I am, spanning most classic remasters and some development for *Age of Empires 4*. This article focuses mainly on *Age of Empires 2* and its HD/Definitive editions. Feedback on pathfinding is almost entirely negative—but understandably so. The most valuable reports often include comparisons to the original or a previous version, helping us quickly identify regressions. It's even better if players can provide reproducible cases. *Age of Empires* uses deterministic simulation with replay support. When players attach a recorded game and point to the exact moment of the issue, we get a perfect reproduction environment, drastically reducing debugging cost. ## Unique Complexity of *Age of Empires* Pathfinding The pathfinding in *Age of Empires* is far from conventional. Units collide with each other while moving, stop, and replan their paths. The system strictly forbids pushing or overlapping (except for friendly units within a formation). The formation system introduces a second layer of movement logic, and the interaction between the two dramatically increases complexity. On top of that, maps are completely random and dynamically changing; any building or terrain can be altered at any time. The system is partially grid-based: units are not locked to tiles, but obstacles like buildings and water are strictly grid-aligned. ## Why Not Simply Copy *StarCraft 2*? *StarCraft 2*'s pathfinding is widely praised, largely because Blizzard simplified the problem: they used fixed maps, adopted steering behaviors, and allowed units to slightly overlap and slide past each other. This design is visually smooth and generally feels better to players. However, the *Age of Empires* team couldn't just adopt that approach. We're working on remasters and definitive editions, not a brand-new game. Adapting *StarCraft 2*'s pathfinding logic would require rewriting most of the low-level game code. For *Age of Mythology: Retold*, we did experiment with Boy's algorithm, but results were mixed. More importantly, while the community complains about pathfinding, they also rely on the unique tactical gameplay it creates. For instance, one player used a controller to emulate mouse input and precisely moved a fishing boat to block a knight charge at the last moment, saving the game. With "smoother" pathfinding, such brilliant micro moments would vanish. ## 25+ Years of Code and Lost Knowledge This C++ codebase is over 25 years old. The original developers have all left the team, leaving behind only a handful of online articles, code comments, and log entries. By legacy-code standards, the documentation is decent, but the development span covers over two decades, multiple teams, and the pathfinding system has been modified again and again. Even trickier: we lost the source code change history when we inherited the code, making it impossible to trace the intent behind early edits. The community once optimized pathfinding by reverse-engineering the executable and directly patching the assembly code, and that version was hailed as the "gold standard" by players. However, the developer of that patch vanished without a trace, so we never obtained the changes—putting us at a disadvantage from the start. Internally, we constantly find ourselves in a loop of "fix one bug, introduce three regressions." Moreover, the code is full of undocumented "ritualistic programming": certain functions must be called in a specific order, or connected systems silently fail, forcing developers to rely on rote memorization. ## Short-Distance Pathfinding Algorithm Uncovered The full pathfinding system is massive; here I'll break down only the short-distance algorithm, which accounts for about 10% of the logic. The algorithm has no formal documentation but ran efficiently on 1999-era hardware and worked most of the time. Its core flow: 1. **Collect obstacles**: Define a rectangular search area between start A and target B, extract all axis-aligned rectangular obstacles. 2. **Shrink space**: Shrink the pathfinding unit to a point, then inflate that volume onto all obstacles, reducing obstacle avoidance to point-vs-rectangles. 3. **Build convex hulls**: Use the Gift Wrapping Algorithm to construct one or more convex hulls around the obstacles. 4. **Escape and ray tests**: If start and target lie in different hulls, fire rays from the start in the four cardinal directions. If a ray hits an obstacle, it bounces sideways until it escapes the current hull. 5. **Hug edges**: After escaping, the unit moves along the convex hull’s edges. At each vertex, a ray is fired toward the target; if blocked, it continues hugging edges and retesting until reaching the target. 6. **Smooth path**: Redundant waypoints are removed via brute-force testing to ensure the new path does not overlap obstacles. **Edge cases**: If start and target are in the same or different hulls, the system essentially performs a bi-directional search, firing rays from both ends to escape hulls and then connecting the paths. If a hull exceeds the search area, the area is expanded and the process retried. If the unit is completely surrounded (no path), the search area is enlarged and random attempts are made within array bounds, with a maximum of 64 iterations or until all unvisited vertices are exhausted. Long-distance pathfinding uses an A* algorithm over intermediate navigation points (an early form of hierarchical pathfinding), which is extremely fast and was key to maintaining overall performance back then. ## Floating-Point Precision Disaster and Wall-Clipping Bugs The algorithm has a classic flaw: units occasionally walk right through walls or buildings. This is a textbook case of geometric precision errors. When building the convex hull with the Gift Wrapping Algorithm, it must decide whether three points make a "left turn" or "right turn." When points are extremely close or nearly collinear, insufficient floating-point precision can cause a wrong turn decision. That erroneous result can make the convex hull fail to fully enclose the obstacle, instead cutting into it and generating a path straight through the wall. *Age of Empires 2*, *Age of Empires 3*, and *Age of Mythology* all suffer from this, and recently the frequency has strangely increased. The original developers tried removing points that were too close together, but that didn't cover all cases. During *Age of Empires 3: Definitive Edition* development, one developer upgraded `float` to `double` (64-bit), which improved precision and reduced the bug's occurrence, but still failed to eliminate it. Other games with similar geometry algorithms have commonly run into the same wall-clipping phenomenon. ## SIMD Instruction Sets and the Trade‑off of 80‑bit Extended Precision While debugging *Age of Mythology: Extended Edition*, I manually turned off compiler optimizations, which incidentally disabled SIMD instruction sets and forced the compiler to fall back to IA32 instructions. To my surprise, the wall‑clipping bug vanished completely. The root cause is **80‑bit extended floating‑point precision**. The early x87 FPU hardware kept extra precision during intermediate calculations using ultra‑wide registers. As SIMD technology spread, architectural choices traded away that extended precision for performance. This trade‑off makes precision state unpredictable: the moment an intermediate result is stored into a temporary variable or a register is spilled, the extra precision is lost instantly. For the Gift Wrapping Algorithm, which is extremely sensitive to collinearity checks, such tiny precision fluctuations are enough to cause a left‑turn/right‑turn misjudgment, leading to a malformed convex hull. When developers moved to SIMD to chase performance, they likely didn't realize the profound impact of precision sacrifice on geometric algorithms. That's why many old games see ancient bugs reappear on modern compilers or architectures. The pathfinding problem isn't just a challenge of algorithm design—it's a tapestry woven from hardware evolution, compiler behavior, and over two decades of code debt. Source: https://www.youtube.com/watch?v=lEBQveBCtKY