Hive Assault: Computational Fluid Dynamics

Approximating Gas Flow in a Real-Time Environment
Information on the implementation of a CFD engine fast enough for 3d gaming
Scott Schaefer, 2001. Email:

The fluid dynamics done in the game is very simple. We make the assumption that we have a perfect, linear flow. This means that it cannot have really interesting behavior like eddies. In reality, this would never happen, however, we must make sacrifices in order to achieve real-time performance. More specifically, we will model the flow as the gradient of a scalar field. It's the scalar field that we'll actually model and approximate its derivative when the flow at a certain point is needed.

We'll model the flow by doing an iterative update in with the mask 1-w for the center coefficient and w/n for the n neighbors of this cell. "w" is a coefficient that should be time and grid space dependent and determines how quickly flow can move over some interval in both space and time. In order for the system to converge we require that "w" is greater than 0 and less than 1. So if N is the set of all neighbors of some node x, then the update equation is now

Flow[x]=(1-w)*Flow[x]+Sum[w*Flow[n]/|N|, n is an element of N]+b[x]/|N|

In this equation "Flow" is the scalar value at the index specified, "w" and "n" have previously been defined and "b" is the correction term. The correction term is the value of the emission for that grid square. For most squares, this will be 0. However, for sources, this value will be positive and it will be negative for sinks. In order for the system to converge, we require that the sum of all of the sources and sinks is 0 i.e. b.1=0 where 1 is the vector of all 1's. At each iteration the entire scalar field is recalculated based on the old scalar field.

To determine the flow at a given grid point we'll calculate the flow at the boundaries of the grid square that contains the point in question and use linear interpolation across each dimension to determine the flow at the given point. To determine the flow at a boundary of the grid square we'll just take the scalar value of the adjacent square and the square in question and subtract them in the axis-aligned direction. In one dimension we'd find the value of the flow on both sides of a square by

right = Flow[x+1]-Flow[x]
left = Flow[x]-Flow[x-1]

We can then interpolate the two values across the square to the desired point. This is only one dimension and needs to be repeated for all dimensions involved (three in the game).


Walls can be incorporated very easily into this model. Essentially, we remove the neighbor from a square if there exists a wall between the two squares. To calculate the flow we use the value 0 for the flow across adjacent squares if there is a wall between them. This has the property that there is no normal flow along walls.

Making It Run Fast

There is still the question of how to implement it so that it runs quickly. Checking for walls for every grid square on each iteration is not the way to make it fast. We implemented a small table of masks that was indexed by the wall configuration. There are a small number of possible wall configurations for a given square. If all of the coefficients for all of the neighbors and the square in question are kept in a table indexed by the wall configuration, then those coefficients can just be multiplied by the respective members without any if-statements. If there is a wall between two squares, then the coefficient of the other square becomes 0. Extraneous numerical operations are performed, but no branches occur.