Life on Canvas
I was lucky enough to be taught maths by John Horton Conway, if only for an hour a week for a single term. He was lucky enough to be teaching number theory: a subject packed with treasures picked from the full history of mathematics.
I remember him as animated and unkempt. He bustled into that first lecture with a carrier bag and started pulling out groceries one by one. How many items were in the bag, he wondered? Could he count them all — it was a very large bag — and what exactly did infinity mean? Later I would see him pacing along Kings Parade dragging a shopping tolley, lost in thought.
Number theory may be as old as mathematics but it remains very much alive. Some 40 years ago Professor Conway discovered a primitive and novel mathematical life form: the Game of Life.
The rules are simple. A colony of cells inhabits a two dimensional grid. At any one time each cell is either alive or dead, and as time advances the fate of a cell is determined entirely by its immediate 8 neighbours:
- reproduction: a dead cell with exactly 3 live neighbours becomes alive
- survival: a live cell with 2 or 3 live neighbours lives on
- overcrowding or loneliness: in all other cases the cell dies or stays dead
In code, we might represent the colony as a two dimensional array filled with 1’s and 0’s for live and dead cells and code up the rules like this:
// Determine the fate of cell i, j in the next generation.
// Return 1 for "lives", 0 for "dies"
function fate(cells, i, j) {
var neighbours = [[-1,-1],[-1,0],[-1,1],
[0,-1], [0,1],
[1,-1], [1,0], [1,1]];
live_neighbours = 0;
neighbours.forEach(function(n) {
live_neighbours += cells[i + n[0]][j + n[1]];
});
return (live_neighbours == 3 ||
cells[i][j] == 1 && live_neighbours == 2) ? 1 : 0;
}
It turns out these simple rules generate an astonishing ecosystem. Simple patterns flourish, evolving into complex patterns which, many generations later may decay into stable forms and repeating patterns, or, occasionally, become extinct.
Can a finite pattern grow indefinitely? Conway originally conjectured no, this was impossible, offering $50 to the first person who could prove or disprove the his conjecture before the end of 1970. In November of that year a team from MIT led by Bill Gosper claimed the prize, disproving the conjecture with a glider gun pattern which spits out a new spaceship every 30 generations.
A 2 dimensional array can naturally be represented on the most basic computer screen — think raster graphics, pixels — and the parallel emergence and development of the personal computer helps explain life’s continuing appeal1. The game of life has become the hello world of graphics frameworks. In 2012 we can use the HTML5 canvas, a 2 dimensional surface for drawing on.
After a little experimentation you’re sure to uncover life’s three main domains: still lives, which remain unchanged; oscillators, which repeat; and spaceships, which move across the board. Then there are methuselahs, puffers, guns …
Here’s a pulsar, an oscillator with period 3.
And here’s a glider, classed as a diagonal spaceship, a pattern chosen by Eric S Raymond as a hackers’ emblem.
Here’s another 5 cell pattern — the R-pentomino. Clear the canvas, pick out an R-pentomino cluster of cells with the mouse, click play, and watch what evolves!
Turtle, garden, unicycle: animal, vegetable, mineral. The kingdom of life is inclusive and extensive, a delight for naturalists and taxonomists alike. It’s seduced logophiles and lexicographers too: reading through Stephen A. Silver’s comprehensive Life Lexicon, I learned that an anteater consumes ants, a caterpillar works by laying tracks at its front end, a baker’s dozen is a loaf hassled by two blocks and two caterers, and an AK47 reaction occurs when a honey farm predecessor, catalysed by an eater and a block, reappears at another location 47 generations later, having produced a glider and a traffic light. I could go on…
1: I’m glossing over details here. The true game of life is played out on an infinite grid, and patterns such as Gosper’s glider gun show that it really does have to be infinite. Computers have trouble with such an unconstrained requirement, and a computer animation might try and adapt the screen as the pattern grows, or limit the region of interest. Another approach is to wrap the canvas, left to right, top to bottom, so the game of life is played out on what’s topologically a toriodal surface. That’s what the canvas shown here does.
§
The icons used on this page were downloaded from http://glyphicons.com and are licensed under the CC BY 3.0 terms. The animated gifs were placed in the public domain by their authors.
Articles