Cellular Automata Laboratory
|
|
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:
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.
