Elementary cellular automaton

Today we’re going to be playing with an HTML5 canvas again (previously we made line art and bugs). This time, the goal is to make a tool where you can explore elementary cellular automaton.

(If you just want to jump to the toy, click here. There’s also a much larger version available here.)

Essentially, you can think of an elementary cellular automaton as a function on a series of rooms. Each room has a light and the ability to see their neighbor’s lights as well as their own. Now if you take that those three inputs, there are 8 cases to consider:

leftmeright
offoffoff
offoffon
offonoff
offonon
onoffoff
onoffon
ononoff
ononon

For each of those eight inputs, there are two possible outputs. I can either turn my light on or turn it off. This in turn will be seen by my neighbors who might the adjust their own lights and so on.

What gets more interesting is when you show a picture of the changing lights over time. Imagine a series of rows where each row is the state of all of the lights at one moment in time. So if the rule is that whenever either neighbor’s light is on to turn your own on, you’ll see a spreading wave of lights turning on as you move down the picture (rule 222).

So how does this all work in practice? It turns out, it’s actually pretty simple.

First, we’ll initialize two arrays. I’ve included a number of initial conditions including all off, all on, half and half, random, and a single point.

var oldRow = new Array(width);
var newRow = new Array(width);

for (var i = 0; i < width; i++) {
  if (initial == "random")
    oldRow[i] = (Math.random() > 0.5 ? 1 : 0);
  else if (initial == "5050")
    oldRow[i] = (i < width / 2 ? 0 : 1);
  else if (initial == "point")
    oldRow[i] = (i == Math.floor(width / 2) ? 1 : 0);
  else if (initial == "black")
    oldRow[i] = 1;
  else if (initial == "white")
    oldRow[i] = 0;
  else
    oldRow[i] = 0;

  newRow[i] = 0;
}

Why two arrays? So that we can update one without the updates themselves having an effect on the row we’re working on. You could actually do that just as well, but it wouldn’t be the simulation we’re trying to do.

In any case, the next step we need is run the actual simulation. Basically, work from top to bottom making each row based off of the previous one.

var index = 0;
for (var row = 0; row < height; row++) {
  for (var col = 0; col < width; col++) {
    if (oldRow[col] == 1)
      c.fillRect(col, row, 1, 1);

    index = oldRow[col == 0 ? 0 : col - 1] * 4 + oldRow[col] * 2 + oldRow[col == width - 1 ? width - 1 : col + 1];
    newRow[col] = setTo[index];
  }

  for (var col = 0; col < width; col++) {
    oldRow[col] = newRow[col];
  }
}

One interesting bit there is the calculation and use of the variable index. Basically, index treats the values to the left, right, and at the given point as a binary number 0-8. These values are each decoded in another part of the code:

var setTo = [0, 0, 0, 0, 0, 0, 0, 0];
for (var i = 0; i < 8; i++)
  setTo[i] = (rule >> i) & 1;

That may look like black magic, but all it’s doing is turning a number in the range [0, 255] into a set of rules for the automaton. Here’s how that works:

First, convert the number into binary: Rule 30 = 00011110

Then, go through the 8 possibilies for off/on patterns we discussed earlier. Assign each bit to each pattern in order, treating 0 as off and 1 as on:

leftmerightbit
offoffoff0 = off
offoffon0 = 0ff
offonoff0 = off
offonon1 = on
onoffoff1 = on
onoffon1 = on
ononoff1 = on
ononon0 = off

Then, we can interpret the table by finding the row that corresponds to what we currently see and adjusting our lights accordingly. So if our light is on and so is our left neighbor but the right is out, that means we are in the second last row and should keep our light on. If our right neighbor turns their light on though, that puts us in the last row so we should turn our light off. That then means we’re in the 6th row, so we should turn it back on (and thus we alternate between the 6th and 8th rows until one of our neighbors turns their light off). Isn’t it neat how you get oscillating behavior like that from such a simple set of rules?

In any case, that’s about enough from me for the time being. Why don’t you try out the demo below? You can choose any of the 256 possible rules with 5 initial conditions I mentioned above or you can try out the interesting cases mentioned in the Wolfram Mathworld article mine is based on.

If you have any questions / comments / suggestions, feel free to drop me a line below.

If you would like to try this in a larger, resizable version, you can do so here.

Have fun!

Rule
Scale
Initial condition
Interesting rules

If you’d like, you can download the source here: cellular automaton source code