Woosls2

2000-01-01

Everything is done in the map. Each map tile has a list of object. An object can be a unit, an item, a building...
And each map tile has a terrain.
There are two functions: find_path(pos1, pos2) and find_nearest_item(pos, item).
To allow big maps, the item finder is optimized using a simple quad-tree. All items are inserted into the tree, so the first tree level will simply be a listing of all objects in the map, and the deepst level will represent a single tile. It's possible to quickly locate any item on the map that way.
For the path finder, the map is first split into sectors of passable and not passable terrain, and each tile knows its sector number. This makes it possible to immediately decide of a path exists (both positions must be in the same sector). If a path exists, a hierarchical A* is used - finding a tile-by-tile path if the positions are near, else doing a coarse search first using an additional sectors map.