Cellular Automata Laboratory
|
|
Cellular Automata Laboratory |
|
To define a rule in Java, you write a rule function called jcrule 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 rulefunction is a method of a rule definition class derived from the parent class ruletable. An object of this class is created by a small main program, and a method invoked which creates a .jc rule definition file.
Recapitulating, use your text editor to write a program called mylife.java. Then save the file and compile mylife.java and run the resulting mylife.class file. When your "mylife" program runs, it creates a lookup table for mylife called mylife.jc. If you have an integrated Java development environment, you can enter, edit, compile, and run the program using its facilities.
And what is a .jc file good for? It is what WebCA uses in order to run cellular automata at a good rapid speed. The .jc file codes up the jcrule result for each of the 64K possible combinations of oldstate and EightNeighborhood that a cell might have. A .jc file will not, however, normally take up 64K bytes of storage because a compression technique is used.
To understand how to write a jcrule method, first we must consider the neighborhood of a cell, as seen by the function through its argument and the variables inherited from its parent class ruletable. The rule is defined in a class definition of the form:
class RuleName extends ruletable {
int jcrule(int oldstate) {
int NewSelf;
// Calculate value for NewSelf
return NewSelf;
}
}
The jcrule method sees the neighborhood through the following variables in the parent class:
| 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.
class Life extends ruletable {
int jcrule(int oldstate) {
int 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;
if (EightSum == 2) {
NewSelf = self;
} else if (EightSum == 3) {
NewSelf = 1;
}
return NewSelf;
}
}
public class mylife {
public static void main(String args[]) {
(new Life()).generateRuleFile("mylife");
}
}
The main program at the bottom of the file simply creates an instance of the class Life and invokes its generateRuleFile method (implemented in the parent class ruletable), which creates a rule definition file with the name given by the string argument with ".jc" appended, in this case mylife.jc.
If you have a Java compiler handy, you should try creating and running the mylife.java rule right now. Where do you get a file to start work on? One way is simply to type in the text of mylife.java. An easier way is to copy one of our .java ruleprograms to a file called mylife.java and then make a few changes to “mylife.java” until it looks like the program above.
As it turns out, the life.java 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.java is quite similar to what you want for mylife.java, so you should copy life.java onto mylife.java and use that as the starting point for your program.
So the steps for running mylife are as follows: copy the existing life.java file to a new mylife.java file. Then use your text editor to work on mylife.java. Once you have mylife.java in shape, compile and run it, either within a Java development environment or from the command line with:
javac mylife.java
java mylife
If all goes well, you'll create mylife.jc, which you can load into WebCA and run. All Java rule programs define rule classes which extend the class ruletable which is defined in the file ruletable.java. If you are using a version of Java which is not compatible with the compiled version of this file included with CelLab, you may need to manually recompile ruletable.java with the command:
javac ruletable.java
before you compile your rule program. If you are using an integrated Java development environment, consult its documentation on how to include either ruletable.java or the compiled ruletable.class in your rule program project.
Since the rule for the game of Life doesn't use bit-planes #1 through #7 at all, the mylife.java rule program contains no reference to oldstate. Rules which use the higher bit-planes may also be specified straightforwardly by Java 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 Java 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
*/
class Brain extends ruletable {
int jcrule(int oldstate) {
int 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. */
}
}
public class brain {
public static void main(String args[]) {
(new Brain()).generateRuleFile("brain");
}
}
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 noise generator
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
*/
class Sublime extends ruletable {
static final int HPPlane = 4, // Horizontal phase plane
HPNbits = 1, // Horizontal phase plane count
VPPlane = 5, // Vertical phase plane
VPNbits = 1, // Vertical phase plane count
RIPlane = 2, // Random input plane
RINbits = 1, // Random input bit count
RSPlane = 0, // Random seed plane
RSNbits = 1, // Random seed bit count
TPPlane = 6, // Temporal phase plane
TPNbits = 2; // Temporal phase plane count
void jcruleModes() {
setPatternRequest("sublime");
setPaletteRequest("sublime");
/* 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 ..
: : : : */
setTextureHorizontal(HPPlane, HPNbits);
setTextureVertical(VPPlane, VPNbits);
setInitialRandomSeed(RSPlane, RSNbits);
setRandomInput(RIPlane, RINbits);
setTemporalPhase(TPPlane, TPNbits);
setWorld(1);
}
int jcrule(int oldstate) {
int 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;
}
}
public class sublime {
public static void main(String args[]) {
(new Sublime()).generateRuleFile("sublime");
}
}
For now don't worry about the intricacy of Sublime's definition of the jcrule method. Instead, let's focus on the jcruleModes method, which we haven't encountered before. This method is called before your jcrule method is called for the first time, and can set up various modes which affect how the rule is generated and/or perform any initialization needed by the jcrule method. mylife and brain didn't need to change any of the modes from the defaults, so their definitions didn't include a jcruleModes method.
A variety of methods in the parent ruletable class can be called from jcruleModes to specify rule generation modes or options for the simulator. These fall into the following categories.
setPaletteRequest and setPatternRequest are particularly useful for creating rules to be shown by self-running demos. If setPaletteRequest and setPatternRequest are not called in your jcruleModes method, 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 file which is not available on the WebCA 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 setRandomInput, we can have random bits fed into any span of bits that we like. Calling setRandomInput(startBit, bitCount) causes WebCA to randomize the contents of bitCount planes, starting with plane startBit. New random data are stored into the requested planes on each generation. For example, if you invoke setRandomInput(2, 3); in your jcruleModes method, WebCA 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 setTextureHorizontal and setTextureVertical methods feed in horizontal or vertical texture. setTextureHorizontal(startBit, bitCount) puts in bitCount planes of horizontal texture starting at plane startBit. setTextureVertical(startBit, bitCount) does the same, but in the vertical direction. If I have one bit of texture, that means that the texture bit will cycle between 0 and 1. If I were to use setTextureHorizontal(5, 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 setInitialRandomSeed(startBit, bitCount, density) method 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 setInitialRandomSeed instead of setRandomInput. startBit specifies what plane to begin random seeding at, and bitCount tells it how many planes to seed. In addition, density allows you to specify the percentage of ones you want. (This is not possible for setRandomInput, which always seeds at 50%.) density 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 density is omitted from the call on setInitialRandomSeed, 255 is used, generating a seed with 50% ones and 50% zeroes.
Thus if I call setInitialRandomSeed(2, 1, 128) in my jcruleModes method, 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 setInitialRandomSeed 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 setInitialRandomSeed, 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 the setTextureHorizontal and setTextureVertical 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 Bit Plane Editor or load a new pattern. The setInitialRandomSeed planes are re-randomized whenever you load a new pattern, but not when you leave the Bit Plane Editor.
setWorld(worldType) 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 setWorld is 1, which means a two dimensional world with wrap turned on. It was actually unnecessary to call setWorld with 1 in the Sublime rule, because setWorld always defaults to 1. To get a two dimensional world with the wrap turned off, call setWorld(0).
If you call setWorld with 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 jcrule. 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 setWorld arguments as listed below:
| setWorld | 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:
| setWorld 2, 3: Eight Neighbors, 1 bit each | ||||||||
|---|---|---|---|---|---|---|---|---|
| N8L4 | N8L3 | N8L2 | N8L1 | oldstate | N8R1 | N8R2 | N8R3 | N8R4 |
| setWorld 4, 5: Four Neighbors, 2 bits each | ||||
|---|---|---|---|---|
| N4L2 | N4L1 | oldstate | N4R1 | N4R2 |
| setWorld 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.java below. Aurora uses two four-bit neighbors, so we use variables N2L1 and N2R1 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.
*/
class Aurora extends ruletable {
void jcruleModes() {
setWorld(9);
setPaletteRequest("aurora");
setInitialRandomSeed(0, 4);
}
int jcrule(int oldstate) {
return ((N2L1 + (oldstate & 15) + N2R1) / 3) + 1;
}
}
public class aurora {
public static void main(String args[]) {
(new Aurora()).generateRuleFile("aurora");
}
}
In the rule descriptions later in this document I give an example of a setWorld 5 rule (ShortPi) and an example of a setWorld 2 rule (Axons).
Choosing setWorld 10 or 11 causes WebCA to evaluate averaging rules. These rules were devised to allow generalizations of the Rug rule. In both of these modes the screen is wrapped. setWorld(10) computes the sum of EveryCell's eight nearest neighbors, and setWorld(11) gets the sum of EveryCell's four nearest neighbors.
In the averaging rules, the oldstate argument passed to jcrule holds the low five bits of the EveryCell's old eightbit state, the sum of EveryCell's neighbors is in the variable SUM_8 (for setWorld(10)) or SUM_4 (for setWorld(11)). (Eight neighbors in setWorld(10), and 4 neighbors in setWorld(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 setWorld(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 eightcell 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.
*/
class Heat extends ruletable {
void jcruleModes() {
setWorld(10);
}
int jcrule(int oldstate) {
int r = 0;
if ((oldstate & 1) > 0) {
if (oldstate < 16) {
r = oldstate;
} else {
r = oldstate + 128;
}
} else {
r = (SUM_8 >> 3) & 0xFE;
}
return r;
}
}
public class heat {
public static void main(String args[]) {
(new Heat()).generateRuleFile("heat");
}
}
setWorld(12) and setWorld(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 setWorld 12 or 13, one must have a predefined evaluator function. These inner loop functions are written in JavaScript, have extension .js, and are discussed more fully in the previous section.
The Rug rule below is an example of a rule of this type. I could have written a similar Rug rule using setWorld(10), but I wanted to have the wrap off. The WebCA Rug rule calls a 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 eightcell averaging rule of eight bits per
cell. We program it as a nowrap owncode WorldType 12 calling
semi8.jco.
*/
class Rug extends ruletable {
void jcruleModes() {
setWorld(12);
setOwnCodeRequest("semi8");
}
int jcrule(int oldstate) {
return ((oldstate >> 3) + 1) & 0xFF;
}
}
public class rug {
public static void main(String args[]) {
(new Rug()).generateRuleFile("rug");
}
}
The speed at which the simulator runs depends only on the setWorld you have chosen. It does not depend at all on the complexity of the Java 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.
.java 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.java. Then you can edit first.java to your own purposes and to run it and generate your first.jc file. If your rule happens to return a value for jcrule outside the range 0–255, or supplies invalid arguments to one of the setup functions in its jcruleModes method, you will get an error message when the program tries to generate first.jc. If this happens, fix your program and try again.
After you've written a number of rule definition programs, you'll find yourself using common sequences of code in program after program for operations such as counting the number of firing cells in a neighborhood, checking position of cells within blocks defined by a texture, keeping a cycle count for multi-phase rules, and extracting bit fields from a cell. The ruletable parent class provides ready-to-use shorthand variables and methods for performing these calculations. You don't have to use the shorthand, but if you're writing a large number of rule programs, you may find they're less work to write and easier to understand when you refer back to your rule programs later on.
Many two-dimensional, one bit rules depend, in part, on the number of neighboring cells which are nonzero. You can calculate these sums by adding the neighbor state in the variables nw, n, ne, etc., but as a convenience, before calling the jcrule method when setWorld is 0 or 1, the following sums are precomputed:
SUM_4 = n + w + e + s;
SUM_5 = n + w + self + e + s;
SUM_8 = nw + n + ne + w + e + sw + s + se;
SUM_9 = nw + n + ne + w + self + e + sw + s + se;
so a rule program can simply reference these commonly used sums of neighbors instead of adding them up itself.
When using the margolus or margolusp evaluators, two bits of state of each of the four cells in the relative positions of the Margolus neighborhood are packed into the upper six bits of the high byte of the lookup table index. When using a world type of 12 or 13, the following preset variables may be used to reference these cells.
CENTER Current cell, plane 0
CW Clockwise cell, plane 0
CCW Counterclockwise cell, plane 0
OPP Opposite cell, plane 0
CENTERp Current cell, plane 1
CWp Clockwise cell, plane 1
CCWp Counterclockwise cell, plane 1
OPPp Opposite cell, plane 1
Rule programs are forever interrogating information in various planes or collections of planes encoded as bits in the state of a cell. A collection of methods lets you directly access planes by number.
Many rules use a “texture” stored in one or more bit planes to allow the rule program to locate a cell within a block of a given size. The setTextureHorizontal and setTextureVertical methods allow a rule to request a texture pattern to be preloaded into specified planes. If these functions have been called in jcruleModes to request texture, the jcrule method may obtain the value of the texture with the following method calls.
Many rules dedicate one or more bits in each cell to maintain a cycle counter that increments, in each generation, modulo the length of the bit field. This allows multi-phase rules to perform different calculations in successive steps and/or access alternate neighborhood regions as in the gas rules. A “temporal phase” mechanism is provided in ruletable to automate the bookkeeping associated with this. A rule program declares which bit planes are to be used for a cycle counter by calling setTemporalPhase(startBit, bitCount) in its jcruleModes method. Unlike setTextureHorizontal and the other texture requests, this call does not affect the simulator nor the contents of the cell map—it merely declares which planes the rule is using for its cycle counter. Within the jcrule method, the cycle counter for this generation is obtained by calling TPHASE(). When the new value for the cell is returned by jcrule the cycle counter can be automatically incremented and placed in the selected planes by returning TPUPD(newValue), where newValue is the new value for the cell, leaving TPUPD to fill in the cycle counter.
Certain categories of rules can be defined in a very compact form by a few numeric parameters. The following generators are provided by ruletable which allow one-line jcrule functions which simply invoke them with the parameters for the rule desired.
int jcrule(int oldstate) {
return NLUKY(1, 2, 2, 9, 9); // Brain
}
int jcrule(int oldstate) {
return TOTALISTIC(976, true); // Vote rule with history
}
