Environmental Engineering Reference
In-Depth Information
Fig. 8.2 Neighbourhoods in cellular automata: (a) focal cell; (b) von Neumann neighbourhood
comprising the four adjacent cells - North, South, East, West; (c) Moore neighbourhood consid-
ering eight directly adjacent cells; and (d) a neighbourhood which consists of the nearest and
second-nearest cells. Other definitions of neighbourhoods are also possible
The Rules
Rules of the CA are fundamental to specify how cells change their states. There can
be an arbitrary number of rules. The rule-set for a CA applies to all cells. The
current state of a particular cell and the states of the cells in the neighbourhood
determine which of the rules are applied to change the cells state. The rules must
consider all possible combinations of situations which can occur in the neighbour-
hood of a cell. A very simple example of a rule for a CA would be that the state of a
cell can be any natural number, and that the subsequent state of a cell in the next
step is the sum of the states of the neighbouring cells. This rule would constitute a
deterministic CA. It would, however, also be possible to add stochasticity, e.g. by
determining that for a given probability the state of the focal cell is zero.
Running a CA: The Iteration
A CA is processed step by step. One step (one iteration) comprises an application of
the rules to all cells on the grid. To process a CA, the initial state of all cells must be
set. This initial configuration is used for the first update. Cell by cell the rules are
applied, taking into account the state of each cell and the state of cells in the
neighbourhood. This yields the next state of all the cells. To avoid a bias of the
update procedure, the new state of each cell is saved in a separate interim grid, so
that the transition is applied only once after all the states (or transitions) of all cells
have been calculated. Then the iteration can be repeated until a termination
condition is met. The termination condition can be a maximum number of itera-
tions, a pre-defined state of the grid, or an interruption by the user.
Boundary Conditions
Practical applications cannot work with infinite grids. The grid has to be spatially
limited and a specification is required on how to process the cells at the boundary,
