dave reid

blog

TIL: How DOOM Fire Works

I recently came across this excellent article by Fabien Sanglard which documents how DOOM originally created their fire effect. At the bottom of the article is a link to a working version of the code.

I had an idea where I wanted to port this into the terminal using Rust but it quickly became evident I wasn’t exactly sure how the algorithm was working. I have recently spent some time trying to wrap my head around it and I wanted to share back some thoughts on things that weren’t immediately obvious to me.

This post does assume that you have read through the original code.

At its core, the fire effect relies on a simple array (a.k.a framebuffer) covering the whole screen. Each value in the framebuffer is within [0, 36]. These values are associated with a palette where colors range from white to black, using yellow, orange, and red along the way. The idea is to model the fire particle’s temperature as it elevates and cools down.

Whilst I understood what this meant, it wasn’t until I saw the code that I understood how this was implemented exactly. What I found is that the palette array and firePixels array are working in tandem. The firePixels array (our framebuffer) holds a value for every pixel (or cell) in our grid and that value will be between 0 and 36 as those are the bounds of our palette array. We then use those values in the firePixels array as an index into our palette array to get the correct colour for a cell.

To give a simplified example, pretend that firePixels held a 3x3 grid as a one dimensional array and that we only had 3 palette colours as hex values. We could have something like this:

let palette = ["#070707", "#CF6F0F", "#FFF"];
let firePixels = [0, 0, 0, 1, 1, 1, 2, 2, 2];

When the rendering code eventually runs, it will loop over every value in the firePixels array, output its correct position in the grid and then get its colour by using its value as an index into the palette array.

Below is a snippet of the original code that handles this. You can assume canvas.height and canvas.width would both be set to 3 in our example.

for (var y = 0; y < canvas.height; y++) {
  for (var x = 0; x < canvas.width; x++) {
    var index = firePixels[y * canvas.width + x];
    var pixel = palette[index];

    // ...
  }
}

Visualised (with borders added for clarity), we would end up with something like this.

Spreading the fire

To make the actual effect of fire moving upwards, the code loops through the grid in columns and for each cell, takes note of its current value in the firePixels array, chooses a cell in the row above and then manipulates its colour to either match the value of the cell that is currently getting processed or decrements it by 1.

The following functions in the original code are responsible for this:

function spreadFire(src) {
  var pixel = firePixels[src];
  if (pixel == 0) {
    firePixels[src - FIRE_WIDTH] = 0;
  } else {
    var randIdx = Math.round(Math.random() * 3.0); // & 3;
    var dst = src - randIdx + 1;
    firePixels[dst - FIRE_WIDTH] = pixel - (randIdx & 1);
  }
}

function doFire() {
  for (x = 0; x < FIRE_WIDTH; x++) {
    for (y = 1; y < FIRE_HEIGHT; y++) {
      spreadFire(y * FIRE_WIDTH + x);
    }
  }
}

This might not make immediate sense, so hopefully a visual example will make it clearer. I’ll use a 5x5 grid with the bottom row of cells set to white to match the original articles setup.

The code loops through each column going cell by cell. I am going to skip over any black cells for now because the interesting fire spreading logic happens when we hit a non black cell:

The index of this cell is 20. When this is passed to the spreadFire function as its src parameter, the first thing the code does is look up this index in the firePixels array.

function spreadFire(src) {
  var pixel = firePixels[src]; 
  if (pixel == 0) {
    firePixels[src - FIRE_WIDTH] = 0;
  } else {
    var randIdx = Math.round(Math.random() * 3.0); // & 3;
    var dst = src - randIdx + 1;
    firePixels[dst - FIRE_WIDTH] = pixel - (randIdx & 1);
  }
}

What we will find is that this cell has a value of 36 as it has a white background. This means we are going to end up within the else block of the function:

function spreadFire(src) { 
  var pixel = firePixels[src]; 
  if (pixel == 0) {
    firePixels[src - FIRE_WIDTH] = 0;
  } else { 
    var randIdx = Math.round(Math.random() * 3.0); // & 3;
    var dst = src - randIdx + 1; 
    firePixels[dst - FIRE_WIDTH] = pixel - (randIdx & 1); 
  }
}

The purpose of this code is to randomly pick a cell in the row above the src cell that is either 2 to the left, 1 to the left, directly above or 1 to the right and update its value. If we were to visualise it, it would pick one of these marked with an “x”:

x
x
x
x

And then updates its value in the firePixels array to be the same or 1 less than the original cells value. Whether we decrement it or not depends on whether the variable randIdx is odd or even. There are 4 values that randIdx can be (0, 1, 2, 3) so there is a 50/50 chance. If the value is odd, we will decrement, if the value is even, we will use the exisiting value.

So let’s now pretend that the code has picked one of the cells above and adjusted its colour:

If we move to the next white square, the code could update the following cells:

x
x
x
x

So we could end up with:

The third column could be something like this:

The fourth column is where something slightly different happens. The first coloured cell the code hits isn’t actually the white cell on the bottom row. It’s the cell that got manipulated on the first iteration.

The same logic applies though. The code now just starts from this cell instead and has the potential of decrementing from 35. For example, the code can update the following cells:

x
x
x
x

Let’s assume the code is going to adjust the cell directly above our src cell. This means that randIdx must equal 1. So, as we know, odd numbers decrement, so its going to set this cells value to be 34.

And this is the point where we have to talk about the truthy side of the original if statement.

function spreadFire(src) { 
  var pixel = firePixels[src]; 
  if (pixel == 0) { 
    firePixels[src - FIRE_WIDTH] = 0; 
  } 
  else {
    var randIdx = Math.round(Math.random() * 3.0); // & 3;
    var dst = src - randIdx + 1;
    firePixels[dst - FIRE_WIDTH] = pixel - (randIdx & 1);
  }
}

The code is about to process a black cell which has a value of 0 in the firePixels array:

This means the if statement is going to set the cell directly above to also have a value of 0.

Effectively, knocking out its colour. The importance of this is for three reasons as far I can tell:

  1. If this didn’t happen, it would never create natural gaps within the flames as they are growing. This is because every coloured cell would usually be connected. By occasionally introducing black cells in-between colours, we help create the effect of the flames blowing in the wind and embers flying away which looks more natural.

  2. As we get to the top of the fire, flames need to die out and be cleaned off the screen. If the code didn’t adjust cells directly above already black cells, previously coloured cells would stay on the screen. This would create the wrong illusion as you would keep the outline of previous flames.

    To see what I mean, I have created this CodePen which should highlight the two issues above.

  3. It keeps the firePixel array values within the bounds of the palette array. If we adjusted the spreadFire function to remove the if statement, we would get:

    function spreadFire(src) {
  var pixel = firePixels[src];
  var randIdx = Math.round(Math.random() * 3.0);
  var dst = src - randIdx + 1;
  firePixels[dst - FIRE_WIDTH] = pixel - (randIdx & 1);
}

    And let’s assume the pixel variable had a value of 0. When the following line runs:

    function spreadFire(src) {
  var pixel = firePixels[src];
  var randIdx = Math.round(Math.random() * 3.0);
  var dst = src - randIdx + 1;
  firePixels[dst - FIRE_WIDTH] = pixel - (randIdx & 1); 
}

    If randIdx was equal to an odd number, it would try to decrement the pixel value from 0 to -1 and set this in our firePixels array. When the code then comes to index into the palette array using the firePixels value, it’s going to be out of bounds.

Going back to our visualisation, let’s pretend the code has gone and looped through the bottom white pixel in column 4 and also finished column 5. The grid may end up looking like this:

The code keeps repeating this process for each cell on every frame. As cells get closer to 0, they go through all of the palette fire colours and get increasingly closer to the background colour which gives the illusion of cooling off and this really is the core of the effect.

The source of fire

In the original setup, the bottom row of cells are set to white. As far as I can tell, this is for two reasons:

  1. It creates the illusion of having a white hot bottom to our fire
  2. It caps the highest value that the firePixels can be. This is important because as the flames move up the grid, the code decrements the value of firePixels from 36 to 0.

The code will always skip updating the bottom row

In the original code, the doFire() function starts its y loop with a value of 1. This actually skips over the first row but hopefully you can see why that is important.

We only ever manipulate cells on the row that is above the cell that is currently being processed. So the code needs to start at an offset of 1 so that it can change cells in the top row. This also has the side effect of leaving the bottom row white as we only ever work above it.

The flames favour the left

It always looked to me like the flames were moving slightly to the left and I do think this is true. If we look again at the cells that can be updated from a given cell, we can see that there are more cells to the left than the right.

x
x
x
x

This happens because we are choosing a random number between 0 and 3. If we were to drop this and choose a number between 0 and 2, the cells that could be updated would be as follows:

x
x
x

It gives us a more balanced appearance. The side effect of this though is that we have reduced the chance that a cells value will be decremented. This is because we have now reduced the chance of getting an odd number because we have taken 3 out of the mix.

Porting to Rust

I did eventually manage to get this going in the terminal using Rust. I used a library called Ratatui to help with the rendering. I also had to make a few tweaks to the code because I didn’t have enough cells within the terminal to get the visible cells down to 0. The flames would look like they are going off of the screen. To combat this, I increased the speed in which cells could reduce down from 36.

If you are interested, you can see the code over on Gitlab.

Finally, I have a minimal working version of Fabien’s version up on a CodePen. It removes the DOOM logo and keeps the fire going forever.

I’ve really enjoyed getting to grips with this code and it amazes me that something so simple can create such an incredible effect.

Until next time!