INTRO

A few years ago, I got the opportunity to architect and code the fire propagation system in Far Cry 2.  At that time,  it was a gigantic task and it scared the hell out of me. Luckily, it turned out well enough.

With the upcoming Far Cry 3, several people recently asked me how the system worked. I realized that I never took the time to write it down. So, before I forget and also because it might be useful to somebody out there, here’s a high level overview of its inner workings.  Pretty programmer art included as a bonus.

Disclaimer: Although Far Cry 3 uses the same system I wrote, I was not involved in the project. They may or may not have changed / adapted or modified the algorithms. What I describe below is accurate for Far Cry 2.

BASE STRUCTURE

At the core, the fire propagation system is quite simple. Since gameplay is what’s important, we sacrifice some of the realism for fun. The fire propagation in Far Cry 2  (and Far Cry 3) has just enough realism to maintain the player’s suspension of disbelief, but certainly not enough to get published anytime soon. Because I like to keep things simple, it doesn’t involve any complicated mathematics, physics or fluid dynamics. That has the additional advantage to be fast to simulate and easy to understand.

The secret sauce is an equally spaced grid. It is true for grass, for objects as well as for trees. The only difference is that we use a 2D grid for grass and a 3D grid for objects and trees.

Each cell of the grid has a position in the world, a radius and hitpoints. The cells have a plethora of properties, but these three are the bare minimum to propagate fire.

LIGHT MY FIRE! HOW TO START ONE?

The game engine tracks all damage done in the game, might it be bullet shots, impacts or fire damage. When a game entity is damaged, it is notified by an event. The damage event includes how much damage was done, what kind it was and what caused it.  If the kind of damage was fire based and the entity is flammable, then at least two things happen:

• Firstly, the fire grid is dynamically created for the damaged entity. We create them dynamically because we don’t want those grids to exist in the wild for no reasons. That would take memory, disk space, etc, so we create them as we go. But, once created, it remains as long as the game entity exists.

• Secondly, we figure out which cell in the grid is closest to the damage source. That cell then takes the damage and its hitpoints are reduced accordingly.

That’s where things get interesting – When a cell has been damaged by fire and has lost all its hitpoints; it catches fire.

While burning, the cell becomes a damager itself. It deals damage to its neighbour cells on the grid; cells that share an edge with it. By doing so, it reduces their hitpoints and when in turns these cells have lost all their hitpoints, they catch fire. That’s how the propagation is created.

Lastly, a cell from the grid as a finite lifetime. Otherwise, it would burn forever. It can be seen as the amount of energy given by the material that is burning.  For instance, a piece of paper would most likely burn faster than a wood log, so it would be given a shorter lifetime value.

That’s it. A fully functional fire propagation system good enough for a AAA game!

TECHNICALITIES

Simulate wet jungle VS dry patch of grass
How to simulate a wet jungle versus a dry patch of grass? They behave differently. Quite easily!
Increase the fire cell’s hitpoints and it’s difficult to set it on fire and it’s slow to propagate. Decrease its burning lifetime and the fire dies out quickly. There, you just simulated a wet jungle environment.

How to create the propagation grids

Grass / Land
For grass wildfire,  an axis-aligned 2D grid is built in realtime and projected on a 3D terrain. For each of the cell, we take care to determine if the cell position is underwater, or under an object such as a rock or a building. In which case, we disable that cell and it can no longer catch fire. We wouldn’t want to have fire propagating under rock, would we?

Objects
For objects, it’s a little bit more complicated. First, we create an AABB that entirely surrounds the object.  Second, we somehow need to detect the shape of that object. After all, it could be a chair, an oil barrel or a whole house for all we know. To accomplish that, the  bounding box is divided in equally spaced cubes. The size of each cube depends of the object size, the number of fire emitter we want to have, performance, memory, etc.

An iterative algorithm then go through all those cubes and test their location against the collision shape of the object. If the test return a positive result, this cube is kept, otherwise it is discarded. At the end, we have a collection of cubes that approximately represent the shape of the object to be burned. That’s our propagation grid.

WIND EFFECT

The wind is an important disruptive factor for a wildfire and it adds a great layer of realism for the player.  Here it could be tempting to over-think the design and go with a very complicated system. After all, it’s an active area of research and several papers on the subject are available online.

Luckily, with what have been explained thus far, it’s quite easy to simulate if we accept to cut corners a bit.

In our system, the fire propagates by damaging the neighbor cells on a grid. And it is generally accepted that a fire should spread faster in the direction of the wind than against the wind? Then, with that in mind, we can create a rule where a burning cell deals more damage to its neighbor cells if that neighbor is in the direction of the wind.

We do that by getting the dot product between the wind direction vector and the direction of the neighbor cell to damage. If the result is greater than zero, then that node is dealt greater damage.  Likewise, if the result is negative,  the node is against the wind and should be dealt less damage. To be fancy, the amount of damage is interpolated with the dot product result as shown in the picture below.

With that rule alone, you will get a nice bell shaped fire front that propagates in the direction of the wind. Simple, yet believable enough to get the player’s stamp of approval.

It’s worth noting that we simulate gravity the exact same way.

PROPAGATING TO THINGS AROUND AND CHAIN REACTIONS

When a cell burns, it sends a “I’m on fire and I burn this much in this radius” message down the game event pipeline. This event is caught by objects, AI and other game systems that are in that area. They react to this message their own specific ways. The AI freaks out, the flammable objects get damaged and eventually catch fire. And,  it is also true for dynamic objects.  For example, if a burning oil barrel goes flying through the map, every step of the way,  it will send that “i’m burning” message and a lot of things around might hear it.

This causes a chain reaction effect where trees, explosive items,  objects and patches of grass set each others on fire.  It’s completely systemic and it makes it much more believable. It  also scores pretty high on the player’s fun meter because it behaves as one would expect, yet as real fire, it sometimes gets totally out of control.

OPTIMISATION

The Hair Transplant Strategy

In an ideal world, we would have access to enough memory to hold an infinite number of particle emitters and we could display an infinite number of particles on screen. Unfortunately, the reality is that those numbers are actually pretty low.

To do more with less, we have to put our emitters where it really counts. Enters the hair transplant strategy!  In Far Cry 2, the fire emitters are constantly being teleported around, most importantly, from the back of the camera to the front. The player’s point of view is monitored at all time and emitters that are burning out of sight are moved to a better location where they are also needed.

In addition, the emitters’s density is higher in close proximity of the player and lower as the distance increases. A kind of fire LOD if you will. If things are getting bad and we still need more emitters but none are available, we increase the particle sizes to give them more volume and fill more space on screen.

With this strategy, and some others, we can simulate a wildfire that is several meters wide with a relatively low number of particle emitters.

Event Pipeline
Since the described system tried to avoid all complicated maths, generally speaking we will be GPU bound before being CPU bound.

That being said, the event pipeline could be a bottleneck. It works well when you have just a few cells on fire. But, it’s another story when you have thousands of them burning and advertising their state to the world. That will likely clog your CPU’s arteries.

The trick for me was to regroup the cells that were burning into AABB groups. These groups would constantly merge, split and change shape to follow the evolution of the fire. The events would then be sent per AABB instead of per cell, which saves a significant amount of processing power. Additionally, the events would be spread out across several frames in order to distribute the load and avoid framerate spikes.

Keeping things under control.
In your game, if you don’t constrain the propagation somehow, it will either

• Burn the entire map and kill all the NPCs
• Fill out the memory with thousands of fire grids and particle emitters.
• Choke the framerate to death
• All of the above

There are many ways to approach this problem and mine is not necessarily the best. Once again,  I tried to find the easiest and simplest solution.

I designed a closed loop system where you feed the fire with spreading points and it consumes them to propagate. Here’s an example. The player throws a Molotov into a dry patch of grass. The Molotov gives,say, 60 spreading points to the patch of grass. The fire, by consuming the grass, requires 8 spreading point for each fire cell of the grid. Thus, the fire could propagate on 7 cells before dying. If the player throws 2 Molotov instead of one, it generates more heat, more energy, it gives 120 spreading points to the patch of grass. That much points gives it enough energy to consumes 15 fire cell. It will then spread farther.

It’s not perfect, but it behaves realistically enough to entertain the player, while keeping the developer sane and within her budget.

WRAP UP

That completes the high level overview of the fire propagation system in Far Cry.  I know it sounds cliché, but I feel I just scratched the surface. I didn’t talk about the particle emitters, which alone would be worth an entire blog post.  Also you might find that this system behaves well alone in a vacuum state,  but it’s something else when you put it out there in the world. Suddenly, it’s got to play nice with all these other components that make a game. It brings its share of challenges.

If you reached this point, thanks for reading.  I hope you found the information useful and that you’ll use it to build something even bigger! If so, let me know.

Have fun and happy coding!

-jf

Credits:
Header Image -> http://pcgamer.com/
Rock clipart -> http://clipart-for-free.blogspot.ca/2009/01/rock-clipart.html
Flame clipart -> http://sweetclipart.com/red-and-yellow-fire-logo-408