Problem: Simulating the Game of Life

In 1970, mathematician John H. Conway proposed a simulation that he called the Game of Life. Martin Gardner wrote an column about Life in the October 1970 issue of Scientific American that brought widespread attention to the Game of Life. It’s not what most people think of as a game; there are no players and there’s no way to win or lose the game. Instead, Life is more like a model or simulation in which you can play and experiment.

Life takes place on a two-dimensional grid of square cells. Each square cell can be either alive or dead (full or empty).

Example of a Life board.

Example of a Life board. Cell x‘s eight neighbours are numbered.

The simulation is carried out at fixed time steps; every time step, all the cells on the grid can switch from dead to alive, or alive to dead, depending on four simple rules that only depend on a given cell’s eight immediate neighbours. Let’s take the cell x in the diagram, whose neighbours have been numbered 1 through 8 in the diagram.

If the cell is dead:

  1. Birth: if exactly three of its neighbours are alive, the cell will become alive at the next step.

If the cell is already alive:

  1. Survival: if the cell has two or three live neighbours, the cell remains alive.

Otherwise, the cell will die:

  1. Death by loneliness: if the cell has only zero or one live neighbours, the cell will become dead at the next step.
  2. Death by overcrowding: if the cell alive and has more than three live neighbours, the cell also dies.

These rules are simple and readily understandable, but they lead to surprisingly complex behaviour. (The general term for a simulation carried out on a grid of cells and following some simple rules is a cellular automaton.) For example, here are some patterns that occur after starting with five live cells in a row.

This pattern ends up in a cycle that repeats itself endlessly. Researchers in Life have coined many terms for different types of pattern, and this one is called an oscillator. The wiki at ConwayLife.com <http://www.conwaylife.com/wiki/Main_Page> describes many such terms. For example, oscillators go through a cycle of states and return to their initial state; still life patterns are stable and don’t change over time at all; spaceships return to their initial configuration but in a different position, and therefore the pattern moves through the grid.

Approach

It’s possible to work out Life patterns using pencil and paper, but obviously this is boring for large or long-lived patterns, and there’s also the risk of error. Computer implementations of Life were written soon after Conway described it.

A basic implementation is straightforward: store the state of the board, and loop over every cell to determine its new state. To be correct, the code has to record new states in a copy of the board’s data structure and not update the original board as it’s scanned.

Solution

This implementation of Life uses the turtle graphics to draw the board. Keystrokes are used to control the program; hit ‘R’ to fill the board with a random pattern, and then ‘S’ to step through one generation at a time.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
#!/usr/bin/env python3

# life.py -- A turtle-based version of Conway's Game of Life.
#
# An empty board will be displayed, and the following commands are available:
#  E : Erase the board
#  R : Fill the board randomly
#  S : Step for a single generation
#  C : Update continuously until a key is struck
#  Q : Quit
#  Cursor keys :  Move the cursor around the board
#  Space or Enter : Toggle the contents of the cursor's position
#

import sys
import turtle
import random

CELL_SIZE = 10                  # Measured in pixels

class LifeBoard:
    """Encapsulates a Life board

    Attributes:
    xsize, ysize : horizontal and vertical size of the board
    state : set containing (x,y) coordinates for live cells.

    Methods:
    display(update_board) -- Display the state of the board on-screen.
    erase() -- clear the entire board
    makeRandom() -- fill the board randomly
    set(x,y) -- set the given cell to Live; doesn't refresh the screen
    toggle(x,y) -- change the given cell from live to dead, or vice
                   versa, and refresh the screen display

    """
    def __init__(self, xsize, ysize):
        """Create a new LifeBoard instance.

        scr -- curses screen object to use for display
        char -- character used to render live cells (default: '*')
        """
        self.state = set()
        self.xsize, self.ysize = xsize, ysize

    def is_legal(self, x, y):
        "Returns true if the x,y coordinates are legal for this board."
        return (0 <= x < self.xsize) and (0 <= y < self.ysize)

    def set(self, x, y):
        """Set a cell to the live state."""
        if not self.is_legal(x, y):
            raise ValueError("Coordinates {}, {} out of range 0..{}, 0..{}".format(
                    x, y, self.xsize, self.ysize))
                             
        key = (x, y)
        self.state.add(key)

    def makeRandom(self):
        "Fill the board with a random pattern"
        self.erase()
        for i in range(0, self.xsize):
            for j in range(0, self.ysize):
                if random.random() > 0.5:
                    self.set(i, j)

    def toggle(self, x, y):
        """Toggle a cell's state between live and dead."""
        if not self.is_legal(x, y):
            raise ValueError("Coordinates {}, {} out of range 0..{}, 0..{}".format(
                    x, y, self.xsize, self.ysize))
        key = (x, y)
        if key in self.state:
            self.state.remove(key)
        else:
            self.state.add(key)

    def erase(self):
        """Clear the entire board."""
        self.state.clear()

    def step(self):
        "Compute one generation, updating the display."
        d = set()
        for i in range(self.xsize):
            x_range = range( max(0, i-1), min(self.xsize, i+2) )
            for j in range(self.ysize):
                s = 0
                live = ((i,j) in self.state)
                for yp in range( max(0, j-1), min(self.ysize, j+2) ):
                    for xp in x_range:
                        if (xp, yp) in self.state:
                            s += 1

                # Subtract the central cell's value; it doesn't count.
                s -= live             
                ##print(d)
                ##print(i, j, s, live)
                if s == 3:
                    # Birth
                    d.add((i,j))
                elif s == 2 and live: 
                    # Survival
                    d.add((i,j))
                elif live:
                    # Death
                    pass

        self.state = d

    #
    # Display-related methods
    #                    
    def draw(self, x, y):
        "Update the cell (x,y) on the display."
        turtle.penup()
        key = (x, y)
        if key in self.state:
            turtle.setpos(x*CELL_SIZE, y*CELL_SIZE)
            turtle.color('black')
            turtle.pendown()
            turtle.setheading(0)
            turtle.begin_fill()
            for i in range(4):
                turtle.forward(CELL_SIZE-1)
                turtle.left(90)
            turtle.end_fill()
            
    def display(self):
        """Draw the whole board"""
        turtle.clear()
        for i in range(self.xsize):
            for j in range(self.ysize):
                self.draw(i, j)
        turtle.update()


def display_help_window():
    from turtle import TK
    root = TK.Tk()
    frame = TK.Frame()
    canvas = TK.Canvas(root, width=300, height=200, bg="white")
    canvas.pack()
    help_screen = turtle.TurtleScreen(canvas)
    help_t = turtle.RawTurtle(help_screen)
    help_t.penup()
    help_t.hideturtle()
    help_t.speed('fastest')

    width, height = help_screen.screensize()
    line_height = 20
    y = height // 2 - 30
    for s in ("Click on cells to make them alive or dead.",
              "Keyboard commands:",
              " E)rase the board",
              " R)andom fill",
              " S)tep once or",
              " C)ontinuously -- use 'S' to resume stepping",
              " Q)uit"):
        help_t.setpos(-(width / 2), y)
        help_t.write(s, font=('sans-serif', 14, 'normal'))
        y -= line_height
    

def main():
    display_help_window()

    scr = turtle.Screen()
    turtle.mode('standard')
    xsize, ysize = scr.screensize()
    turtle.setworldcoordinates(0, 0, xsize, ysize)

    turtle.hideturtle()
    turtle.speed('fastest')
    turtle.tracer(0, 0)
    turtle.penup()

    board = LifeBoard(xsize // CELL_SIZE, 1 + ysize // CELL_SIZE)

    # Set up mouse bindings
    def toggle(x, y):
        cell_x = x // CELL_SIZE
        cell_y = y // CELL_SIZE
        if board.is_legal(cell_x, cell_y):
            board.toggle(cell_x, cell_y)
            board.display()

    turtle.onscreenclick(turtle.listen)
    turtle.onscreenclick(toggle)

    board.makeRandom()
    board.display()

    # Set up key bindings
    def erase():
        board.erase()
        board.display()
    turtle.onkey(erase, 'e')

    def makeRandom():
        board.makeRandom()
        board.display()
    turtle.onkey(makeRandom, 'r')

    turtle.onkey(sys.exit, 'q')

    # Set up keys for performing generation steps, either one-at-a-time or not.
    continuous = False
    def step_once():
        nonlocal continuous
        continuous = False
        perform_step()

    def step_continuous():
        nonlocal continuous
        continuous = True
        perform_step()

    def perform_step():
        board.step()
        board.display()
        # In continuous mode, we set a timer to display another generation
        # after 25 millisenconds.
        if continuous:
            turtle.ontimer(perform_step, 25)

    turtle.onkey(step_once, 's')
    turtle.onkey(step_continuous, 'c')

    # Enter the Tk main loop
    turtle.listen()
    turtle.mainloop()

if __name__ == '__main__':
    main()

Code Discussion

The LifeBoard class has a state attribute that’s a set of (X,Y) tuples that contain live cells. The coordinate values can vary between 0 and an upper limit specified by the xsize and ysize attributes.

The step() method computes a single Life generation. It loops over the entire board, and for each cell the code counts the number of live cells surrounding it. A new set is used to record the cells that are live in the new generation, and after the whole board has been scanned, the new set replaces the existing state.

The size of the state set is therefore proportional to the number of live cells at any given time. Another approach would be just to have an N x N array representing the board, which would require a fixed amount of memory.

If there are only a few live cells on a large board, most of the time will be spent scanning empty areas of the board where we know nothing is going to happen. Cells never come alive spontaneously, without any live neighbours. Therefore, one minor optimization is to record the minimum and maximum coordinates of live cells, and then limit the scanning accordingly. An entirely different approach called Hashlife represents the board as a quadtree, a 2-dimensional tree structure, and relies on large Life patterns often containing many copies of similar structures. (See the references for an explanation of Hashlife.)

Lessons Learned

Part of what makes Life so fascinating is that it’s easy to ask questions and then try to answer them. For example, if you start with a straight line of N cells, which values of N produce interesting patterns? What if you make squares, or two lines of cells? This leads to asking more theoretical questions: are there Life patterns that can make copies of themselves? How fast can a spaceship move? You can get an idea of the complexity hiding inside Life by exploring some of the references for this section.

You may wonder if there’s anything special about the rules that Conway chose for Life. For example, what if live cells survived when they had four neighbours instead of dying? You can easily experiment with different rules by modifying the life.py program. Mirek Wojtowicz has written a list of alternate rules at http://www.mirekw.com/ca/rullex_life.html and comments on the different properties of the resulting simulations.

People have also created many other cellular automata that change other aspects such as:

  • having the world be a 3-dimensional grid of cubes or a 1-dimensional line of cells instead of a 2-dimensional grid.
  • use a triangular or hexagonal grid instead of a square one.
  • have multiple colours for live cells; a newborn cell’s can either be the majority colour of its neighbours, or
  • have the cells containing decimal values between 0 and 1, instead of restricting values to only 0 and 1.

Fairly soon after Life was invented, Conway proved that there existed Life patterns that were equivalent to a Turing Machine and therefore could carry out any computable function. In April 2000, Paul Rendell actually constructed a Life pattern that behaved like a Turing machine.

References

Relevant web pages, books, with an annotation about why it’s notable or worthwhile.

http://www.math.com/students/wonders/life/life.html
An introductory article by Paul Callahan. The web page includes a Java applet that’s similar to our Python application.
http://www.nytimes.com/1993/10/12/science/scientist-at-work-john-h-conway-at-home-in-the-elusive-world-of-mathematics.html
A New York Times profile of mathematician John H. Conway, who invented Life.
http://www.ibiblio.org/lifepatterns/october1970.html
A copy of Martin Gardner’s 1970 Scientific American article that started it all.
http://home.interserv.com/~mniemiec/lifeterm.htm
A glossary of Life terminology.
http://www.conwaylife.com/wiki/
LifeWiki contains over a thousand Wiki articles about Life, including definitions of terms and descriptions of various patterns.
http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478
An April 2006 article by Tomas G. Rokicki that explains the HashLife algorithm and implements it in Java.