Summary
A generic and fairly complete cellular automata simulation engine.
Overview
CAGE is a fairy generic and complete cellular automaton simulation
engine in Python. It supports both 1D and 2D automata, a variety
of prepackaged rules, and the concept of "agents" which can move
about independently on the map for implementing agent behavior.
CAGE comes with numerous examples of fullyfunctional CA systems,
including Conway's Game of Life, Langton's selfreproducing
automaton, Langton's "vants," and 1D automata rule explorers. It
also comes with simple displayers (including a curses interface
for 2D automata). Also included is a unique implementation of a
finite state machine (ant.py).
Note that CAGE is implemented entirely in Python, and due to its
very generalized nature, is not designed for speed. It is
sufficient to update a 80x24 Conway's Game of Life grid at a few
times per second on a modern machine. CAGE is intended primarily
as an education toolkit, rather than an industrialstrength CA
simulator.
Getting the software
The current version of cage is 1.1.4.
The software is available in a tarball here:
http://www.alcyone.com/software/cage/cagelatest.tar.gz.
The official URL for this Web site is
http://www.alcyone.com/software/cage/.
License
This code is released under the LGPL.
Introduction
In very general terms, a cellular automaton has the following key
features:
time is measured in discrete steps, called time units;
a network of cells, each of which with a welldefined state at
each time unit;
at each time unit, each cell has a series of other cells which
constitutes its neighorhood;
the state each of cell changes according to a state transition
function which depends on the state of that cell and the states
of the cells of its neighbors;
in synchronous automata (the typical usage), all cell
transitions take place simultaneously.
In most cellular automata (and most textbook definitions), the
cellular network is arranged into a rigid lattice (i.e., a line
or a grid), and for any given cell its neighborhood is constant
(that is, the same for all time steps). These assumptions,
however, are not present in CAGE.
CAGE employs the following abstractions of the cellular automaton
model (and classes):
 State
 The state of a cell is repesented with an integer
from 0 to N, where N is the total number of allowed states.
 Address
 An address is merely a tuple of one more integers
that represents the location of a cell in a given topology.
 Dimensionality
 The number of elements of the tuple in an
address; this must match the dimensionality of the topology
being used.
 Topology
 Topologies determine the arrangements of cells in
a network. Topologies can be bounded (where they have an edge,
and any addresses off that edge are taken as having some
background state), or unbounded (usually where they wrap around
on themselves, such as for the surface of a sphere). Topologies
have the ability to normalize addresses, and additionally can
make morphologically identical clones of the same size and shape
(not necessarily their actual cellular states) for synchronous
automata that need to maintain multiple topologies for the sake
of simultaneous update. Note: Topologies and neighborhoods
are intended to be used as mixin classes, in order to make maps
that automatas use.
 Neighborhood
 Neighborhoods encapsulate the translation of
addresses (not cell states) to a list of their neighbors, taking
into account the topology they are connected with. The abstract
Neighborhood class also supports a wide variety of helper
methods (which need not be overridden) in order to help do
common operations with neighborhoods, such as finding neighbors
in a given state, summing the states of all neighbors, etc.
Some automata make a distinction between inclusive and exclusive
neighborhoods  inclusive ones include the cell itself (whose
neighborhood is being computed), whereas exclusive ones do not.
CAGE does not make this distinction; some helper methods support
an optional inclusive argument for making this distinction; the
list of neighboring addresses should never include an address
consisting of all zeroes. Note: Topologies and neighborhoods
are intended to be used as mixin classes, in order to make maps
that automatas use.
 Map
 The Map is the highlevel class that the Automaton uses
in order to do operations on the cellular network, intended to
be a mixing of a Topology and a Neighborhood.
 Automaton
 The Automaton class is the core of the CAGE
system. An Automaton knows how to update itself each turn; this
is the primary class which does the busy work of processing a
cellular automaton system. Typically the Automaton class stores
a map, and has a rule method that specifies the transition
function. There is no restriction that an Automaton must house
exactly one map; for an agentbased automata it might store
none, or for interacting automata overlaid on top of each other
it might store several.
 SynchronousAutomaton
 A synchronous automaton is one in
which all processing is done simultaneously  that is, during
the processing of an update, the transitions of any given cell
will not affect the transition of any other cell. For this to
be accomplished, the SynchronousAutomaton creates and stores a
clone of the map in order to act as a work area, and the real
and work maps are swapped when processing is complete.
Most cellular automata are typically synchronous.
 Rule
 The rule class is an optional mixin class (intended to
be mixed into an Automaton) which implements generic rules that
are independent of topology, neighborhood, and/or
dimensionality.
 Agent
 CAGE supports the concept of agents, which are
individual objects that can interact with the automata
independently of a cell. Agents typically have a location
(specified as an address) and a direction, which allow them to
move freely over an underlying automata topology (though
strictly speaking it is not necessary for one to exist). This
allows simulation of, for instance, Langton vants, or ants which
drop pheromones, and so on.
 Direction
 To facilitate implementing independent agents,
CAGE also introduces the abstraction of a direction, which
allows agents to specify a facing. Directions are subclassed
according to the topology and neighborhood they would be most
appropriate for. Directions have a facing, as well as an
advance method which allows agents to move along the direction
specified.
 Initializer
 An initializer is used to set the initial
states of an automaton map to the desired settings before the
automaton begins.
 Player
 Finally, a player represents the abstraction that
displays an automaton on the screen. Two main classes are
provided, a LinePlayer for use with 1D automata, and a
CursesPlayer, which uses curses to display 2D automata and a
simple user interface. Also included is an ImagePlayer, which
uses PIL to
render a "movie" of a 1D automaton. Players support a size
attribute that can be passed into a map/automaton constructor
that supports dynamic sizing of the map to the terminal size;
for this reason, a Player is constructed, and then an Automaton
is constructed with its size attribute; this allows the Player
to give feedback to the Automaton, so that, for instance, the
screen size can be autodetected by the Player.
Known issues
CAGE is not designed for speed, and probably never will be. It
is designed primarily for educational or experimental purposes.
However, given the speed issues, some inPython optimizations
might be in order, such as support for only updating
dynamicallyresizing regions for automata with largely quiescent
states, to reduce processing overhead. Since speed itself is
not the primary concern, this is a fairly low priority, however.
Only 1 and 2dimensional topologies are truly supported,
although the core system could be easily extended to support 3
or higherdimensional automata. Visualization, of course, would
present a problem.
There is strictly no need for states to be represented as
integers, perhaps the concept of a state could be generalized to
include any object which support the required operators
(integers, rationals, floats, even vectors).
Wish list
Use of NumPy for faster array access.
For interactivity, help screens in the CursesPlayer and the like
are probably warranted.
A more uniform form of invocation of each of the sample
automata, e.g., command command line arguments for specifying
the neighborhood, boundary conditions, number of states, and so
on, via command lines.
An obvious enhancement would be a module which can read and
write standard cellular automata pattern file formats.
An interactive graphical Player would be a good idea, maybe
using Tkinter one of the other user interface libraries.
More examples, especially of Agentbased automata, are
warranted. Some of the systems described in the first few
chapters of A New Kind of Science, for instance, are
promising.
A sort of reverse map for agents would be a good idea, so that
automata with the need to lookup agents at a particular address
would be easier to write.
References
Cellular Automata Machines, Toffoli, Margolus.
Cellular Automata and Complexity, Wolfram.
Cellular Automata: Theory and Experiment, Gutowitz (ed.).
A New Kind of Science, Wolfram.
Release history
1.1.4; 2006 Jul 29. Minor organizational changes; add stepping
stone automaton.
1.1.3; 2003 Oct 5. Fix AsynchronousAutomaton updating method;
add a chain reaction demo; changed license to LGPL.
1.1.2; 2002 Nov 4. Workaround for reported crashes on some
Linux systems in either curses or the Python curses glue layer.
1.1.1; 2002 Jul 23. The Conway automaton inadvertently
defaulted to "high life" instead of the standard rule.
1.1; 2002 Jul 21. More examples, much better abstraction of
dimensionality, PointInitializers, simple ImagePlayer (using
PIL) and rule 110 example, concept of Rule mixins, 1D
nontotalistic and totalistic rule examples, separation of
concept of "icon" from Automaton classes.
1.0; 2002 Mar 29. Initial release.
Author
This module was written by Erik Max Francis. If you use this software, have
suggestions for future releases, or bug reports, I'd love to hear
about it.
Version
Version 1.1.4 $Date: 2006/07/29 $ $Author: max $
Modules and Packages


110 
Same 1D rule 110 displayer using PIL. Note that the display does not

1d 
A trivial 1D automaton rule explorer. The example used here is for

1dtotal 
A trivial 1D automaton rule explorer. The example used here is for

ant 
A sample implementation of a unique finite state automaton with agents.

brain 
An implementation of the threestate Brian's Brain rule.

cage 
A fullfeatured, generic cellular automata engine in Python.

chain 
A simulation of a chain reaction.

conway 
An implementation of Conway's Game of Life, really just a specialization of

cyclic 
An implementation of the Demons of Cycling Space automaton. Note:

diamonds 
A simple reduction automaton that generates diamond patterns.

langton 
An implementation of the Langton selfreproducing automaton.

packard 
An implementation of Packard's automaton.

parity 
An implementation of a trivial parity rule as a reduction automaton.

rug 
An implementation of the rug rule.

squares 
A simple reduction automaton that generates square patterns.

stepping 
An implementation of Packard's automaton.

sugar 
An implementation of the BelousovZhabotinsky reaction. Note: This

total 
An implementation of arbitrary twostate totalistic automata.

vant 
An implementation of Langton's virtual ants (vants).

vote 
An implementating of the voting rule.

wire 
A WireWorld simulation.


