You may have heard that mathematician John Conway died last April. To his everlasting dismay, most people only know him for his “game” of Life (which he considered trivial and inferior to his real mathematical work). Unfortunately for Conway, his Life game is fascinating.
To honor his passing, I whipped up a Python version that I thought I’d share. Python is about the only language I’ve used a lot in which I’ve never implemented Life, so high time I did, right?
I’ll start by quickly going over the basic Life algorithm (for a more detailed look see the wiki page or any number of other sources). Then I’ll explore a very basic “first draft” (Step 1: Make it work). Finally I’ll show you a ConwayLife class (Step 2: Make it work right).
§
Life is easily summed up by a set of simple rules:
- It’s played on a 2D grid of “cells”.
- A cell can “alive” or “dead” (on or off).
- The game proceeds in cycles (or clock ticks).
- On each cycle, each cell does a calculation:
- If it’s alive, it needs 2 or 3 living neighbors to stay alive.
- If it’s dead, if it has exactly 3 living neighbors, it’s reborn.
- A game starts with a (typically random) cell pattern.
So the basic algorithm involves modeling the 2D grid of cells (initializing them with a starting pattern), operating on a cycling basis, and implementing the rules from #5 and #6 in the list above.
Pretty simple, really. It’s a good student assignment because it really is simple, but it contains a lurking gotcha to offer a little challenge.
The grid is an array or matrix, of course. Cells can have a value zero or one. Each cycle we scan the array, looking at each cell. We count that cell’s living neighbors and apply the appropriate rule, depending on whether the cell was initially alive or dead.
And therein lies the gotcha. If we do a cell and immediately apply the rule to change that cell, then that cell’s neighbors see a different value, and their count, when we get to them, will be wrong. That breaks the game.
So on the first pass we need to buffer the neighbor counts for each cell in a separate matching array. Then we make a second pass to apply those counts per the rules.
When it’s done right, it looks like this:
§ §
These days, a common way to implement Life is to display the grid live, as the program calculates. This obviously requires a graphics environment.
An alternate way is to have the program generate a series of frame files — actual images, if possible, but numeric data files might be inputs some other app could convert to images. (RAW would be one possible way to do that.)
There is a common Python library, PIL, that can generate PNG files, so I’m using that here. The program will generate one PNG file for each cycle of the game. We can use a viewer to see them in rapid succession, or import them to an app that can create a video.
§
We’ll start with a few global variables and a routine to initialize the grid:
CellSize = (4, 4)
LiveColor = (0, 0, 0)
DeadColor = (0xcf,0xdf,0xff)
NC = 1280//CellSize[0]
NR = 720//CellSize[1]
Buf1 = []
Buf2 = []
def initialize_buffer (percentage=0.5):
global Buf1, Buf2
Buf1 = [[0 for c in range(NC)] for r in range(NR)]
Buf2 = [[0 for c in range(NC)] for r in range(NR)]
for r in range(NR):
for c in range(NC):
Buf1[r][c] = (1 if random() < percentage else 0)
#
The percentage specifies how many cells to initialize to alive when the game starts. The default is 50% (which is high; closer to 15% works better).
Buf1 is the grid; Buf2 is the buffer for living neighbor counts. NC and NR are the number of columns and rows. They’re calculated by dividing the desired image size by the cell size.
Now that we’ve defined the data model, working from the bottom up on functionality, we know we need to be able to count neighbors. Each cell potentially has eight, but we need to think about cells at the edges.
For now, cells along the edge have fewer neighbors because of the edge. Corner cells have only three, and edge cells have five. Later we’ll wrap the edges so all cells have eight neighbors.
def count_neighbors (row, col):
total = 0
# Top row...
if 0 < row:
total += (Buf1[row-1][col-1] if 0 < col else 0)
total += (Buf1[row-1][col])
total += (Buf1[row-1][col+1] if col < (NC-1) else 0)
# Middle row...
total += (Buf1[row][col-1] if 0 < col else 0)
total += (Buf1[row][col+1] if col < (NC-1) else 0)
# Bottom row...
if row < (NR-1):
total += (Buf1[row+1][col-1] if 0 < col else 0)
total += (Buf1[row+1][col])
total += (Buf1[row+1][col+1] if col < (NC-1) else 0)
Buf2[row][col] = total
return total
#
This code just checks to see if a grid reference (grid[r][c]) would read off the grid (in which case it would be an out-of-bounds array index error). If it would, it just assumes a zero (dead virtual neighbor cell).
It returns the number of living neighbor cells given a grid reference.
The next piece we need is something to apply the rules:
def apply_rule (row, col):
m = Buf1[row][col]
n = Buf2[row][col]
if 0 < m:
return (1 if (n in [2,3]) else 0)
return (1 if n == 3 else 0)
#
This also takes a grid reference. It returns 1 or 0, which determines the cell’s new status, alive or dead, respectively.
The last building block does the two step process of, first doing all the neighbor counts, and then applying the rules.
def life_cycle ():
# Do neighbor counts...
for r in range(NR):
for c in range(NC):
count_neighbors(r,c)
# Apply results...
for r in range(NR):
for c in range(NC):
Buf1[r][c] = apply_rule(r,c)
#
It should be pretty self-explanatory.
Lastly, we need a function to cycle the frames:
def do_life (cycles=20, percentage=0.5):
initialize_buffer(percentage)
for n in range(cycles):
life_cycle()
fn = 'life-%05d.png' % n
create_image_file(fname=fn, fpath=ImgsPath)
#
And we’re done. Just call do_life() with the desired parameters, and it’s off to the races.
The create_image_file() function depends on exactly how you want to create your images. Here’s one that uses PIL:
def create_image_file (fname, fpath=ImgsPath, mode='PNG'):
filename = path.join(fpath, fname)
dims = (NC*CellSize[0], NR*CellSize[1])
im = Image.new('RGB', dims, (255,255,255))
draw = ImageDraw.Draw(im)
for y in range(NR):
for x in range(NC):
v = Buf1[y][x]
cc = LiveColor if 0<v else DeadColor
x0 = x * CellSize[0]
y0 = y * CellSize[1]
for yy in range(CellSize[1]):
for xx in range(CellSize[0]):
draw.point((x0+xx,y0+yy), fill=cc)
im.save(filename, mode)
#
See the PIL docs if you have questions.
§ §
There are a couple of changes we can make right away.
One is to notice that apply_rule doesn’t really do what it says; it doesn’t apply anything. The count_neighbors function modifies Buf2, and apply_rule already accesses both buffers, so it makes sense to have it actually apply the rule:
def apply_rule (row, col):
m = Buf1[row][col]
n = Buf2[row][col]
if 0 < m:
v = (1 if (n in [2,3]) else 0)
else:
v = (1 if n == 3 else 0)
Buf1[r][c] = v
return v
#
And now the life_cycle function looks much neater:
def life_cycle ():
# Do neighbor counts...
for r in range(NR):
for c in range(NC):
count_neighbors(r,c)
# Apply results...
for r in range(NR):
for c in range(NC):
apply_rule(r,c)
#
The more significant change involves the count_neighbors function:
def count_neighbors (row, col):
total = 0
left = (Cols-1) if col == 0 else (col-1)
right = (col+1) if col < (Cols-1) else 0
top = (Rows-1) if row == 0 else (row-1)
bot = (row+1) if row < (Rows-1) else 0
# Top row...
total += Buf1[top][left]
total += Buf1[top][col]
total += Buf1[top][right]
# Middle row...
total += Buf1[row][left]
total += Buf1[row][right]
# Bottom row...
total += Buf1[bot][left]
total += Buf1[bot][col]
total += Buf1[bot][right]
Buffer2[row][col] = total
return total
#
We calculate the left and right columns as well as the top and bottom rows. In doing so, if an access goes beyond the grid, we wrap around to the other side. This joins the left and right edges and the top and bottom edges.
Geometrically, the space is now a flattened torus.
§ §
That might be enough for this time. Next time I’ll show you the class ConwayLife and some other improvements to the code.
∅
The Hard-Core Coder 