Cellular Automata Laboratory

Defining Rules in Java

Recapitulating, use your text editor to write a program called mylife.java. Then leave the editor 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. If you don't have a Java compiler, you can use our Java Rule Compilation Server, described later in this chapter, to generate the .jc file for you.

And what is a .jc file good for? It is what our simulator 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 memory 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:

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 the simulator 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 ruleprogram 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.

i)

StartUp: setPaletteRequest, setPatternRequest, and setOwnCodeRequest allow you to have your rule start by loading a .jcc colorpalette, a .jcp start pattern, and/or a .jco own code evaluator.

ii)

Background. The setRandomInput, setTextureHorizontal, setTextureVertical, and setInitialRandomSeed methods control what we call textures of bits that your rule can automatically load into selected planes. These texture bits are often left invisible.

iii)

Topology: The setWorld method specifies whether the screenwrap is to be on, whether you want to consider your rule to be two-dimensional or one-dimensional, and how many bits of how many neighbors are visible to the rule program.

StartUp

If a rule requests a .jcc, .jcp, or .jco file which is not in the current directory, a warning message appears to let you know the file requested by the rule could not be found, leaving the previous colorpalette, pattern, or no own code evaluator in effect.

Background

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. density works only if bitCount is 1. 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 my program 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 disk space 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 JC status line or the Options/Texture dialogue in CelLab for Windows.

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 JC editor or load a new pattern. The setInitialRandomSeed planes are re-randomized whenever you load a new pattern, but not when you leave the JC editor.

Topology

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 one-dimensional rules run quite a bit faster than the two-dimensional rules.

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:

When we are in one of the three 1D modes the values of the neighboring cells are passed in variables as follows:

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 the simulator to evaluate averaging rules. These rules were devised to allow generalizations of the Rug rule of RC. 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. Since setWorld(11) has less work to do it runs faster than setWorld(10), although both types run slower than do our standard two-dimensional rules.

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-randomising 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 "own code 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 inner loop function. These inner loop functions have extension .jco. 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 setWorld(10), but I wanted to have the wrap off. The JC Rug rule calls a function called semi8.jco 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 JC 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.

Rule Program Shorthand

Precomputed Neighbor Counts

    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.

Bit Planes and Fields

int BIT(plane)

Returns the single bit mask corresponding to plane plane. For example, BIT(0) = 1 and BIT(7) = 128.

int BITMASK(plane, nbits)

Returns a bit mask for extracting a field of nbits bits starting at plane. BITMASK(4, 2) = 48. nbits may be 1, in which case only one bit is set in the mask, or zero, yielding a zero mask.

boolean BITSET(plane)

Tests whether the bit corresponding to plane is set in oldstate. Note that the result of this method is boolean; if you want an integer result use the BITFIELD method described below.

int BITFIELD(plane, nbits) or BITFIELD(plane)

Returns the integer value of the field in oldstate which starts at plane and extends for nbits. The the nbits argument is omitted, a one bit field is returned. Suppose oldstate is 237, or binary 01101101, and we wish to extract the three bit field starting at plane 4 (shown in bold in the binary value). The call BITFIELD(4, 3) returns the desired bits, whose decimal value is 6.

int BF(value, plane)

Returns the given value (which can be either an int or boolean taken to be 1 if true and zero if false), shifted to appear in a bit field starting at plane. BF is handy when returning a new state from your rule function composed of several items stored in separate bit fields.

Texture and Phase

HPHASE()

Contents of the horizontal texture plane(s) for this cell.

VPHASE()

Contents of the vertical texture plane(s) for this cell.

HVPHASE()

Result of concatenating the contents vertical phase planes(s) with the horizontal phase plane(s), with the vertical phase in the most significant bits. The horizontal and vertical texture fields need not be contiguous within oldstate.

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.

Parametric Rule Definitions

int NLUKY(N, L, U, K, Y)

Returns the new state for an NLUKY rule with the current state given in oldstate and the specified parameters for N, L, U, K, and Y. A jcrule method defining the Brain rule can be written as:

    int jcrule(int oldstate) {
        return NLUKY(1, 2, 2, 9, 9);  // Brain
    }

int TOTALISTIC(code, history)

Returns the new value for a totalistic rule with the given code, a number between 0 and 1023 whose 2ⁿ bit gives the new state when the current state and eight adjacent neighbors sum to n. If the boolean argument history is true, a one bit history of the last state is kept in plane 1. If history is not specified, false is assumed. The following jcrule method is a complete definition of the Vote rule with a one bit history.

    int jcrule(int oldstate) {
        return TOTALISTIC(976, true); // Vote rule with history
    }

Using the Rule Compilation Server

To use the server, first write your rule program as described earlier in this chapter, but include only the definitions of the jcrule and, if needed, jcruleModes methods--don't include class declaration that encloses them or the main program; these are supplied automatically by the compilation server. You can then navigate to the rule compilation form, paste your program into the text box, enter the name of your rule in the field at the top and press the Compile button to submit the rule to the server. If all goes well, in a few moments, your browser will inform you a file with the name of your rule and an extension of .zip is ready to download. Proceed with the download and after the file is received, use a ZIP extract program such as PKUNZIP to extract the .jc file from the archive. Once you've extracted the contents, you don't need the .zip file any more, so you might as well delete it. You can then load the .jc into JC or CelLab for Windows and try out your new rule.

Let's try it right now. The following form is filled out with a definition of the Brian's Brain rule.

Note that we've entered the rule name, "brain", in the title box at the top and placed the code for the jcruleModes and jcrule methods (but nothing else) in the text edit box. The Compile button above is live--press it to submit the rule to the compilation server. If your browser manages to download the resulting .zip file, you'll be able to use the compilation server for rules of your own. Some browsers can't manage to download the .zip file from the server; if you have such a browser, replace it with a more capable program and try again later.

If your rule program contains an error which causes it to fail to compile or a runtime error, instead of a .zip file, you'll receive back a text page listing the error from the compiler or runtime system along with a listing of your program with line numbers corresponding to those cited in the error message(s). The program listing will contain lines added by the compilation server--don't copy these back into your rule program in the text box. The following form contains a copy of the Brain rule with a deliberately-introduced error.

Press Compile to submit this flawed rule program and you'll see the error page which results. When you get an error page from the server, you can return to the rule compilation page in order to correct your program and try again by pressing your browser's Back button.

Compiling a Rule from a File

Back to Defining Rules

Onward to Defining Rules in Turbo Pascal