1# Pathfinding 2 3[Source](http://www.gamasutra.com/view/feature/131844/postmortem_ensemble_studios_age_.php?page=2) 4 5[Source](https://web.archive.org/web/20081221121604/http://www.gamasutra.com/features/gdcarchive/2000/pottinger.doc) 6 7and *Ensemble Studios Official Strategies & Secrets to Microsoft's Age of Empires II: The Age of Kings*, Bruce Shelly, 1999, published by Sybex Inc. 8 9## Algorithms 10 11Age of Empires 2 uses three different algorithms for pathfinding plus two obstruction systems. 12 13The first (high-level-)pathfinder is meant for long distances and uses mip-mapping to create a general route across the map. Criteria for the mip-map subdivision is *passability*. It ignores moving objects, e.g. units or wildlife, though it takes "static" object like buildings into account. Whenever a building is constructed the pathfinder gets notified and updates the corresponding mip-map chains. 14 15Further reading: [3D Pathfinding](http://www.in.tum.de/fileadmin/user_upload/Lehrstuehle/Lehrstuhl_XV/Teaching/SS06/Seminar/3dpf-doc-final.pdf) (p. 11) 16 17The other two pathfinders are for short and medium distances. One uses tile-based pathfinding while the other one is a polygonal pathfinder that dynamically generates convex hulls. These are used in combat situations or when units cross paths. 18 19## Examples 20 21*(Please add more examples if you know any)* 22 23``` 24............... ............... ............... ............... 25............... ............... ............... ....XX.XXXXX... 26......T........ ---> ......T........ ---> ....XXTXXXXX... ---> ....XXTXXXXX... 27............... ---> ....XX.XXXXX... ---> ....XX.XXXXX... ---> ............... 28....XXXXXXX.... ....XX.XXXXX... ............... ............... 29....XXXXXXX.... ............... ............... ............... 30``` 31Units will split up their formation if they encounter an obstruction such as a tree. 32 33``` 34.............. .............. .............. .............. 35.............. .............. .............. ....X....X.... 36....YYYYYY.... ---> ....YYYYYY.... ---> ....YYYYYY.... ---> ...XYYYYYYX... 37.............. ---> ....XXXXXX.... ---> ...XXXXXXXX... ---> ...XXXXXXXX... 38....XXXXXX.... ....XXXXXX.... ....XX..XX.... .............. 39....XXXXXX.... .............. .............. .............. 40``` 41When troops encounter an enemy formation they will try to go around to engage in combat. Though if units get killed and create a gap, the pathfinder has some difficulties to distribute units efficiently. 42