This Blog post talks about several fluid simulation methods-often called Computational Fluid Dynamics (CFD)--that exist today and examines the advantages and problems I encountered with each method while trying to make a game in a single month.
For my October game I had to simulate fluids flowing around in a more-or-less realistic manner. In addition, the fluid was to have a significant effect on actual gameplay and not just be a whiz-bang special effect. To achieve this I had to write up a computer simulation that would be easy to integrate with actual game logic.
I thought setting up the CFD simulation would be fast and easy, but I took two weeks (out of an allotted month) trying out several CFD methods to see how appropriate they would be for making game.
There were several things I was looking for specifically for my October game and my discussion of the various simulation methods is heavily influenced by these requirements. If you're making a different kind of game on a different schedule, you won't come to the same conclusions as I do here and will probably choose a different method for your fluid simulation.
The requirements are:
- The fidelity has to be "good enough."
- Simulation has to run pretty fast on a single CPU core.
- It's easy to examine and manipulate fluid flow.
- It's easy to tweak simulation parameters.
In more detail:
The fidelity has to be "good enough." The simulation certainly doesn't have to be super-accurate. I'm not designing jet turbines with this software or anything. However, it has to be realistic enough so that someone looking at it would think it's a fluid and interact with it as if it were a real fluid. As a kid most of us have seen swirling eddies in a running stream; the simulation just has to be accurate enough so that we can use that experience to guide our choices in the game.
Simulation has to run pretty fast on a single CPU core. There are all sorts of CFD methods that use multithreading or GPU processing to achieve ludicrous speeds. Since I'm making a game that is distributed to many platforms, there's no guarantee that I have access to multiple cores. Also, getting any code to run at all is already pushing my time constraints; getting it run on multiple cores or on the GPU could easily use up the rest of my allotted month if something goes wrong. If I was writing a fancy new game engine I would certainly use these more advanced programming options, but here I just needed something up and running so that I could get on with the actual game.
It's easy to examine manipulate fluid flow. By this I mean it should be fairly easy to add things like walls and fluid "pumps" to change the fluid flow. In fact, I might need to add an arbitrary number of this things. Also, I need to be able to find the current velocity and density (if applicable) at any point in the flow. Again, I might need to get these values at quite a few places in the simulation.
Easy to tweak simulation parameters. It turned out that changing the fluid properties has a dramatic effect on the actual gameplay, so I need to be able to change how the fluid flows by modifying one or two values. In many CFD methods I can quickly modify the weight (or density) and viscosity of the liquid, which is ideal. If I have to fiddle around with other obscure parameters, I can waste a lot of time stumbling around trying various changes to get the fluid to work just right. In contrast, I know that upping the viscosity makes the fluid more "goopy" in an intuitive way, so modifying viscosity is probably the easiest way to get the effect that I want.
You can sort of divide the simulation methods into grid-based and particle-based methods. These methods are also referred to as Eulerian and Lagrangian methods respectively.
First I'm going to talk about some particle-based methods I looked at. Specifically this includes Smoothed-Particle Hydrodynamics (SPH), Stochastic Rotation Dynamics (SRD) and Vorton Simulators. All three methods simulate the "fluid" as a large collection of particles and update particle properties like velocity, spin, etc. over time.
SPH is basically a particle simulation where the particles are smeared out to represent a continuous medium like water or some other fluid, and finding the velocity/pressure/etc. at any point is done by combining weighted values of nearby particles. You use these derived values to apply forces to the particles and update their individual velocities.
SRD again takes a bunch of particles flying around with specific velocities, but instead of interacting via a derived field, you basically grab groups of particles (typically grouped into cells on a square grid) and randomly modify the whole group. Over time the random bits cancel out and you are left with the same result as if you had solved actual fluid equations.
Vorton Simulators use particles, but instead of representing bit of fluid with velocity, vorton represent vorticity, or spin. In many other respects they are like SPH but by tracking vorticity you can easily produce cool-looking swirly bits of smoke and fog.
The main advantage of particle-based methdods is (IMHO) that you only need to do computation in areas where interesting fluid flow is actually happening. In a really big game world, you can't afford to simulate the air flow of every cubic inch of space. With particle-based methods you can kind of "spray" particles in the areas that are important, and simply ignore the rest of the space.
In my case, however, the game space was not particularly big: everything happens in a fairly well-contained area slightly smaller than the screen size. In addition, I wanted to allow the player to create fluid flows anywhere and have them work naturally, which meant I would either have to spray particles wherever the player interacted or (more likely) just try to keep a more-or-less uniform distribution of particles over the entire area.Getting such a simulation working is certainly possible, but I was pretty sure it would require some fiddling time which would eat into my already short 30-day timespan.
Field-based methods (Eulerian) typically divide up the continuous fields (velocity, pressure, etc.) into a grid or array of values. Often this grid is uniform but it can be irregular and have multiple levels in more advanced simulations. There are about a million grid-based fluid solution to the Navier-Stokes equation, but the two I examined were Jos Stam's hybrid fluid flow and the Lattice Boltzmann Method (LBM).
Stam's method is interesting since it is sort of a hybrid combining Eulerian and Lagrangian methods: the fluid values are stored in a grid and diffusion is done via grid neighbors, but the advection part of Navier-Stokes is done by moving bits of fluid around the grid as if they were particles. Among other things, this allows particles to move quite fast, faster than a single grid cell per timestep.
I keyed into the Lattice Boltzmann Method mostly due to this video which showed a 2D fluid simulation using roughly a page of Python code. Copying it into equivalent C# code was pretty simple, and as long as I kept the resolution fairly small (I settled on a 96x64) it run well on the computers I had around the house.
The main drawback in using a Eulerian method like LBM is that of instability. Simulatoin instability is the bane of numerical computation, since one small error balloons into infinity. Your boxes go shooting into space, cars spin out of control, and your fancy water spiral dissolves into a field of white noise. Argh! In our case, stability requirements mean that the timestep has to be relatively small, so having fluid "stuff" flying around the screen at high speeds isn't an option. Stam's method gets around this by using a particle-like update for the advection step. However, for vanilla LBM this is a pretty heavy constraint.
In my case the LBM implementation was so easy to write and use (except for boundary conditions, argh!) that I decided to just accept the timestep constraint and accept that my fluids would flow around somewhat sluggishly. It was going to be a puzzle game so everything would tend to happen quite slowly in the game anyway. In the end, you can get what appears to be quite fast fluid flow but it still takes several seconds for this "fast" flow to cross from one end of the screen to the other.
In the end I use the Lattice Boltzmann method and it turned out pretty well. If I had more time for fiddling and debugging I probably would have ended up using SPH or SRD since they don't have the stability problems of LBM and would allow me to work in a larger space for future games. In the end, you have to choose the fluid method that fits well with the kind of game you are trying to make. And while there are some turnkey fluid solution out there, in many cases you may have to write up a simulator yourself in order to get the features and speed that you need.
Want to use fluid simulation in your game? Here are some articles to read:
Fluid Simulation for Video Games by Dr. Michael J. Gourlay is a comprehensive examination of fluid dynamics simulations that are "good enough" for games. In most cases the actual physical models are examined, derived, and then implemented in working code. Both SPH and Vorton simulators are examined, with lots of C++ code designed to run fast and efficiently. If you have a good background in numerical computation and general physics you can quickly get up to speed by plowing through the dozen-plus parts of this series.
Alternate approaches to fluid dynamics on GPU is an article by Urban Hermit Games shows the SRD method using GPU shaders. UHG clued me into the SRD method which has good stability properties and is easy to implement.
Real-Time Fluid Dynamics for Games is one of Jos Stam's early fluid simulation articles, which is the original source for many smoke and water simulators in games. There are code snippets but no full source; however, you can probably find a complete implementation to suit your needs by looking around in the internets.