The real fun is designing the agent's AI: exploration, avoidance, engagement ;)
Crowd Pathfinding And Steering Using Flow Field Tiles
http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd...
Flow Field Pathfinding Tutorial
I think you're forgetting there is no map design time in Age of Empires since the maps are RNG. Also, walls, structures, and destroyed forests are critical to gameplay, so it has to be an extremely dynamic process.
There are obviously ways to improve the pathfinding, https://github.com/SFTtech/openage has many plans, but your dismissals are starting from wrong assumptions.
And for AoE you cannot precompute everything. Things you have to tackle:
- Walls being built or torn down
- Trees being chopped down, gold being mined
- Units moving as a single group, not bumping into each other, not creating a dead lock when entering a narrow passage
- Units of various sizes (ram vs. villager)
This would not have been a great solution on the original AoE's 16MB target memory.