Cellular Automata Laboratory

Cellular Automata Laboratory

Fourmilab home

Defining Rules

Each cell in the automaton has eight bits of “state” information. The eight state bits are combined to get a number between 0 and 255. It is important to thoroughly understand the “binary” or “base two” system by which this is done. The eight bits in a binary number like 11010010 are named and weighted from right to left as follows:

Bit number 7 6 5 4 3 2 1 0
Value 1 1 0 1 0 0 1 0
Weight
=
27
128
26
64
25
32
24
16
23
8
22
4
21
2
20
1

So 11010010 can be viewed as the number 128+64+16+2=210. Another way of characterizing this number would be to say that it has Bits #1, #4, #6, and #7 turned ON, but it has Bits #0, #2, #3, and #5 turned OFF. We often think of the cellular automaton as having eight planes laid over each other, and a cell's state bits as specifying the cell's one-bit states in each of the eight planes. The zero, bottom, or low plane is the plane that holds Bit #0. Note that Bit #0 counts as one in forming the number value of an eight bit state pattern, that Bit #1 counts as two, Bit #3 counts as four, and so on. This is sometimes a cause of confusion.

So each cell has a state between binary 00000000 and 11111111 (decimal 0 and 255). For a fully general cellular automaton, we might expect that at each update each cell can see all eight bits of each of its eight nearest neighbors. (Rug, for instance, is a rule of this nature.) But if we were to implement such generality for every rule, WebCA would run too slowly. Instead, most of the rule definitions require only that each cell be able to see the low bit #0 of its nearest eight neighbors. At each generation, each cell has, in other words, sixteen bits of information to base its new state on: it has the eight bits of its own present state, and it has 8 bits of information about its neighbors, one bit (the low #0 bit) from each.

In talking about a cell's neighbors, we think of a general cell, designated by •, as being surrounded by eight adjacent cells, named by the points of the compass.

NW N NE
W E
SW S SE

The eight bits of a cell's own state are called oldstate, and the eight individual bits of the cell's neighbors are called NW, N, NE, E, SE, S, SW, and W respectively. The cell's new state is called newstate. Defining a cellular automaton in WebCA involves specifying some program, function, or lookup table f for computing the output value for all 64K possible sixteen-bit inputs to the equation:

newstate = f(oldstate, NW, N, NE, E, SE, S, SW, W)

A cell's extra bits of individual state act like an individual memory. Keep in mind that a cell can see its own memory bits, but it can't see the memory bits of the neighbors. All it can see of its neighbors is their lowest bits.

The collection of all the bits representing the primary state of cells, those bits visible to the neighbors, is referred to as Plane 0, or the main bit plane. The collection of bits which hold the local cell state information are referred to as Planes 1, 2, 3, 4, 5, 6, and 7. These auxiliary bit planes can be configured to provide other information to rules, including random bits for rules which include randomness, spatial textures for position-dependent rules, and temporal phase for time-dependent rules. These uses for Planes 1–7 compensate for many of the limitations that would normally be imposed by restricting communication between cells to a single bit of state.

Although most of our rules conform to the description just given, it is actually possible to create and run other sorts of rules with WebCA. The three other general classes of rules which we allow are as follows:

  1. It is possible to define one-dimensional rules, where only the cells on the top line of the screen are updated. These one-dimensional modes are invoked by setting a variable called worldtype to one of the values 2, 3, 4, 5, 8, or 9.
  2. It is possible to define averaging rules where the new state depends on the low five bits of oldstate and on the full sum of the states of EveryCell's Neighbor. In worldtype 10, one gets the 11 bit sum of the eight 8-bit neighbors; and in worldtype 11, one looks at the 10 bit sum of four 8-bit neighbors. HeatWave is an example of an averaging rule which can be realized in WebCA by using worldtype 10.
  3. You can create user evaluator rules by writing any desired function which returns a sixteen bit number for each cell. User evaluator rules are created by writing a JavaScript evaluator function which computes this number. One uses this file by loading it with a rule which has its worldtype set to 12 or 13. The Langton rule is an example of such a rule. The user evaluator for Langton looks at three bits each of EveryCell and its North, South, East, and West neighbors.

A rule of any kind is defined by a function, written in either JavaScript or Java, which, when called with arguments representing the state of the cell and its neighbors, calculates and returns the new state of the cell. Rule functions are not, however, used directly while simulating the cellular automaton—calling a function for each cell on every step would run hundreds to thousands of times more slowly than the simulator operates. The functional definition of the rule is, instead, used to define a rule table which maps the state of the cell and its neighbors into the cell's new state. This rule table is either generated directly from a JavaScript definition or, for a rule defined in Java, written into a .jc file which can be loaded into WebCA to run the automaton it defines.

You can define rules by writing functions in JavaScript or Java. Let's use the most famous cellular automaton of them all, John Horton Conway's original game of Life. William Poundstone, in The Recursive Universe [Poundstone85], gives the rules as follows:

Each square cell has eight neighboring cells. It adjoins four cells on its edges and touches four more at the corners. During each moment of time, the player or computer counts the number of neighboring cells that are on for each and every cell.

If, for a given cell, the number of on neighbors is exactly two, the cell maintains its status quo into the next generation. If the cell is on, it stays on; if it is off, it stays off.

If the number of neighbors is exactly three, the cell will be on in the next generation. This is so regardless of the cell's present state.

If the number of on neighbors is zero, one, four, five, six, seven, or eight, the cell will be off in the next generation. There are no other rules.

Let's see how to turn that into code. The following sections explain how to define rules in JavaScript and Java, and how to write user evaluators in JavaScript. Because most users are likely to use only one language, information is duplicated in these three sections so that each may serve as a self-contained guide to rule definition in its respective language.


Previous     Next     Contents