Last edited 4may05 by lmendes@uiuc.edu
Find this document at http://www.ncsa.uiuc.edu/Classes/MATH198/lmendes/banister.html

Scott Banister


To view Scott Banister's original webpage, click here.

The following is an excerpt from Banister's original documentation of CAVEvolve:

ABSTRACT

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.

DESCRIPTION

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 [11]; 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 drawn.

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 improvement.