Conway’s Game of Life
Volume Number: 14 (1998)
Issue Number: 3
Column Tag: Programming Techniques
Conway's Game of Life
by F.C. Kuechmann, Vancouver, WA
Another look at a familiar recreation
The Game
The Game of Life is a "cellular automaton'" invented by British mathematician John Horton Conway. It first became widely known when it was featured in Martin Gardner's column in Scientific American in October 1970 and February 1971. Since then it has taken on a life of its own (groan...), so to speak. It's been discussed in that publication numerous times and elsewhere, including several books targeted for audiences ranging from popular to professional scientific and in articles of publications ranging from the popular audience oriented Omni to obscure mathematics journals. Byte has ventured into the subject on several occasions, as have other computer magazines. See the references for a partial list.
On the Internet, information on the game and versions in languages ranging from C to Java are widely available for online execution or download. A web search on the phrase "conway's game of life" will turn up numerous links to follow and explore. There's also a six generation life editor, with THINK Pascal sourcecode, on Celestin's Apprentice 5 CD-ROM, that's useful for exploring simple patterns of cell placement.
The Life game field is a two-dimensional matrix on which cells live, die or multiply in accordance with a small number of simple rules. The cells form various patterns as the rules are repeatedly applied to the matrix. It is these patterns that make the Game of Life interesting.
The Rules
For a matrix location that is occupied by a living cell:
- Each cell with fewer than two neighbors dies from isolation.
- Each cell with four or more neighbors dies from overcrowding.
- Each cell with two or three neighbors survives.
For a location that is empty:
- Each cell with three neighbors births a living cell.
This Version
I implemented Conway's game in CodeWarrior Pro Pascal on a PowerPC Mac 6500 using a 60 by 100 two-dimensional Boolean array. This array is mapped to a 300 pixel high, 500 pixel wide area with a cell size of 5 pixels square, as shown in Figure 1. The Figure 1 screenshot was taken after 18 generations in Random-Static mode with 500 live cells to start.
Figure 1. The game field.
At the lower left of Figure 1 is a quad, 3-cell oscillator, and in several places we see single, 3-cell oscillators, and static 4-cell blocks and 6-cell groups. The 3-cell binary (2-state) oscillator and 4-cell block are perhaps the most common regular patterns formed in the Game of Life when the field is initially randomly populated with a sufficiently large number of cells. Another common pattern is the 5-cell, 4-state glider whose states are shown in Figure 2.
Figure 2. The states of the 5-cell, 4-state glider.
The 5-cell, 4-state glider eventually becomes a static, 4-cell block at the edge of the field if enough generations are allowed to elapse.
Figure 3 shows the stages of development of the quad, three-cell binary oscillator. Starting from a block of either nine or ten cells (the center position can be either populated or unpopulated) at left, the generations proceed rightward. The sixth and seventh (two rightmost) generations alternate indefinitely.
Figure 3. Stages of the quad, three-cell binary oscillator.
Another interesting starting cell pattern is a straight vertical or horizontal line several cells long -- ten is a good number to start with and evolves into an oscillator with 15 states. "H" patterns also give interesting results, five cells to each vertical line, three to five cells in the crossbar.
Some Source Code Conventions
The use of descriptive names for constants, variables, functions and procedures makes the CodeWarrior Pascal sourcecode largely self-documenting. Constants and variables that are global to the entire program begin with the letters "ggc" (constants) or "gg" (variables), followed by at least one uppercase alpha or numeric character. They are defined in the globals unit. Constants and variables global to a single unit begin with "gc" or "g", followed by at least one uppercase alpha or numeric character. The MenuStuff unit holds menu routines, EventStuff the event handlers, etc.
Running Life
On the menu bar are the standard Apple, File and (inactive) Edit menus, plus menus for Speed, Generations, Cells, Color and Delay. The File menu offers only the Quit option. The Speed menu offers Wait Go button, Very Slow, Slow, Medium and Fast.
Speed is varied by changing the amount of delay invoked between generations. The Wait Go button option enables stepping a single generation at a time.
The Generations menu allows selection of the maximum number of generations executed per cycle. Default is 25, with options of 1, 5, 10, 25, 50, 75, 100 and 200. A cycle terminates if a static condition is reached, regardless of the generations setting. In random mode, the play field clears after the selected number of generations have passed. The field is then randomly repopulated and, after a two second pause, the generations cycle repeats.
In manual mode, operation pauses and can be restarted by clicking the Go button. During pauses, you can add or remove living cells by clicking their locations with the mouse.
The Cells menu allows selection of the number of initial live cells in random mode. Default is 500, with options of 175 to 525 in 25 cell increments.
The Color menu allows selection of live cell color. The options are Random, plus the eight standard Macintosh colors -- White, Black, Yellow, Magenta, Red, Cyan, Green and Blue.
The Delay menu sets the delay after each cycle. Default is 5 seconds, with options ranging from None to 30 Seconds in 5 second increments, plus Wait (for the Go button to be pushed).
The Modes
Life has four basic operating modes -- manual, random, static and dynamic -- that are invoked in pairs of manual or random with static or dynamic. In manual mode, living cells are birthed or killed by clicking their locations on the game field, then processed by Conway's rules when the Go button is clicked. Listing 1 shows the mouse button-processing code from the EventStuff unit. The code first tests for routine mouse locations like the menu, system window and close box via a case-statement. The last case-statement option, inContent, tests first to see if a button has been clicked. If so, it calls the DoButtons procedure to process, otherwise it tests to see if the mouse pointer is in the active game field. If it is, the code that births or clears the cells is executed.
Listing 1. HandleMouseDown.
HandleMouseDown
procedure HandleMouseDown;
var
whichWindow: WindowPtr;
thePart, X, Y, row, col : integer;
menuChoice: longint;
thePoint : Point;
theControl : ControlHandle;
begin
ggButtonFlag := TRUE;
thePart := FindWindow(gTheEvent.where, whichWindow);
case thePart of
inMenuBar:
begin
menuChoice := MenuSelect(gTheEvent.where);
HandleMenuChoice(menuChoice);
end;
inSysWindow:
SystemClick(gTheEvent, whichWindow);
inDrag:
begin
DragWindow(whichWindow, gTheEvent.where,
qd.screenBits.bounds);
ggInBkGndFlag := TRUE; {force redraw}
RedrawBoard;
end;
inGoAway:
ggDoneFlag := TRUE;
inContent:
begin
GetMouse(thePoint);
thePart := FindControl(thePoint,
whichWindow,theControl);
if thePart <> 0 then
DoButtons(theControl)
else
begin
{locate mouse pointer; if it's in the}
{playing field, birth or kill cell at}
{the mouse pointer}
with thePoint do
begin
Y := v;
X := h;
end;
if (X < ggWindRect.right) and
(X > ggWindRect.left) and
(Y < ggWindRect.bottom) and
(Y > ggWindRect.top) then
begin
Y := Y + 5;
X := X + 3;
row := Y div ggcLifeSize;
col := X div ggcLifeSize;
if ggLifeBoard[row, col] = FALSE then
begin
MakeLiveCell(row, col);
ggLifeBoard[row, col] := TRUE;
Inc(ggCellCount);
UpdateCellCount;
end
else
begin
KillCell(row, col);
ggLifeBoard[row, col] := FALSE;
Dec(ggCellCount);
UpdateCellCount;
end;
end;
end;
end; {inContent}
end; {case}
ggButtonFlag := FALSE;
end;
In random mode, cells are birthed randomly by the program at the start of each cycle (length set via the Generations menu). That code is shown in Listing 2.
Listing 2. NewCell and FillRandom.
NewCell
Procedure NewCell;
{generates a pair of random integers 1..60 and 1..100
then tests the matrix location defined by those numbers
to see if it is already occupied by a cell. The process
continues until the necessary cells are created}
var+
X, Y, tryCount : longint;
row, col: integer;
begin
tryCount := 0;
repeat
{divisors 218 and 131 determined by experiment}
Y := (Random + 32768) div 218;
X := (Random + 32768) div 131;
row := Y div ggcLifeSize;
col := X div ggcLifeSize;
if row < 2 then
row := 2
else if row > 59 then
row := 59;
if col < 2 then
col := 2
else if col > 99 then
col := 99;
LongInc(tryCount);
until (ggLifeBoard[row, col] = FALSE) or
(tryCount > 10000000);
if ggLifeBoard[row, col] = FALSE then
begin
ggLifeBoard[row, col] := TRUE;
MakeLiveCell(row, col);
Inc(ggCellCount);
UpdateCellCount;
end;
end; { NewCell }
FillRandom
procedure FillRandom;
{births starting number of cells by repeatedly calling NewCell}
begin
{erase just count nums}
ClearCellCountRect;
repeat
NewCell;
until ggCellCount > (ggStartCellCount - 1);
end;
The FillRandom procedure calls the NewCell procedure in a loop until the required number of randomly-located cells have been birthed. NewCell generates two random integers, scales and converts them to a location in the 60 by 100 matrix, then tests to see if that location holds a live cell. If so, the selection process is repeated; otherwise a new cell is birthed at the selected location and the matrix location marked TRUE.
Once Life begins applying Conway's rules the program can be paused at any time by clicking the Pause button. During pauses cells can be killed or birthed by clicking their locations regardless of the manual/random mode setting.
In applying Conway's rules to the matrix, there is a choice of two approaches: static and dynamic. Both methods count the number of live cell neighbors had by each location in the 6000-cell matrix using the code in Listing 3 from the Action unit.
Listing 3. CountNeighbors.
CountNeighbors
procedure CountNeighbors(row, col :integer;
var neighbors: integer);
{counts the number of live cell neighbors of matrix location
defined by row and column; returns count in integer neighbors.}
begin
neighbors := 0;
{up}
if row > 1 then
if ggLifeBoard[row - 1, col] then
Inc(neighbors);
{down}
if row < ggcMaxRow then
if ggLifeBoard[row + 1, col] then
Inc(neighbors);
{left}
if col > 1 then
if ggLifeBoard[row, col - 1] then
Inc(neighbors);
{right}
if col < ggcMaxCol then
if ggLifeBoard[row, col + 1] then
Inc(neighbors);
{downright}
if (row < ggcMaxRow) and (col < ggcMaxCol) then
if ggLifeBoard[row + 1, col + 1] then
Inc(neighbors);
{upleft}
if (row > 1) and (col > 1) then
if ggLifeBoard[row - 1, col - 1] then
Inc(neighbors);
{downleft}
if (row < ggcMaxRow) and (col > 1) then
if ggLifeBoard[row + 1, col - 1] then
Inc(neighbors);
{upright}
if (row > 1) and (col < ggcMaxCol) then
if ggLifeBoard[row - 1, col + 1] then
Inc(neighbors);
end;
The code uses a series of conditionals to test matrix positions neighboring the location passed by row and column numbers, while accounting for boundary conditions.
The static mode code that calls the code in Listing 3 is given in Listing 4. A local array is used to store changes until the scan of the matrix is completed. Then the field is updated, along with the global array. The SetMaxCol and SetMaxRow procedures called near the beginning of Listing 4 set local variables maxCol and maxRow equal to global constants ggcMaxCol and ggcMaxRow. CodeWarrior Pascal won't let me use the global constants directly in the for loop statements, demanding local variables or constants. CodeWarrior Pascal also won't allow a simple assignment such as: maxCol := ggcMaxCol. I wrote procedures, included in the Misc unit, to do the assignments by incrementing or decrementing the variable passed to it in a loop until it equals the global constant.
Listing 4. CheckStaticNeighborhood.
CheckStaticNeighborhood
procedure CheckStaticNeighborhood;
{Tests the 60 row, 100 col grid by first copying the global
boolean array to a samesize local array. CountNeighbors
is called for each matrix position. When cells need
to be birthed or killed, changes are flagged in the local
array only until the entire board has been scanned. Then
the two arrays are compared and the board updated. The
local array is copied to the global to update it.}
var
neighbors, col, row, maxRow, maxCol : integer;
lifeBoard : array[1..60, 1..100] of boolean;
begin
SetMaxCol(maxCol); {set maxCol = ggcMaxCol}
SetMaxRow(maxRow); {set maxRow = ggcMaxRow}
{copy global array into local array}
for col := 1 to maxCol do
for row := 1 to maxRow do
lifeBoard[row, col] := ggLifeBoard[row, col];
gChangeFlag := FALSE;
for col := 1 to maxCol do
for row := 1 to maxRow do
begin
CountNeighbors(row, col, neighbors);
{update local array from neighbor count}
if (neighbors > ggcMaxNeighbors) and
ggLifeBoard[row, col] then
begin
lifeBoard[row, col] := FALSE;
gChangeFlag := TRUE;
end
else if (neighbors < ggcMinNeighbors) and
ggLifeBoard[row, col] then
begin
lifeBoard[row, col] := FALSE;
gChangeFlag := TRUE;
end
else if (ggLifeBoard[row, col] = FALSE) and
(neighbors = ggcBirthNeighbors) then
begin
lifeBoard[row, col] := TRUE;
gChangeFlag := TRUE;
end;
end;
{update the play field}
for col := 1 to maxCol do
for row := 1 to maxRow do
begin
if (lifeBoard[row, col] = TRUE) and
(ggLifeBoard[row, col] = FALSE) then
begin
{birth a new cell in an unoccupied location}
Inc(ggCellCount);
MakeLiveCell(row, col);
end
else if (lifeBoard[row, col] = FALSE) and
(ggLifeBoard[row, col] = TRUE) then
begin
KillCell(row, col);
Dec(ggCellCount);
end;
ggLifeBoard[row, col] := lifeBoard[row, col];
end;
ClearCellCountRect; {erase just count nums}
UpdateCellCount;
end;
Listing 5 and Listing 6 perform similar functions for the dynamic mode, the key differences being that, in dynamic mode, the relative positions of the row and column loops is significant, whereas in static mode the order makes no difference. The global boolean variable ggColumnIndexFlag, toggled by clicking the Row/Column button, determines the execution order of the loops.
In dynamic mode, the matrix is updated immediately after counting neighbors. Listing 5 calls Listing 3 to do the count, then calls Listing 6 to perform the update.
Listing 5. CheckDynamicNeighborhood.
CheckDynamicNeighborhood
procedure CheckDynamicNeighborhood;
{calls CountNeighbors for each matrix location
and then calls UpDateBoard to make changes immediately;
results vary with the relative positions of the row and
column loops.}
var
neighbors, col, row, maxRow, maxCol : integer;
ticks : longint;
begin
SetMaxCol(maxCol); {set maxCol = ggcMaxCol}
SetMaxRow(maxRow); {set maxRow = ggcMaxRow}
gChangeFlag := FALSE;
if ggColumnIndexFlag then
begin
for col := 1 to maxCol do
for row := 1 to maxRow do
begin
CountNeighbors(row, col, neighbors);
UpdateBoard(row, col, neighbors);
end;
end
else
begin
for row := 1 to maxRow do
for col := 1 to maxCol do
begin
CountNeighbors(row, col, neighbors);
UpdateBoard(row, col, neighbors);
end;
end;
end;
Listing 6. UpdateBoard.
UpdateBoard
procedure UpdateBoard(row, col, neighbors : integer);
{called by CheckDynamicNeighborhood after each call to
CountNeighbors to make any needed changes to the board.}
begin
if (neighbors > ggcMaxNeighbors) and
ggLifeBoard[row, col] then
begin
KillCell(row, col);
ggLifeBoard[row, col] := FALSE;
gChangeFlag := TRUE;
Dec(ggCellCount);
UpdateCellCount;
end
else if (neighbors < ggcMinNeighbors) and
ggLifeBoard[row, col] then
begin
KillCell(row, col);
ggLifeBoard[row, col] := FALSE;
gChangeFlag := TRUE;
Dec(ggCellCount);
ClearCellCountRect; {erase just count nums}
UpdateCellCount;
end
else if (ggLifeBoard[row, col] = FALSE) and
(neighbors = ggcBirthNeighbors) then
begin
ggLifeBoard[row, col] := TRUE;
MakeLiveCell(row, col);
gChangeFlag := TRUE;
Inc(ggCellCount);
UpdateCellCount;
end;
end;
With the default static approach, which conforms more closely to the previously published versions and discussions of Conway's game that I have seen, changes are not made to the matrix until it has been completely scanned. The dynamic approach makes changes immediately. The default mode combination is manual-static.
Playing the Game of Life
The opening screen is a blank field with a control panel to the right. The control panel shows two data windows, cell count and generations. There are six buttons initially labeled Row, Clear, Dynamic, Random, Go and Quit. In manual mode, cells are birthed or killed by clicking their locations with the mouse. When the desired cell arrangement is in place, clicking the Go button begins execution. Go changes to Pause and is used to temporarilly interrupt execution. The Clear button, enabled only in manual mode, removes all living cells from the game field.
In random mode, the Random button is relabeled to Manual, and clicking the Go button initiates automatic operation that continues uninterrupted until manual mode is reselected by clicking the Manual button, the Pause button is clicked, or operation is terminated by clicking Quit, typing Command-Q, or selecting Quit from the File menu.
In Dynamic mode, the button inially labelled Row is enabled. It is used to switch the relative positions of nested row and column loops. In the default state, the outer loop is indexed by columns, the inner by rows. Clicking the Row button reverses the two and relabels the button to read Column.
The static approach yields more oscillator and glider patterns. The button initially labelled Dynamic is used to toggle between the two approaches. In Dynamic mode the button is relabeled Static and can be clicked to reselect that operating mode.
Enhancements
The most obvious way to add to the existing program would be to allow menu selection of some of the more interesting initial patterns, such as the 5-cell, 4-state glider, 10 live cells in a horizontal or vertical row. Live-cell co-ordinates for the patterns could be stored in records. Placing the cells would simply involve calling the MakeLiveCell procedure the required number of times with the proper row and column values.
Source Code
Source code in CodeWarrior Pascal and CodeWarrior IDE 2.0 projects is available for download from Mactech. Color Quickdraw is required.
Bibliography and References
- Buckingham, David J. "Some Facts of Life." Byte. December 1978.
- BYTE magazine: Sep 75, Oct 75, Dec 75, Jan 76, Jan 79, Apr 79, Oct 80, Jul 81.
- Gardner, Martin. "On cellular automata, self-reproduction, the Garden of Eden and the game 'Life.'" Scientific American, February 1971.
- Gardner, Martin. "The Fantastic Combinations of John Conway's New Solitaire Game 'Life.'" Scientific American, October 1970.
- Scientific American: Nov 70, Jan 71, Mar 71, Apr 71, Nov 71, Jan 72, Dec 75, Mar 84, May 85, Feb 87, Aug 88, Aug 89, Sep 89, Jan 90.
- Gardner, Martin. "The Game of Life." Wheels, Life and other Mathematical Amusements. W.H. Freeman 1983. ISBN 0-7167-1589-9.
- Morris, Scot. "The Game of Life," Omni. October 1984.
- Poundstone, William. The Recursive Universe. William Morrow & Co., 1985. ISBN 0-688-03975-8.
- Berlekamp, Conway, and Guy: Winning Ways (for your Mathematical Plays), Volume 2, (c)1982. ISBN 0-12-091152-3.
- Dewdney, A.K.: The Armchair Universe, (c)1988. ISBN 0-7167-1939-8.
F.C. Kuechmann, fk@aone.com, is a programmer, hardware designer and consultant with degrees from the University of Illinois at Chicago and Clark College. He is building a programmers' clock that gives the time in hexadecimal.
