Inside simplicity, there is always complexity to be discovered.

-- Gang Yu, in Data Warehousing in the Age of Big Data, p. 40

What is a cellular automaton?

A cellular automaton (CA) is a system loosely described by the following properties:

  • The system has a grid of cells on which the drama plays out
  • Each cell has more than one possible state, e.g. on and off
  • The system has a discrete sense of time i.e. t 0 -> t 1 -> t 2 in clear steps
  • The system features a rule-set that generates a new grid state for t + 1 based on the current state of the board
  • Cells interact with others within a set of neighbouring cells commonly known as the cell’s neighbourhood - handily enough

A neighbourhood can be defined in several ways. One of the most commonly used neighbourhoods in a two-dimensional grid is defined as the cell itself plus the 8 surrounding cells. Such a set-up is known as a Moore neighbourhood. The cells are typically square, but you are free to implement a cellular automaton in triangles, hexagons, cubes, etc. The states that these cells can assume are generally discrete, meaning that they are distinct and non-continuous. Again, you can go against the tide and have a cellular automaton with not-so-distinct states, in which case you will have a Continuous Automaton. The different properties of cellular automata as I describe them are in no way meant to be exhaustive or prescriptive. The generalities given merely scratch the surface of the properties of these systems and serve to provide an overview of a typical CA.

The most famous example of a cellular automaton is Conway’s Game of Life, a two-dimensional system created by mathematician John Conway in 1970. Probably the best way to make the idea of cellular automata ‘click’ would be to have a quick glance at Conway’s system. I would recommend anyone who is interested in cell-based computational systems to study the Game of Life and perhaps implement it in your favourite language. Conway himself seems to be a bit tired of the old GOL, but there’s no denying that it is an important milestone in the field of cellular automata and the first exposure that many have to this strange mathematical world of soulless autonomous data-structures. You can hear the origin story and some relevant historical context from Conway himself here.

Why care?

I believe there are at least a few reasons why one should get interested in an array of cells blinking in different abstract states. Before I go on to explain some of the aspects of CA that appeal to me, I’d like to concede that this topic may not instantly consume everyone. However, whenever I first learned about CA, it immediately fascinated me and I set out on implementing a few of the popular rule-sets in Java and C++. To me, cellular automata represented a microcosm of the universe that gives a perspective on how complex behaviour can arise from a very simple set of laws and states. I concede that this view is somewhat grandiose, and I don’t know enough about stars to fully appreciate the gaping chasm of detail between a chaotic mathematical system and our cosmology. Nonetheless, these structures provide a solid analogy for this jump between the simple and the mind-boggling that we see in dynamic systems.

Apart from the fascinating, mysterious and otherwise aesthetic qualities of cellular automata, they also offer the prospect of pragmatic applications. Using CA, we (or some person smarter than we) can model physical systems in order to gain concrete insight into the world of chaotic systems. A wide variety of phenomena have been modelled by cellular automata to varying levels of success. These include the growth patterns of sea shells, fluid mechanics and geographical population dynamics to mention a few. In saying that, it seems that CA hype has died down over the years in regard to what the field can provide to the hard sciences. Several avenues of research into traffic dynamics as well as other infrastructural networks seem promising but needless to say, these aren’t my fields, so it would be a bit presumptuous of me to expound any further on the topic.

DIY

Something that I’ve been meaning to look into for a while is the idea of creating my own cellular automaton from scratch. When reading the literature, you may get the sense that all the exciting CA was created many decades before by some wise mathematicians who simulate Turing Machines in their heads while trying to fall asleep. Now I plan to sneak my way into the cellular automata club by creating my own model while hopefully avoiding being kicked out by someone who knows their definitions better than I.

Desired outcomes

Basically I want two things out of this simple project:

  1. Gain some insight into the definition and mechanics of cellular automata
  2. Get a result that looks pretty or interesting (preferably both!)

With these humble goals in mind, I had a bit of a scribble and came up with…

SNIM

The cellular world I’ve devised is called the Simple Neural Ignition Model. While this sounds fancy, the system is only loosely inspired by the actual function of neurons. To keep things interesting, let’s pretend that we have found an alien insect and would like to get an insight into its nervous system by examining the precious brain. Okay, it seems that the creature has a matrix-like substrate (or grid) of neurons. The neurons of the beast are arranged in such a way that they are intimately bound to the four diagonally connected neurons to the northwest, northeast, southwest and southeast. On the image below, the green cells represent the neighbours of the red neuron. Each neuron fires depending on its current state and the states of its four neighbours. Wow, this situation sounds ripe for modelling.

SNIM neighbourhood

States

As we are not trying to model neuronal activity to any sort of realistic degree, we break the different conditions in which a neuron might find itself into 3 basic states:

  • Resting (the default state)
  • Firing
  • Recovering

In additional to these 3 possibilities, a cell might also be empty, leaving us with 4 states.

The Rules

To start off, I’ve devised a couple of very simple rules, which are as follows:

  • If any of a resting neuron’s neighbours are firing, it will also fire at t + 1 (the next turn)
  • If the neuron is firing, it will enter a recovering state at t + 1
  • If the neuron is recovering, it will enter a resting state at t + 1

It is important to note that all of the cells in the grid will simultaneously update at each tick of the clock. This means that if we cycle through all of the cells in an update loop, we must not update a cell’s state until all of the board state has been computed.

Enough planning

Now for the actual implementation of the thing. I have chosen to use the Python language (specifically Python 3.5) due to its great capacity for rapid prototyping. Without further ado, I’ll create the modest classes that I’ll use to build my model.

# snim.py
class Snim:
    t = 0

    def __init__(self, w, h):
        self.width = w
        self.height = h
        self.board = [[Cell(x, y) for x in range(w)] for y in range(h)]

# cell.py
class Cell:
    def __init__(self, x, y, state = SnimState.EMPTY):
        self.x = x
        self.y = y
        self.state = state

# snim_state.py
from enum import Enum

class SnimState(Enum):
    EMPTY = 1
    RESTING = 2
    FIRING = 3
    RECOVERING = 4

You can see from the Snim class that we are using a simple two-dimensional list to hold the board information. We can use the handy Python list comprehension construct to create a blank cell for each position on the board as I’ve done with the line:

self.board = [[Cell(x, y) for x in range(w)] for y in range(h)]

Apart from that, there’s nothing much to say here, so I’ll continue to scaffold out the structure of the program.

Updating the board state

The basic idea of running the cellular automaton is simple enough. We’ll have a loop that runs indefinitely, updating the board and pausing for a pre-defined amount of time which I’ll initially set to 0.5, which translates to one update per half a second. The update function will cycle through all the cells, telling them to update themselves then incrementing the time (t) when all of the board has been traversed.

# ... snim.py ...
import time
import copy

...
delta = 0.5
...

def run(self):
    while True:
        self.update()
        time.sleep(self.delta)

def update(self):
    new_board = copy.deepcopy(self.board)
    for row in new_board:
        for cell in row:
            cell.update(self)

    self.board = new_board
    self.t += 1

The only thing we have to be mindful of here is that we obtain a clone of the board before updating, then switch out the real board with the clone board at the end. This is rationale behind calling copy.deepcopy, which will allow us to perform the aforementioned simultaneous update at the end of the turn. When we later ask the cell in the clone neighbourhood to update itself we will have to make sure it is looking at neighbours in the original board when computing its next state.

Getting a neighbourhood

Before a cell can update itself we must first write the function to provide a neighbourhood for a given position, keeping in mind the grid diagram from above.

# ... snim.py ...
def get_diag_neighbours(self, x, y):
    neighbours = []
    for i in range(-1, 2):
        for j in range(-1, 2):
            if i is not 0 and j is not 0:
                # Prevent list wrap-around
                if y + i < 0 or y + i >= self.height or x + j < 0 or x + j >= self.width:
                    neighbours.append(Cell(x + i, y + j))
                    continue
                neighbours.append(self.board[y + i][x + j])
    return neighbours

Now there may be simpler ways to write this function, but instead of hard-coding four relative positions for a given point, I wanted to loop over the Moore neighbourhood and eliminate relative positions (i, j) that are invalid. The reason I’ve done it this way is that it makes for quick extension if you want to switch to another common neighbourhood in the future. The only annoying part here is the line:

if y + i < 0 or y + i >= self.height or x + j < 0 or x + j >= self.width:

Which assures that we will not wrap-around the end of a list and address a ‘neighbour’ on the other side of the board - instead providing a default empty cell. Again, there may be cleaner ways to do this, and if at any point you are infuriated by my lack of pythonic whizz-skills, feel free to make a PR here.

Implementing the Rules

Now that we have a function to get a list of neighbour cells at a certain location, we can lay the rules down in stone, albeit magic magnetic computer stone.

# ... cell.py ...
def update(self, snim):
    neighbours = snim.get_diag_neighbours(self.x, self.y)
    firing_neighbours = sum(1 for n in neighbours if n.state is SnimState.FIRING)

    if self.state is SnimState.FIRING:
        self.state = SnimState.RECOVERING
        return

    if self.state is SnimState.RECOVERING:
        self.state = SnimState.RESTING
        return

    if self.state is SnimState.RESTING:
        if firing_neighbours >= 1:
            self.state = SnimState.FIRING
            return

After getting the cell’s neighbours, we use another list comprehension to count up the amount of neighbours that are firing (a simple any function would also suffice for our particular rule-set). From there on, there’s a very simple mapping of states to states facilitated by a few ifs.

Displaying

There’s not much point of creating a little patch of twinkling states if you can’t observe it. The SnimPrinter class will draw a given Snim by printing the time, then looping the board and printing each state.

# ... snim_printer.py ...
import os

class SnimPrinter:

    def draw(self, snim):
        os.system('clear')

        print("Time: {}".format(snim.t))
        for row in snim.board:
            for cell in row:
                print(str(cell.state) + " ", end='')
            print('')

The Observer Pattern

The Observer pattern is a basic software design that makes an object maintain a list of observers and notifies these subscribers on a change of state. For our purposes we’ll only have one observer (the printer) watching, but I´ve allowed for multiple observers incase we want to extend the project to do something a bit more interesting. One example of this could be to have a class watch the state changes of the board and build a heat-map of firing states over-time, without messing with our original class.

# ... snim_printer.py ...
class SnimPrinter:
  def __init__(self, snim):
      snim.register_observer(self)

  def notify(self, snim):
      self.draw(snim)

# ... snim.py ...
class Snim:
    t = 0
    observers = []
    ...

    def register_observer(self, observer):
        self.observers.append(observer)

    def notify_observers(self):
        for observer in self.observers:
            observer.notify(self)

    def update(self):
        ...

        self.t += 1
        self.notify_observers()

# ... main.py ...
width = 5
height = 5

snim = Snim(width, height)
snim_print = SnimPrinter(snim)

snim.run()

I’ve also created a main.py to kick off the whole process.

Initial State

At this point in the project, the board will be filled with empty cells, so I´ll quickly populate the board based on the following rules:

  • Each cell has a 50% chance of being empty
  • If the cell is not empty, it has a 50% chance of firing
  • Otherwise, it is at rest
# ... main.py ...
width = 5
height = 5

chance_of_empty = 50
chance_of_firing = 50

snim = Snim(width, height)
snim_print = SnimPrinter(snim)

for i in range(height):
    for j in range(width):

        if random.random() < chance_of_empty / 100:
            state = SnimState.EMPTY

        else:
            if random.random() < chance_of_firing / 100:
                state = SnimState.FIRING
            else:
                state = SnimState.RESTING

        snim.set_state(j, i, state)

snim.run()

Now we can run python3 main.py and . . .

First attempt

Well obviously that’s hideous. It’s like a list of enums begging to be put out of their misery…

Pretty print

Instead of directly printing the value of the state, I’ll create a dictionary mapping of each state to a character and print that.

# ... snim_printer.py ...
...
    print(self.get_symbol(cell.state) + " ", end='')
...

def get_symbol(self, state):
    return {
        SnimState.EMPTY: " ",
        SnimState.RESTING: u"\u2606", # Black star
        SnimState.FIRING: u"\u2605", # Filled in star
        SnimState.RECOVERING: u"\u2022", # White dot
    }[state]

Second attempt

Now that looks better. We have a bit of sparkle and can actually see the alleged transfer of electricity from neuron to neuron.

Updating the Rules

After running the project in its current state a few times I’m pleased with what I have so far (as simple as it is), but all of the sizes of grids that I try result in a quick pulse (or two) of firing across the board which quickly settles to empty stasis by around t = 20. In the interest of maintaining a firing state across the board for a bit longer and allowing for more interesting interactions, I’ve devised a few extra simple rules discovered some new properties of the bug brain (are we still doing that?):

  • If all of an empty cell’s neighbours are living neurons, a new resting cell will be spawned in the empty place
  • If a firing neuron has no living neighbours, it will continue to fire as it cannot ‘discharge’
  • If a recovering neuron has over 2 firing neighbours, it will be re-ignite
# ... cell.py ...
def update(self, snim):
    neighbours = snim.get_diag_neighbours(self.x, self.y)
    neural_neighbours = sum(1 for n in neighbours if n.state is not SnimState.EMPTY)
    firing_neighbours = sum(1 for n in neighbours if n.state is SnimState.FIRING)

    if self.state is SnimState.EMPTY:
        # If all of the surrounding cells are living, spawn a new living neuron
        if neural_neighbours is 4:
            self.state = SnimState.RESTING
            return

    if self.state is SnimState.FIRING:
        # If firing and there are no surrounding neurons, neuron unable to discharge
        if neural_neighbours < 1:
            self.state = SnimState.FIRING
            return

        self.state = SnimState.RECOVERING
        return

    if self.state is SnimState.RECOVERING:
        # If recovering and over 2 neighbours are firing, re-ignite
        if firing_neighbours > 2:
            self.state = SnimState.FIRING
            return

        self.state = SnimState.RESTING
        return

    if self.state is SnimState.RESTING:
        # If resting and any neighbours fire, ignite
        if firing_neighbours >= 1:
            self.state = SnimState.FIRING
            return

One minor thing I haven’t mentioned yet is to take note that we return from the function after updating the state to avoid any unintended breaking of the rules. This may seem obvious, but I did spent an embarrassing couple of minutes back there looking at a few simple if statements trying to see the glaring mistake. Now we run main.py and . . .

New rules

Now we have something that I’m happy with. You can see this interesting pulsing pattern that is facilitated by the looping firing mechanism around the neuron at 4 across, 5 up from the bottom left.

Complexity

When playing with this final rule-set using different grid sizes and percentages of empty/firing/resting neurons, I’ve found some interesting complex patterns that are facilitated by relatively simple constraints. One common pattern that arises with a bigger grid size and a small amount of empty neurons is the following:

Complexity

You can see that from a chaotic starting position of resting and firing neurons, there seems to be a stabilising phase during which the pulses of firing neurons assemble into spiralling waves that grow until it reaches a stable vertical wave grid.

Conclusion

The take away from this little project is that given a few hours, a couple of Wikipedia pages and some creativity, you too can create a cellular automaton that can generate some interesting output. I have included the source code of the project below which I encourage you to review, copy, critique or whatever else. I have also expanded the project to allow for the main.py script to take a variety of optional arguments which allow you to quickly change parameters such as the grid-size, delta, and initial state seed without having to edit any code.

Source: https://github.com/markormerod/simple-neural-ignition-model