Scrapped header animations: Cellular Automata

While working on the homepage header animations for this website, I explored and worked on many ideas; not all of them made it to the header for one reason or another, but I had fun implementing them and felt like telling their tale anyway. Here's the one about cellular automata.

...Cellular Automata?

──────────────────────────────────────────────────────────────────────────────────────────

As soon as I began brainstorming for simple yet beautiful animations, cellular automata came immediately to my mind: they're easy to render (you just need black and white cells) so a type character version seemed feasible, and even though the instructions are very simple, they can produce beautiful and complex patterns.

If you don't know what CA are and don't want to read the Wikipedia article, they're basically grids in which the cells can be empty or filled, and the state of a single cell depends on rules tied to the three cells just above it. An example of rule: if the three cells are empty-empty-filled (001), the new one will be filled (1).

-------------
| 0 | 0 | 1 |
-------------
    | 1 |
    -----

These rules are totally arbitrary, and if you know a little about combinatorics, you know that 3 cells with 2 possible states can have 2^3 combinations, so we only need 8 rules to exahust all the possibilities, and there are 2^8 possible sets of rules. Anyway, after a brief research, I decided to go with rule 90.

Let's put it into code

──────────────────────────────────────────────────────────────────────────────────────────

Rule 90 is very simple to explain, and even simpler to codify: if the cell above to the northwest of the current one has the same state of the one to the northeast, leave it empty, otherwise fill it (the middle one just above the current can be ignored). In boolean terms, it's an exclusive or(XOR): either one or the other, but not both. In JavaScript, the bitwise XOR operator is represented by the ^ symbol, here are a few basic examples:

0 ^ 1 // 1
1 ^ 1 // 0
0 ^ 0 // 0
undefined ^ 1 // 1
undefined ^ 0 // 0
undefined ^ undefined // 0

So supposing that the previous state of the cellular automaton is encoded in an array of 0(empty) and 1(filled), the n-th position of the array containing the next state is just next[n] = prev[n - 1] ^ prev[n + 1]. Anyone who's ever worked with arrays will immediately notice a problem in the edge cases: in the first and last position there won't be an n - 1 and an n + 1, respectively. There are two solutions to this problem.

The boring one

Assume the invalid index accesses to always be 0 or 1. In JavaScript that's particularly easy too, because there are no out of bounds exceptions and accessing an invalid index will just return undefined; and as we've seen above, XOR-wise 0 and undefined are the same.

The less boring one

Assume you're rendering on a torus, so just wrap around when you reach the edges. This means e.g. that the p[0 - 1] element is actually the last one.

Needless to say, I decided to go with solution 2. The first edge case is immediately solved with a relatively new JavaScript array API, the at() method: when used with negative indexes JS will count back from the last item, which is exactly what we want. The second edge case is resolved with a simple modulo, as p[length % length] becomes p[0] but in all other cases p[n % length] stays p[n]. Putting it all together:

function applyRule90(p: (0 | 1)[])  {
  return p.map((_, i) =>
    (p.at(i - 1)! ^ p.at((i + 1) % p.length)!) as 0 | 1)
}

Sadly, TypeScript cannot know if our at() call will be in the bounds, so the return type always includes undefinded. One could argue that it should depend on wether noUncheckedIndexedAccess is set to true, but such is life. Also, the return type of bitwise operations is always a number, so we have to make up for the loss of information with an ugly cast.

Once I had the basic logic, I could move on to the other requirements: given a grid (an array of arrays), take the last row, use it to generate the next one and then append it to the grid. If the grid has now more rows than the max number of rows we want to render, remove the first row.

function generateNextRow (
  grid: (0 | 1)[][],
  maxRows: number
): (0 | 1)[][] {
  const newGrid = grid.concat([
    applyRule90(grid[grid.length - 1])
  ]);

  if (newGrid.length > maxRows) {
    return newGrid.slice(1);
  }

  return newGrid;
};

Do not miss the brackets wrapping our applyRule90 call: concat() unwraps its arguments, but we actually want to concatenate our array as it is, not just its values.

[[0]].concat([1]); // [[0], 1] - Not what we want
[[0]].concat([[1]]); // [[0], [1]] - Ok

Rendering to type characters

──────────────────────────────────────────────────────────────────────────────────────────

The next step was choosing which characters could render empty and filled cells: the obvious choice of █ and the empty space couldn't render the CA with a decent level of detail on a grid of 58x5, so I needed to increase the resolution somehow. Luckily, I stumbled on the Wikipedia page for box-drawing characters and found this nice character set:

▖ ▗ ▘ ▙ ▚ ▛ ▜ ▝ ▞ ▟

Now the resolution was quadrupled, and I just needed to associate every possible subgrid state (2^4 combinations) to its own character. I noticed that every combination uniquely represents a number from 0 to 15 expressed in binary (taking the 0 and 1 in reading order).

"▛" -> ▉▉ -> 1 1 -> 1 1 1 0 -> 14
       ▉     1 0

So, given four cells (0 or 1), we can combine them into a number with some simple bitwise operations and then just use it as an index to access an array containing our ordered characters.

const BLOCKS = [
  " ", // 0,0,0,0 -> 0
  "▗", // 0,0,0,1 -> 1
  "▖", // 0,0,1,0 -> 2
  "▃", // 0,0,1,1 -> 3
  "▝", // etc.
  "▐",
  "▞",
  "▟",
  "▘",
  "▚",
  "▍",
  "▙",
  "▀",
  "▜",
  "▛",
  "▉",
]

function subgridToChar(
  a: 0 | 1,
  b: 0 | 1,
  c: 0 | 1,
  d: 0 | 1
): string {
  return BLOCKS[(a << 3) | (b << 2) | (c << 1) | d];
}

In case you aren't familiar with bitwise operations, the left shift operator << shifts our binary representation to the left by the specified value, inserting zeroes in the freed-up positions to the right.

1 << 3 // 1   -> 1000, 8 in binary
4 << 1 // 100 -> 1000, 8 in binary

The bitwise OR operator | combines two binary representations, comparing each bit position with an "or".

4 | 2 // 6
// 4 in binary is 100, 2 is 10
// 4    2    6
// 1 or 0 -> 1
// 1 or 1 -> 1
// 0 or 0 -> 0

Therefore what we're actually doing in the above snippet is just putting each 0 or 1 in its right position and then we squash them all together to form a number.

// suppose a,b,c,d = 1
(1 << 3) | (1 << 2) | (1 << 1) | 1 // 15
// 1 << 3 -> 1000
// 1 << 2 ->  100
// 1 << 1 ->   10
// 1      ->    1
// 8 (1000) | 4 (100) | 2 (10) | 1 -> 1111 -> 15

So, supposing we have our grid of empty/filled states, we can turn it into a full string like this:

const renderGridToString = (grid: (0 | 1)[][]) => {
  let aggregate: string = "";

  for (let i = 0; i < grid.length; i += 2) {
    for (let j = 0; j < grid[i].length; j += 2) {
      aggregate += subgridToChar(
        grid[i][j],
        grid[i][j + 1],
        grid[i + 1]?.[j],
        grid[i + 1]?.[j + 1]
      );
    }
  }

  return aggregate;
};

Nothing fancy here, the only thing worth noticing is the optional chaining on the second row of the grid: that is necessary as the rows in our grid might be odd(in fact, at the beginning there is only one line) so that row could be non-existent.

Bringing it to life

──────────────────────────────────────────────────────────────────────────────────────────

I was finally ready to bring it all to React, I had all I need, the only thing missing was the animation itself. I decided to go for a simple setInterval to append a new row every n seconds, starting from a randomly generated line.

const initialGrid = [generateRandomLine()];

export const AnimationAutomata = () => {
  const [grid, setGrid] = useState(initialGrid);

  useEffect(() => {
    const interval = setInterval(() => {
      setGrid(generateNextRow(grid));
    }, 200);
    return () => {
      clearInterval(interval);
    };
  }, [grid]);

  return (
    <div
      style={{
        whiteSpace: "break-spaces",
      }}
    >
      {renderGridToString(grid)}
    </div>
  );
};

Given that the string contains white spaces to render [0,0,0,0] cells I had to account for white-space collapsing, so I had to use the white-space value "break-spaces" to preserve white space even at line breaks.

Sadly, the final result on a 58x5 was a little underwhelming, which is why in the end I decided to scrap the idea. You can see it for yourself:

Anyway, even though the effect on a small grid is not great, with a bigger grid and some tweaks to line height and animation speed, it really comes to life!

I love that, in the end, it's just a very big string.

Thank you for reading.