Conway’s Game of Life
Volume Number: 14
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:
1. Each cell with fewer than two neighbors dies from isolation.
2. Each cell with four or more neighbors dies from overcrowding.
3. Each cell with two or three neighbors survives.
For a location that is empty:
1. 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
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;