5.3. Cellular Automata

A cellular automaton is a collection of cells on a rectangular grid that evolves through a number of discrete time steps according to a set of rules based on the states of neighbouring cells. The rules are then applied iteratively for as many time steps as desired.

You will investigate a cellular automaton model as part of your group project.

Fig. 5.2 Cellular automata models of the spread of an epidemic on a 2-dimensional grid of cells. Each timestep corresponds to one day .

Diffusion Model

Diffusion is the movement of a substance from an area of high concentration to an area of lower concentration. For example, suppose we have an 2-dimensional region which is initially empty except for a square region at the centre where we inject a high concentration of a chemical. As time progresses, the chemical gradually diffuses throughout the region until the concentration is everywhere equal (Fig. 5.3).

Fig. 5.3 A chemical introduced into the centre of a square region (left) gradually diffuses across the region. Eventually the chemical would be distributed evenly throughout the region.

We can model this using a 2-dimensional array representing the concentration at each point in space (Fig. 5.3). At each timestep, the concentration \(x_{i,j}\) at each point changes as the chemical flows between the 8 immediate neighbouring cells.

We can construct a (very crude) model of diffusion using 2d averaging. In this model, we repeatedly apply a moving average, so that at each timestep the concentration of cell x[i,j] is replaced by the average of the 9 cells in the 3 by 3 subarray centred at i,j.

def moving_average_2d(x):
    # create empty array of correct dimensions
    n, m = x.shape
    result = np.zeros((n, m))
    
    # fill in moving avg
    for i in range(1, n-1):
        for j in range(1, m-1):
            sub_array = x[i-1:i+2, j-1:j+2]
            result[i, j] = np.average(sub_array)
           
    return result

Exercise 5.3

Build a simulation model similar to Fig. 5.3. First create an square array whose elements are zero everywhere except for a square of cells in the centre. Then repeatedly apply the function moving_average_2d. Use imshow to plot the array at each timestep.

Experiment with different arrays sizes. Can you achieve a result that looks like Fig. 5.3?

Conway’s Game of Life

The Game of Life is a simple cellular automaton devised by mathematician John Conway in 1970. The automaton mimics the dynamical evolution of “life-forms” existing in the grid of cells Fig. 5.4 shows an example evolution of the Game of Life.

Fig. 5.4 The Game of Life is an example of a 2-dimensional cellular automaton.

The rules of Conway’s Game of Life are given below, and an example of two iterations of the Game are shown in Fig. 5.5.

The Rules of Conway’s Game of Life

1. Start with a rectangular grid of cells, each of which is “alive” (black) or “dead” (white).

2. Count the number of each cell’s 8 immediate neighbours that are alive, and
   a. any live cell with fewer than 2 live neighbours dies;
   b. any live cell with more than 3 live neighbours dies;
   c. any live cell with 2 or 3 live neighbours lives on;
   d. any dead cell with exactly three live neighbours becomes alive, and otherwise stays dead.

3. Repeat step 2 as many times as desired.

Fig. 5.5 An initial configuration of cells (left) and two iterations of the Game of Life (centre and right).

Exercise 5.4

What would the next iteration of the Game of Life in Fig. 5.5 look like?

Using pseudocode, sketch an algorithm for calculating one iteration of the Game of Life.

Below is template code for a Python program which executes a single iteration of the game of life. The grid is represented by an n by n array where dead cells are 0 and live cells are 1. The function count_neighbours calculates the number of live neighbours of single cell, whereas the function advance calculates the next iteration of the entire grid of cells.

import numpy as np
import matplotlib.pyplot as plt

def count_neighbours(x, i, j):
    pass
    # Return the number of live neighbours
    # of the cell at position i, j
    # (NB you should delete 'pass' which
    # is a Python keyword which does nothing)

def advance(x):
    pass
    # Loop over each of the cells in the array x.
    # For each cell, determine the number of live neighbours.
    # Use the game of life rules to determine if the cell lives or dies.
    # Finally, set the value of the equivalent cell in the output array.


n = 5
grid0 = np.zeros((n, n))

# set the initial value of grid0 where
# 0 represents 'alive' and 1 represents 'dead'  

print("grid0:")
print(grid0)

# Simulation code goes here

grid0:
[[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.]]

Exercise 5.5

1. Complete the function count_neighbours(x, i, j) so that it returns the total number of live neighbours of cell i, j. Test that the function works by setting grid0 to the initial configuration in Fig. 5.5 and checking your function gives the expected result for various values of i and j.

2. Complete the function advance(x) so that it returns the array after applying the rules of the Game of Life simulation. Test the function by applying it to the initial configuration in Fig. 5.5.

3. By repeatedly calling advance, execute the simulation for 10 or more steps, using imshow to display the array at each step. Check that your simulation works by comparing to an online Game of Life simulator.