# Flame Simulation in 2D

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.

- Heat rises
- Temperature drops the further away you are from the heat source
- Flames are stochastic - they should have an element of randomness

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:

- Nearly all initial patterns evolve quickly into a stable, homogeneous state. Any randomness in the initial pattern disappears.
- 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.
- 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.
- 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:

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

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 01000000
2&&00111100
3----------
4 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:

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

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.