Hey everyone!
I wanted to share a little summer project I’ve been working on called NativeFlowField (MIT License). It’s inspired by an article on visualizing Dijkstra maps, which you can check out here.
Flow fields are an alternative approach to A* pathfinding that is useful with large numbers of agents. It’s been around for a while but I’ve noticed an uptick in popularity over the past year.
Below is an example of an animated flow field heatmap that shows the paths that agents will move along to reach the target at the center of the maze.
The Challenge:
I initially created a .NET implementation, which was straightforward but didn’t meet my performance expectations. So, I ported it to Unity DOTS to utilize native containers and Burst compilation. This significantly boosted performance, but it still did not scale well enough for real-time scenarios.
Basically, my goal was to be able to recreate the flow field continuously, to make it adaptable to dynamic environments and moving targets.
The Idea:
To overcome the scalability issue, I decided to port the implementation to compute shaders and treat the entire flow field as one big texture (or compute buffer).
A key difference from the traditional priority queue approach here is parallelization. While Dijkstra’s algorithm requires that you process nodes sequentially, the compute shader approach allows all nodes to process simultanously, causing the distance field to propagate outwards in all directions as a wavefront.
How It Went:
The compute shaders were easy to implement. The propagation shader simply scans neighboring cells, picks the one with lowest value, adds 1 (or sqrt2 for diagonals) and writes that value back to the cell. The second shader converts the propagated distance field into a flow field and the third (optional) shader converts the distance field into a heatmap render texture (like the one at the top of this post).
Managing buffers and efficiently shuffling data from CPU to GPU (and back again) was a bit more challenging. In the end, I got a setup that runs quite smoothly and successfully offloads the workload from the CPU. Due to GPU readback latency, it takes ~1-2 frames for the flow field to finish baking, but I think that should be quite alright even for most fast-paced games.
One major problem I still haven’t solved is leveraging async compute. In theory, flow field generation should be completely decoupled from rendering, and therefore able to execute during idle GPU time. This is essentially “free” compute resources. But at time of writing, flow fields with high iteration count can make the application GPU-bound and reduce frame rate, at least on my machine. I have added an option for incremental dispatch as a workaround.
Performance:
It is difficult to create a meaningful benchmark that compares the compute shader implemenation to the .NET and DOTS implementations. Clearly, the compute shader implementation has much lower CPU impact, but the trade-off is that it consumes GPU resources and comes with a larger memory footprint and a bit of readback latency.
One interesting difference between the implementations is how terrain affects performance. With Dijkstra’s algorithm, each reachable cell is visited exactly once. So for 1 million reachable cells, the algorithm will run 1 million iterations. It does not matter how those 1 million cells are layed out.
With the compute shader implementation, however, each iteration propagates the wavefront in all non-blocked directions simultanously. Therefore, in the best case scenario, a 1000x1000 cell map only requires 500 iterations for the wavefront to finish propagating (that is, if the target is at the center and there are no obstacles). The number of iterations needed equals the longest distance from any cell to its nearest target.
This favors large open terrains over maze-like dungeons. And as a neat little bonus, adding multiple targets actually reduces iteration count further.
Potential Improvements:
There’s still plenty of room for optimization! In the future, I’d love to explore 3D topologies, arbitrary graph costs and some of the other use-cases described in the article mentioned at the start of the post like flee maps, range maps, exploration, hazards etc.
I’d love to hear your thoughts and any suggestions for improvements.
Cheers!