-
Notifications
You must be signed in to change notification settings - Fork 19
Pathfinding Notes
Currently, the class DijkstrasAlgorithm.cs is the heart of our pathfinding. This was originally written by Quintillus and significantly overhauled and generalized by Kright.
If run with the stopWhenReachingDestination parameter, which is true by default, our Dijkstra's is in fact equivalent to Uniform Cost Search (UCS). We add nodes to the queue as we encounter them and, with that parameter, stop once we find our goal, which are the distinguishing characteristics of UCS. These were added as intuitive optimizations, as at least Quintillus had not heard of UCS at the time they were added. The benefits are lower memory requirements due to adding nodes as they are encountered, and quicker run time due to not having to calculate to all goals.
A* pathing requires a heuristic that indicates which paths are likely to be inexpensive. How can we determine what that heuristic is? Great question!
Amit at Stanford has written some detailed articles on pathing, and his heuristic page is a great reference. Some salient points:
- If we set the heuristic at or below the actual minimal cost, A* will always find the best path
- If we set the heuristic somewhat above the actual minimal cost, A* will run faster, but may not find the absolute fastest path
- There is a tradeoff between speed and accuracy; we may give A* a higher heuristic for more speed on slower computers or as turn times slow down, for example.
- Dijkstra's will never be faster than A* (though with a heuristic of 0 it will be equal), and will always find the optimal path
(Note that in this case I am referring to Dijkstra's where it stops after finding its goal, as our implementation currently does in the default case)
What does this mean for us? It depends on the rules. If we have no roads, the heuristic can be set to 1 and it will always produce an optimal result, while being somewhat better than Dijkstra's due to not having to explore as far in the "wrong" direction. If we have roads (but no rails) and the default road cost, setting the heuristic to 1/3 will accomplish the same. Setting it to a higher value, such as 1/2, may result in sub-optimal routing, e.g. going over a mountain when it would have been quicker to go around that mountain, and the higher the value, the more likely that is to happen but the quicker the algorithm will run.
Since railroads, by default, have a cost of 0, the heuristic would have to be 0 to be lower than or equal to the actual minimal cost. In that case, there is no benefit to using A* over UCS/our implementation of Dijkstra's.
This presents an interesting conundrum where the later in the game we are, the less optimal A* can be at pathing, slowing the game down at the same time that the explosion of units, cities, and everything else is also slowing the game down. This may be related to why Civilization III has noticeably slow path re-calculation in the late game every time a road is built or destroyed; its cost design actively inhibits optimization. Nevertheless, the fact that it sometimes does use sub-optimal routes suggests that at least to some extent it does try to use A* optimization, with a heuristic set higher than the actual minimum cost.
This is an area where we may want to consider configurability. Thankfully, Amit has lots of writing on that topic as well (he also has writing on other topics that may be of interest, such as map generation.
In addition to linear distance based heuristics, we can use landmark heuristics. This is an approach Quintillus had thought might help, and it turns out others had already thought of the idea, decades ago. In our case, the intuitive landmarks may well be cities. By precomputing the absolute cost between cities, the overall algorithm can be optimized.
Whether that would be a net savings after the precomputation is debatable and likely depends on how often the cost of navigating between those landmarks changes. Road and rail construction could invalidate the cache frequently, so it might not be a net savings, and if we try to restrict the precomputation to nearby cities and only recalculate if nearby infrastructure changes - probably necessary to avoid the slowdowns Civ3 has late-game - then we risk being unaware of a newly-enabled circuitous but quick route. In other words, to avoid precomputation being too expensive, we may have to apply heuristics that themselves have a chance of being inaccurate.
Factorio Friday Facts 317 has a good explanation including animations showing how they optimized their A* path-finding by means of using an improved heuristic, which used chunking and a simplified approach to provide an improved heuristic.
In Factorio's case, the simplified heuristic algorithm looks at chunks of land tiles - water tiles are impassable (except to Spidertrons, which are a later addition, but Spidertrons are not long-distance-pathed as biters are). In C7, water tiles may be passable, but unless units of both land and sea classes are implemented, or we implement some sort of embarkment/combine-with-ships routing, we'd still be able to divide based on a land/water division.
There are also some differences. In Factorio, the heuristic ignores cliffs and other entities (walls, etc.) which may significantly lengthen the path. In our case, a heuristic would/may ignore roads/railroads, which could significantly shorten a path - the same problem described above where a very circuitous route could be the shortest. Still, it could be of use, especially in cases involving impassible or unimproveable terrain.
This comment also makes an important note - by running pathfinding from start to end and end to start at the same time, they will meet in the middle, but if either end is e.g. an unconnectable island, that is discovered much more quickly. This is relevant for us as that case may apply - the user trying to tell a unit to move from an island to another landmass, for example.
Our current Dijkstra's uses a binary heap. This is pretty good. However, a D-ary heap would be the optimal structure, where D is calculated based on the ratio of edges to vertices. The Fibonacci heap is also (theoretically) faster than the binary.
How much of a difference this makes and whether it's worth the effort are debatable. We shouldn't just replace what we have because of theoretical improvements, but if and when we do so, make detailed comparisons. To so this we likely need the game to evolve first, so at most we could introduce alternatives (pluggable heaps?) without removing what we have now prior to that point.
At this point in time, pathing is not currently a major problem; there are other things such as gameplay features that are more important.