Cellular Automata

CA simulations are a collection of cells arranged in a grid of specified shape, such that each cell changes state as a function of time, according to a defined set of rules driven by the states of neighboring cells.

Typical characteristics of a CA are the following:

1. The cells in a CA reside on a grid which has a specified shape (square, triangle, hexagon, etc.) and exist in a finite number of dimen- sions.

2. Each cell on the grid has a state. While there are numerous finite possibilities of the state, the simplest state form is usually On or Off (or True/False or 1/0).

3. The cells adjacent to one cell constitute its neighborhood. Cells in a neighborhood affect each other, and each cell on the CA grid has a neighborhood.

Based on predetermine rules complex dynamical behavior arises from these CA models that can be used to describe many natural phenomena. For example, one of the most famous CA is Conway’s Game of Life which has only four deterministic rules but can create very intriguing patterns that we will explore in this blog.

CA models are capable of modelling many biological behavior from microbial growth to cancer research. In particular, applied mathematicians use these models to better understand the growth of biological cells and couple these with experimental data to predict biological behavior. These models also have numerous applications in other fields of research such as ecology, physics, chemistry, and other sciences.

The 4 Rules of the Game of Life

The four simple rules Conway (Shiffman, Fry, and Marsh 2012) initially discovered are given below

1. Death. If a cell is alive (state = 1) it will die (state becomes 0) under the following circumstances.

   • Overpopulation: If the cells has four of more neighbors, it dies.

   • Loneliness: If the cell has one or fewer alive neighbors, it dies.

2. Birth. If a cell is dead (state = 0) it will come to life (state becomes 1) if it has exactly three alive neighbor (no more, no less)

3. Stasis. In all other cases, the cells state does not change. To be thorough, let’s describe those scenarios.

   • Staying Alive: If a cell is alive and has exactly two or three live neighbors, it stays alive.

   • Staying Dead: If a cell is dead and has anythign other than three alive neighbours, it stays dead.

Matlab Implementation

We will now code the Game of Life in Matlab. We begin by initializing the board randomly using 0 or 1 using Matlab 2D array. Then we ran the simulation \(N\) times. At each iteration we implement the algorithm described above.

% This Matlab script implements Conways Game of Life.
%
% Kai Li
% 08/01/2023

clear; % clear workspace
close all; % close all figures

rows = 50; % number of rows of board
cols = 50; % number of columns of board
 
% intialise board 
board = round(rand(rows,cols));

% initialise next step of rules 
next = zeros(rows,cols);

% number of simulations 
N = 100;

% black and white color map
cmap = [1 1 1; 0 0 0];

figure('Position',[500,250,500,450])

% create gif
gif('game-of-life.gif', 'DelayTime', 0.1) 

for z = 1:N % loop over N simulations 
    for x = 2:rows-1 % iterate overs rows 
        for y = 2:cols-1 % iterate over columns 

            neighbours = 0; % initialise neighbour count 
            
            % count number of neighbours 
            for i = -1:1
                for j = -1:1
                    neighbours = neighbours + board(x+i,y+j); 
                end
            end
            
            % remove current board position from count
            neighbours = neighbours - board(x,y);
            
            % implement the 4 rules of Conways game of life rules 
            if board(x,y) == 1 && neighbours < 2 % death by loneliness 
                next(x-1,y-1) = 0; 
            elseif board(x,y) == 1 && neighbours > 3 % death by overpopulation
                next(x-1,y-1) = 0; 
            elseif board(x,y) == 0 && neighbours == 3 % birth 
                next(x-1,y-1) = 1; 
            else % else remain the same 
                next(x-1,y-1) = board(x,y);
            end

        end
    end
    
    board = next; % update board 
    board = padarray(board,[1 1]); % deal with edge case 
    
    % visualise board 
    [r1, c1] = size(board);
    imagesc((1:c1)+0.5, (1:r1)+0.5, board);
    colormap(cmap);
    title("Iteration = " + z)
    axis equal 
    box on
    set(gcf,'color','w')
    set(gca,'XTick',[], 'YTick', [])
    
    % capture gif
    gif
end

Below is the initial condition of the grid populated randomly (left) and after \(N=100\) iterations of the algorithm we get the final state (right).

Here is an animation of the output.

There are countless pattern that arises from this algorithm (Izhikevich, Conway, and Seth 2015) which I find fascinating. See the Wikipedia page for more details.

References

Coding train: https://www.youtube.com/watch?v=FWSR_7kZuYg