Cellular automata

Cellular Automata Icon

The increasing prominence of computers has led to a new way of looking at the world. This view sees nature as a form of computation. That is, we treat objects as simple computers, each obeying its own set of laws.

The “cellular automaton” extends this analogy to provide a way of viewing whole populations of interacting “cells”, each of which is itself a computer (automaton). By building appropriate rules into a cellular automaton, we can simulate many kinds of complex behaviour, ranging from the motion of fluids governed by the Navier-Stokes equations to outbreaks of starfish on a coral reef.

In this tutorial:
  1. Definition
  2. Example – Fabirc Patterns
  3. Properties
  4. The Game of Life
  5. An Application to simple forest models
  6. Exercises

Related tutorial: Critical connectivity in cellular automata.

Definition

A cellular automaton is an array of identically programmed automata, or “cells”, which interact with one another.

The arrays usually form either a 1-dimensional string of cells, a 2-D grid, or a 3-D solid. Most often the cells are arranged as a simple rectangular grid, but other arrangements, such as a honeycomb, are sometimes used.

The essential features of a cellular automaton (“CA” for short) are:

  • its STATE is a variable that takes a different separate for each cell. The state can be either a number or a property. For instance if each cell represents part of a landscape, then the state might represent (say) the number of animals at each location or the type of forest cover growing there.
  • its NEIGHBOURHOOD is the set of cells that it interacts with. In a grid these are normally the cells physically closest to the cell in question. Here are some simple neighbourhoods (cells marked n) of a cell (C) in a 2-D grid:
    ca-2d.png

  • its PROGRAM is the set of rules that defined how its state changes in response to its current state, and that of its neighbours.

[ Top ]

Example – Fabric patterns

Imagine a CA consisting of a line of cells as follows:

  • states: 0 or 1
  • neighbourhood: the two adjacent cells N C N
  • rules: the following list shows the new state of a cell for each possible local “configuration”, i.e. arrangement of states for the cell and its two neighbours. Because there are two possible states (0 or 1) for each of 3 cells, there are 2^3 = 8 rules required. Here they are:
    ca-rules.png

Suppose that we start with just a single cell in state 1. Then here is how the array will change with time (here “.” denotes 0 for clarity).

ca-change-with-time.png

The following figure shows several examples of “fabric patterns” that can be produced by one dimensional cellular automata similar to the above. Cellular Automata Patterns [ Top ]

Properties

  • Self-organization. Notice that when we plot the successive states as shown in the above example a pattern emerges. Even if the line of cells starts with a random arrangement of states, the rules force patterns to emerge (Fig. 1).
  • Life-like behaviour. Empirical studies by Wolfram and others show that even the simple linear automata above behave in ways reminiscent of complex biological systems. For example, the fate of any initial configuration of a cellular automaton is either:
    1. to die out;
    2. become stable or cycle with fixed period;
    3. to grow indefinitely at a fixed speed;
    4. to grow and contract irregularly.
  • “Thermal” behaviour. In the above example of a linear automaton 6 of the 8 rules forced a change in the state of the cell concerned. In general, models that force a change of state for few configurations tend to “freeze” into fixed patterns, whereas models that change the cell’s state in most configurations tend to behave in a more active “gaseous” way. That is fixed patterns do not emerge. Thermal behaviour

[ Top ]

The game of LIFE

The game LIFE, invented by the Cambridge mathematician John Conway, is a simple 2-D analogue of basic processes in living systems. The game consists in tracing changes through time in the patterns formed by sets of “living” cells arranged in a 2-dimensional grid. Any cell in the grid may be in either of two states: “alive” or “dead”. The state of each cell changes from one generation to the next depending on the state of its immediate neighbours. The rules governing these changes are designed to mimic population change: The Game of Life Patterns The game LIFE. Some simple patterns that die (left); remain constant (centre); and cycle (right). The pattern at lower right, called a “glider”, not only cycles but also glides diagonally across the grid of cells. The Game of Life self-organisation
Self-organization in the game LIFE. The random initial configuration of cells (left) reduces to constant and cycling elements after 2500 generations (right).

  1. A living cell with only 0 or 1 living neighbours dies from isolation.
  2. A living cell with 4 or more living neighbours dies from overcrowding.
  3. A dead cell with exactly 3 living neighbours becomes alive.
  4. All other cells remain unchanged.

The behaviour of LIFE is typical of the way in which many cellular automata reproduce features of living systems. That is, regularities in the model tends to produce order: starting from an arbitrary initial configuration, order (i.e. patches of pattern) usually emerges fairly quickly. Ultimately most configurations either disappear entirely or break up into isolated patterns that are either static or else cycle between several different forms with a fixed period.

[ Top ]

An application to simple forest models

Cellular automata models of landscapes consist of fixed arrays in which each cell represents an area of the land surface. The states associated with each cell correspond to environmental features, such as coral cover or topography. This approach is compatible with both pixel-based satellite imagery and with quadrat-based field observations. It also enables processes that involve movement through space (e.g. fire, dispersal) to be modeled in “natural” fashion.

To see how easily the cellular automaton idea can be brought to bear on real systems, consider a system whose states are of the form ( s,t ), where t denotes “time since fire burned out the cell” and stakes one of the values: “bare earth” (E), “grass” (G), “woodland” (W), and “closed forest” (F). Define state transitions rules as follows:

state-transitions-rules.png

Starting with an arbitrary “landscape”, consisting of a 2-D grid of cells in random states, the rules quickly produce patterns (Fig. 3). For instance, “forest zones” quickly develop, even though the model contains no assumptions about the environment or site preferences of the vegetation. Admittedly, this model is a mere caricature of true forest succession, but it is only a short jump to management models taking (say) satellite data as inputs.

[ Top ]

Exercises

  1. Use the program Basic 1D CA to look at patterns formed by linear CAs. Select 2 colours and 20 cells. The program forms both the initial row of cells, and the rules, at random.
    1. What sorts of patterns emerge?
    2. Try to deduce the rules from the patterns you see.
  2. Play with the Game of Life.
    1. Draw some simple configurations and run the model. What happens?
    2. Try running the model with well-known patterns.
    3. Run the model a few times starting with a random scatter of “live” cells. Does the model settle down to a fixed pattern? If so, how many generations does it take?
  3. The program COT shows how the basic CA model can be varied to simulate artificial life. Here the basic CA models corals and water. Overlaid on top of it are Crown of Thorns starfish (COTs) that move around from cell to cell and interact with the coral by eating it.
    1. First run the reef model (COT.MOD) with the default settings. What happens?
    2. Change the assumption (under Options) about starfish behaviour. How does this change the movement of starfish?
    3. Use the options to start the random walk model (WALK.MOD). This model simulates N animals walking at random from a single starting point and is a simple example of “diffusion limited aggregation” or DLA for short. The What happens with just 1 animal?
    4. Rerun the walk model with 100 animals. How does the area covered differ from that with a single animal?
  4. The FILL option in the program PIXED illustrates a simple epidemic process in a CA (see Figure 4). At the start all cells are in a single state and a new state spreads outwards from a “seed” by “infecting” its neighbours.
    1. Try FILL (F) to see the epidemic spread outwards from the centre. Use Undo (U) to reset the grid.
    2. In a real epidemic, not everyone is infected. The “infection rate” is the proportion of susceptible cells that are actually infected. Use “%” to set the infection rate r (0-100).
    3. Try a series of runs with r in the range 50-70. How does the size of the epidemic change as you change r? For what value of r is the size of the epidemics most variable?

[ Top ]