Gosper’s HashLife in CoffeeScript
Pull request Compare This branch is 126 commits behind raganwald:master.
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.


Cafe au Life

Cafe au Life is an implementation of John Conway's Game of Life cellular automata written in CoffeeScript. Cafe au Life runs on Node.js, it is not designed to run as an interactive program in a browser window.

Cafe au Life's annotated source code is here.

Gosper's Glider Gun

(Gosper's Glider Gun. This was the first gun discovered, and proved that Life patterns can grow indefinitely.)

Conway's Life and other two-dimensional cellular automata

The Life Universe is an infinite two-dimensional matrix of cells. Cells are indivisible and are in either of two states, commonly called "alive" and "dead." Time is represented as discrete quanta called either "ticks" or "generations." With each generation, a rule is applied to decide the state the cell will assume. The rules are decided simultaneously, and there are only two considerations: The current state of the cell, and the states of the cells in its Moore Neighbourhood, the eight cells adjacent horizontally, vertically, or diagonally.

Cafe au Life implements Conway's Game of Life, as well as other "life-like" games in the same family.


Period 24 Glider Gun

(A period 24 Glider Gun. Gliders of different periods are useful for synchronizing signals in complex Life machines.)

Cafe au Life is based on Bill Gosper's brilliant HashLife algorithm. HashLife is usually implemented in C and optimized to run very long simulations with very large 'boards' stinking fast. The HashLife algorithm is, in a word, a beautiful design, one that is "in the book." To read its description is to feel the desire to explore it on a computer.

Broadly speaking, HashLife has two major components. The first is a high level algorithm that is implementation independent. This algorithm exploits repetition and redundancy, aggressively 'caching' previously computed results for regions of the board. The second component is the cache itself, which is normally implemented cleverly in C to exploit memory and CPU efficiency in looking up precomputed results.

Cafe au Life is an exercise in exploring the beauty of HashLife's recursive caching or results, while accepting that the performance in a JavaScript application will not be anything to write home about.

My understanding of HashLife was gleaned from the writings of: