Cellular Automata Laboratory
|
|
Cellular Automata Laboratory |
|
To define a rule in JavaScript, you write a rule function which, when called with an argument containing the state of a cell and the state of its neighbors in variables, returns the new state for the cell as an integer from 0 to 255 (the low bit #0 is the state of Plane 0, bit #1 is the state of Plane 1 and so on). The rule function program is loaded into a text box in the WebCA page, and run to generate the lookup table for the rule.
Recapitulating, use your text editor to write a program called mylife.js. Then paste the program into the Rule Program box in WebCA, press “Generate” to run it and generate the rule table, and now you're ready to run the rule by pressing the “Start” button below the map display.
To understand how to write a rule program, first we must consider the neighborhood of a cell, as seen by the function through its arguments. The rule is defined as a function of the form:
function ruleName(oldstate,
nw, n , ne,
w, self, e,
sw, s , se
) {
var newSelf;
// Calculate value for newSelf
return newSelf;
}
The rule function sees the neighborhood through the following arguments:
| nw | n | ne |
| w | self | e |
| sw | s | se |
Each of these variables will be 1 if the low-order bit of the corresponding cell in the neighborhood is on, and 0 if it is off. In addition, the rule function may examine the argument oldstate, which contains the full state of the center cell (eight bit planes). Thus, oldstate ranges from 0 to 255, with the presence of low bit (also supplied in variable self) signifying the state of Plane 0. The function defining the rule must examine these input variables, calculate the resulting state for the cell (from 0 to 255), and return that value. The following sample code, including the required declarations and main program, defines the game of Life, proceeding directly from Poundstone's description.
function mylife(oldstate,
nw, n , ne,
w, self, e,
sw, s , se
) {
var eightSum, newSelf = 0;
/* We sum up the number of firing neighbor cells. If this
eightSum is anything other than 2 or 3, the cell gets
turned off. If the eightSum is 2, the cell stays in its
present state. If the eightSum is 3, the cell gets turned
on. */
eightSum = nw + n + ne + e + se + s + sw + w;
switch (self) {
case 0:
if (eightSum == 3) {
newSelf = 1;
} else {
newSelf = 0;
}
break;
case 1:
if (eightSum == 2 || eightSum == 3) {
newSelf = 1;
} else {
newSelf = 0;
}
break;
}
return newSelf;
}
You can try pasting the program above into the Rule Program box of WebCA, press “Generate”, and then press “Start” to watch the mylife rule run.
As it turns out, the life.js rule program provided with CelLab is similar but not quite the same as mylife. Our Life is actually the rule “LifeMem,” which colors the cells differentially depending on their state in the last generation. But our life.js is quite similar to what you want for mylife.js, so you should copy life.js onto mylife.js and use that as the starting point for your program.
So the steps for running mylife are as follows: copy the existing life.js file to a new mylife.js file. Then use your text editor to work on mylife.js. Once you have mylife.js in shape, paste it into the Rule Program box of WebCA, press Generate, then press Start.
Since the rule for the game of Life doesn't use bit-planes #1 through #7 at all, the mylife.js rule program contains no reference to oldstate. Rules which use the higher bit-planes may also be specified straightforwardly by JavaScript rule definition functions. For example, here is the definition of Brian's Brain, a rule developed by Brian Silverman and described in [Margolus&Toffoli87], p. 47, as:
The rule involves cells having three states, 0 (“ready”), 1 (“firing”). and 2 (“refractory”). A ready cell will fire when exactly two of its eight neighbors are firing; after firing it will go into a refractory state, where it is insensitive to stimuli, and finally it will go back to the ready state.
This translates directly into a JavaScript program as follows:
/*
Each cell has three states, though only one bit of the state
is used to determing whether neighbors are on or off. The
rule is as follows:
Old cell state New state
0 (Ready) 1 if exactly 2 neighbors in state 1,
0 otherwise.
1 (Firing) 2
2 (Refractory) 0
*/
function brain(oldstate, nw, n , ne,
w, self, e,
sw, s , se) {
var count = nw + n + ne + w + self + e + sw + s + se;
if (oldstate == 2) { // If in refractory state...
return 0; // ...become ready.
}
if (oldstate == 1) { // If firing...
return 2; // ...go to refractory state.
}
return (count == 2) ? 1 : 0; /* If ready, fire if precisely
two neighbors are firing. */
}
It is possible to define much more complicated rules by using the high bits for various bookkeeping purposes. Here is an example of a rule that simulates thermally driven random diffusion. The theory of why the program works is explained in the Theory chapter.
/*
This rule implements the Margolus rule for simulating a gas of
cells diffusing. Particle number is conserved. We set up a
lattice of position values that looks like this:
0 1 0 1 ..
2 3 2 3 ..
0 1 0 1 ..
2 3 2 3 ..
: : : :
This lattice is alternately chunked into
A blocks 0 1 and B blocks 3 2
2 3 1 0
and the blocks are randomly rotated one notch CW or one notch CCW.
We use the eight bits of state as follows:
Bit #0 is used to show info to neighbors
Bit #1 is the gas bit
Bit #2 is fed by the system Noiseizer
Bit #3 stores the 4-cell consensus on direction 0 is CCW, 1 is CW
Bits #4 & #5 hold a position numbers between 0 and 3
Bits #6 & #7 control the cycle
*/
rule.worldtype = 1; // 2D torus world
rule.patreq = "sublime";
rule.palreq = "sublime";
rule.randb = 2; // Random input
rule.randn = 1;
rule.rseedb = 0; // Initial random seed
rule.rseedn = 1;
/* We set a horizontal pattern of alternate 0s and 1s in bit 4
and a vertical pattern of alternate 0s and 1s in bit 5.
This produces a pattern that goes 0 1 0 1 ..
2 3 2 3 ..
0 1 0 1 ..
2 3 2 3 ..
: : : : */
rule.texthb = 4; // Horizontal texture
rule.texthn = 1;
rule.textvb = 5; // Vertical texture
rule.textvn = 1;
rule.tempb = 6; // Temporal phase
rule.tempn = 2;
function sublime(oldstate, nw, n , ne,
w, self, e,
sw, s , se) {
var Cycle, Position, Direction, NewDirection = 0,
Noise, Gas, NewGas = 0, r = 0;
Cycle = TPHASE();
Position = HVPHASE();
Direction = BITFIELD(3);
Noise = BITFIELD(2);
Gas = BITFIELD(1);
switch (Cycle) {
case 0: // In A block mode set direction to NW's
switch (Position) {
case 0:
NewDirection = self;
break;
case 1:
NewDirection = w;
break;
case 2:
NewDirection = n;
break;
case 3:
NewDirection = nw;
break;
}
r = TPUPD(BF(Position, 4) | BF(NewDirection, 3) |
BF(Gas, 1) | Gas);
break;
case 2: // In B block mode set direction to NW's
switch (Position) {
case 0:
NewDirection = nw;
break;
case 1:
NewDirection = n;
break;
case 2:
NewDirection = w;
break;
case 3:
NewDirection = self;
break;
}
r = TPUPD(BF(Position, 4) | BF(NewDirection, 3) |
BF(Gas, 1) | Gas);
break;
case 1:
switch (Direction) {
case 0: // CCW rotation of an A block
switch (Position) {
case 0:
NewGas = e;
break;
case 1:
NewGas = s;
break;
case 2:
NewGas = n;
break;
case 3:
NewGas = w;
break;
}
break;
case 1: // CW rotation of an A block
switch (Position) {
case 0:
NewGas = s;
break;
case 1:
NewGas = w;
break;
case 2:
NewGas = e;
break;
case 3:
NewGas = n;
break;
}
break;
}
r = TPUPD(BF(Position, 4) | BF(Direction, 3) |
BF(NewGas, 1) | Noise);
break;
case 3:
switch (Direction) {
case 0: // CCW rotation of a B block
switch (Position) {
case 0:
NewGas = w;
break;
case 1:
NewGas = n;
break;
case 2:
NewGas = s;
break;
case 3:
NewGas = e;
break;
}
break;
case 1: // CW rotation of a B block
switch (Position) {
case 0:
NewGas = n;
break;
case 1:
NewGas = e;
break;
case 2:
NewGas = w;
break;
case 3:
NewGas = s;
break;
}
break;
}
r = TPUPD(BF(Position, 4) | BF(Direction, 3) |
BF(NewGas, 1) | Noise);
break;
}
return r;
// Return bit set for plane
function BIT(p) {
return 1 << p;
}
// Test if bit p is set in oldstate
function BITSET(p) {
return (oldstate & BIT(p)) != 0;
}
// Extract bit from oldstate
function BITFIELD(p) {
return B(BITSET(p));
}
/* Mask for N contiguous bits with low order bit in plane P. Note
how this definition craftily generates masks of zero when a
zero bit field is specified. */
function BITMASK(p, n) {
return BIT(p + n) - BIT(p);
}
// Test value nonzero
function B(i) {
return i ? 1 : 0;
}
// Place a value in a specified bit field
function BF(v, p) {
return v << p;
}
// Return horizontal phase of oldstate
function HPHASE() {
return (oldstate >> rule.texthb) & BITMASK(0, rule.texthn);
}
// Return vertical phase of oldstate
function VPHASE() {
return (oldstate >> rule.textvb) & BITMASK(0, rule.textvn);
}
// Return horizontal and vertical phase together, vertical most sig.
function HVPHASE() {
return (VPHASE() << rule.texthn) | HPHASE();
}
// Return temporal phase of oldstate
function TPHASE() {
return (oldstate >> rule.tempb) & BITMASK(0, rule.tempn);
}
// Update temporal phase in state x
function TPUPD(x) {
return (x & (~(BITMASK(rule.tempb, rule.tempn)))) |
(((TPHASE() + 1) & BITMASK(0, rule.tempn)) << rule.tempb);
}
}
For now don't worry about the intricacy of the definition of the sublime function. Instead, let's focus on the assignment statements before the function declaration, which we haven't encountered before. These statements make up what we call the “prologue” of the rule program, and are executed before the rule is generated. They can set up various modes which affect how the rule is generated and/or perform any initialization needed by the rule function. mylife and brain didn't need to change any of the modes from the defaults, so their definitions didn't include a prologue.
A variety of variables in the rule object can be set from in the prologue to specify rule generation modes or options for the simulator. These fall into the following categories.
rule.palreq and rule.patreq are particularly useful for creating rules to be shown by self-running demos. If rule.palreq and rule.patreq are not called in your rule prologue, the pattern and the color palette left over from the last rule are used. If you have just loaded the simulator, the default.jcc color palette is loaded and the starting pattern will consist of all zeroes in planes #1 through #7, with random bits of plane #0 turned on. This start will be modified by the rule's texture settings, if any.
If a rule requests a .jcc, .jcp, or .js evaluator file which is not in available on the server, a warning message appears to let you know the file requested by the rule could not be found, leaving the previous color palette, pattern, or no user evaluator in effect.
With rule.randb, and rule.randn we can have random bits fed into any span of bits that we like. Setting rule.randn causes the simulator to randomize the contents of rule.randn planes, starting with plane rule.randb. New random data are stored into the requested planes on each generation. For example, if you specify rule.randb=2; rule.randn=3;, the simulator will put random bits in planes #2, #3, and #4. The density of these random bits will always be 50%, meaning that approximately half of each randomized plane's cells will be set to 0 and half to 1. If you require a randomness of, say, 25% ones, you can simulate it by filling two planes with random bits and looking for the cells that have both bits set to 1. The rule.texthb, rule.texthn, rule.textvb, and rule.textvn, variables feed in horizontal and/or vertical texture. rule.texthb specifies the starting plane of the horizontal texture and rule.texthn the number of bits of horizontal texture (0 for none). Similarly, rule.textvb specifies the starting plane of the vertical texture and rule.textvn the number of bits of vertical texture (0 for none). If I have one bit of texture, that means that the texture bit will cycle between 0 and 1. If I were to use rule.texthb=5; and rule.texthn=2; however, I would get two bits of texture, meaning that the fifth and six bits would cycle through 00, 01, 10, 11, 00, 01, 10, 11, and so on across the screen. Vertical texture works the same way, and the combination of horizontal and vertical can produce a more complicated pattern as in Sublime.
The rule.rseedb, rule.rseedn, and rule.rseedp variables allow you to start up a rule with random seed bits in some planes. If you only want some random bits for the startup, but don't want them to keep coming in later, use these variables instead of rule.randb and rule.randn. rule.rseedb specifies what plane to begin random seeding at, and rule.rseedn tells it how many planes to seed (0 for none). In addition, rule.rseedp allows you to specify the percentage of ones you want. (This is not possible for random input set by rule.randb and rule.randn, which always seeds at 50%.) rule.rseedp can be set to any value between 0 and 255. These settings correspond to a percentage of ones which goes from 0% to 50%. Thus a setting of 255 means 50% ones and 50% zeroes, while a setting of 128 means 25% ones and 75% zeroes. If rule.rseedp is not set, 255 is used, generating a seed with 50% ones and 50% zeroes.
Thus if I set rule.rseedb=2, rule.rseedn=1, and rule.rseedp=128 in my prologue, then plane #2 will be randomized at the start of execution of the rule by a pattern that is 25% ones, but it will not be randomized again.
The primary purpose of rule.rseedb, rule.rseedn, and rule.rseedp is to make it possible to request a start pattern with randomness in some special planes without having to store the random information as part of the start pattern. Look at Soot or Dendrite for examples of this. The reason you don't want to have to store a .jcp file which has random bits in one of its planes is that then the file will be about 64K bytes in size, and will take up more space and download time than you really want to give it. Because the Soot pattern gets its “random gas” from rule.rseedx, its .jcp file is only some 2K bytes instead of 64K.
When a rule is running, you can see what kinds of texture the rule requested by looking at the WebCA Rule Modes dialogue.
A special feature of horizontal and vertical textures is that you can't get rid of them through editing or changing patterns. The idea is that if your rule calls for these textures, then it needs them, so they are put back in every time you leave the map editor or load a new pattern. The initial random seed planes are re-randomized whenever you load a new pattern, but not when you leave the map editor.
rule.worldtype variable specifies three things: a) Whether your screens wrap around the edges, b) Whether a rule is two-dimensional or one-dimensional, and c) How big a neighborhood you want to look at, and how many bits of each neighbor you want to see.
The most commonly used rule.worldtype is 1, which means a two dimensional world with wrap turned on. It was actually unnecessary to set rule.worldtype to 1 in the Sublime rule, because rule.worldtype always defaults to 1. To get a two dimensional world with the wrap turned off, use rule.worldtype=0;.
If you set rule.worldtype to one of the values 3, 4, 5, 6, 8, or 9, your rule will act on a one-dimensional (1D) world.
The 1D rules work by first copying each line of the screen onto the line below it, and by then filling in the top line with a new line calculated according to the rule function. This produces a spacetime trail of the 1D rule, with earlier times appearing lower on the screen like geological strata.
Our simulator is built to suck in eight bits of neighborhood information. We allow it to get neighborhood information in several different ways. These ways correspond to rule.worldtype setting as listed below:
| worldtype | Dimensionality | Wrap? | Neighbors | Bits |
|---|---|---|---|---|
| 0 | 2D | NoWrap | 8 | 1 |
| 1 | 2D | Wrap | 8 | 1 |
| 2 | 1D | NoWrap | 8 | 1 |
| 3 | 1D | Wrap | 8 | 1 |
| 4 | 1D | NoWrap | 4 | 2 |
| 5 | 1D | Wrap | 4 | 2 |
| 8 | 1D | NoWrap | 2 | 4 |
| 9 | 1D | Wrap | 2 | 4 |
| 10 | 2D | Wrap | 8 | Sum of 8 |
| 11 | 2D | Wrap | 4 | Sum of 4 |
| 12 | User | NoWrap | User | User |
| 13 | User | Wrap | User | User |
When we are in one of the three 1D modes the values of the neighboring cells are passed in variables as follows:
| worldtype 2, 3: Eight Neighbors, 1 bit each | ||||||||
|---|---|---|---|---|---|---|---|---|
| N8L4 | N8L3 | N8L2 | N8L1 | oldstate | N8R1 | N8R2 | N8R3 | N8R4 |
| worldtype 4, 5: Four Neighbors, 2 bits each | ||||
|---|---|---|---|---|
| N4L2 | N4L1 | oldstate | N4R1 | N4R2 |
| worldtype 8, 9: Two Neighbors, 4 bits each | ||
|---|---|---|
| N2L1 | oldstate | N2R1 |
To give an example of a one-dimensional rule, I give the code for the rule aurora.js below. Aurora uses two four-bit neighbors, so we use arguments l and r to reference their four-bit values. We extract the four-bit value of the cell's own state by ANDing oldstate with 15. This gets the low four bits out of oldstate because 15 in binary is 00001111, and ANDing any of the eight bits B in oldstate with a 0 produces 0, while ANDing a bit B with a 1 produces B.
/*
A one dimensional rule with two neighbors, and 4 bits of each
neighbor visible. This is run as a sixteen state rule, where
NewC = (L + OldC + R ) / 3 + 1.
*/
rule.worldtype = 9; // 1D ring world, 2 neighbors
rule.palreq = "aurora";
rule.rseedb = 0; // Initial random seed, planes 0-3
rule.rseedn = 4;
function aurora(oldstate, l, self, r) {
return ((l + (oldstate & 15) + r) / 3) + 1;
}
In the rule descriptions later in this document I give an example of a worldtype 5 rule (ShortPi) and an example of a worldtype 2 rule (Axons).
Setting rule.worldtype 10 or 11 causes the simulator to evaluate averaging rules. These rules were devised to allow generalizations of the Rug rule. In both of these modes the screen is wrapped. rule.worldtype=10; computes the sum of EveryCell's eight nearest neighbors, and rule.worldtype=11; gets the sum of EveryCell's four nearest neighbors.
In the averaging rules, the oldstate argument passed to the rule function holds the low five bits of the EveryCell's old eightbit state, the sum of EveryCell's neighbors is in the argument SUM_8 (for rule.worldtype=10;) or SUM_4 (for rule.worldtype=11;). (Eight neighbors in rule.worldtype=10;, and 4 neighbors in rule.worldtype=11;.) This sum can take as many as eleven bits to write out, which is why we are only allowed to see five bits of EveryCell's old state. The limitation is that our rules use lookup tables whose entries are indexed by sixteen bit “situation” codes.
As an example of rule.worldtype=10;, here is a program called Heat. A Heat cell takes a straight average of its neighbor cells, except that if a cell has its low bit on, the cell's value is kept fixed. The idea is that this rule is to simulate the heat flow in a metal plate certain of whose locations are kept fixed at certain temperature values.
/*
This is an eight cell averaging rule with zero increment.
Odd states are frozen states and even states generate
even states. One can reanimate the vacuum by
re-randomizing bitplanes 5 or 6.
*/
rule.worldtype = 10; // 2D open semitotalistic rule
function heat(oldstate, SUM_8) {
var r = 0;
if ((oldstate & 1) > 0) {
if (oldstate < 16) {
r = oldstate;
} else {
r = oldstate + 128;
}
} else {
r = (SUM_8 >> 3) & 0xFE;
}
return r;
}
rule.worldtype=12; and rule.worldtype=13; are for “user evaluator rules.” Type 12 has wrap turned off, with zero on the boundary; and Type 13 is the torus wrap mode. To run a rule of rule.worldtype 12 or 13, one must have a predefined user evaluator function. These functions are written in JavaScript and have extension .js. They are discussed more fully later in this manual.
The Rug rule below is an example of a rule of this type. I could have written a similar Rug rule using rule.worldtype=10;, but I wanted to have the wrap off. The WebCA Rug rule calls an evaluator function called semi8 which returns the eleven bit sum of the eight nearest neighbors, so we can use this function to define a rug rule.
/*
This program runs an eight cell averaging rule of eight bits
per cell. We program it as a nowrap worldtype 12 calling
the semi8 evaluator.
*/
rule.worldtype = 12; // User evaluator, 2D open world
rule.ocodereq = "semi8";
function rug(lutindex) {
return ((lutindex >> 3) + 1) & 0xFF;
}
The speed at which the simulator runs depends only on the rule.worldtype you have set. It does not depend at all on the complexity of the JavaScript rule you write or on the start pattern you select; it is completely constant. Thus, there is no need to make the function that defines the rule efficient—it is executed only to create the rule definition file, then never used again. The paramount consideration in writing a rule program is that it be clearly expressed so that you can come back to it later and still be able to tell what you were trying to do.
.js rule programs are provided for all the WebCA demos. A good way to start writing rules of your own is to copy one of our rules onto your own file first.js. Then you can edit first.js to your own purposes, paste it into the rule program box, and Generate and run it. If your rule happens to return a value for outside the range 0–255, or supplies invalid arguments to one of the prologue variables, you will get an alert when the attempt to generate the rule. If this happens, fix your program and try again.
