Last edited 4may05 by firstname.lastname@example.org
Find this document at http://www.ncsa.uiuc.edu/Classes/MATH198/lmendes/banister.html
To view Scott Banister's original webpage, click
The following is an excerpt from Banister's original documentation
CAVEvolve is an interactive 3D cellular automaton that uses the Von Neumann
neighborhood. It is modeled after Stanislav Ulam's 2D game, Reproduction,
which CAVEvolve can also play. The user can control both the rules and
the display of the automaton.
In order to explain the basics of CAVEvolve (hereinafter called Evolve) it
is helpful to first explain the game upon which it is based, Stanislav Ulam's
Reproduction. A concise description of the original game can be found in
_The Second Law_ by P.W. Atkins, which is where I first discovered the game.
"A counter is placed at the center of the board. The next generation is
formed by placing a counter on any empty square that has one and only one
occupied immediate neighbor. (Neighboring squares are taken to be the four
to the north, south, east, and west, not the diagonal neighbors.) Then the
rule is applied again, after which the grandparent generation of counters
is removed (the original seed at this stage). After the next round of
generation of children, the second generation, also now grandparents, is
removed. The procedure is then allowed to continue indefinitely."
To take this game into 3D I simply extend the neighborhood (which is
called the Von Neumann neighborhood, as opposed to the Moore
neighborhood which includes diagonal neighbors) along the z-axis. This
gives each cell 6 neighbors. Other than that, the rules remain the
same, except that I make almost every aspect of the rules configurable
by the user. The rules for generation and display which the user may
change are listed below, with explanations:
RULE: This is the basic rule used to determine births. I use 2
numbers, L (lower bound) and U (upper bound) to describe the birth-rule
set. On the screen this is displayed as a bracketed pair, [LU]. A
birth will occur in any cell where the number of occupied neighbors is
greater than or equal to L but less than or equal to U. In the
original game, the rule is ; exactly 1 occupied neighbor is
required for a birth to occur. While this is the default rule in
Evolve, the user is allowed to experiment by changing both L and U.
FERTILE: This is the number of previous generations which will affect
births in the current generation. In other words, it's the number of
generations which count as neighbors in the neighbor count. This
number is 2 in the original game because each cell is allowed to
"reproduce" in two cycles before it becomes a grandparent and gets
removed. This is also the default in Evolve. The user can experiment
with this number to see how it affects the automaton.
FILL LEVEL: This number controls how many generations back cannot be
the site of a new birth. It is called the "fill level" because the
more generations that are protected, the less the cellular universe
fills up with cells (when only the current generation is being
displayed). It is represented as a negative number so that increasing
the fill level toward 0 also increases how filled the universe looks.
For example, in the original game this number is -2, because new cells
are not allowed to be born in spaces where the previous two generations
are located. In Evolve, this number defualts to -19, because I found
that a a filled up universe is not very interesting to look at.
Setting the fill number to a high number forces the new generations to
expand only outward and form a hollow shell.
GENERATIONS: This is the number of recent generations which will be
displayed. Two generations are displayed in the original game, but in
Evolve the default is one because it cuts down on the clutter.
In Reproduction, the number fertile, the fill level, and the number of
generations displayed are all the same variable determined by when old
counters are removed from the playing board. Evolve separates them
into three separate variables to allow for greater flexibility and more
experimentation. Although not mentioned above, the user can also
change the size of the universe, change the number of initial seeds and
their placement, or choose from 8 predefined models which show examples
for 1 initial seed up through 8 initial seeds.
The 3D universe in which the game is played is represented as a
100x100x100 array. When counting neighbors, the universe wraps around
from left to right, top to bottom, and front to back; thus, while the
universe is represented as a cube of cells on the screen, the universe
is actually toroidal in structure. The default size for the cube is
31x31x31, represented as size 15 in the program (2 * 15 + 1 = 31).
Each cell in the cube is originally assigned the number 0. 1 or more
live cells are then added; they are set to a value of 1. As the game
progresses, the most recent generation of living cells (those just
added) always have a value of 1, while previous generations (if they
haven't been overwritten with a new birth) have a value corresponding
to how old they are (2, 3, 4, etc.) This allows me to display any
number of generations simply by adjusting a cutoff value for what gets
Rather than having each empty cell count the number of occupied cells
around it, occupied cells alert each surrounding empty cell of their
existence. Each empty cell then determines how many occupied cells are
around it by the number of alerts it received. In general, this makes
the program quite a bit faster, especially near the beginning of a game
when the number of empty cells greatly outnumbers the number of
occupied cells that are involved in the the birth process.
An experiment with randomness can still be found in Evolve, although
the results were uninteresting. In the most random mode (level 4) each
living cell randomly picks a set of two neighbors to inform of its
existence: left and right, top and botom, or front and back. This
produces results which look . . . random. It makes the game field look
more like a particle explosion than an ordered colony of cells. Three
other random modes pull the random choice further out of the for loop,
so the same choice is made for every set of z's in a given xy-plane
(level 3), every set of yz-planes for a given x (level 2), or every xyz
in a given generation (level 1). Level 1 looks the most interesting
simply because it has the least random choices.
I added a 2D mode in order to be able to play the original Reproduction
game. Evolve can switch to 2D mode on the fly and play in the
xy-planes, the xz-planes, or the yz-planes. The 2D game is actually
rather interesting; it produces really interesting Persian rug-like
patterns if the number of generations displayed is cranked up to around
6. 2D mode and random mode cannot work at the same time; 2D mode takes
precedence if there is a conflict. Designing the two modes to allow
them to work simultaneously is left as a possibility for future