Wednesday, February 28, 2018

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:
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:
  • 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.


  1. As a software developer and _huge_ fan of aoe1-2 I want to express my gratitude for dusting off this title.
    My opinion is that you cannot expect people to understand this is not a full rewrite. It's just the way it is.

    Do you think there is margin of progress with the resources you currently have?

    PS: I'd love to see a technical post where you explain how you fixed one+ of the above issues!

    Keep up the good work!

    1. Thanks. If I had the proper amount of time (several months), I could improve pathing/movement massively. I'm leaving some things out about the entire experience of fixing pathing/movement in Age1 which I'll eventually talk about once the dust settles.

      Note I'm no longer associated with FE, and not working on Age DE anymore. I'm moving on to my product and other opportunities.

  2. Please i need gates...what good are the walls ...if i have to leave gaps open for my troops that can be used by opponent.....seriously how can such a gameplay blunder survive ur testing phase

    1. Sorry, I hear you, but gates are not part of Age 1 (and never have been):

  3. Great post, Rich! I think you did an amazing job to help bring Age I into the modern RTS market. Without a full-blown remake, this is the best version this game could be. You've turned an antique, almost unplayable game into a fun experience. It's still odd to me that Starcraft fans wanted exactly the same gameplay for the remastered edition, and a lot of Age fans wanted Age II gameplay in Age DE. As a major Age fan myself, I celebrate each game's uniqueness and I'm in love with the Age of Empires revival.

    I'm looking forward to your future projects!

    1. This comment has been removed by a blog administrator.

    2. This is very likely because Starcraft is oriented way more on competition and esports. I am a very strong Age 1 player myself and I actually don't mind the quirky path finding in Age 1. As a strong player you will find ways around this in order to play better. In other words: your skill in the game makes up for the game's limitations.

      Imagine if you mastered all these skills and suddenly a remaster renders all these skills useless by changing the game's mechanics in such a way that it becomes much easier. Of course as a strong player this is not what you want. I think this is exactly why Starcraft fans did not want different gameplay. Starcraft is backed by a TON of competitive players. On the other hand, AoE is not very oriented on e-sports, but instead, has more of a casual gamer public. These type of gamers prefer easier gameplay and thus want a better experience.

      As an example: Many strong AoE 1 players don't like stuff like auto farm reseed, formations etc. Because these all replace skills that were acquired to micro manage these kind of things, even though this may seem ridiculous.

  4. Wow, super interesting post. Agreed about reading more details about the pathing. This is also the first time I've heard of the Definitive Edition or Forgotten Empires.

    Didn't making all these changes affect the balance of the game a lot? Did any of the scenarios need to be edited to change unit placement as a result of taking different paths/not bunching up as muct?

    1. Thanks! For sure, balance has been impacted. It's now possible to combine together dozens or even a hundred villagers into an 'Uber Villager" of sorts, and use them to attack single units. The combo can be quite effective to protect your base. Also, you can have a dozen villagers gathering a single resource at an accelerated rate vs. the original game. None of these issues have been addressed yet.

      I don't believe combat was impacted in any significant way vs. the original (excluding vills).

    2. Also, the scenarios were modified in DE, but I don't think any major changes were triggered by the pathing/movement fixes.