Cellular automata

One-dimensional elementary cellular automata are very simple. You just got a single row of cells which have one of two states: On or Off (0 or 1, living or dead, whatever you want to call it), so they can be nicely represented by a simple two-color bitmap.

States in cellular automata change according to the neighbourhood of a cell in the previous (global) state. Let's say you're a living cell (On, 1) and your neighbours in both directions are dead (Off, 0). Suppose you also have a table that states that your state in exactly this case changes to dead (might happen, maybe you just were too lonely to exist, don't blame me). But in another configuration your left neighbour might still be living and in that case you get to live on. Or in yet another configuration you are a dead cell and regardless what your neighbours are you change state to living.

State transitions

Such a table essentially needs only a few things: State of a cell, state of all neighbour cells (two in this case) and the state of the cell in the following generation. We can visualize this as follows:

In the top row we have a cell with two neighbours, one left, one right, so three cells each. The bottom row gives the following state for each configuration. As you may have noticed, there are only eight possible configurations. And we can impose an order on them as I have done here. And the relevant part, once that order is established is simply a string of eight zeros and ones—so essentially eight bits. We can simply write this rule as a number. What wonderful way of shortening things. This numbering was conceived by Stephen Wolfram, a British mathematician and thus it's called Wolfram code or a Wolfram rule.

The rule pictured above is rule 30.

Display

So we now know that such a cellular automaton might be described by a single number and that it can change states. What good is that?

Well, we might display a certain state of the automaton as a series of either black or white boxes:

and then we might display each of these states below the previous one:

et voila, we got a nice picture. Slightly chaotic, but that's usual for rule 30 and we got some nice recurring triangle formations in there.

So the point of all that was to generate a weird-looking image. Now for the fun part of this. Programming such a beast.

The code

It isn't exactly complicated to do this, so lets start at the top:

We obviously need some control over how much is calculated and rendered. I put a single cell with state 1 in the center of the first row (initial state) so it's advisable to choose an uneven width because many patterns fan out to both sides (as seen above) and then they reach the left and right edge simultaneuosly. Height might be chose for a similar reason, since as the pattern fans out and reaches the sides it gets meaningless pretty quickly.

If the rule is given as the first parameter we only ask for it if it lies outside the permitted range (0–255), else we ask anyway until a correct rule is given.

Following that I wrote a simple subroutine which dissects the numerical rule into its eight parts:

So after that we have eight variables, named <cmd>wolfram_x</cmd> with <cmd>x</cmd> being a number from 0 to 7 which hold the successor states for each configuration.

We then initialize the area in which we store the states of each cell for each generation:

Basically we just initialize everything with zero and add a single one in the center of the first generation.

We have a problem with this approach, however, since when states are computed they need a neighbourhood. But how does the neighbourhood look for the first and last cells in each row? At first I simply put another cell to the left and right of the row, containing a zero. This works fine for most rules and we leave it as that for now. How one would implement this I leave as an exercise for the reader.

We might need a subroutine to display the whole area:

As you can see, that are actually two subroutines. They come in handy later.

What is still missing, however, is the calculation of successor states. So let's do that now.

Nothing fancy here, we just delegate the computation of a single cell to another subroutine. As you may note we display the calculated row immediately after we calculated it, this makes the watching experience while the batch file runs a bit less boring as we see a new line every few seconds (yes it is that slow).

Here we calculate the new state for a given cell, by using another helper subroutine which looks up the specific case from the table. We make use of the fact that the configuration of a cell and its neighbours are essentially three-bit numbers and the table is laid out in such a way here that we can access it simply by converting the configuration into a number between 0 and 7. The code for that looks a little ugly, since lots of escaping is needed (I escaped the parentheses just out of fear they might break something, as they often do when nesting structures).

But that was it, essentially. Running the batch without arguments produces the following prompt:

entering, say, 54 in there, yields the following picture:

The actual source code is a bit longer, since I offer an option how the sides of the area are handled (all zero, all one, wraparound and copy, the last of which is now the default which seems the most sensible to me—rules like 169 look very different when calculated with the edges being zero).

I am now working on SVG export from within the same batch file and I hope I found all major bugs by now. But the first working version was just 54 lines long. I think, had I been using Java instead (which was the other choice here), I would have needed significantly more.

UPDATE (2008–12–26 16:21): SVG export is now done and works as it should. At the moment I am mis-using the terminal server in the uni to compute all 256 rules simultaneously: