Multi-turn pathfinding
In Unciv, our pathfinding algorithm is one of the major points of performance costs, a trait it seems to share with many other turn-based strategy games.
I am often asked if we can’t optimize this using a variation on a classical pathfinding algorithm like A*, and while I’d welcome any working solution that improves upon our existing one, there’s a reason this question is prevalent —it is not immediately obvious that classical pathfinding algorithms cannot account for the multi-turn aspect.
This is an explanation of the problem and our current solution, and the alternative we tried and which ultimately failed to outperform it.
The Problem, or, Dijkstra’s Folly
Strategy games often have movement points (MPs) for each unit, limiting a unit’s movement per turn. Different tiles will have different movement costs, and if a unit’s MP are less than the cost, the game can decide to do one of 2 things:
- Allow the unit to enter the tile (e.g. Civ V) — this is the behavior we’ll be discussing
- Disallow (e.g. Civ VI)
Classical pathfinding algorithms — BFS/DFS, Dijkstra, A* — assume that given a given cost for each movement between nodes, the goal is minimizing the sum of costs.
For a simple example, consider the following scenario:
Assuming infinite movement is possible, classical algorithms will give the correct result, that going around the hills is optimal.
Limiting turns, though, fundamentally changes the problem. For the bottom-left unit to reach the top-right, it will have a different optimal path depending on the amount of MP it gets per turn.
- If we only have 1 MP per turn, the optimal path is through the hills, taking us 3 turns — we can only move one tile per turn in any case, so the extra cost of the hills doesn’t affect us.
- If we have 5 MP, we can get to our destination directly, in one turn — and in this case, going through the hills will cost us 2+2+1=5 MP, while going around will cost us only 1+1+1+1=4 MP, so going around the hills is the optimal solution.
Our pathfinding algorithm thus will act similarly to a classical pathfinding algorithm within the bounds of a specific turn, but this breaks at the boundary between turns.
Our current solution
We divide the pathfinding into 2 separate functions
A. Intra-turn pathfinding which is a classical BFS, but includes some game-specific changes such as guessing unknown tiles to be 1, saving known unenterable tiles, etc
B. Inter-turn pathfinding, which is the interesting part, and the one we’ll focus on :)
Algorithm outline
The meat of the multi-turn pathfinding is, starting with the current tile, on each iteration (==unit turn):
- Sort ‘tiles to start turn on’ by hex distance to target — here it’s a hexagonal grid, but the algorithm would work equally well on arbitrary graphs using “min distance to target”
2. For each tile we can start on:
- Get ‘distance to tiles’ for this turn
- If the tile we want to reach is there, success!
- Otherwise, add all tiles to candidate tiles for starting on next turn
3. Filter out tiles where we have paths to all adjacent tiles — they would never be a candidate for starting next turn, since every path they lead to, we could just start on the next tile of that path
Much of the intermediate results are cached for performance.
Visual representation
In effect, we’re building an ever-expanding ‘bubble’ of tiles to “perhaps start the turn on” in turn N, each one leading back to its source in turn N-1, giving us the ‘route to destination’ once we’ve reached our target.
For a simple example, if from the central tile here we’re trying to reach the mountain with a 2-movement unit, after 2 “turns” our ‘group of tiles to check’ would be the outermost ring. Since we sort tiles to check by grid distance to the target, I’ll use a desert tile to signify the first tile we’re going to check, and its adjacent tiles will be next in line, etc.
Checking the tiles we can reach this turn, we’ll get the following white tiles:
And since this includes the tile we’re trying to reach, we’ve finished and return the path so far, plus the destination, as the final path.
Trade-offs
Of note is that we sacrifice true certainty to gain performance: We return the path for the first tile from which we can reach the target tile, even though theoretically a different path could lead to that tile with more movement points remaining. While we will always provide a turn-optimal solution, we may provide a solution that gives us less remaining movement points upon arrival.
This is because we determined that such cases are rare, and the alternative is hermetically checking every viable start tile. For the example given above, we only had to check 1+12+1=14 “tiles to reach this turn” with this short-circuit, whereas if we check all start tiles in the final turn we would need 1+12+24 =37, which is a severe performance penalty.
The Alternative — Unifying inter- and intra-turn movement
In a bid to maximize performance, we want the ability to make more explicit trade-offs. For example, if we manage to get to the target in a straight line, do we really need to check the opposite direction? On the one hand, nothing guarantees that the other direction won’t have a super-fast highway to go around all the tiles we’ve checked so far, but it is unlikely. Having everything in one function means we can choose how we make these trade-offs, and how we choose which tile to work on next.
We consider movement cost as a tuple of turns and remaining movement.
Function Outline
A. Initialize ‘tiles to check’ with current tile
B. For each tile in tiles to check, check its neighbors. Any neighbor we have reached in less than the distance to the origin tile, we obviously can’t get to faster. For the rest, we check the distance between this tile and the neighbor. We then need to ‘add’ the movement cost to the cost up till now.
- If the previous movement cost had zero remaining movement, that means we had to start a new turn to get here — increment turns by 1 and set remainingMovement to maxMovement — distanceBetweenTiles.
- Else, set remaining movement to remainingMovement-distanceBetweenTiles, with a minimum of 0
- If the distance to this tile is less than the current minimum, we have a winner, we cache the result and we add this as a tile to keep exploring from on subsequent loops
Each step references the previous step, so we can have the entire path we took.
Move-through only tiles
Another thing that distinguishes our pathfinding is there are some tiles a unit cannot enter but can move through — e.g. they already contain a unit. In the previous algorithm this is handled naturalistically — we find the maximum bounds of a given turn and find the ‘edge tiles’ that we can get to on this turn — but since our new algorithm considers tiles as a stream and not as a set of batches, we need to handle this differently.
For example, say we have tiles ABCD, our unit is on A and has 2 movement, and tile C is pass-through only. The unit can reach tile D by passing a turn in B, which is fine for the old algorithm — it would gather all tiles the unit can reach on turn 1 (B+C), discard the non-enterable ones (C) and continue from B as a start-of-turn tile.
But our new algorithm doesn’t batch these tiles, once it reaches C with zero movement, how do we know that it can enter D?
One possible option is that on every tile, we continue on with two ‘alternative histories’ — one where we ended a turn on that tile, and one where we didn’t. But this will exponentially increase the number of checks we need to do, and confuses our caching (how do we compare with the cached ‘best route’ if we may be on an alternative path that is intentionally slower?)
Instead, we can consider that the only tile that needs this alternate history is a tile that is otherwise unreachable. In effect, once we’re checking C and we see that it’s on zero movement and unenterable, we need to find the next-best alternative by backtracking to the last tile we can end a turn on, and taking the alternate route (increase turn, remove interim movement costs).
In our example, when we see we ended our turn on C, we will go back until we can end a turn — to B —and change the cost of getting to C from “1 turn 0 movement” to “2 turns 1 movement”. Under this new movement cost, we see that we can reach D!
Trade-offs
This all-in-one solution lets us improve several things:
- For “can we reach” questions, where we only care about getting to the target and not about finding the minimal path, we can sort the tiles by distance to target so we’re always working on the closest tile, even if it gives a suboptimal route
- For “best path” questions, we can sort the tiles by A. turns and B. distance to target. This means we will retain the current behavior of “finish an entire turn before starting the next” to ensure we’re turn-optimal, as discussed in trade-offs above.
These sorts are done using a heap for efficiency, and obviously there is a lot of caching going on.
However, we can start considering sorting by combinations of turn and distance — say, “sort by turn + (distance/maxmovement)” —to give us a ‘best guess’ of which tiles are the best candidates. We can then alter the distance by some multiplier to increase or reduce, giving us a precision vs performance tradeoff we can play with.
This also lets us get a much more granular view of the pathfinding results. Instead of only knowing which tile the unit will go to on each turn, we can now know the exact path within that turn, because it’s all represented on the same ‘level’.
Wait, it’s SLOWER?!?!
After getting the all-in-one solution up and running, we were excited what performance gains we would see — after all, aren’t we prioritizing tiles, and caching results?
I personally was shocked to see that the new algorithm was up to 7 times slower that the old one, and even with all the performance improvements we could think of (compareValuesBy is inordinately slow!) we still could get 3x better results on the old algorithm in worse cases. What’s going on?!
The sad truth of the matter is — the time it takes to store and retrieve an object in a sorted set was taking longer than the entire rest of the algorithm. We had already optimized our existing algorithm to within an inch of its life, hence at the local maxima we were at we could only change by using a different algorithm. But the fact is, a O(lg(n)) add() and pop() function don’t tell you anything about the millisecond cost of such functions.
In practice, we were talking about less than 1000 tiles — not in the millions — and the cost of sorting tiles as they come, as well as caching results to reuse later, were on the same order of magnitude as the cost function itself which we considered to be the big time sink.
Without testing this out ourselves, we could never have known. And I want to point out Intellij Idea’s excellent profiling capabilities, which I discovered during this adventure. The per-line and per-function cost being displayed by the code was a game-changer for nailing down performance issues — and we even managed to find room for improvement in our existing algorithm!
End notes
This seems to be a relatively unexplored area of pathfinding — I haven’t been able to find any other sources on this problem, and many other strategy games have implemented multi-turn pathfinding, so there must be other people who are knowledgeable about this.
If you’re one of those people, please reach out to me here or at yairm210@hotmail.com so we can improve the performance of Unciv :)
