Flame Simulation in 2D

Wyatt Sheffield

I am a fan of useless terminal commands. Cowsay, Figlet, and pipes.sh have all brought me hours of joy. But I had always dreamed of having my own fireplace in the terminal to keep me warm during those cold late-night coding sessions. Sure, I had tried a few (aafire comes to mind), but none of them ever really suited me. They all had their own problems - opening in a new window, no color, lame effect, etc. Finally, I could bear it no longer; It had been a while since I had given myself a frivolous challenge, and my cold terminal had nearly given me frostbite. There was but one option: I would build my very own fireplace. And to make it a real challenge, I would do it without any googling.

The Design

Setting out to design a flame simulation in a terminal, my immediate thought was that a convincing effect could be achieved using cellular automata, and indeed this approach proved to be effective. The rationale behind this decision was twofold: the terminal is a grid and the Navier-Stokes equations are hard.

I began by laying down some rules for how fire behaves.

The first two items on the list are fairly trivial, but creating a convincingly random flickering effect took the bulk of my mental effort for this project.

My initial idea was to put a heat source (a 1d array of cells) at the bottom of the screen and have it change randomly each frame. Of course, flames are not completely random. A flame will not ignite one moment and extinguish completely the next, nor will it jump from place to place, appearing to teleport. Clearly, a more nuanced solution was needed, and in sticking with the theme of cellular automata, I came to settle on using Wolfram’s Elementary Cellular Automata to get the job done.

Rise of the Automaton

Elementary cellular automata (from here on referred to as ECA) are known for producing complex patterns from unbelievably simple rules. In his book, A New Kind of Science, Wolfram classified ECA into four types:

  1. Nearly all initial patterns evolve quickly into a stable, homogeneous state. Any randomness in the initial pattern disappears.
  2. Nearly all initial patterns evolve quickly into stable or oscillating structures. Some of the randomness in the initial pattern may filter out, but some remains. Local changes to the initial pattern tend to remain local.
  3. Nearly all initial patterns evolve in a pseudo-random or chaotic manner. Any stable structures that appear are quickly destroyed by the surrounding noise. Local changes to the initial pattern tend to spread indefinitely.
  4. Nearly all initial patterns evolve into structures that interact in complex and interesting ways, with the formation of local structures that are able to survive for long periods of time.

For this application, I was interested in class 3 ECA, but in sticking to my no google rule, not only did I not know that what I was looking for was a class 3 automaton, I had no idea which of the 256 rules would produce the desired behavior. The only option was to try them all. I wrote a quick program to iterate through about two hundred generations of a given rule and print the results to stdout. I then wrote a bash script to iterate from rule 0 to 255 and pipe the output to a file. Then, using less, I paged through each output and made note of the more promising looking patterns to test later.

I wrote the following function to calculate the next generation of an ECA given the current generation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
 
void wolfram(int* world, const int rule)
{
    int* next = new int[WIDTH];
    int l,c,r;
    int lidx, ridx;
    int current;
    for (int i = 0; i < WIDTH; i++) {
        lidx = i > 0 ? i - 1 : WIDTH - 1;
        ridx = (i + 1) % WIDTH;
        l = world[lidx];
        c = world[i];
        r = world[ridx];
        current = (l<<2) | (c<<1) | r;
        next[i] = (rule>>current) & 0b1;
    }

    for (int i = 0; i < WIDTH; i++) {
        world[i] = next[i];
    }
    delete[] next;
}

The array next holds the result, l, c, and r hold the value of the cell to the left of the current cell, the value of the current cell, and the value to the right of the current cell, respectively. WIDTH is a global variable giving the width/length of the tape of cells.

Within the loop, lidx and ridx are checked to see if they are within [0, WIDTH). If they are not, they wrap around to the opposite end of the tape, creating a ring of cells as opposed to just a line (this is important later). Next, we simply get the values for l, c, and r.

Now for the evil bitwise arithmetic. Let us imagine an arbitrary tape with the positions of l, c, and r marked. We will use rule 60 in this example.

So we have, in binary notation,

l = 1, c = 1, r = 0

we then shift the bits to the left, per line 12, giving

l = 100 c = 10 r = 0

and finally, OR-ing these values together yields

current = 110 = 6 (base 10).

Line 13 is perhaps the most important and the most tricky. We take the number 1 and shift it left current (in this case current = 6) places 1 << 6 = 01000000 This shifted value is then bitwise-ANDed with the rule, in our case 60 (00111100)

1
2
3
4
 
  01000000
&&00111100
----------
  00000000

Since 0 is not greater than 0; the value of this cell in the next generation will be a 0.

Once I had the ECA-powered heater down, I figured I was done with that portion of the fireplace, but the effect still wasn’t just right™. After some thought, it became clear to me that the new problem was similar to the old problem: although rule 60 “smooths out” the randomness, it can still have sudden spikes from hot to cold. The solution, then was to have the ECA heater warm up a secondary array of cells (the hotplate, which cool down slowly over time. In my implementation, if cell i of the ECA heater has a value of 1 at time step 0, it will instantaneously add heat to cell i. If at the next time step, cell i of the heater has a value of zero, the hotplate’s temperature at cell i will decrease by one half. At last, this arrangement produced a convincing effect.

Cooling Off

With a working heater in place, I then had to make a convincing flame. Flames point up[citation needed], and they get cooler the further they are from the heat source. To tackle the cooling, and add a bit more randomness, I wrote this rather simple function:

1
2
3
4
5
6
 
int cooldown(int heat) {
    if (heat == 0) return 0;
    int r = (rand() % (heat));
    if (r == 0) heat--;
    return heat;
}

Essentially, if the heat of a cell is 10, there is a ⅒ chance that the temperature will decrease on the next frame. Likewise, a cell with temperature 5 has a ⅕ chance of cooling off. That is the cooler a cell gets, the more quickly it cools down.