flowfield – jdxdev

Since Unity’s data-orientated tech stack (DOTS) appeared there have been quite a few tech demos testing it out. Writing flowfield implementations seems to have recently become popular in the niche crowd of early adopter Unity game tech enthusiasts. Flowfields were first used in games such as Supreme Command 2 and then later Planetary Annihilation. They make sense when you have very large numbers of agents path-finding. The initial cost for a single agent is going to be higher than using something like a NavMesh but as you get into the hundreds or thousands of agents they may scale better.

For an RTS pathfinding prototype I initially used Unity’s built in NavMesh with the hybrid-DOTs navmesh query API. It was very fast for path queries but struggled performance wise when updating the NavMesh with dynamic obstacles. When weighing up the pros/cons of various methods I thought flowfields could be well suited since my problem-case involves large numbers of units. The grid data-structure inherent with flowfields can also be useful for storing other map information such as additional movement costs, heights, island IDs (an island is a single isolated area of the the grid that can’t path to another island). The grid data structure is also quite quick to look-up information in. Finally, for an RTS style project, pathfinding is one of the most critical bits of tech and having full control & understanding over it with no blackboxes was desirable (which wasn’t the case with using Unitys out-of-the-box implementation) and I had some ambitious highly specific goals that I wasn’t sure would be accommodated by Unitys built-in solution.

Making a basic dijkstra flowfield is one thing but a robust RTS game can be a lot more involved, and may require a fair few additional items such as:

Flowfield tiles
Hierarchical A* or some other high level pathing between tile portals
Caching of paths & flowfield tiles
Eikonal solver for smoother cost field generation
Greater than 8 directions for each cell for smoother movement
Line of sight (LOS) flags for smoother movement
Parallelised generation of paths and flowfields

There’s lots of media on the internet of people doing a basic implementation but it’s hard to find many that are using it in more complex situations such as an RTS game. The basics of flowfields are already well explained in numerous blogs and youtube videos such as this great one at HowToRTS https://howtorts.github.io/2014/01/04/basic-flow-fields.html. Although I might touch on some basics below, in general the rest of this post will assume a knowledge of basic flowfields. The following is more a collection of notes & workings I collected recently whilst trying to implement flowfields in a prototype RTS, rather than a robust tutorial.

Dijkstra vs Eikonal cost spread

The Dijkstra flood filling algorithm is used to expand the cells of the flowfield. Given a starting cell, the path goal, it will spread to all valid neighbour cells.

Flowfield spread visualised with different iteration counts. Cost increases as colour changes outwards from centre.

Whilst running the Dijkstra algorithm you can calculate cost in a basic way by simply incrementally increasing as it spreads (like image 2 below), however, this can lead to diamond like patterns forming in the cost field. This may in turn lead to slightly geometric looking path movement.

Image 2. Dijkstra cost field with a very low cost colour wavelength, basically the colour changes more frequently as the cost changes. This can help to see cost-spread patterns better.

Smoother cost spread can be generated by using using an Eikonal solver as shown in image 3. This can lead to more optimal paths, especially if there are up to 16 possible directions per a cell available.

Image 3. Eikonal equation generating a smoother more spherical cost field.

A sample Eikonal equation implementation is available here: https://github.com/SCIInstitute/StructuredEikonal/blob/master/src/cuda_fim_kernel.cu

Flowfield Tiles

To create flowfields across the entire map area would be very costly so an initial optimisation is to only generate the flowfield across a high-level (or hierarchical) path. To accomplish this the map is divided up into tiles. Flowfields will be generated for the tiles that are on the hierarchical path. After some basic optimisation a single 50*50 flowfield area generates in ~0.3ms. The map itself is ten times this size. The map is represented by a 500*500 grid, which is divided into 100 50*50 tiles.

The underlying map grid. Green cells are passable, red cells are obstacles.

When a path is required, hierarchical A* is run through tile portals (explained more below). The result of this is a list of tiles that the path runs through. Flowfields are requested for these tiles and the units read the direction value on their cell to get to the destination.

Each of these map tiles has portals along the edges that act as hierarchical A* path nodes. These portal nodes are generated at initialisation or even offline entirely and loaded from disk. A better description of the portals is explained by Eiljah who did the SupCom2 pathfinding here: http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter23_Crowd_Pathfinding_and_Steering_Using_Flow_Field_Tiles.pdf

A map tile with portal cells in pink and paths in green between the portals. The length of these paths is the cost of the edge in the hierarchical A* graph.

Green lines visualising the hierarchical graph edges

Other tips

Debug visualisation is very important obviously with this sort of work. It’s really worth putting some time in here to have a robust visualisation system to keep you sane & discover bugs quickly.

Using a branchless math.select in GetNeighbours to replace if branches gave a crazy 10* speed-up compared to the if else branching I was doing previously. Although this will vary on the compiler it’s probably worth giving some serious consideration to, profiling before & after.

eg. here is a snippet of the branching version of some code to find neighbour indices on a grid:

if (x > 0)
{
	int neighbourIndex = ((x - 1) + (gridWidth * z));
	neighbours [neighboursCount ++] = neighbourIndex;
	
	if (z > 0)
	{
		neighbourIndex = ((x - 1) + (z - 1) * gridWidth);
		neighbours [neighboursCount ++] = neighbourIndex;
	}

	if (z < (gridHeight - 1))
	{
		neighbourIndex = ((x - 1) + (z + 1) * gridWidth);
		neighbours [neighboursCount ++] = neighbourIndex;
	}
}

And the branchless version:

bool leftValid  = (x > 0);
bool rightValid = (x < (gridWidth - 1));
bool upValid    = (z < (gridHeight - 1));
bool downValid  = (z > 0);

neighbours [neighboursCount] = math.select (neighbours [neighboursCount], (x - 1) + (gridWidth * z), leftValid );
neighboursCount = math.select (neighboursCount, neighboursCount + 1, leftValid );

neighbours [neighboursCount] = math.select (neighbours [neighboursCount], (x - 1) + (z - 1) * gridWidth, leftValid && downValid );
neighboursCount = math.select (neighboursCount, neighboursCount + 1, leftValid && downValid );

neighbours [neighboursCount] = math.select (neighbours [neighboursCount], ((x - 1) + (z + 1) * gridWidth), leftValid && upValid );
neighboursCount = math.select (neighboursCount, neighboursCount + 1, leftValid && upValid );

Making sure to access large grid/tile based arrays in a cache aware way was very important. eg. if you are iterating over large arrays (such as flowfield tile data) make sure you are going in the right column/row major direction to avoid jumping about in memory, or just use 1 rather than 2 dimension loop statements. This was another thing I got wrong first but fixed after profiling and checking the code.

Writing the flowfield implementation started with the need to have more control over the pathfinding implementation but it ended up being a decent revision for writing faster data-orientated code.

Closing Notes – movement behaviours

Having got reasonably well optimised and usable flowfields working I soon found out I was still someway from having large group movement work without any issues. A single unit could get to its destination fine. A small group was ok. But when 100 or so units all had to move around a corner to a common destination they tended to cluster quickly and end up forming into a single/double file line, like a line of ants. This was not what I had in mind. My original goal was to achieve something like Starcraft2 which has with a very smooth & responsive level of control for group movement. Specifically, when going around a corner, I wanted the group to move around a centralised centre as one, more or less maintaining relative offsets to each other. A lot of this would be dramatically helped by adding some boids style localised forces. However, even after some initial work in that area I couldn’t quite get it to fix the problem entirely with large groups of units when using flowfields.

Formations forces applied in addition to the flowfield are a potential idea to solve this problem, but I’ve not been able to get this to work yet in practice. The group movement just didn’t look well suited to the situation. Although it could be more appropriate when trying to model an actual swarm of insects or liquid like things. I might revisit flowfields for swarm style units or multiple goal based paths (such as close combat fighting with groups) in the future.

I shelved the flowfield work whilst keeping it as an option to switch back to if required and started on a new approach. I went back to using a more traditional pathing solution involving waypoints at path corners which you can then apply offsets to and assign individual positions per unit. This method would also need a lot of boid forces interplay but the path destinations would hopefully be more precise at least.

Resisting the urge to go back to Unity NavMesh and its slow rebuild/update times, I started using my existing ‘NavGrid’ with plain old grid based A* searches. Although the path search cost for a grid is higher than I’d expect from a good NavMesh implementation the insertion or rebuild time for a grid based graph is trivial, and I had ambitious ideas that involved regular updates of the graph. I tweaked the heuristics and added a tie-breaker http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html to improve the efficiency. Then I calculated the path ‘corners’ or waypoints along the path.

The path corner positions could then be used to calculate position offsets of varying length depending on the group size allowing for better formation movement.

This will be continued in RTS pathfinding part 2.

Tag: flowfield

RTS Pathfinding 1 – Flowfields

Dijkstra vs Eikonal cost spread

Flowfield Tiles

Other tips

Closing Notes – movement behaviours