A flexible implementation of Conway's Game of Life

– Posted January 25, 2016 the refsmmat report · a blog at refsmmat.com

Conway’s Game of Life is a simple simulation with surprisingly complex behavior. We start with a simple 2D grid of cells. Each cell can be either alive or dead. The rules are:

• A live cell stays alive if it has two or three live neighbors.
• A dead cell becomes alive if it has exactly three live neighbors.

We started with a certain set of cell states and then iterate, applying the rules to every cell at each iteration. Despite their simplicity, these rules can produce amazingly complicated behavior. For example, here is Gosper’s Glider Gun, which produces “gliders” which wander off to infinity:1

For our Statistical Computing course, Chris Genovese used the Game of Life as an example at the very beginning of the course to illustrate the flexible design of programs. Students first were told to write an ordinary implementation following the rules above – then asked how they’d abstract their algorithm so they could replace the rules or even work on a non-rectangular grid. Without careful planning, that kind of abstraction could be very difficult.

So here’s a sample implementation in Racket, my favorite little Lisp.

Setting up the rules

First we need to specify the rules of the game. Conway’s rules are the most popular, but it’s possible to use different rules to decide which cells live or die, so we’ll abstract the rules out to a function.

The rules function only needs to know two things: the number of neighbors the cell has, and whether or not it’s currently alive. Then it returns a boolean indicating whether the cell will stay alive.2

``````(define (conway-rules neighbors alive?)
(if alive? (or (= neighbors 2) (= neighbors 3))
(= neighbors 3)))``````

If we want to try out different sets of rules, it’s easy to define entirely new functions – with arbitrary logic and complexity – which can replace `conway-rules`. As you’ll see below, `conway-rules` is passed as an argument to our other functions, so replacing it requires no source code changes at all.

Operating on the grid

It’s tempting to store the state of the Game of Life using some kind of two-dimensional array or matrix. Then, on each step, we’d loop through the whole board, checking which cells should live or die. But this would become slow – the gliders we saw earlier can wander off arbitrarily far, so our board would have to be large and the loop slow. If our board isn’t large enough, cells could reach the edge, and we’d either need to increase the board size or accept that their behavior will be wrong.

Worse, the amount of computation needed would grow with the board size, regardless of how many cells in the board are actually alive. In the worst case, we’d have an enormous board of entirely dead cells, and at every step we’d still loop through the whole thing checking if anything should come alive.

But look back at the rules. All we really need to keep track of is the live cells. We can tell if a cell comes alive just by knowing if it has live neighbors.

Imagine we have a list of currently live cells. If we find the neighbors of each live cell, we’ll have a big list of coordinates; if a cell is the neighbor of three live cells, it’ll appear in that list three times. So, for example, a currently dead cell which is the neighbor of three live cells will appear in the list, and we can mark it as alive on the next step.

On our rectangular grid, we can easily find the neighbors of a single cell with

``````(define (neighbors-rect location)
(let ([x (first location)]
[y (last location)])
(for*/list ([dx '(-1 0 1)]
[dy '(-1 0 1)]
#:when (not (= dx dy 0)))
(list (+ x dx) (+ y dy)))))``````

Coordinates are stored as `(x, y)` pairs. We loop through perturbations, adding or subtracting 1 from `x` and `y`, generating the eight neighbor coordinates.

Taking the next step

I’m going to put together a key function from a few pieces here. Let’s start with the basic bits. To apply Conway’s rules, we start by getting the list of all neighbors of all cells:

``(append-map neighbors (set->list live-cells))``

We need to count how many times each coordinate appears in this list, so we’ll use a hash table. The result is a table of `item,count` pairs:

``````(define (count-occurrences neighbors)
(for/fold ([ht (hash)])
([item neighbors])

`hash-update` takes a hash table, looks for a key (`item`), and updates it according to the function passed to it – in this case `add1`, so the count is incremented by 1. If the key doesn’t exist, we pass 0 to `add1` as the default. As a result, we have a count of how many time each `item` appears in the `neighbors` list.

Then it’s just a matter of applying the rules. If we have the number of neighbors and a set of live cells, then applying the rules is as simple as

``````(conway-rules (hash-ref num-neighbors cell)
(set-member? live-cells cell))``````

The `hash-ref` simply looks up the `cell` in the table, returning how many neighbors it has.

Now we can assemble together a function to take a set of live cells and return a new set:

``````(define (step rules neighbors live-cells)
(let ([num-neighbors
(count-occurrences (append-map neighbors (set->list live-cells)))])
(list->set (filter (lambda (cell)
(conway-rules (hash-ref num-neighbors cell)
(set-member? live-cells cell)))
(hash-keys num-neighbors)))))``````

Running more generations

Our `step` function only runs one iteration: it applies the rules, generates the new set of live cells, and returns it. How do we run the Game of Life for more steps?

A simple route would be a `for` loop. But we can be fancier. Racket supports lazy sequences: infinitely long sequences whose elements are calculated only when we ask for them. We can define one recursively.

``````(define (life cells)
(stream-cons cells (life (step conway-rules neighbors-rect cells))))``````

`stream-cons` is an interesting function that works recursively. It defines a stream (a sequence) that begins with `cells` and whose next element is formed by calling its second argument – which creates another sequence that starts at the next step.

In summary, `life` applies Conway’s rules on a rectangular grid, making an infinite sequence of cell states. We can ask Racket to provide any element in the sequence and it’ll be calculated on demand.

The results

Let’s try our code on a sample set of live cells. We’ll use the “acorn”, a configuration which starts small and then grows for thousands of generations. I’ve imported a `draw-game` function which draws the results. At the beginning, it looks like this:

``````(define acorn (set '(1 1) '(2 1) '(2 3) '(4 2) '(5 1) '(6 1) '(7 1)))
(draw-game (set->list acorn))``````

But after just fifty steps, we have:

``(draw-game (set->list (stream-ref (life acorn) 50)))``

And after fifty more:

``(draw-game (set->list (stream-ref (life acorn) 100)))``

Life on a hexagonal grid

One more thing. Previously we defined a neighbors function, which gets the list of neighbors of a cell. That function assumed we were working on a rectangular grid. But, if you look carefully, you’ll see it’s the only function which assumes that. If we want to change the grid, we need only swap out the neighbors function.

Suppose, then, we swap out the rectangular grid for a hexagonal one. There are many possible hexagonal grid coordinate systems, so I’ve chosen one arbitrarily, and to make it brief, each cell has six neighbors instead of eight, and we can generate them all with a slightly different function:

``````(define (neighbors-hex location)
(let ([x (first location)]
[y (last location)])
(for*/list ([dx '(-1 0 1)]
[dy '(-1 0 1)]
#:when (and (not (= dx dy 1))
(not (= dx dy -1))
(not (= dx dy 0))))
(list (+ x dx) (+ y dy)))))``````

By swapping out `neighbors-rect` for `neighbors-hex` in our definition of life, we can work on a hexagonal grid. No other code needs to change except for how we draw the grid.

1. Animation from Wikimedia Commons.

2. I apologize for the minimal syntax highlighting. pandoc’s syntax highlighting library doesn’t support Racket yet, so I’m using the Clojure highlighting, which doesn’t recognize most of Racket’s keywords.