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