About U of O
Prospective Students
News & Events
Alumni & Friends
FranšaisLibrariesMapsKeyword Search and DirectoriesCoursesU of O Home







Cellular Automata "Mini-Models":
Emergent Spatial Structure in Vegetation Succession

By: David E. Atkinson, Mike C. Sawada and Konrad Gajewski

Paper presented at the Canadian Association of Geographers annual meeting,
Ottawa 1998


Slide 1

The purpose of the talk we present today is to demonstrate the use of a modeling methodology termed "cellular automata". I will first review the morphology and dynamical aspects of CA and then proceed into a brief history, leading towards some of the uses to which CA has been put in geography, ecology and other disciplines.

Mike will then review the technical aspects of our model operation and the results of experiments conducted to examine the influence of various adjustable parameters on the evolution of spatial structure in the model environments.

The model we present here is the essence of the model Mike and I and Konrad Gajewski will use to examine the response of the boreal treeline of northern Québec to various environmental forcing factors, such as climate amelioration in the post-glacial period.


A cellular automata model can be characterized by making reference to its physical layout, its rules of transition and the discrete nature of space, time and interaction within its world.

The spatial realm, or "universe", of any CA consists of a one, two or three dimensional space that has been divided into discrete units, or "cells", that completely fill the universe.

Each cell in a CA is irreducible, or discrete, in nature and thus is capable of taking only one value, or "state", selected from a finite set of states. The cell forms the lowest limit of spatial resolution in a CA, much like a single pixel in a raster image from a GIS or satellite image.

Slide 2

Here is the layout of the grid. Because interactions in a CA are local scale, the frame of reference changes continually with each cell considered. Thus, at this point the white cell in the middle is the cell under consideration and the cells surrounding the middle cell form "the neighborhood". The dark blue cells represent a "von Neumann" neighborhood structure and the dark blue and red cells taken together constitute a "Moore" neighborhood structure.

Usually, a CA structure is a square grid, although triangular and hexagonal cell spaces have been used.

Slide 3

Other characteristics of Cellular Automata include such things as:

  • The fate of any cell is governed by local-scale interactions with its neighbors, or what are termed "transition rules".
  • The transition rules reflect system dynamical agents as applied at the local-scale . These govern things such as interspecies competition, reproduction, death due to overcrowding.
  • Transition rules are either deterministic or stochastic (i.e. probabilistic)
  • .
  • Time steps are discrete and indivisible within the model.

It is the set of simple, local-scale rules that, when applied over thousands of neighbor interactions over scores or hundreds of time steps, determines the spatial structure for the entire universe under consideration.

Slide 4

Here is a generalized transition rule expressed in formalized notation for a von Neumann neighborhood.

Briefly, the state any cell a will take at the next time step is a function f of its own state at time t and the state of its neighbors at time t . The function f represents the transition rule set.

Slide 5

Here we can follow through the application of a simple transition rule. The cell under consideration possesses state zero. There is a transition rule that specifies when a cell will take state one and when it will take state zero. In this case, a cell will take state one if exactly three of its neighbors possess state one. Application is a simple matter of polling the neighborhood and comparing against the transition rule. In this case, three neighbors possess state one. Thus, the state of the cell under consideration is set to 1, to be implemented at the next time step. Focus then shifts to the next cell down (or to the right) and the application of the transition rule is repeated.


Slide 6

I will now briefly review the history of Cellular Automata.

The earliest work on CA began in the 1950s by John von Neumann, one of the main workers on the ENIAC project. He was interested in the concept of "machine self-replication", and after a suggestion by Stanislow Ulam, began to use CA to create machines that could control information and processes to reproduce themselves or to construct other entities.

These early CA are very similar in form and function to CA models used today: they possessed grids made up of discrete elements, discrete states and time steps, and transition rules that governed the evolution of a cell.

In general, CA from the pre-1970s were confined to computer science and digital electronics. Its spread into other research fields was limited by a lack of computer availability and power.

Slide 7

Much theoretical work was laid out by the early workers in CA, including:

  • 2- and 3-dimensional structures
  • transition rules that are not stationary, meaning the transition rules can change according to some function that is time, space or neighborhood dependent
  • deterministic and stochastic rules
  • cell age limits, an important consideration for ecological/biological applications
  • neighborhoods of 4 (von Neumann) and 8 (Moore) square elements
  • universe constructed of various geometric elements (square, triangle, hexagon)

Slide 8

In 1970 an article appeared in Scientific American describing a CA model that, although small and not particularly complex, was very important in raising awareness of Cellular Automata. This was an article by Gardner detailing a "mathematical recreation" devised by the Cambridge mathematician Conway, called the Game of Life. It is a simple example of a CA that uses a deterministic, completely stationary transition rule set on cells that can possess one of only two states. Its significance lay more with the fact that it brought the concept to many people. It is one of the most frequently cited CA references.

Throughout the 1970s the concept began to permeate into other disciplines. That plus an increase in availability and power of computers meant that CA models were more frequently actually implemented on computer and were being applied to model problems and systems in nature.

Slide 9

In the 1980s the dominant force in CA modeling was Stephen Wolfram. He published papers formalizing aspects of the mathematics and statistical mechanics of CA and demonstrating the application of CA in such fields as artificial life, fluid dynamics and cryptology. He initiated the modern study of the "Science of Complexity", which is tasked with investigating the ability of simple structures with simple, local scale transition rules to generate large-scale patterns possessing great complexity.

Also in the 1980s University of Ottawa professor Michel Phipps devised the "neighborhood coherency principle", an important early contribution to CA modeling as applied to ecology.

Now, before describing our CA model, I will detail recent applications of CA in ecology.

Ecology Applications

Slide 11

Since 1990 CA has been applied to various questions in ecological research, including:

  • effect of spatial pattern form on species coexistence or diversity
  • succession modeling
  • disturbance modeling
  • environmental gradient forcing
  • effect of different plant strategies on community structure
  • wave regeneration of trees
  • host-parasitoid relationships
  • predator-prey relationships

Our model

Slide 12

The van der Laan model is a three-state probabilistic CA. It considers state zero also called the dead state, state one also called species A and state two also called species B. Three types of competition between cell states can be modeled:

  1. Coexistence, where the probability of a cell in state 1 or 2 becoming state 0, or dead, is greater if its neighborhood contains states of its own kind. Here we do not expect large tessarae of any cell to develop.
  2. Contingent competition, where the probability of a cell dying is greater if its neighborhood contains more cells of a different state. Here we expect large tessarae of each cell to develop.
  3. Dominance, under dominance a species in any situation is more robust than another species. In our model this is represented as a gradient across the cellular space, such that, in the left side of the universe one species dominates over another and vice versa on the other side.

Slide 13

The following schematic outlines the operation of our model.

Boxes in yellow correspond to the basic van der Laan model and blue boxes represent our extensions upon this basic model:

  1. We initialize three two-dimensional arrays, one contains the states of cells at time t, the second the states at time t+1 and the third contains the age of each cell at time t.
  2. At this point a random age structure can be introduced to the cells which eventually determines their probability of undergoing competition.
  3. After initialization looping begins, one loop for the number of generations and one for each cell in the cellular universe which also applies the rule sets for each cell.
  4. The edge structure is determined as is the neighborhood of influence for each cell, a Moor Neighborhood in our case.
  5. A dead cell, state 0, chooses a random neighbor. If this takes place then the loop is exited and the next cell is considered.
  6. If a cell is in state 1 or 2 then it has a probability of dying.
  7. If it does not die then a rule set specific to the state of the cell being considered is applied. These rules are based on the competition types previously noted and determine the state of a cell in the next generation as a function of its current state and that of its 8 nearest neighbors.
  8. This loop is repeated for every cell in the universe and new states are updated each time in the second array.
  9. Once the states in the generation are determined then the current cellular universe and its corresponding cells are sent to analysis modules which determine, amongst others, the average patch sizes, area, perimeter, and fractal dimension for each generation.
  10. Then the states at t+1 are updated as the states for time t.
  11. If a disturbance has been specified it is now applied and can take the form of either a symmetrical species unspecific, patch specific or species patch specific disturbance.
  12. The loop is repeated for each generation.

Slide 14

The model parameters can be specified by the user in this form according to the specific goal of the simulation.

  1. Our simulations used 200x50 cell universes with an island structure.
  2. All the simulations have the same parameters of Beta = 5% (the probability of a cell dying due to neighbors of its own kind) and Lambda 2.5 to 7.5% (the probability of a cell dying due to neighbors of another kind) with Omega = 0 (the probability of a cell dying for some other reason). Note however, these values are used differently in each type of competition modeled.
  3. Our first set of runs introduce the van der Laan model which contains a gradient from coexistence to contingent competition, followed a run with dominance and then these runs with an age structure and disturbance regime.


Slide 15 (for discussion slide click here)

  1. Here is a pair of runs to demonstrate the basic functioning of the van der Laan model without our extensions.
  2. This simulation has two different starting densities but the same rule sets.
  3. There is a gradient, such that, coexistence is modeled on the left side of the universe and grades into contingent competition on the right side of the universe. In other words, the probability of a cell dying due to neighbors of its own state is greater on the left side of the universe than on the right side of the universe.
  4. First, on the left is competition modeled with an initial 100% density of states 1 and 2 and second with an initial 1% density of 1 and 2 states.
  5. Both show smaller patches and more fragmentation on the left side and larger patches or tessarae on the right side of the universe.
  6. However, the initial density has effects on the patch size at generation 500, such that, with a low initial density the tessarae are much larger.
  7. In terms of average patch size, with a 1% density, both species increase rapidly initially creating large patches. At which point the average patch size slowly decreases as competition leads to fragmentation of the larger patches at the edges.
  8. This, note, is reflected in the Fractal Dimension which indicates that patches are more complex in the high density run.
  9. Also of interest, is the implicit development of feedback in the system. At the left side of the universe there is implicit negative feedback, such that, large tessarae are discouraged from developing. On the right side of the universe there is positive feedback which encourages the development of large tessarae, but only to a point. Once two large tessarae develop they have a negative feedback relation due to contingent competition at their edges.

Slide 16 (for discussion slide click here)

  1. This run has the same parameters as the previous but models dominance from two different initial conditions.
  2. The Average Patch Size results are similar with the qualification that the average patch size under the random start becomes larger for both species.
  3. However the fractal dimension is more difficult to interpret at this time.
  4. Also, at the 500th generation we find with the low density initial conditions, remnant patches of both species outside of their optimal range, this is due to the dynamics of the initial increase in patch sizes, such that, large patches which developed outside of their optimal ranges persist for longer due to initial large tessarae

Slide 17 (for discussion slide click here)

  1. This run illustrates the previous Coexistence to Contingent Competition run but with our extension of the model with an age structure.
  2. Here, the maximum ages for each species in terms of generations are assigned to each state at the beginning of the simulation, creating a uniform age structure for each species.
  3. The probability of a given cell undergoing competition effects is directly proportional to its age. The younger the cell, the more susceptible it is to death due to competition. A cell, which reaches its maximum allotted life span, must of course die.
  4. We have three runs where species A the red cells are assigned an age of 40 generations and we vary the age of species B each run by decrementing its maximum age by 5 generations.
  5. We do this to determine whether the longer lived species has a competitive advantage with all other things being. Furthermore, we want to see how initial mass deaths lead to large die-offs of one species, which as a historical factor may be important in the evolution of the end spatial structure.
  6. In the first graph, we see that each species begins with initial average patch sizes which are nearly identical, that is, until the initial die-off begins between 30 and 40 generations. At this point the average patch sizes for each species within a given run rapidly diverge. The species which died first ends up being excluded from many areas. The exception is when the maximum age of both species is the same.
  7. This illustrates how the present spatial structure is influenced by historical events long after they have occurred even when no present trace of these events remains.
  8. The Fractal Dimension indicates that patches are most complex under an equal age structure. Fractal dimensions become less complex as the age difference increases. This is largely due to the fact that the species with a longer life-span becomes more dominant and creates larger homogeneous patches which percolate, that is, decrease the perimeter/area ratio.
  9. Finally, we can see the degree to which age structure is important in the competitive dynamics by looking at this figure. This figure illustrates the number of dead cells each generation. It shows that the die-offs of fully mature cells oscillate with a dampened amplitude. At approximately generation 200 a random age structure has developed and the number of dead cells each generation cannot be distinguished from a run with the same parameters but no age structure. However, this is not to say that the field at 500 generations is identical since the initial age structure has significant effects on the end structure.

Slide 18 (for discussion slide click here)

  1. This run is similar to the previous but with dominance.
  2. The major difference is in the average patch size trend of the species with the shorter life-span. This graph shows that, although there is a divergence after the initial die off, because species B the blue species is dominant on the left side of the universe it continues to grow. Under the previous model, species B trended toward smaller and smaller patches to eventual extinction with a large age difference in some simulations.
  3. The fractal dimension is again like the previous dominance run and is difficult to interpret at this time.

Slide 19 (for discussion slide click here)

  1. This run represents coexistence to contingent competition under three different disturbance regimes. In each case, the chance that a disturbance will occur in any generation is 15 percent.
  2. Run A shows a disturbance that produces square blocks occupying 5 percent of the universe. These disturbances are species independent.
  3. Run B shows a disturbance that affects patches. Either species can be affected, but a given disturbance is limited to one species and one patch.
  4. Run C shows a patch-specific disturbance regime that is limited to one species, species A.

Where disturbance regimes are concerned, I would like to draw your attention to this graph which illustrates the number of cells of each species in each generation.

With square symmetrical disturbances under the coexistence to contingent competition model, the species dynamics follow more closely a model run with the same parameters but without any disturbance regime. Chance, in this case, determines the advantages one species will gain over another.

With patch specific disturbances that can take place in patches of either species under some empirical or probability density function, the divergence of the dominance of each species takes place quite early, indicated by the black (purple) lines. Since the disturbance regime is patch specific but species unspecific, competitive advantages between the species can rapidly change depending on the disturbance and its magnitude. Note the two change overs in the dark lines. Here species A begins the run by increasing its dominance over species B. Suddenly a disturbance takes place in a large patch of Species A and the relation immediately shifts. Then, for sometime, species B dominates, and at approximately generation 370 a massive low frequency high magnitude disturbance destroys a lot of Species B and quickly Species A begins to take over. At the end of the run, species A largely dominates the space as seen in the second figure.

Similarly, and not unexpected, with the same disturbance frequency but specific to patches containing Species A, by the end of the run Species B dominates the field.


In our current model, the rules by which cells change states are not space-time stationary. In order to incorporate environmental gradients that influence state changes in different areas of space we have introduced gradients which influence how the rules are applied for each cell. Furthermore, in order to introduce an age structure to the model we found it necessary to break the time stationarity rule as well, such that the probability of a certain rule being applied changes according to the age of each cell.

Although we base our model nomenclature upon the van der Laan model of competition, we could have called the model "state succession across environmental gradients". This is because the essence of cellular automata deals with state changes as a function of local neighborhood interactions. In this sense, our competition gradients represent environmental gradients which affect the probability of a given cell adopting a given state in the next generation.

In general, it is apparent that the system portrayed here is sensitive to a number of parameters. Further work with this model will include analyses to better quantify the observed sensitivities, in order to determine critical or "threshold" values.

As geographers, we are fundamentally interested in spatial relations and the processes which give rise to spatial structure in the landscape which surrounds us. From this perspective, our current model is generic and applies to no specific 'real-world' situation. However, from this we find that cellular automata may be a unique tool that will allow us to understand and generalize the processes which give rise to 'real-world' spatial structure.



About U of O | Prospective Students | Students | Services | Academics | Research | News and Events | Alumni and Friends

System requirements | Feedback | Privacy Policy | Accessibility

© University of Ottawa
If you are looking for additional information, please contact us.
Technical questions or comments about this site? Last updated: 2009.11.23