It's Life, Jim, but not was we know it.
The Game of Life is a zero-player game. There is a grid with an initial configuration and a cell in the grid will come to life or die, depending on the state of its neighbours. These rules are checked over and over until the game comes at a halting state or until all cells have died. The rules on what cell lives and dies are simple:
- A living cell with less than two living neigbours dies.
- A living cell with two or three neighbours lives on.
- A living cell with more than three neighbours dies.
- A dead cell with exactly three neighbours comes to life.
Here is the Game of Life, with an initial, oscillating, configuration called the Gosper Gliding Gun. If you have an up to date browser you should see Life below.
As this is just a simple grid, the game could be drawn on a simple HTML table with appropriate CSS styling. This is certainly a good option but because I don't like tables, I didn't go for this option.
Then I stumbled upon a very cool project called RaphaelJS. This library helps out in drawing SVG graphics and you can definitely created some nice stuff with it like charts, vector map viewers and even animated movies. I had implemented the whole thing using Raphael but found it to be a bit too slow in the end.
The final option then was to use the new-ish HTML5 canvas element, a standard which finally seems to have made it to all major browsers. I found this was the way to got, so I got started.
I wanted to make the implementation easy to use, so settings the whole thing up should be pretty simple. I came up with a configuration object and a fluent builder implementation for it, so you configure the Game of Life rendering like this:
The algorithm itself implements a few quick win optimizations but nothing as drastic as done in hashlife. A first optimization was that the neighbour of each cell is computed once at initialization, this allows us to skip grid boundary checks each time to find a cells' neighbours.
A second optimization was to keep a change list. This list contains the cells that could change state in the next generation of the algorithm. The list contains cells that were born or died and their respective neighbours. A pretty big speedup was obtained this way because only cells in this list need to be checked and rendered.
The hard parts
Weirdly enough, the hardest part was enabling user interaction with the grid. The user can interact with the grid by moving the mouse. Any cells under the mouse pointer will come to life. The difficulty here was catching this event in a browser-independent way and I had to resort to jQuery for this. This is the only part of the library that uses an external library.
Use it yourself?As always you can find the code on my github page.
Published on 12 Feb 2012