On Age DE's pathing/movement

Typical Age DE forum post:

The pathfinding in the game is terrible.

First off, Age of Empires Definitive Edition is a remaster of Age of Empires. It's not a rewrite, it's not a new engine, and that's what we've been saying for almost a year. Age of Empires 1's path finding was really bad, as most reviews point out:

https://gamespot.com/reviews/age-of-empires-the-rise-of-rome-review/1900-2532811/

This is the code we started with in DE. Not Age 2, not new code, but the original code which had a ton of flaws and quirks we had to learn about the hard way. This code was almost a quarter of a century old, and it showed. The original movement/pathing code was very weak to say the least. Yet entire complex systems above it (combat, AI, etc.) depended on this super quirky movement/pathing code. It took multiple Ensemble engineers several years of development to go from Age 1 to Age 2 level pathing.

We made a number of improvements to the path finding and unit movement code without breaking the original system. It must be emphasized that Age1's pather and movement code is extremely tricky and hard to change without breaking a hundred things about the game or AI (sometimes in subtle ways). It was a very tricky balance. The current system still has problems with chokepoints, which can be fixed with more work, but we instead had to focus on multiplayer which had to basically be 85% rewritten.

Here's a list of fixes made so far to DE's pathing and movement code in the time I had, which was only like 2 months:

• DE's pathing system's findPath() function was speeded up by approx 3-4x faster vs. Age1's
  I performed around a dozen separate optimizations passes on the core pather. I implemented the A* early exploration optimization (eliminating 1 open list insertion/removal per iteration), and massively tuned the C++ code to generate reasonably efficient x64 assembly. I transformed the inner loops so much that they barely resemble the original code. We retested the pather and game thoroughly after each major optimization pass. 

• Age1's pather's A* implementation was outright broken (the open list management was flawed, so the cheapest node wasn't always expanded upon during each iteration). DE's pather fixes all these bugs and is a proper implementation of A*. (I have no idea how the original code shipped, but it was 1997!)
• DE's pather gives up if after many thousands of iterations it can't make forward progress towards the goal, to avoid spending CPU cycles on hopeless pathing unnecessarily. (It's more complex than this, but that's the gist of it.)
• Added multiple lane support to villager pathing.
• Villagers can use one of two collision sizes (either small or large), so if a villager bumps into another friendly villager we can immediately switch to the smaller radius to avoid stopping. So basically, villagers can get very close to each other, avoiding gathering slowdowns. Villager vs. military combat was preserved because vills use large radii by default, and if a vill vs. vill collision doesn't occur after a set period of time the villager returns back to the large radius. (An unfortunate side effect of this: It's possible to group together a ton of villagers - way more than the original game - and use them to attack other units. Villager Mobs are a game unbalancing issue in DE.) Note that another engineer (not associated with FE) attempted to "fix" villagers by allowing them to collide/overlap and totally broke the entire game, and that code did not and could not ship because it broke the engine's assumptions in multiple ways.
• Movement of units through single-tile openings was greatly improved and tested with all unit types. Age 1's handling of single tile openings was so bad that players would exploit it:
  http://artho.com/age/placeb.html
• The DE pather was modified to have a much higher max iteration count than Age1's, so longer and more complex routes can be found.
• The per-turn pathing cap in Age1 was switched to short and long range pathing categories in DE. 8 short range paths can occur per turn, and for long range paths it supports up to 4 findPaths() per turn.
• For short range paths, straight line paths are preferred vs. the tile path returned by findPath() if the straight line path is safe to traverse.
• Boat movement was modified to have deceleration.
• Waypoints along a path can be skipped if a unit can safely move from its current position to the next waypoint
• Added support for 32-facing angles vs. Age's original 8. Also, the unit direction/facing angle is interpolated in DE, instead of "snapped" to like in Age1. The interpolation is purposely disabled when units switch angles during combat.
• Added stuck unit detection logic to DE's movement code, to automatically detect and fix permanently stuck units (rare, but possible).
• We ported Age2's entire obstruction manager into DE, replacing the old bitmap system. Units use circular obstructions, and buildings use square obstructions.
• Added several new behaviors to the movement code to help with chokepoints: A "wait" behavior, that checks every second or so for up to 45 seconds to see if the unit can be moved to the destination, and a stuck unit "watchdog", which watches to see if a unit hasn't made forward progress and tries to switch behaviors to get the unit unstuck. Age1's code would just give up at the slightest problem.
• The pather tries to path starting from the center of each tile, but this sometimes fails in tight spaces or with lots of units around. DE tries harder to find a good starting position, so movement through single tile openings isn't broken.
• Path caching system: Villagers and boats can reuse previously found paths in DE, for efficiency.
• In situations that Age1's pather would just outright give up and stop, DE's pather tries a lot harder to get the unit where it needs to go using several randomized fallback behaviors.
• Age1's waypoint detection code was very janky and fixed in DE. Age1's code would sometimes cause units to oscillate around their current waypoint until it figured out it was ok to go to the next one.
• The original Age1 devs used text log files to debug the pather/movement systems. I had to write a 2D/3D debug primitive system so I could see what was actually going on. Here are some development screenshots - notice how complex this stuff is:

Age1's pathing/movement systems implements a form of randomized, emergent behavior. The units are basically like dumb ants. It's imperfect in chokepoints, but it's a continuation of the essence of what made Age 1 what it was. If all the units are moving in the same direction it can usually handle chokepoints (I tested this over and over with a wide variety of units on a pathing torture test scenario from MS before release). The fundamental behaviors the AI and combat systems expected were accurately preserved in DE's pather, which was our goal.

Instead of people saying "the pathing in DE sucks!", I would much rather hear about the specific issues with movement/pathing, and actually constructive suggestions on how to improve the system without breaking the game or turning it into Age 2.