Finally, time to get to the good stuff :)
This article will go through what Flow Fields are and show a very basic implementation of them. Everything in here was learnt from Elijah Emersons article in Game AI Pro, Graham Penthenys article also in Game AI Pro and the Continuum Crowds Paper which also uses the technique. So a huge thank you to all of these people for doing the hard work. The Game AI Pro book is awesome and I wholeheartedly recommend buying it.
Flow Fields are a technique for efficient crowd pathfinding. They are most suitable for situations where you want to move a large group of agents to a common destination, something very common in RTS games. Flow fields are a steering behaviour, we’ll be using them to replace our fixed point seek behaviour so that our agents instead follow the flow field to their destination.
Let’s open up the rough Working Example.
In this example, red squares are impassable areas, the blue circle at the right is the destination, the numbers are the distance of that grid square to the destination and the blue lines are the flowfield vectors which represent the path to the exit.
As you can see, the agents roughly follow a fairly efficient path from their starting position to the exit. Sometimes they’ll overlap the inpassable areas (we have no physics to prevent this) and they’ll also move through each other (no physics and no flocking behaviours to prevent this). We’ll add these in in a future article!
Generating a Flow Field
A Flow Field is a grid where each grid square has a directional vector. This vector should be pointed in the direction of the most efficient way to get to the destination, while avoiding static obstacles.
There are many different techniques that can be used to generate a Flow Field, we are going to implement a minimal version and revisit it in a future article. Your terrain and design goals will influence how you generate your Flow Field.
We will reuse our dijkstra flood fill code from before, this generates the distance-to-destination numbers shown on the grid.
We then go through each grid square, look at all its neighbours (including diagonals), choose the one with the lowest distance-to-destination and set our grid square to have a vector in this direction. We do not set Vectors for impassable grid squares.
This gives a grid like follows:
You’ll notice that there are grid squares which don’t give the most efficient path (such as the 4 at the top right, it should be pointing directly at the destination), this happens as we only support straight lines and 45 degree diagonals. The Supreme Commander 2 implementation uses Line of Site tests to to the destination to provide better paths when nearby. We will also try and direct an agent on a diagonal between 2 impassable areas, which would not be passable.
With this grid in hand, we just need to create a new steering behaviour to follow it.
Following the flow field
To follow the Flow Field we will implement a steering behaviour that directs the agent in the direction of the grid square it is standing on. To smooth this vector we will use Bilinear Interpolation so we get influenced by the 4 grid squares we are nearest to, with the closest providing the most influence.
This steering behaviour can then be used to direct our agent as before. Easy as :)
Above I’ve described the minimal essential components of Flow Fields to get our agents moving to their destination following a relatively efficient path.
To use this in a real game, we’ll still need:
- Physics - To stop agents moving through impassable areas
- Flocking Behaviours - We probably want some degree of flocking behaviours so units don’t get too separated.
- Pre-emptive collision avoidance - In SupCom2 the units will avoid running in to each other when you run 2 groups at one another. The original Continuum Crowds paper talks about this, I’m not sure what was implemented for SupCom2
- Better Flow Field generation - Our Flow Field does not contain optimal paths. It needs to be improved to make more efficient paths
- Handle grid squares with some cost to traverse - Currently we assume all grid squares are impossible to cross or free
- Flow Field Tiling - Generating a Flow Field for an entire game map will probably be too big to fit in memory, this is another technique used in Supreme Commander 2 and Planetary Annihilation to reduce memory usage and generation time