GAME OF LIFE

As part of the BSc study program, I attended a course all about languages and automata. There, I was exposed to automata theory and various types of state-machines along with it. I had really enjoyed that course, but it was only about two years later that I was reminded of it, when I stumbled upon this video showing massively complex simulations in the Game of Life.

See, I find the subject of cellular automata very appealing however we never got to cover it explicitly during the course, unfortunately. Coming across that video and seeing the mesmerizing patterns the Game of Life is capable of producing has re-ignited my interest for the subject.

And so, I started reading about cellular automata and the Game of Life in particular. Simple simulations were available for view in animated form as gifs, however in order to view more complex ones one was required to download a desktop application. I wanted a compromise: A simple implementation of the Game of Life for the browser.

Table of contents

Introduction

The Game of Life (or in short, Life) is a cellular automaton model developed by mathematician John Horton Conway.

Within Life, the universe consists of an infinite-planar-regular grid, where each cell can assume one of two states: dead or alive:

Figure 1: Five living cells (black) in a 5x5 grid.

The evolution of the cell population proceeds through generations. The evolution from one generation to the next adheres to the following rules:

  1. Death by isolation: Living cells with less than two live neighbours die.
  2. Death by overcrowding: Living cells with more than three live neighbours die.
  3. Birth by reproduction: Dead cells with exactly three live neighbours become alive.

In all other cases, the cell retains its state from the previous generation. Use the following interactive widget to better grasp these rules:

Figure 2 (interactive): Current and next generations. Click on the cells in the current generation's grid to toggle their state and observe the corresponding changes in the next generation to come.
Current
Next

As simple as they are, these three rules together with certain initial patterns give rise to many complex, interesting evolutions. The Life Wiki is a good place to look for such configurations. Below you'll find some representatives from each category in action:

3.1: Still lifes are patterns that remain constant throughout the simulation.
3.2: Spaceships reproduce themselves at an offset from their initial position after a fixed number of generations.
3.3: Oscillators repeat themselves after a fixed number of generations.
3.4: Guns emit spaceships.
3.5: Puffers are spaceships that leave residual debris behind them as they move.
3.6: Methuselahs are patterns that take a long time to stabilize.

Implementation

Life, although capable of producing complex evolutions, is inherently quite simple: just three rules, two states, and a grid. Our implementation aims to preserve that simplicity, and expose a clean, user-friendly interface to the consumer of the module.

With that in mind, our implementation (gol.js) exposes only one class, World, which represents the Life universe (i.e. the grid) and some methods to manipulate, evolve, and inspect it. Here's a schematic:

World.prototype = {

    // Manipulation
    spawn: function(x, y) { ... },
    kill: function(x, y) { ... },

    // Evolution
    step: function() { ... },

    // Inspection
    inspect: function(x, y) { ... },
    inspect_all: function(callback) { ... }
};

Now, the two main issues that remain to be satisfied are firstly: How to model the grid without needless waste of memory, and secondly: How to implement the evolution method efficiently.

Representing the grid

Technically, the Life grid spans into infinity. However, for our purposes we are content with a grid of fixed width and height. Now, perhaps the most intuitive representation of the grid would be a two-dimensional array of boolean values, indicating whether each cell is dead or alive. Unfortunately, this approach hardly makes efficient use of memory and neglects to take advantage of the fact that in the vast majority of scenarios - much like the zombie-apocalypse - the number of the dead far exceeds that of the living.

A different approach (and the one which we use) keeps track of only the cells which are live. We identify each cell by its coordinates (x, y), and store them in a set. Now, Javascript does not officially have a built-in Set data-structure (at least not before the 2015 specification), but we can easily mimic set-like behavior using Object, like so:

function HashSet(hash) {

    this._hash = hash || HashSet.HASH_IDENTITY;
    this._items = {};
}
HashSet.HASH_IDENTITY = function(item) { return item; };
HashSet.prototype = {

    constructor: HashSet,

    contains: function(item) {

        return this._items.hasOwnProperty(this._hash(item));
    },

    add: function(item) {

        this._items[this._hash(item)] = item;
    },

    remove: function(item) {

        delete this._items[this._hash(item)];
    },

    clear: function() {

        this._items = {};
    },

    enumerate: function(callback) {

        var key, item;
        for (key in this._items) {

            if (this._items.hasOwnProperty(key)) {

                item = this._items[key];
                if (callback(item)) { return; }
            }
        }
    }
};

Computing the next generation

The state of a cell in the next generation depends on its current state and the state of its neighbours, or more specifically: the number if its live neighbours. This calls for us to keep track of the number of living neighbours of each cell.

We do this by linking this record-keeping to cell addition and removal. That is, whenever a cell spawns (becomes alive), we increment the neighbour-count record of all cells in its neighbourhood by one, and when a cell dies, we decrement it. Now when we evolve a cell, we can simply access its neighbour-count record and apply Life's rules to determine its next state.

But, how many cells should we look into when computing the next generation? All of them? - that would be quite depressing... Especially since a great many cells may not change their state from one generation to the next. Luckily, there's a better way.

Observe that when a cell's neighbourhood doesn't change, its own state won't change either. This observation encourages us to only bother evolving cells whose neighbourhood had recently changed.

Again, we attach this task to cell addition and removal. That is, whenever a cell spawns or dies, we add it and its neighbours into a set of 'dirty' cells - cells whose neighbourhood has changed in the last generation.

Putting all of this together gives us the following algorithm for the simulation's evolution:

function step() {

//    for each cell in the dirty set: {
//
//        Compute cell's next state and remember it.
//    }
//    Clear the dirty set.
//
//    Apply the computed state to each former-dirty cell.
//    (...this re-fills the dirty set for next time)
};

Source code

You can view the source code and documentation of the main module on GitHub. Additional code used to parse and display patterns (such as was done on this page) can be found in the GitHub Pages branch of the repository.

See also