Background material on the following topics is available on this site:

• Geosimulation
• Spatial complexity
• Cellular automata
• Agent-based models
• Land-use and transport models
• 3D visualization and geovisualization

Cellular automata have their foundations in the specification of digital computers. They were pioneered by Alan Turing, John von Neumann, and Stanislaw Ulam, initially as computing media. Later, they have been adopted by other fields outside of computing and put to a wide variety of applications. They have been used in the simulation of urban phenomena with a recent flourish of activity. If you are interested in learning more about cellular automata: their origins and their use in urban geosimulation, you can check out a working paper, entitled, 'How cellular models of urban sytems work', penned by yours truly.

Cellular automata consist of several key components: cells arranged evenly on a tessellated grid-space, cell states, neighborhoods, transition rules, and time.

The cell space on which a cellular automaton operates might be considered equivalent in an urban sense to an environment, a landscape, or a territory. The cell space in a cellular automaton is assumed to be both regular in structure, i.e., it resembles a checkered grid like a chess table (although it does not have to be regular), and infinite in extent (infinity is generally achieved by describing the cell space as a torus: its edges 'wrap around' on themselves; again, the cell space does not have to be infinite in extent).
Just like the pixels that comprise a television screen, the individual cells in a cellular automaton are occupied at any given time by a discrete state, e.g., full or empty, alive or dead, yellow or blue, one or zero. In an urban context the cell state can be made to represent any attribute of the urban environment, e.g., land use (residential or commercial), density (high density or low density), land cover (forested or concrete), etc.

Each cell in the cellular automata has a neighborhood of adjacent cells that surround it. Neighborhoods are commonly characterized as either being 'Moore' (the cell in question and the eight surrounding cells that border it) or 'von Neumann' (the cell in question and its four cardinal neighbors), as the diagram below illustrates. However, a neighborhood can be specified to represent any form of action-at-a-distance.

Simple spcifications for a one-dimensional CA

Simple spcifications for a two-dimensional CA

Certain rules included alongside the model in a transition table govern the state of any given cell in the matrix at any given time in the evolution of the model. These transition rules are applied to cells synchronously, altering the state of cells according to their individual condition and the condition of adjacent cells in the neighborhood. One of the most famous sets of transition rules in John Conway's Game of Life. In the Game of Life, cells are considered to be 'alive' (their state is coded as 'alive') or 'dead'. In each iteration of the model, transition rules are applied to the cells' states. A 'live' cell in one iteration remains 'alive' in the next iteration if its neighborhood contains either two or three other alive cells, otherwise its state is coded as 'dead'. Additionally, a 'dead' cell in one iteration can become 'alive' in the next if its neighbourhood contains exactly three 'live' cells.

Of course, in an urban context, transition rules can be constructed to represent any process affecting an urban system, e.g., a cell is suitable for conversion from vacant to developed if all cells in its neighbourhood have states corresponding to 'extremely high land value'; otherwise it remains vacant.

As the previous discussion of transition rules alludes to, time in cellular automata is discrete. It proceeds in iterative steps, 'jumping' from one point to the next: t; t+1; t+2; t+3; ...; t+n.

A three-dimensional Sierpinski carpet (source: Paul Bourke, http://astronomy.swin.edu.au/pbourke/fractals/gasket).

Cities and cellular automata
There are many advantages to applying cellular automata models to urban systems: realism, spatiality, resolution, presentation, and links with geographic information systems, object-oriented programming, and remotely sensed data.

Cellular automata have been used as a simulation technique in the study of an impressively wide range of urban phenomena, including regional growth, urban sprawl, gentrification, Pareto equilibrium, residential growth, population dynamics, economic activity and employment, historical urbanization, land use evolution, and polycentricity to name but a few.

Cellular models of urban systems
Cellular automata models have enjoyed a wide application to the study of urban phenomena. In the formal sense described by the original devleopers of cellular automata--Turing, von Neumann, Wolfram, Conway-- cellular automata are quite rigid in their structure. This rigid structure works well in the simulation of many physical systems in biology, chemistry, and physics, but wanes as an appropriate framework for studying socio-enviro-economic systems such as cities. Understandably, researchers have adapted the formalism of the traditional cellular automata to suit their simulation needs. In this sense, many cellular-automata--like models of urban systems are really cellular models rather than cellular automata.

The formalism described in the first section of this page is adapted to meet the needs of urban researchers in several ways:
Cell space: Of course, the idea of an infinite spatial plain is unrealistic in an urban context. Cellular automata are therfore constrained in their cell space to finite dimensions. The regularity of this space is also questionable in urban contexts. Some cities are quite regular in their structure (at least from the perspective of block configuration, say, in a city like Manhattan), but most are markedly irregular, e.g., cities such as Dublin, Athens, Venice, etc. Recent research has adapted the structure of cellular automata spaces and rendered them irregular.

Cell states: In the traditional cellular automaton, cell states are discrete (and quite often binary): alive or dead, one or zero. There is little in the city, however, that is discrete. Most conditions--land use, land value, land coverage, demogrpahic mix, density, etc.--are continuous, and of course urban spaces are multi-faceted. Therefore, cellular models of urban systems commonly contain several cell states simultaneously, and these states range in type from absolute to discrete and to continuous. An innovative adaptation to the traditional idea of the cell state is the introduction of fixed (states that cannot be altered by transition rules) and and unfixed cell states, corresponding respectively, for example, to water sites or land values.

Neighborhoods: The idea of the neighborhood in the formal cellular automaton is rather restrictive. Urban neighborhoods come in many shapes, configurations, and sizes. Complaining that neighborhoods such as the Moore and von Neumann restrict the level of spatial variation that cellular automata models can generate, many researchers have tinkered with neighborhoods to include the notion of 'action-at-a-distance'. Cell neighborhoods consisting of 113 cells, have in some cases been used in simulations.

Transition rules: Perhaps the greatest tinkering with cellular automata models comes in the formulation of the transition rules. It is here that cellular models of urban systems are generated with adherance to what we know in theory about cities. Recently, urban studies using cellular models have intriduced an innovative range of parameters into transition rules in a bid to enhance their realism. These parameters have included probabilistic functions, utility-maximization, accessibility calculations, exogenous links and constraints (linking cellular models to other models), weights, hierarchies, inertia, and stochasticity.

Cellular automata and agent programming environments
Here is a list of cellular automata and agent-based modeling platforms. Most of them are available under the GNU or GPL Public Licensing Agreements (which means that you can get the source code for the package and modify it, if necessary, to suit your own needs; you cannot use the package commercially, however.) You may also be interested in looking at the COSI project homepage at the Institut de Recherche en Informatique de Toulouse, France, which is investigating various ways to model complexity.

Cellular automata and agent programming environments
Here is a list of cellular automata and agent-based modeling platforms. Most of them are available under the GNU or GPL Public Licensing Agreements (which means that you can get the source code for the package and modify it, if necessary, to suit your own needs; you cannot use the package commercially, however.) You may also be interested in looking at the COSI project homepage at the Institut de Recherche en Informatique de Toulouse, France, which is investigating various ways to model complexity.

Dynamic physics for built infrastructure

Moving agents through space and time

Modeling riots

Validating agent-based models

Machine-learning behavioral geography

Accelerating agent-based models

Megacity futures

Immersive modeling

Space-time GIS and analysis

A toolkit for measuring sprawl

Modeling time, space, and behavior

Simulating crowd behavior