The Core Algorithm
The Game of Life runs on a simple set of rules, based around cells in a grid and their neighbours. Cells may be dead or alive, and whether they live or die is decided in a generation, an iteration in the algorithm.
The rules of this algorithm are as follows:
- Any live cell with fewer than two live neighbours dies, as if by underpopulation.
- Any live cell with two or three live neighbours lives on to the next generation.
- Any live cell with more than three live neighbours dies, as if by overpopulation.
- Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
From these simple rules we can form the following pseudocode to describe the process.
if the cell is dead, and number of neighbours equal to 3
it becomes live
otherwise if the cell is alive, and the number of neighbours less than 2 but more than 3
it dies
Implementing the Core Algorithm
So we have broken down the process, but to implement this within Python is much more complex, and I do the following steps:
- Define the size of our grid of cells.
- Create a data structure to store the cell states.
- Calculate a generation in a loop.
-
- Iterate over every cell in the 2d list.
- Count the neighbours.
- Calculate and store the changes.
- Apply the changes.
Now that we've broken down the basic steps, we can examine the Python code required to calculate a generation below.
Note that I have adapted my code to better fit this section.
#Define the size of our grid
xSteps = 100
ySteps = 100
#Creating a data structure to store our cell states, and changes
cells = [[0 for i in range(ySteps)] for j in range(xSteps)]
changes = []
#Calculate a generation in a loop
for x in range(xSteps): #Iterate over each column
for y in range(ySteps): #Iterate over each cell in a column
#Calculate count of neighbours
cell = cells[x][y]
neighbours = 0
for i in range(-1, 2):
for j in range(-1, 2):
x1 = x + i
y1 = y + j
neighbour = cells[x1][y1]
#Check if neighbour is out of bounds
if x1 == -1 or y1 == -1 or x1 >= xSteps or y1 >= ySteps:
pass
#Don't count the original cell as a neighbour
elif x1 == x or y1 == y:
pass
#Outcomes are the same past count of 4, so end early
elif n >= 4:
break
elif neighbour == 1:
neighbours += 1
#Check if a change is required
if cell == 0 and neighbours == 3:
changes.append((x, y, 1))
elif cell == 1 and neighbours < 2 or neighbours > 3:
changes.append((x, y, 0))
#Apply changes
for i in changes:
x = changes[i][0]
y = changes[i][1]
cells[x][y] = changes[i][2]
Most of this implementation is self explanatory, I use a 2d list generated with a list comprehension to emulate a physical grid of cells and store the states, giving an intuitive x, y coordinate system
to work with when iterating through it by indexes.
Calculating neighbours is done using the range(-1, 2) to begin at the cell index one row and one column above,
preventing the current cell being counted by testing if the neighbour x and y are equal to that of the current cell. Checking for literal edge cases, where the neighbour would be out of bounds,
by making sure x and y coordinates are within the boundaries of the 2d list. I also cut off the neighbour search at 4 as not to waste time checking further as the outcome isn't impacted.
Changes are stored as tuples of x coordinate, y coordinate and new value, only if a change is required. Then applied only after all changes are calculated. I could have built up a new grid array reflecting
the next generation rather than modifying the current one but this method seemed like it would be less resource intensive.
Graphical Implementation
As previously stated, I use the Tkinter module to create a GUI and render my implementation, which was considerably more work than implementing the core algorithm.
class gameWindow(tk.Canvas):
def __init__(self, master, width, height, *args, **kwargs):
super().__init__(master, width= width, height= height, *args, **kwargs)
self.grid(row=0, column= 0)
self.width = width
self.height = height
self.play = False
self.debug = False #Enables limited generations and gen ms recording
self.debugLog = []
self.debugCounter = 0
self.size = 20 #Size in px of grid cells
self.cellStates = self.makeGrid() #Create rectangle objects for UI and matching array of state values.
self.changes = []
def makeGrid(self):
#Calculate how many cells to generate and gap left on screen edges
xSteps = self.width // self.size - 1
ySteps = self.height // self.size - 1
border = self.size // 2
cellIndices = [[] for i in range(xSteps)]
#Generate cells in accordance with calcs and collect their ids in an array so we know their coordinates.
for x in range(0, xSteps):
for y in range(0, ySteps):
x0 = x * self.size + border
y0 = y * self.size + border
x1 = x * self.size + self.size + border
y1 = y * self.size + self.size + border
cell = self.create_rectangle(x0, y0, x1, y1, fill= "white", tags= (f"{x},{y}."))
self.tag_bind(cell, '<Button-1>', self.onCellClick) #Allows toggling state via click
cellIndices[x].append(0)
return cellIndices
def pauseSim(self):
#Toggle play constant, restart recursive sim loop if stopped.
if self.play == True:
self.play = False
frameControls.playPauseText.set("Play")
elif self.play == False:
self.play = True
frameControls.playPauseText.set("Pause")
self.simulateGenerationThreaded()
def onCellClick(self, event):
#Pull cell id with 'current' tag denoting mouseover
cell = event.widget.find_withtag('current')[0]
tag = self.itemcget(cell, "tag")
xEnd = tag.find(",")
yEnd = tag.find(".")
x = int(tag[0:xEnd])
y = int(tag[xEnd + 1:yEnd])
#toggle fill
if self.itemcget(cell, "fill") == "black":
self.itemconfig(cell, fill= "white")
self.cellStates[x][y] = 0
else:
self.itemconfig(cell, fill= "black")
self.cellStates[x][y] = 1
class controlFrame(Frame):
def __init__(self, master):
super().__init__(master)
self.grid(row= 1, column= 0)
self.elapsedTime = tk.StringVar()
self.framesPer = tk.StringVar()
self.playPauseText = tk.StringVar(value="Play")
self.pauseButton = tk.Button(self, textvariable= self.playPauseText, command= gameView.pauseSim)
self.pauseButton.grid(row=0, column= 0)
self.frameTimeLabel = tk.Label(self, textvariable= self.elapsedTime)
self.frameTimeLabel.grid(row=0, column= 1)
self.framesPerLabel = tk.Label(self, textvariable= self.framesPer)
self.framesPerLabel.grid(row= 0, column= 2)
The GUI consists of two sub-classes, the control panel and a canvas. The control panel having a play/pause button to start and stop the simulation, and a counter showing how many milliseconds a generation took to calculate.
The canvas subobject, gameWindow is the core of the application, with several methods, some not included here. They facilitate user interactions, generation of the grid, and more we'll touch on later.
I'll give a brief outline of how this differs with out previous code below:
- Variables define the height and width of the area, and a cell size in pixels to decide the size and density of our playspace.
- Tkinter rectangle objects are generated to represent the cells, with tags of their x and y coordinate attached and an on-click event bound.
- Object pointers are stored in a 2d array as our states of 0 and 1 were previously.
- The onCellClick method uses the object tags and on click events to change a cell's state based on user input.
Intergrating the Core Algorithm
So we have the core code to calculate our generations, and a GUI with controls and a grid system which can represent the cells, now comes the code to bring them together to a fully funcitoning program.
Here I made a working, but rather ineffective, attempt at multithreading the process to speed up the calculations on larger grids. Unfortunately it made little difference and made the code much messier.
def simulateGenerationThreaded(self):
startTime = time.time()
threads = []
#Divide rows for processing, and take count of remaining rows after whole division.
maxThreads = 1
rowsPerThread = len(self.cellStates) // maxThreads
remainingRows = len(self.cellStates) % maxThreads
lastThreadRows = rowsPerThread + remainingRows
#Run simulate rows on seperate threads. Run final set first as it has the remainder alongside the standard to process.
t = Thread(target=self.simulateRows, args= (rowsPerThread * (maxThreads - 1), rowsPerThread * (maxThreads - 1) + (lastThreadRows - 1)))
threads.append(t)
t.start()
for x in range(0, len(self.cellStates) - lastThreadRows, rowsPerThread):
t = Thread(target=self.simulateRows, args= (x, x + rowsPerThread))
threads.append(t)
t.start()
for i in threads: #Join threads and wait until all are finished.
try:
i.join()
except RuntimeError:
pass
#Apply any found state changes
for i in range(len(self.changes)):
x = self.changes[i][0]
y = self.changes[i][1]
state = self.changes[i][2]
tag = (f"{x},{y}.")
if state == 1:
self.itemconfig(tag, fill= "black")
self.cellStates[x][y] = 1
elif state == 0:
self.itemconfig(tag, fill= "white")
self.cellStates[x][y] = 0
self.changes = [] #Reset changes list for next iteration.
#frame/ms recording stuff
endTime = time.time()
elapsedTime = round((endTime - startTime)*1000)
self.updateTime(elapsedTime)
if self.debug == True:
self.debugCounter += 1
self.debugLog.append(round(elapsedTime, 2))
if self.debugCounter == 50:
self.pauseSim()
self.debugCounter = 0
print(self.debugLog)`
#Limit FPS
desiredTime = 150
holdTime = desiredTime - elapsedTime
time.sleep(holdTime * 0.001)
if self.play == True:
self.after(1, self.simulateGenerationThreaded) #Wait 1ms before starting again to allow tk mainloop to update screen.
def simulateRows(self, start, end):
for x in range(start, end):
for y, value in enumerate(self.cellStates[x]):
#Assign fill of current cell to variable
n = 0
#Iterate over neighbors
for i in range(-1,2):
for j in range(-1,2):
x1 = x + i
y1 = y + j
if x1 == -1 or y1 == -1 or x1 >= len(self.cellStates) or y1 >= len(self.cellStates[0]): #Out of bounds check
pass
elif x1 == x and y1 == y: #Same cell check
pass
elif n >= 4: #if n>=4 outcome doesn't change, stop checks here.
break
elif self.cellStates[x1][y1] == 1:
n += 1
#Check if cell fill must be changed and store
if value == 0 and n == 3:
self.changes.append((x, y, 1))
elif value == 1 and n < 2 or n > 3:
self.changes.append((x, y, 0))
This version of my Game of Life algorithm is significantly different to the original, has many more features, but is honestly much lower in quality.
Here's a quick outline of the changes.
- The fill color attribute of the Tk rectangle objects is used in lieu of 0s and 1s to represent state.
- Tkinter's .after method is used to recursively run the algorithm 1ms after a generation is completed.
- Other methods of the time module are used to monitor the time taken to run a generation.
- time.sleep is used alongside a constant to make the simulate run at a consistent FPS.
- To limited effect - rows of cells are calculated in parallel on seperate threads.
Complete Code
The complete code has a handful more features that I haven't yet shared, and a call to create a gameWindow object, the Tk.Mainloop() method which allows the program to run indefinitely, and
finally a function that randomly creates live cells prior to running, commonly referred to in the GoL community as 'Soup'.
You should be able to Ctrl+A then copy and paste this into a .py file without installing any additional modules if you'd like to run this yourself or improve upon the code.
import tkinter as tk
import time
import threading
from tkinter import DISABLED, NORMAL, Tk, Frame
from threading import Thread
import random
#Potential optimisation ideas:
#Drop the cell id array, use the numerical ids and row/column count to calc moore's neighborhood instead of for i in len array. IE: 59 columns, so id 59 would be x,y 0,1 (numbered top left to bottom right) and it's neighboor 0,0 would be 59-59, id0
#Make custom rectangle class with a boolean attribute to store dead/alive flag to avoid accessing fill strings
#use threading module to do a row or column on an individual thread
class gameWindow(tk.Canvas):
def __init__(self, master, width, height, *args, **kwargs):
super().__init__(master, width= width, height= height, *args, **kwargs)
self.grid(row=0, column= 0)
self.width = width
self.height = height
self.play = False
self.debug = False #Enables limited generations and gen ms recording
self.debugLog = []
self.debugCounter = 0
self.size = 20 #Size in px of grid cells
self.cellStates = self.makeGrid() #Create rectangle objects for UI and matching array of state values.
self.changes = []
def makeGrid(self):
#Calculate how many cells to generate and gap left on screen edges
xSteps = self.width // self.size - 1
ySteps = self.height // self.size - 1
border = self.size // 2
cellIndices = [[] for i in range(xSteps)]
#Generate cells in accordance with calcs and collect their ids in an array so we know their coordinates.
for x in range(0, xSteps):
for y in range(0, ySteps):
x0 = x * self.size + border
y0 = y * self.size + border
x1 = x * self.size + self.size + border
y1 = y * self.size + self.size + border
cell = self.create_rectangle(x0, y0, x1, y1, fill= "white", tags= (f"{x},{y}."))
self.tag_bind(cell, '<Button-1>', self.onCellClick) #Allows toggling state via click
cellIndices[x].append(0)
return cellIndices
def simulateGenerationThreaded(self):
startTime = time.time()
threads = []
#Divide rows for processing, and take count of remaining rows after whole division.
maxThreads = 1
rowsPerThread = len(self.cellStates) // maxThreads
remainingRows = len(self.cellStates) % maxThreads
lastThreadRows = rowsPerThread + remainingRows
#Run simulate rows on seperate threads. Run final set first as it has the remainder alongside the standard to process.
t = Thread(target=self.simulateRows, args= (rowsPerThread * (maxThreads - 1), rowsPerThread * (maxThreads - 1) + (lastThreadRows - 1)))
threads.append(t)
t.start()
for x in range(0, len(self.cellStates) - lastThreadRows, rowsPerThread):
t = Thread(target=self.simulateRows, args= (x, x + rowsPerThread))
threads.append(t)
t.start()
for i in threads: #Join threads and wait until all are finished.
try:
i.join()
except RuntimeError:
pass
#Apply any found state changes - After calcs as changing during would alter outcome incomplete
for i in range(len(self.changes)):
x = self.changes[i][0]
y = self.changes[i][1]
state = self.changes[i][2]
tag = (f"{x},{y}.")
if state == 1:
self.itemconfig(tag, fill= "black")
self.cellStates[x][y] = 1
elif state == 0:
self.itemconfig(tag, fill= "white")
self.cellStates[x][y] = 0
self.changes = [] #Reset changes list for next iteration.
#frame/ms recording stuff
endTime = time.time()
elapsedTime = round((endTime - startTime)*1000)
self.updateTime(elapsedTime)
if self.debug == True:
self.debugCounter += 1
self.debugLog.append(round(elapsedTime, 2))
if self.debugCounter == 50:
self.pauseSim()
self.debugCounter = 0
print(self.debugLog)
#Limit FPS
desiredTime = 150
holdTime = desiredTime - elapsedTime
time.sleep(holdTime * 0.001)
if self.play == True:
self.after(1, self.simulateGenerationThreaded) #Wait 1ms before starting again to allow tk mainloop to update screen.
def simulateRows(self, start, end):
for x in range(start, end):
for y, value in enumerate(self.cellStates[x]):
#Assign fill of current cell to variable
n = 0
#Iterate over neighbors
for i in range(-1,2):
for j in range(-1,2):
x1 = x + i
y1 = y + j
if x1 == -1 or y1 == -1 or x1 >= len(self.cellStates) or y1 <= len(self.cellStates[0]): #Out of bounds check
pass
elif x1 == x and y1 == y: #Same cell check
pass
elif n >= 4: #if n>=4 outcome doesn't change, stop checks here.
break
elif self.cellStates[x1][y1] == 1:
n += 1
#Check if cell fill must be changed and store
if value == 0 and n == 3:
self.changes.append((x, y, 1))
elif value == 1 and n < 2 or n > 3:
self.changes.append((x, y, 0))
def placeGlider(self, x, y):
glider = [[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]]
for i in range(0, len(glider)):
for j in range(0, len(glider[i])):
tag = f"{x+i},{y+j}."
if glider[i][j] == 1:
self.itemconfig(tag, fill= "black")
elif glider[i][j] == 0:
self.itemconfig(tag, fill= "white")
self.cellStates[x+i][y+j] = glider[i][j]
def makeSoup(self):
for x in range(0, len(self.cellStates)):
for y in range(0, len(self.cellStates[x])):
if random.randrange(3) == 1:
tag = f"{x},{y}."
self.cellStates[x][y] = 1
self.itemconfig(tag, fill= "black")
def pauseSim(self):
#Toggle play constant, restart recursive sim loop if stopped.
if self.play == True:
self.play = False
frameControls.playPauseText.set("Play")
elif self.play == False:
self.play = True
frameControls.playPauseText.set("Pause")
self.simulateGenerationThreaded()
def onCellClick(self, event):
#Pull cell id with 'current' tag denoting mouseover
cell = event.widget.find_withtag('current')[0]
tag = self.itemcget(cell, "tag")
xEnd = tag.find(",")
yEnd = tag.find(".")
x = int(tag[0:xEnd])
y = int(tag[xEnd + 1:yEnd])
#toggle fill
if self.itemcget(cell, "fill") == "black":
self.itemconfig(cell, fill= "white")
self.cellStates[x][y] = 0
else:
self.itemconfig(cell, fill= "black")
self.cellStates[x][y] = 1
def updateTime(self, elapsedTime):
frameControls.elapsedTime.set(f"{elapsedTime}ms")
class controlFrame(Frame):
def __init__(self, master):
super().__init__(master)
self.grid(row= 1, column= 0)
self.elapsedTime = tk.StringVar()
self.framesPer = tk.StringVar()
self.playPauseText = tk.StringVar(value="Play")
self.pauseButton = tk.Button(self, textvariable= self.playPauseText, command= gameView.pauseSim)
self.pauseButton.grid(row=0, column= 0)
self.frameTimeLabel = tk.Label(self, textvariable= self.elapsedTime)
self.frameTimeLabel.grid(row=0, column= 1)
self.framesPerLabel = tk.Label(self, textvariable= self.framesPer)
self.framesPerLabel.grid(row= 0, column= 2)
root = Tk()
gameView = gameWindow(root, 1920, 1280)
frameControls = controlFrame(root)
#gameView.placeGlider(1,1)
#gameView.simulateGenerationThreaded()
#gameView.makeSoup()
root.mainloop()