GameOfLife is a numpy based generalized implementation of Convey's Game of Life.
Installation works by:
git clone [email protected]:lionjo/Game-of-Life.git
cd Game-of-LifeThen install using pip:
pip install -e .A Main window can be opened by running the main.py script in Applications.
Or by just typing OurGameOfLife.py in your terminal (this uses the script in scripts/).
Also look through the other files in Applications!
The world is a 2D map of two possible states, alive, represented by 1 or white, and dead, represented by 0 or black.
In the main window the user can "kill" or "give birth" to certain cells by just clicking on them. Living cells then turn dead, and dead cells turn alive.
Now, we can assing a "rule" to the world, which determines which cells should live in the next step and which should be dead. For example, one could impose the following four rules:
- Cells that have exactly 3 alive direct neighbours (diagonal neighbours count), would stay alive or would be born if dead.
- Cells with exactly two alive neighbours would survive if they were alive before but 2 neighbours is not enough for a dead cell to come alive
- Cells with only one alive member would die or would stay dead du to loneliness.
- Cells with 4 or more neighbours would die or stay dead due to overpopulation
This is the standard rule of Conveys Game of life and this simple set of rules leads to surprisingly complex structures.
In general, there are
The rule can be written as a 2D array, e.g.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| if dead: | dead | dead | dead | alive | dead | dead | dead | dead | dead |
| if alive: | dead | dead | alive | alive | dead | dead | dead | dead | dead |
The numbers stand for the number of neighbours. The rule is Convey's game of life. We can also write the above table as an array:
rule = [[0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 0, 0]]Every of such rules can also be written more compactly, by associating every rule with a number.
Just write every rule as a binary number, by flattening it out (and apply some flipping):
e.g. the rule we defined earlier can be written as 000000000011100000.
This is a binary number and can be transferred to 224 -- the unique identifier for Conveys game of life (imposing the 8 field neighbourhood).
Oftentimes numerical implementations of the game of life are done unnecessarily complex or numerically inefficient.
Python, as a interpreted language also has drawbacks in naive implementations of parallel operations.
Luckily there is numpy and we can make use of the concept of vectorization: A very fast implementation of parallel operations within numpy.
The game of life grid can be written as a number of such parallel operations.
The grid can be written as a matrix of 1's and 0's.
To determine the number of neighbours we can just shift the array by one index in every dimension and add it up!
Luckily, numpy has a function to achieve this very efficiently:
no_neighbours = (
np.roll(array, 1, axis=0)
+ np.roll(array, -1, axis=0)
+ np.roll(array, 1, axis=1)
+ np.roll(array, -1, axis=1)
+ np.roll(np.roll(array, 1, axis=1), 1, axis=0)
+ np.roll(np.roll(array, -1, axis=1), 1, axis=0)
+ np.roll(np.roll(array, 1, axis=1), -1, axis=0)
+ np.roll(np.roll(array, -1, axis=1), -1, axis=0)
)This gives us the number of neighbours as entries in the location of the respective cell. Next, we can write the rule in a specific form, discussed in the previous section.
rule = np.array([[0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 1, 0, 0, 0, 0, 0]])And now we can use these two arrays to determine the next array:
next_array = rule[array,no_neighbours]Why does this work?
We specified the rule such that the first vector, [0, 0, 0, 1, 0, 0, 0, 0, 0] applies for dead cells, the second, [0, 0, 1, 1, 0, 0, 0, 0, 0], for alive cells.
array consists of 0s and 1s, hence we can use the entries of array as indices for rule and it automatically applies to the correct rule: dead cells use the first vector, alive cells the second one.
Next, we constructed our vector no_neighbours, such that the number of neighbours are written as entries.
And, you guessed it already, we can use these entries as indices in rule.
When accessing an array, here rule, by two matrices, array and no_neighbours which have the same dimensions, say rule[array,no_neighbours] also has dimensions rule.
These three lines of code are enough to implement a general version of conveys game of life for arbitrary rules. The rest of the package is GUI.
For the 'usual' set of rules, rule 224, aka Convey's Game of Life, there are many known stable figures, e.g. blinkers (left) and gliders (right):
But did you know that there are similar figures for other rules too? Here is an example glider in rule 736:
Considering that there are
The pure computational part of the package can be called like this. Note the check_periodicity=False.
grid = Grid(ruleDEC=225)
grid.randomize()
grid.multiple_steps(no_steps,check_periodicity=False)For a single CPU, these are the run-times in wall clock time:
| # steps (100x100 Size) | time [s] |
|---|---|
| 1000 | 0.25 |
| 5000 | 1.25 |
| 10000 | 5.47 |
| # Gridsize (3000 steps) | time [s] |
|---|---|
| 100x100 | 0.91 |
| 300x300 | 6.51 |
| 500x500 | 25.9 |
These times are about 2 times slower than Mathematicas Cellular Automata implementations:
CellularAutomaton["GameOfLife", RandomInteger[1, {500, 500}], {{{3000}}}]
Which takes 13 s to evaluate on (the same) 1.8 GHz CPU.
Enabling periodicity checks, check_periodicity=True, which is required to find periodic patterns, slows the times down.
Thank you for reading this far! If you like the package and find it useful please consider starring ⭐ the project. If not, let me know what you are missing, via an issue or via DM.