Last week I've been in the lab, polishing the pathfinding algorithm. It was sort of working earlier, but in my opinion it's one of those things that you can't really skimp on in an RTS, since how the units move through the world and react to your commands goes a long way toward determining game feel. Having units get stuck on terrain and get lost in the woods may have been acceptable in a 90s RTS, but these days it would be unacceptably frustrating.
Before, the pathfinding system in Trollskog was based on the Jump Point Search search algorithm, which is an optimized variant of A* that assumes the traversed graph is a grid. I first encountered the algorithm in
this whitepaper.
Since the terrain in Trollskog certainly is a grid, it seemed like a good fit.
The lit area indicates a route calculated by the JPS pathfinder. The yellow squares indicate jump points. Path-smoothing is applied to the route, as JPS tends to generate straight routes that take as few 45 degree turns as possible.
While JPS was orders of magnitude faster than my initial A* prototype, it wasn’t the performant silver bullet I’d hoped for, and it didn't help at all with steering behaviors - A single entity following a path worked fine, but having a large group of entities all navigating together, bumping into each other and other entities along the way resulted in a lot of edge-cases, sometimes requiring path recalculation. I kept piling on band-aids for a while, trying to fix new strange behaviors as they arose, but eventually made the decision to try another algorithm.
Some research into my problems led me to flowfields. These are great because they practically solve pathfinding and steering using the same algorithm.
This GameAIPro chapter by Elijah Emerson remains the best writeup I’ve found on the subject.
Flowfields work quite differently from graph-traversal algorithms like A* and its variants. To summarize, it works by calculating a vector to the goal from each tile on the map, then each entity just has to follow the average vector of the four tiles around it to find the goal.
Filling the entire world with vectors for every move command would be crazy inefficient, so instead we break the world up into sectors, and only fill the sectors that contain moving entities.
Here we see a 64x64 chunk of Trollskog’s world, divided into 8x8 sectors.
These sectors play two roles, one as a convenient bound for our vectorfield floodfill (to avoid having to fill the entire game world with vectors) and also for the first-pass hierarchical pathfinding. We can let the pathfinding system do an initial, broad-strokes search by traversing whole sectors at a time before we run a finer search on a tile-level, letting us break up a potentially large request into many smaller ones.
A region showing debug vectors. Tiles that have line of sight to the target just have a vector pointing straight to the goal.
We need to keep these pathfinding sectors up-to-date by recalculating them, individually, whenever an entity that blocks a tile is placed or removed. And naturally, we want to generate these pathfinding regions as late in the terrain generation process as possible - An average 64x64 chunk of terrain in Trollskog contains about 2000 trees, and keeping the pathfinding regions up-to-date during the generation process while those trees are being placed would be a pointless waste of resources.
The advantages to this approach were immediately apparent. In the worst-case, A* and JPS explored most of the world before concluding that, yes, this unreachable spot surrounded by trees is, in fact, unreachable. The hierarchical flowfield approach can often rule out destinations which are not connected to any portal instantly, or at worst rule them out during the initial portal traversal stage. The algorithm scales wonderfully with multiple pathing agents, since they can re-use the same pathfinding data.
Here, 2 entities pathfinding with vector field debug display enabled.
The result works a lot better than the previous (JPS) implementation, with a lot of tweakable variables (like collision radius, repelling force, etc) that I can play around with to make the end result look and feel the way I want.