Contents

Cellular automata can produce dynamic patterns from very simple rules.

Conway's Game of Life is surely the most well-known example. It uses a 2D grid, in which each cell can be either 'living' or 'dead'. The grid is then passed through a number of generations (or steps). In a generation, each cell is updated based on its Moore neighbourhood, which consists of the eight surrounding cells:

For each generation, dead cells with three neighbours are born, and living cells with two or three neighbours stay alive. All the others die or stay inactive.

This can give rise to complex patterns and structures which repeat themselves. Below is an oscillator, which repeats itself after a given number of generations. Gliders may also occur, which move in a straight line.

If you fill the field with random noise and then set it running, at the end it is usually filled with simple still lives (static patterns) and oscillators like below, which never go away.

Maybe one of the most interesting things about this is despite its apparent structure and complexity, the entire set of rules can be encoded in a short string. Conway's Life has the rule set "23/3". This specifies the conditions for birth and persistence. Changing this string generates other CAs, many of which are interesting in their own right. "12345/3", for example, generates mazes (read more here).

This makes cellular automata relevant to this site because we are concerned with emergent behaviour.

Technically the Game of Life is infinite in size, but to simulate it you can choose either to have a hard border of dead cells, a field which wraps around on all four sides, or expand the simulated area dynamically (in which case you should use a sparse matrix to store the data).

Using a sparse matrix can optimise the processing of large fields. The simulation also lends itself well to parallelisation, as all processing within the grid happens locally.

Edwin Martin's blog provides an extensive list of some of the most common and most interesting patterns to be found. The Life Wiki is also an excellent resource. Optimisation is discussed here.