Game of Life overview

We’re going to wrap up the semester with a set of exercises that collectively build a Racket implementation of Conway’s Game of Life (the Wikipedia entry is good and recommended).

Life is an example of a cellular automata, a simple model of computation that nicely illustrates how some very simple rules can lead to quite complex behavior. There is evidence, for example, that some chemical processes may behave in ways similar to cellular automata, and that these may play an important role in the evolution of color patterns in plants and animals.

The rules

The short version is that we have a grid of cells, where each cell is on/off (true/false, black/white, zero/one, alive/dead). At each timestep every cell is updated according to these simple rules:

  • Any live cell with two or three neighbors survives.
  • Any dead cell with three live neighbors becomes a live cell.
  • All other live cells die in the next generation. Similarly, all other dead cells stay dead.

Here “neighbor” is any of the eight cells that are adjacent horizontally, vertically, or diagonally.

Some sample behaviors

From these simple rules quite remarkable complexity can develop. There are stable configurations that just stay exactly as they are, assuming some other patterns don’t come in and interfere. For example the block pattern will, on its own just persist forever. (You probably want to confirm that by applying the rules above).

The block configuration, which remains stable over time

There are also oscilating configurations such as the blinker:

The blinker configuration, which oscilates back and forth between two states indefinitely

And configurations that move forever like the glider, which (in this example) moves down and to the right forever, or until it runs into some other live cells which alter or disrupt its behavior.

The glider configuration, which moves forever down and to the right

In fact you can build entire computational systems in Life, where things like gliders can be used as “signals” that travel from one part of the system to another, triggering other events upon their arrival.

Implementing this in Racket

So let’s implement this in Racket!

To implement the whole thing isn’t actually that complicated, but I think it would be a bit much in our timeframe, so I’ll provide parts and you’ll provide parts. I’ll also break this up into several pieces that will be due at different stages so we have a structured path for getting this done.

The world state: A list of posn

We’ll use Racket big-bang to run the simulation. To do that we need to design the “world state” that we’re going to use. I’m going to structure our solution around a world state that will be a list of the “live” cells in the world, where each cell is just going to be a posn holding the the x- and y-coordinates of that cell on the grid. So a world is a list of posns, where each posn contains two numbers:

;   live-cell: posn
;   world: [posn]

Note that here it’s crucial that we have lists to hold the state since we don’t know how many live cells there will be at any particular moment in time. So we simply couldn’t have done this before we had gone over cons, lists, and the like. A lot of our implementation will require processing lists of cells (posns), either through explicit recursion or through the use of list processing tools like map, filter, or foldl/foldr.

The structure of the solution

The pieces will be:

Originally written by @elenam, with subsequent modifications by @NicMcPhee