Cellular Automata Laboratory


Defining Rules in C

To define a rule in C, you write an int function called jcrule which, when called with arguments containing the state of a cell and its neighbors, returns the new state for the cell as an integer from 0 to 255. You place this function in a file by itself and compile it. You then link your function with a compiled version of the program in the file JCMAKER.C (supplied in source code form so you can compile it with whatever C compiler you're using), and execute the resulting object file with the command:

exename rulename

where exename is the name of the executable file generated by the linker and rulename is the file name into which you wish the rule definition written, as rulename.jc. Because implementations of C differ in the ways that compiling and linking are performed, you'll have to refer to the manual for your compiler to see precisely how to do these tasks. In addition, various implementations of C have subtle incompatibilities which may result in warning messages or outright errors when code is moved to a different compiler. This code has been designed to avoid most of the common pitfalls, but you should be aware of the possibility that you may have to do a little debugging the first time out. One thing to look out for is to make sure that your C compiler is set so as to choose the "Large Data Model." Borland's Turbo CŪ Version 2.0 was used to develop this code. To understand how to write a jcrule function, first we must consider the neighborhood of a cell, as seen by the function through its arguments. If the function is defined as:

int jcrule(oldstate,
                    nw, n , ne,
                    w, self, e,
                    sw, s , se)
int oldstate, nw, n, ne, w,
          self, e, sw, s, se;
{
          ...
}

then the arguments represent the neighborhood as follows:

nwnne
wselfe
swsse

Each of these arguments will be 1 if the low-order bit of the corresponding cell in the neighborhood is on, and zero if it is off. In addition, the rule function may examine the argument oldstate, which contains the full state of the center cell (eight bits). Thus, oldstate ranges from 0 to 255, with the presence of the 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 defines the game of Life, proceeding directly from Poundstone's description.

/* The game of Life */
int jcrule(oldstate,
                    nw, n , ne,
                    w, self, e,
                    sw, s , se
          )
int oldstate, nw, n, ne, w,
     self, e, sw, s, se;
{
  int count;

/* Each square cell has eight neighboring cells.  It adjoins
   four cells on its edges and touches four more at the
   corners.  During each moment of time, the player or
   computer counts the number of neighboring cells that are
   on for each and every cell.  */

     count = nw + n + ne + w + e + sw + s + se;

/* If, for a given cell, the number of on neighbors is
   exactly two, the cell maintains its status quo into the
   next generation.  If the cell is on, it stays on; if it
   is off, it stays off.  */

     if (count == 2)
          return self;

/* If the number of neighbors is exactly three, the cell
   will be on in the next generation.  This is so regardless
   of the cell's present state.  */

     if (count == 3)
          return 1;

/* If the number of on neighbors is zero, one, four, five,
   six, seven, or eight, the cell will be off in the next
   generation.  */

     return 0;
/* There are no other rules. */
}

Since the rule for the game of Life doesn't use the higher bit-planes at all, the rule contains no reference to oldstate. Rules which use the other bitplanes may also be specified straightforwardly by C rule definition functions. For example, here is the definition of Brian's Brain, a rule developed by Brian Silverman and described in [Margolus&Toffoli87], § 6.1, Page 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 C function as follows:

/* Brian's Brain */
int jcrule(oldstate,
                    nw, n , ne,
                    w, self, e,
                    sw, s , se
          )
int oldstate, nw, n, ne, w,
     self, e, sw, s, se;
{
     int count;

     count = nw + n + ne + w + self + e + sw + s + se;

/* If previously in the refractory state, go to the ready
   state.  */

     if (oldstate == 2)
          return 0;

/* If firing, go to refractory state.  */

     if (oldstate == 1)
          return 2;

/* Otherwise, fire if exactly two neighbors are firing.  */

     return count == 2 ? 1 : 0;
}

A rule definition function in C may also configure certain modes for the simulator by declaring extern references to several global variables defined in JCMAKER.C, then setting them to the desired values inside the rule function. These values affect the simulation as a whole, not on a cell-by-cell basis: only the last values stored by the jcrule function will take effect. They are set inside the jcrule function just for convenience--since few rule definitions will wish to change these variables from their defaults, setting them inside jcrule keeps most rules from having to define a dummy function just to specify these modes. To save time, you can use a static variable so that your jcrule function only sets these variables the first time it's executed. You may define all of these variables by including the definition file jcrule.h in your rule function with the statement:

#include "jcrule.h"

The file jcrule.h also supplies a set of definitions to aid in constructing complex rules: refer to the file and sample C rule definitions which use it, such as perfumex.c, for details.

You can specify the dimensionality of the cellular automaton and whether the world is open or closed (wrap or no wrap). For one-dimensional automata you can also specify the tradeoff between the number of visible neighbors and the number of bits of state visible from each by setting the variable worldtype. The settings are as follows:

worldtypeDimensionalityWrap?NeighborsBits
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

The 1D rules work by a) updating the top line of the screen, and b) copying each line to the line below it. This produces a spacetime trail of the 1D rule, with earlier times appearing lower on the screen like geological strata.

jcrule.h includes definitions which provide one-dimensional neighbor names as follows. Three sets of neighbor declarations are provided; choose the correct set based upon your choice of the tradeoff between the number of visible neighbors and the number of visible bits of neighbor state per cell, as expressed in the setting of worldtype. The following table presents the options.

WorldtypeNeighborsBitsNeighbor Names
2 or 3 8 1 N8L4 N8L3 N8L2 N8L1
self
N8R1 N8R2 N8R3 N8R4
4 or 542 N4L2 N4L1 self N4R1 N4R2
8 or 924 N2L1 self N2R1

As with a two-dimensional rule, you should use "self" for the current cell if you're interested only in the low-order bit of the cell and "oldstate" if you want to examine all 8 bits. All one-dimensional modes provide the standard 8 bits of local state per cell.

The following C code is an implementation of the one-dimensional Aurora rule using these facilities.

/* This is a C version of the Aurora rule.  The rule runs in
     a one-dimensional closed ringworld with two visible
     neighbors each providing 4 bits of state.  The rule is:

     NewState = (Left + Self + Right) / 3 + 1 */

#include "jcrule.h"

RULEDEF()
{
   static int firstime = 1;

   if (firstime) {
        firstime = 0;
        worldtype = 9; /* 2 neighbors, 4 bits each */
        strcpy(palreq, "aurora"); /* Aurora colorpalette */
        rseedn = 4;         /* Seed with 4 random bits   */
        rseedb = 0;         /* Starting at bit 0         */
   }

   return ((N2L1 + (oldstate & 15) + N2R1) / 3) + 1;
}

Choosing WorldType 10 or 11 causes JC to evaluate averaging rules. These rules were devised to allow generalizations of the Rug rule of RC. In both of these WorldTypes the screen is wrapped. WorldType 10 computes the sum of EveryCell's eight nearest neighbors, and WorldType 11 gets the sum of EveryCell's four nearest neighbors. Since WorldType 11 has less work to do it runs faster than WorldType 10, although both types run slower than do our standard two-dimensional rules.

In these rules, the first argument passed to jcrule holds the low five bits of the EveryCell's old eightbit state, and the second argument passed to jcrule holds the sum of the EveryCell's neighbors. (Eight neighbors in WorldType 10, and 4 neighbors in 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.

In WorldTypes 10 and 11, the variables other than the first one are simply placeholders, and have no functionality whatsoever.

WorldTypes 12 and 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 WorldType 12 or 13, one must have a predefined inner loop function which repeatedly returns a sixteen bit number. These inner loop functions have extension .JCO. They are discussed more fully later in this section.

You can select random input to any contiguous span of bits in each cell. On every generation these bits will be set to a new random value. The random bits are uniformly distributed; on average half the bits are zeroes and half are ones. To select random input set variable randb to the least significant bit of the desired random bit field and randn to the number of random bits desired; by default no random bits are supplied. Selecting random bits slows the execution of the simulator somewhat.

To create position sensitive rules, you can specify that a vertical or horizontal texture be placed in the state map as input to the rule definition. Horizontal texture identifies the individual cells along rows in the state map. To enable horizontal texture set texthb to the number of the least significant bit of the field which contains the horizontal texture and texthn to the number of horizontal texture bits desired. You specify vertical texture information to the rule in a similar manner by setting textvb and textvn; vertical texture supplies values that increment on successive lines. If you select one bit of texture (the most common case), you'll get a bit that toggles between zero and one for each column (horizontal texture) or row (vertical texture). If you select more than one bit of texture, the value increments within the field size you specify. For example, if you set texthb to 5 and texthn to 2, the two bit field (bits 5 and 6) will cycle among binary values 00, 01, 10, 11, 00, 01, 10, 11, and so on for successive columns in the state map. If you set texthb and textvb to the same bit and texthn and textvn to 1, a checkerboard pattern will be generated. The texture specification simply places an initial texture in the state map when a rule or pattern is loaded; the texture is not replaced on every generation. It's up to the rule to preserve the texture from generation to generation by returning the texture bits as they were specified by oldstate.

You can request that a specific pattern file be loaded when a rule is loaded by setting the patreq variable to the pattern file name using the strcpy function. For example, if your rule should be run with the pattern in file TRICORN.JCP, you can include the statement:

strcpy(patreq, "tricorn");

in your rule definition. Similarly, a rule definition can request that a colorpalette file be loaded by setting the variable palreq with strcpy. To load a colorpalette file called VIVID.JCC, add the statement:

strcpy(palreq, "vivid");

to your rule definition function. You can request that an own code evaluator be loaded by setting the variable ocodereq. To load own code evaluator LAPLACE.JCO, use

strcpy(ocodereq, "laplace");

Many rules require a random seed pattern in one or more bit planes. While you can supply these bits by saving them in a pattern file, pattern files with random bits occupy large amounts of disk space. To save space your rule can request that one or more bit planes be randomized programmatically. To specify an initial random seed, set the variable rseedb to the least significant bit of the initial random seed field and rseedn to the number of bits of initial random seed desired. Random bits generated by the initial random seed mechanism are by default uniformly distributed: half zeroes and half ones. You can specify the density of the bits generated by setting the variable rseedp; the default value of 255 generates half ones and half zeroes.

Values less than 255 select lower densities of ones. If you set rseedp to 128 only 25% of the bit fields will be nonzero. Since the density specification works by setting the specified percentage of bit fields to zero, the rseedp specification makes sense only when rseedn is set to 1.

Since setting patreq, palreq, and ocodereq can be time-consuming, it makes sense to only set them in the first execution of the rule definition function. For example, here's the code that sets the rule definition variables in the PerfumeX.C sample rule definition function.

int jcrule(oldstate, nw, n, ne, w, self, e, sw, s, se)
int oldstate, nw, n, ne, w, self, e, sw, s, se;
{
          static int firstime = 1;

          if (firstime) {
               firstime = 0;
               texthb = 4;
               texthn = 1;
               textvb = 5;
               textvn = 1;
               strcpy(palreq, "perfume");
               strcpy(patreq, "perfume");
          }

          ... rule definition ...
}

The speed at which the simulator runs does not depend at all on the complexity of the rule or the pattern; it is completely constant. There is no reason to make the function that defines the rule efficient--it is executed only to create the rule definition file, then never used again.

Several sample C rule definitions are supplied with the CelLab. You may wish to examine the files for examples of how to define rules. An easy way to slide into writing your own rules is to copy of one of our .C ruleprograms to a new file, say FIRST.C, change FIRST.C to suit your own purposes, and then run it to get your own first JC rule, FIRST.JC. If it happens that your rule either 1) fails to return a value for some inputs or 2) returns a value outside the range 0-255, then you will get an error message when the program tries to generate FIRST.JC. If this happens, fix your program and...try again.

Back to Defining Rules

Onward to Defining Rules in BASIC


Next Previous Contents