Expand description
The sector graph, and the “path rank” distance that storage, job and resource searches use.
Running a full A* search for every candidate storage or job would be slow. So the game cuts the map into 8 × 8-cell sectors. The walkable cells of each sector split into connected areas, and each area becomes a node at the mean of its cells. Nodes link to the nodes just outside their sector. A distance is an A* search over the nodes, with Euclidean costs truncated to integers, and it is cached for 120 seconds of game time.
When the map changes, SectorGraph::mark marks the sector, and the graph rebuilds the
marked sectors before the next search.
Structs§
- Sector
Graph - The sector graph: the map cut into 8 × 8-cell sectors, the walkable areas of each sector as nodes, and links between neighbouring areas. It gives the “path rank” distance that storage, job and resource searches use, and caches it.