## Cellular Automata Laboratory |

This section contains quite advanced material and should not be tackled until you a) have a thorough familiarity with CelLab and b) understand JavaScript programming.

The section arose because Rudy kept asking me to add new modes to the basic program. First he wanted a one-dimensional mode. Then he wanted a mode that can see more than one bit of neighbor state so he could do the Rug rule. Each of these changes involved adding new code to the main simulator program, which meant I had to keep remaking all the rulemakers. And each addition only stimulated more requests. What a drag….

In order to get out of the business of adding custom evaluator after custom evaluator, and to completely open the architecture of the program, rendering it extensible almost without bound, I implemented “user evaluators”. These allow any user to write his own custom inner loop for any kind of automaton he wishes and have it executed as the update rule by WebCA, retaining all of the facilities of the program including the lookup table. This facility is intended for experienced JavaScript programmers only, but the way in which it is integrated with WebCA allows new evaluators to be coded and run with WebCA. Thus WebCA can get smarter without the need to post updated versions.

We have used this facility already to implement several interesting new evaluators. One performs the optimal solution of Laplace's equation in the plane. A second implements a general-purpose von Neumann neighborhood where each cell can see 3 bits of state from each of its neighbors and four bits of local state. A third implements Langton's self-reproducing creature.

The rules for JavaScript user evaluators are detailed and highly rigid, but once you understand them the actual job of coding an evaluator is not all that difficult. First, let's examine it from a rule definition standpoint. Consider the following JavaScript rule definition:

/* 3 bit parity rule for von Neumann neighborhood implemented with the vonn3 user evaluator. */ rule.worldtype = 13; // 2D torus world rule.patreq = "square"; rule.ocodereq = "vonn3"; function vonpar(oldstate) { return (oldstate & 7) ^ ((oldstate >> 3) & 7) ^ ((oldstate >> 6) & 7) ^ ((oldstate >> 9) & 7); }

This is a parity rule that works on 3 bits of state in the von
Neumann neighborhood. Since this is a neighborhood option not
built into WebCA, the rule definition invokes an
user evaluator called “**vonn3**” which
implements that custom neighborhood. It sets rule.worldtype to 13 to select a toroidal
world (it would be 12 if open), and a generic look-up table in
which the meaning of the entries is totally up to the user
evaluator's implementation. The **vonn3** user evaluator,
implemented in the file **vonn3.js** is requested by setting
“rule.ocodereq” to its file
name (less the “.js”, which is
assumed). User evaluators defined with world types 12 and 13
work with rule definition functions called directly with the raw
lookup table index in oldstate; the rest
of the rule definition function arguments are undefined. The
meaning of the 16 bits of oldstate is
defined by the user evaluator itself. For **vonn3** the
assignments are as follows:

oldstate bits | Meaning |
---|---|

2 – 0 | South |

5 – 3 | East |

8 – 6 | West |

11 – 9 | North |

15 – 12 | Self |

Thus, as advertised, 3 bits from each neighbor and four local bits are visible (the local bits aren't used in this rule definition). Since only oldstate is passed, the vonpar function extracts the neighbors itself from oldstate. It calculates the new value and returns it in the conventional manner.

When this rule definition is loaded into WebCA, it searches for
the file **vonn3.js** and loads it as a user evaluator.

So what are these mysterious user evaluators, and how do I go about writing one? Listen up, sharpen your coding stick, and get ready to be initiated into the gory details of the innards of WebCA. First of all, a user evaluator is mechanically a JavaScript function which is called to update each cell in the map for every generation of the rule's execution. The evaluator is, in essence, the “inner loop” that updates the state of cells in the state map. There is no measurable speed penalty when using a custom evaluator rather than a built-in evaluator of the same complexity. Obviously, if you do lots of computation within the evaluator, WebCA will slow down accordingly.

Let's examine the definition for the **vonn3.js** user
evaluator.

/* User evaluator for von Neumann neighborhood with 3 bits of state visible from each neighbor and 4 bits of local state. Neighborhood is: N W C E S and index to the lookup table is: CCCCNNNW WWEEESSS */ function vonn3(cells, phyx, phyy, p, lut) { var self = cells[p]; var north = cells[p − phyx]; var south = cells[p + phyx]; var east = cells[p + 1]; var west = cells[p − 1]; return lut[((self & 0xF) << 12) | ((north & 7) << 9) | ((west & 7) << 6) | ((east & 7) << 3) | (south & 7)]; }

This code appears puzzling until we explain some things about the arguments with which the evaluator function is called and the handling of the state map.

The job of each call on the evaluator function is to update the cell whose index in the cells array (the old state map) whose index is given by p, returning the new state of the cell which will be stored into the new state map for the next generation. The cells array is a linear vector of cells, arranged as phyy lines of phyx rows. Neighbors of the cell being updated are accessed by arithmetic on the cell's index in the array as performed by the assignment statements at the top of the function. You don't have to worry about wrap-around or whether the rule.worldtype is open or closed; that is handled by duplicating cells around the edges of the map which are updated automatically before the user evaluator is called.

When p is pointing to a given cell, its neighbors may be found by the following expressions:

NW | N | NE |

W | C | E |

SW | S | SE |

Neighbor | Address expression |
---|---|

NW | p-(phyx+1) |

N | p-phyx |

NE | p-(phyx-1) |

W | p-1 |

C | p |

E | p+1 |

SW | p+(phyx-1) |

S | p+phyx |

SE | p+(phyx+1) |

While all of our standard patterns assume a 320×200 cell map, the simulator will actually work on a map of any size. You should always use the phyx and phyy dimension arguments so your evaluators will as well.

If you wish to supply modal information to the rule, you can encode 8 bits of information in the “rule.reqauxp” variable in the rule definition function. For user evaluator rules this cell does not cause any special treatment of plane 1, but instead is simply passed to the evaluator function in this variable. The interpretation of this value is totally up to the evaluator.

The built-in logic that calls your user evaluator takes care of
toroidal wrap around and supplying zero neighbors for open
worlds. As long as your evaluator addresses the neighbors with
the expressions given above, it doesn't have to worry about
wraparound or world type. When used with an evaluator, the
lookup table has no predefined meaning—it's simply 64K of
data to which the evaluator assigns its own interpretation.
Consequently, JavaScript or Java rule definitions which use user
evaluators must be coded with an understanding of what the
evaluator expects to find in the lookup table. (Note that if
you really want to go off the deep end, there isn't any reason
own code can't *change* the lookup table as it's
running.) Some evaluator functions don't even need the lookup
table at all.
For example, here's a definition of
**laplace.js** which solves the Laplace equation
in the plane using the formula:

*New* = ((*N* + *S* + *E* + *W*) × 4 +
(*NW* + *NE* + *SW* + *SE*)) / 20

/* User evaluator for the Laplace averaging. All computation is in the code: no lookup table is used. */ function laplace(cells, phyx, phyy, p, lut) { // Compute Laplace average of neighbors // LaplaceAverage = (4 × (N + E + S + W) + // (NW + NE + SE + SW)) / 20 var s = 0; s += cells[p − phyx]; // n s += cells[p − 1]; // w s += cells[p + 1]; // e s += cells[p + phyx]; // s s *= 4; s += cells[p − (phyx + 1)]; // nw s += cells[p − (phyx − 1)]; // ne s += cells[p + (phyx − 1)]; // sw s += cells[p + (phyx + 1)]; // se return Math.floor((s + 10) / 20); }

Since this code computes the new value arithmetically from the neighbor cells, it doesn't bother with the lookup table. A JavaScript or Java rule definition that called it would just always return zero from its rule definition function.

User evaluators should be short, sweet, and simple. Evaluators of the complexity shown here run at speeds comparable to the built in rule evaluators of WebCA. If you need to do lots of computation, try to find a way to reduce it to table lookup or else you're likely to be disappointed at how fast your rule executes.

For an example of what can be done with a user evaluator, please refer
to the definition of
Langton's self-reproducing machine. The
evaluator for this rule (essentially identical to the
**vonn3** example given above) is defined in
**evaluators/langton.js**.
The rule definition which generates the
complicated lookup table used by the evaluator is defined in the
JavaScript file **ruledefs/langton.js**.

If you have a lookup table that you'd like to run with several different evaluators, you can explicitly load an evaluator from the WebCA control panel. You can see a list of standard evaluators in the drop-down list on the Evaluator URL line.

As you come to master the craft of evaluator design, your horizons will suddenly broaden as you come to realize the extent that WebCA places you in control. Appropriate code, written with a thorough understanding of the internal environment seen by the evaluator, can implement such things as:

- Optimized evaluation, skipping inactive regions at high speed.
- Position-sensitive evaluation, for example preserving a constant frame on the screen.
- Non-state inputs (random numbers, etc.).
- Non-local neighbors.
- Temporal phase (for example, alternating block rules).
- Continuous-valued cells.

Your imagination and JavaScript coding skills are truly the only limits to what you can accomplish with user evaluators.

Sometimes an evaluator will need some storage, usually constants
but sometimes variables, which persists over multiple calls
on the evaluator. Initializing these variables on every call
to the evaluator would be costly in compute time and slow down
the simulator: for a standard map of 320×200 cells the
evaluator function is called 64,000 times for *each generation*
of the automaton. WebCA provides an object named
rule.evaluator where evaluators can
keep such information. Variables are initialized by code in the
prologue to the evaluator, before the declaration of the evaluator
function. This code is executed only once, when the evaluator is
initially loaded, and variables it creates can be accessed on
subsequent calls to the evaluator function.

For example, one of our evaluators simulates diffusion of a gas by randomly selecting a neighbor of a particle and swapping the particle with it. To do this efficiently, we need a table of the offsets of the neighbors from the current cell. Creating this array for every call on the evaluator would dramatically slow down the simulation, so we declare the array in the prologue as follows:

// Indices of neighbors for random propagation direction rule.evaluator.nindex = [ −(map[0].phyx + 1), −map[0].phyx, −(map[0].phyx − 1), −1, 1, (map[0].phyx − 1), map[0].phyx, (map[0].phyx + 1) ]; function gasflow(cells, phyx, phyy, p, lut) { ⋮

then, within the gasflow evaluator function, code can reference the rule.evaluator.nindex[] array, which will already have been initialized before the evaluator is called the first time. Storage in rule.evaluator is released when another evaluator is loaded. (Note that when the prologue is executed, the evaluator function arguments have not been set, so the assignment which creates the rule.evaluator.nindex array must obtain the physical width of the map directly using map[0].phyx + 1, etc.)

While most evaluators need do nothing more than update the current cell, some may need to special processing, for example at the start and/or end of each generation. While it is possible to test for this by examining the p argument to detect the first or last cell, making this test for every cell slows down the evaluator. WebCA allows an evaluator to register notification functions for such events by assigning functions to the following variables in rule.evaluator.

The function will be called for each generation, before the evaluator function is called to update the first cell. For example, to perform some processing before each generation, you'd add code like the following to the prologue of the evaluator.

rule.evaluator.generationStart = function () { // Perform processing before generation };

The function is called once each generation, after the last cell has been updated by evaluator function.

The function is called before the very first time the evaluator is called, before its generationStart function, if any. A variable named rule.evaluator.generationFirstDone is set true to indicate the generationFirst function has been called. If the evaluator sets it back to false, generationFirst will be called again on the next invocation of the evaluator.

The function will be called whenever a new rule or pattern is loaded, with a string argument of “rule” or “pattern” to indicate which has changed.

The following evaluators, defined as described above, are available on the WebCA server. You can load them from your rule definition programs, or explicitly from the drop-down list in the Evaluator section of the WebCA control panel by entering the name in the “Evaluator URL” box and pressing “Load”. If one of the standard evaluators does not meet your needs, you still may find one which is close enough to serve as a starting point which you can modify into one that does. Source code for all of the standard evaluators is included in the CelLab Development Kit in the evaluators directory.

In discussing the evaluators, we will use the following terminology to refer to a cell's neighbors. The cell the evaluator is updating, EveryCell, is denoted by C, and is surrounded by eight adjacent cells, named by the points of the compass.

NW | N | NE |

W | C | E |

SW | S | SE |

This is a two-dimensional computational fluid dynamics simulator which runs as an evaluator. Each cell's state is represented by twelve floating-point values which specify the density and velocity of the fluid within it and its neighbors. This evaluator is used by the Wind rule; see its documentation for details and attribution of the work upon which it is based. This evaluator is extremely computationally intense, and requires a high-performance machine and browser implementation of JavaScript to run at an acceptable speed. The evaluator does not use the lookup table, and examines the map only to determine the location of obstacles (indicated as cells with state 255) to fluid flow.

This is a special purpose evaluator built to support the Forest sample rule. It is unlikely to be useful for any other purpose.

This evaluator implements gas flow through randomness, and is used by the Gasflow sample rule. It is configured by variables in the prologue section. Cells which have the bit set in wall are impermeable walls; set to zero to disable walls. Every percent of generations (0–100), cells will be displaced in a random direction, swapping with their neighbors. The flow parameter (0–100) gives the percent bias a cell has not to flow in the directions specified in the nogo array (by default configured for left to right flow). The lookup table is not used. This rule conserves particle number.

This evaluator simulates gas diffusion
through randomness. It is configured by variables
in the prologue section. Cells which have the bit set in
wall are impermeable walls; set to
zero to disable walls. Every percent
of generations (0–100), cells will be displaced in a
random direction, swapping with their neighbors.The
lookup table is not used. This rule conserves particle
number. This evaluator is equivalent to **gaswall**
with flow set to zero, and is used
in the PerfumeR sample
rule.

This evaluator is used by the Langton self-reproducing sample rule, but can be used whenever you need to see three bits of state from the four neighbors N, E, S, W, plus four bits of your own state, C. The lookup table index is assembled with bits as follows.

C C C C N N N E E E S S S W W W

These evaluators compute the Laplace average of their eight surrounding neighbors with the formula:

*new* = ((*N* + *S* + *E* +
*W*) × 4 + (*NW* + *NE* +
*SW* + *SE*)) / 20

The **laplace** evaluator returns *new*, while **lapinc**
returns *new*+1. Neither uses the lookup table. The
RugLap sample rule uses **lapinc**.
You can use **laplace** when you need a more accurate
average than that provided by world type 10.

The Margolus neighborhood is discussed in the Lattice Gas section of the Theory chapter. It is possible to implement a lattice gas in the standard WebCA world type 0 or 1 by devoting bits in the cells' states to keep track of horizontal, vertical, and temporal phase, then writing out special cases in the rule program to handle all of the possibilities. Our PerfumeT and PerfumeX rules are examples of this technique.

While it is possible to do this, the complexity of keeping track of the phases and handling the special cases can dwarf that of the actual rule. The PerfumeX rule definition, for example, is 200 lines of JavaScript, most devoted to twiddling bits and enumerating cases, with only a few actually expressing the rule. Further, using bits in the cell state to keep track of phase makes them unavailable to the rule definition, which may wish to use them for other purposes.

The **margolus** evaluators eliminate this complexity by keeping
track of phase externally, in the evaluator, without bothering the
rule program with such details. Rewritten to use the **margolus**
evaluator, the PerfumeM rule (identical in results to PerfumeX)
is just 35 lines of code, of which 10 express the entire rule.

How does this work? Well, recall that in the Margolus neighborhood, neighbors are denoted by the relationship to the current cell, in its position in the block for the present generation, by their rotation from the cell: CW (clockwise), CCW (counterclockwise), or OPP (opposite).

The **margolus** evaluator computes a lookup table index in
which the lower eight bits are the state of the current cell
and the high eight bits are composed of the states of the
four relative Margolus neighbors and the vertical and horizontal
phases as follows:

CW1 CW0 CCW1 CCW0 OPP1 OPP0 V H

where the “1” and 0” denote bit planes of the neighbors (thus you get to see two bits of the state of the neighbors) and “V” and “H” the vertical and horizontal phases (which will be 1 for odd numbered rows and columns, respectively, and 0 for those with even numbers). Many rules won't need the “V” or “H” bits, but they're supplied just in case.

The index computed by **margolusp** is almost the same:

CW1 CW0 CCW1 CCW0 OPP1 OPP0 0 P

where “P” is the temporal phase: 0 for even-numbered generations and 1 for odd-numbered generations. Due to the limit of 16 bits on lookup table indices, it isn't possible to simultaneously supply vertical, horizontal, and temporal phase to a rule, but if it's needed, a housekeeping bit can be devoted to keeping track of the phase not supplied by the evaluator.

This evaluator causes the cells in a map to “melt down” into a histogram at the bottom, sorted by their states. You can run it with the null Owncode rule to create a column by column histogram of the results of running another rule. This evaluator is similar to the SAFE-PASS rule described in [Margolus&Toffoli87], p. 78. It uses neither the lookup table nor housekeeping bits in the cells.

Simulates random gas diffusion by swapping cells with randomly
chosen neighbors. The prologue variable percent
gives the probability (0–100) that a cell will be swapped
in a generation. It is identical to **gaswall** with
wall set to zero. No lookup table is used,
and the evaluator does not examine the states of cells. This
evaluator is used by the Earthgas
sample rule.

A cell from among the eight neighbors of a cell is chosen at
random, and its state and the state of the current cell are used
to form a 16 bit lookup table index with the neighbor's cell in
the top 8 bits and the cell's state in the bottom 8 bits. The
value at this index in the lookup table becomes the cell's new
state. The **randnabe** evaluator is used in the
Griff sample rule.

One of the cell's eight neighbors is chosen at random, and new values for the cell and its neighbor are taken from the lookup table at indices formed by the neighbor's state in the high byte and the cell's state in the low byte (for the cell) and with the order of the two bytes reversed (for the neighbor). Then the cell and the neighbor are physically interchanged in the map. This evaluator is used by the Wator sample rule.

Simulates runny paint by causing nonzero state cells to run down
the map through areas of zero cells until they all collect at the
bottom. Unlike **meltdown**, the cells at the bottom are not
sorted by their states, but remain in their original vertical
order. This is an example of an evaluator which updates the
entire map at once, rather than cell by cell.

Performs the recursive evolution of the sandpile model for the Sand rule. Each generation adds a grain of sand to the center of the map and then propagates any avalanches which result. No lookup table is used.

Computes the sum of the four neighbors of the cell (**semi4**)
or eight neighbors (**semi8**) and returns the value from
the lookup table with that index. The sample rule
Rug uses **semi8** and
RugF uses **semi4**.

This is a special purpose evaluator built to support the Turmite sample rule. It is unlikely to be useful for any other purpose.

Computes a lookup table index composed of three bits of state from the four neighbors and four bits of state from the cell, arranged as follows:

C C C C N N N W W W E E E S S S

Computes a lookup table index composed of four bits of state from each of the four neighbors and four bits of state from the cell, arranged as follows:

C C C C N N N N W W W W E E E E S S S S

If you've been reading carefully, you're probably exclaiming,
“*Wait a minute!* You told me lookup table indices
are sixteen bits, but here you have a twenty-bit index!”
Indeed…. The **vonn4** evaluator is an example of
an evaluator which uses an *auxiliary lookup table* which
can be larger than the standard 64K lookup table used by most
other evaluators. In this case the lookup table is one megabyte
in length, allowing it to be addressed with a 20 bit index. The
auxiliary lookup table is stored in the **rule.program.lutaux** array
and must be computed and stored there by the rule definition program
which uses the **vonn4** evaluator. To understand how to write
rules definitions and evaluators that use an auxiliary lookup table,
see the source code for **evaluators/vonn4.js** and
**ruledefs/vonpar4.js**, a four
bit per cell parity rule that uses **vonn4**, in the
Cellab Development Kit. The **vonn4** evaluator
is used by the Evoloops
standard rule. The **vonn4ab** evaluator is a modified
version of **vonn4** used by EvoloopsAB; it is unlikely to be
useful with any other rule.

The **water** evaluator is intended to demonstrate how far
off the deep end you can go with user evaluators.
Appropriately, it is intended to simulate fluid flow, although
more one with a high viscosity such as honey as opposed to water
(since the momementum of the fluid is not taken into account).
It is based upon a simulation originally written in Java by
Janis Elsts (W-Shadow) and
described on his Web log.

The evaluator is used in the
Glooper
sample rule which, unlike almost all of our other rules, is a
*continuous* rule. Cells, instead of having discrete
values between 0 and 255, take on values with more than six
significant digits of precision (IEEE single-precision floating
point), which represent the mass of fluid in each cell.
Compressibility, the force of gravity, the pressure of a column
of fluid, and lateral flow among cells with different pressures
are taken into account.

You can draw complex “water works” and watch the
fluid flow through them. If you're interested in implementing
ambitious projects such as computational fluid dynamics in
CelLab, **water** shows you how to go about
it, and **cfd** demonstrates what can be achieved.

Many evaluators work directly on the state map and do not require
a lookup table. For such rules, the only function served by the
rule definition program is to specify the evaluator, pattern,
palette, and rule modes. When you're developing and experimenting
with such evaluators, there's no need to write a rule definition
for each one. WebCA supplies a generic rule definition named
Owncode (available both as a compiled **.jc** file and a
JavaScript rule program) which sets the world type to 13 but does
nothing else. You can then manually load your evaluator, pattern,
palette (if desired) and set any rule modes you require with the
Rule Modes dialogue.