I've recently been trying to teach myself JavaScript and I find the best way to learning a new language is to try and build something in it. Something that's always interesting to build is Conway's Game of Life. The Game of life is a two dimensional Cellular Automaton with some interesting properties. The rules are incredibly simple, yet it can lead to some incredibly complex patterns, and has even been shown to be Turing complete.

The Game of Life is not a game in the traditional sense, there are no players or winners. Rather it is defined on an infinite rectangular grid consisting of "cells", each of which can take one of two states: "dead" or "alive". The a set of rules then describe how each cell changes from one generation to the next.

The rules are simple. For each cell, we look at the it's neighbours, the eight cells closest to it (known as its Moore neighbourhood). Whether the cell is alive or dead in the next generation depends on whether is it alive or dead in the current generation, and the number of alive cells in it's Moore Neighbourhood:

• Each living cell with either two or three living neighbours survives to the next generation, otherwise it dies.
• Each dead cell with exactly three living neighbours comes alive again, otherwise it stays dead.

The game then proceeds, generation by generation. What's interesting are the patterns of living cells on the grid can exhibit. Some initial patterns will move to a fixed state, others will oscillate, some can travel across the grid indefinitely and even self replicating patterns exist.

Implementation

My implementation of the game of life can be found at my github. In terms of how it works its a fairly naive approach: the cells are stored in a rectangular array, and at each timestep we apply the rule to each cell the generate the next generation. The results are then drawn to the canvas. The advantage of this implementation is that it is easy to program - my main focus here was to understand JavaScript rather than optimise it.

A major disadvantage is that we end up doing unnecessary calculations: even if all the cells were dead we end up checking them all. One way around this would be to keep track of which cells are alive and only check these cells and their neighbours. By keeping track of only the living cells we also get around the issue of how to deal with cells at the edge of the array. Currently I either treat the array as having periodic boundary conditions (it wraps back round on itself, acting like the grid was on a torus), or it treats those of the edge as being surrounded by dead cells.

I've added a a few more options, including the ability to change the size of the grid, to initialise to an empty grid or a randomly filled grid and the ability to add "noise" - when used this option means that at each timestep there is a small change for that cell to come alive. This has the effect of breaking up oscillators while not in the initial ruleset adds something.

The result is below, feel free to play with it.

The Game

Click anywhere on the grid to change the state of the cell. Press "run" to begin the game running. Below the canvas are a set of options that allow you to change the rules - after changing them you need to press "initialise" for the changes to take effect. Watch out for larger grid sizes - they can slow things down.

Other Games

The game of life is far from being the only cellular automaton that shows complex patterns. Even simpler rule exist that can show complexity, in one dimension Wolfram's rule 110 has been shown to be Turing complete.

In two dimensions there are a whole family of rules that can be defined. To enumerate these rules, we limit ourselves to the similar idea as life: each cell can either be "dead" or "alive", and the state of the cell in the next generation depends deterministically on the sum of the living cells in the Moore neighbourhood of of that cell. A rule is written in the form Bx/Sy, where "x" and "y" are a list of unique numbers between 0 and 8. The numbers in "x" are the numbers of living neighbours a dead cell needs to come alive, "y" are the number of living neighbour a living cell needs to have to survive to the next round. Using this description Conway's Game of Life would be written as B3/S23.

Some other interesting rule of this form (most taken from wikipedia) have been implemented above, and can be chosen by changing the ruleset.

Questions for another Post

• How does the geometry of the cells change things? For a 2D Euclidean space tiled with regular polygons we could could use hexagonal or triangular cells. What happens if we extend things or hyperbolic geometry or something stranger?
• Is there a way to quantify what makes a ruleset interesting? In such a way we can computationally search through different rulesets?
• The GOL is fundamentally irreversible: there are multiple patterns that all lead to the same final pattern. Do "interesting" cellular automata with reversible rules exist?