Cellular Automata Laboratory

Defining Rules in BASIC

The file JCRULE.BAS contains a BASIC program which defines the rule for the game of Life and forms the starting point for defining your own rules in BASIC. It may be run under IBM BASICA®, GW-BASIC®, or other compatible dialects of BASIC; tricky features have been avoided in an attempt to render the program as portable as possible. Note that these BASICs are all "interpreted" languages, meaning that they must reconvert each program statement to machine code each time it is executed. This means that the generation of a 64K .JC ruletable will take a modicum of time. A faster way to use BASIC is to treat it as a compiled language like Pascal or C. One BASIC compiler which works with our programs is Microsoft® QuickBASIC®. If you write a BASIC program, compile it with QuickBASIC and then run it, you will achieve much faster creation of ruletables. When you run the program, it prompts:

Rule file name:

You should respond with the name of the rule definition file to be generated (don't specify the ".JC" file type; the program adds it automatically). Enter the rule file name; the program will write the rule file and then stop. You may then leave BASIC and execute JC to try out the rule. One point to note is that, unlike Pascal and C, BASIC does not generate the .JC file in compressed format. To put a BASIC-created .JC file into the more space-saving compressed format, go into JC, load the uncompressed rule, and then use Ctrl-F2 to make JC resave the rule. JC will save the rule in compressed format.

The rule-defining function begins at line 10000, and a comment describing it appears immediately before that line in the program. The rule-defining function is called with a GOSUB 10000 with the neighborhood stored in variables as follows.

Variables N1 through N9 are set to the neighborhood of the cell. Each is 0 if the cell is off and 1 if it is on. The neighborhood is represented as follows:


Note that N5 is the cell itself. Access to the local cell state bits is provided by the variable O, which is set to the cell's old state, ranging from 0 to 255. The function must compute the cell's new state, again in the range from 0 to 255, store it into variable R, then return.

The following function defines the game of Life, proceeding directly from Poundstone's description.

10000 rem Each square cell has eight neighboring cells.  It
10010 rem adjoins four cells on its edges and touches four
10020 rem more at the corners.  During each moment of time,
10030 rem the player or computer counts the number of
10040 rem neighboring cells that are on for each and every
10050 rem cell.
10060 rem
10070 C=N1+N2+N3+N4+N6+N7+N8+N9
10080 rem
10090 rem If, for a given cell, the number of on neighbors
10100 rem is exactly two, the cell maintains its status quo
10110 rem into the next generation.  If the cell is on, it
10120 rem stays on; if it is off, it stays off.
10130 rem
10140 IF C = 2 THEN R=N5 : RETURN
10150 rem
10160 rem If the number of neighbors is exactly three, the
10170 rem cell will be on in the next generation.  This is
10180 rem so regardless of the cell's present state.
10190 rem
10200 IF C = 3 THEN R=1 : RETURN
10210 rem
10220 rem If the number of on neighbors is zero, one, four,
10230 rem five, six, seven, or eight, the cell will be off
10240 rem in the next generation.
10250 rem
10260 R=0
10270 rem There are no other rules.
10280 RETURN

Since the rule for the game of Life only uses plane #0, the rule contains no reference to the other state bits stored in O. Rules which use Planes 1-8 may be specified straightforwardly in BASIC 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 BASIC as follows:

10000 rem
10010 rem Brian's Brain
10020 rem
10030 C=N1+N2+N3+N4+N5+N6+N7+N8+N9
10040 rem
10050 rem If previously in the refractory state, go to the
10060 rem ready state.
10070 rem
10080 IF O = 2 THEN R=0 : RETURN
10090 rem
10100 rem If firing, go to refractory state.
10110 rem
10120 IF O = 1 THEN R=2 : RETURN
10130 rem
10140 rem Otherwise, fire if exactly two neighbors are
10150 rem firing.
10160 rem
10170 IF C=2 THEN R=1 ELSE R=0
10180 RETURN

A rule definition function in BASIC may configure certain modes for the simulator by setting certain variables to values defined as follows. The variables and their default values are set at the top of JCRULE.BAS. Edit them as required in your rule definition program that was initially a copy of JCRULE.BAS.

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 specify the tradeoff between the number of visible neighbors and the number of bits of state visible from each, by setting the variable W8. The settings are as follows:

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.

If a one-dimensional neighborhood is selected (by setting W8 from 2 to 9), the neighbor cells N1-N9 have different meanings. In every case, consider the neighborhood of the center cell, O, as:

N1 N2 N3 N4 O N6 N7 N8 N9

The exact meaning of N1 through N9 depends upon the tradeoff between the number of neighbors and the number of bits of state visible from each neighbor chosen by the setting of W8. Regardless, 8 bits of state are available for the cell itself, and thus the value in O will range from 0 to 255. N1 through N9 will always have values of one or zero. If 8 neighbors with one bit of visible state are selected, (W8=2 or 3) these values represent the least significant bit of the state of the 8 cells that are closest to the cell being updated, laid out along the line as shown above.

If 4 neighbors with 2 bits of visible state are selected by setting W8 to 4 or 5, the neighborhood of the center cell O may be considered as:

L2 L1 O R1 R2

where the two bit state of the four adjoining cells are obtained from N1 through N9 through the expressions:

           L2 = (N1 * 2) + N2
           L1 = (N3 * 2) + N4
           R1 = (N6 * 2) + N7
           R2 = (N8 * 2) + N9

The values L1, L2, R1, and R2 are not automatically precalculated for your rule; you may cause them to be calculated by executing a GOSUB 3000.

If 2 neighbors with 4 bits of visible state are selected, by setting W8 to 8 or 9, the neighborhood of the center cell O may be considered as:

L1 O R1

where the four bit state of the two adjoining cells are obtained from N1 through N9 through the expressions:

           L1 = (N1 * 8) + (N2 * 4) + (N3 * 2) + N4
           R1 = (N6 * 8) + (N7 * 4) + (N8 * 2) + N9

The values of L1 and L2 are not automatically precalculated for your rule; you may cause them to be calculated by executing a GOSUB3100.

Thus you simply use N1 through N9 for 8 neighbors, do a GOSUB 3000 and use L2, L1, R1, R2 for 4 neighbors; or do a GOSUB 3100 and use L1 and R1 for 2 neighbors.

Here are the relevant lines from a BASIC definition of the one-dimensional Aurora rule:

1165      W8 = 9
1295      F6 = 15
1350      Q2$ = "aurora"
1540      T7 = 0
1545      T8 = 4
1550      T9 = 255
10000 gosub 3100
10010 r = int(((l1 + (o and 15) + r1)) / 3) + 1
10020 return

The int() is required because division in BASIC returns a floating point value.

Choosing WorldType (W8) 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 rules 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, variable O holds the low five bits of the EveryCell's old eightbit state, and the variable N1 holds the sum of the EveryCell's eight (W8=10) or four (W8=11) eightbit neighbors. 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 O and N1 are not used.

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. These inner loop functions have extension .JCO. They are discussed more fully later in this section.

For own code rules (WorldType = 12 or 13), the raw index into the lookup table is passed in the double precision variable O1# (make sure to use INT() if you use division to extract bits from this value). In addition, I9 contains the most significant 8 bits of the lookup table index and J9 contains the least significant bits. None of the other neighbor variables are initialized.

You can select random input to any contiguous span of bits of every 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 T5 to the least significant bit of the desired random bit field and T6 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 so that the rule can examine it. Horizontal texture identifies the individual cells along rows in the state map. To enable horizontal texture, set T1 to the least significant bit of the field to contain the horizontal texture and T2 to the number of horizontal texture bits desired. You can provide vertical texture information to the rule in a similar manner by setting T3 and T4; 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 T1 to 5 and T2 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 T1 and T3 to the same bit and T2 and T4 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 in R as they were passed in the variable O.

You can request a specific pattern file be loaded when the rule file is loaded by setting the Q1$ variable to the pattern file name. For example, if your rule should be run with the pattern in file TRICORN.JCP, use the statement:

Q1$ = "tricorn"

in your rule definition. Similarly, a rule definition can request a colorpalette file to be loaded by setting the variable Q2$. To load a colorpalette file called VIVID.JCC, use the statement:

Q2$ = "vivid"

in your rule definition program own code request. Your rule can request an own code evaluator to be loaded by setting the variable Q3$ to the file name. To load an own code evaluator named LAPLACE.JCO, use

Q3$ = "laplace"

Many rules require a random seed pattern in one or more bitplanes. While you can specify 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 one or more bit planes to be randomized programmatically. To specify an initial random seed, set the variable T7 to the least significant bit of the initial random seed field and T8 to the number of bits of initial random seed desired. Random bits generated by the initial random seed mechanism normally are uniformly distributed: half zeroes and half ones. You can specify the density of the bits generated by setting the variable T9: the default value of 255 generates half ones and half zeroes. Values less than 255 select lower densities of ones. If you set T9 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 T9 specification makes sense only when T8 is set to 1.

Because interpreted versions of BASIC execute very slowly, a rule definition program may specify which state bits are relevant to the rule; the fewer bits the rule depends upon, the faster it is generated. Variable F6 selects the state bits a rule examines; the default value of 255 describes a rule dependent upon all 8 bits of local cell state. If your rule examines only the two least significant bits of state (as does Brian's Brain, see Brain.BAS), you may set F6 to 3, which will generate the rule definition 64 times faster.

The speed at which the simulator runs does not depend at all upon 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.

For executable examples of BASIC rule definitions, look at the definition of Life in JCRULE.BAS, and also at BRAIN.BAS, the BASIC language definition of Brian's Brain, as given above. A good way to start writing your own rules is to copy JCRULE.BAS to a new file FIRST.BAS. Then you can change a few things in FIRST.BAS and try running the rule to get your own FIRST.JC.

The JCRULE.BAS file contains a built-in definition of Life. All the separate rule sample definitions simply contain lines that replace that built-in definition with the rule they're defining. For example, here is the listing of VONPAR.BAS, which defines a 3 bit von Neumann neighborhood parity rule that works in conjunction with the VONN3 own code evaluator.

1 rem
2 rem  Three bit parity rule in von Neumann neighborhood, 
3 rem  using the VONN3 own code file.
4 rem
5 rem  MERGE this file after loading JCRULE.BAS first.
6 rem
1165 W8 = 13
1295 F6 = 127       : rem Top bit of local state not used
1375 Q3$ = "vonn3"
10000 rem Three bit parity rule in the von Neumann
10010 rem neighborhood implemented using the VONN3
10020 rem own code file. Note how the neighbor cell values
10030 rem are extracted from the lookup table index passed
10040 rem in O1# (and I9 and J9), according to the encoding
10050 rem used by VONN3.
10060 rem
10070 N8 = (j9 MOD 8)                : rem South
10080 N6 = (int(o1# / 8) MOD 8)      : rem East
10090 N4 = (int(o1# / 64) MOD 8)     : rem West
10110 N2 = (int(o1# / 512) MOD 8   ) : rem North
10120 N5 = (int(o1# / 4096) MOD 8)   : rem Self
10120 r = n2 xor n8 xor n4 xor n6
10130 RETURN

The lines number 1165, 1295, and 1375 replace lines so numbered in JCRULE.BAS to set worldtype, the generation optimization mask, and the own code load request. The rule is defined by the code that starts at line 10000, as before. Note that rule definition code must be careful to delete the lines which define Life in JCRULE.BAS, numbered 10000 through 10100 in increments of 10.

To generate this rule using BASICA or GW-BASIC, load BASIC, then enter the commands:

LOAD "jcrule"
MERGE "vonpar"

The MERGE command loads VONPAR.BAS, replacing lines with the same numbers in JCRULE.BAS. If you don't want to go through this MERGE every time, simply SAVE the composite file after the MERGE. Microsoft QuickBASIC does not provide a line number-oriented MERGE facility. If you want to use QuickBASIC and have access to BASICA or GW-BASIC, the easiest approach is to perform the MERGE using one of those products, then SAVE "file",A, to save an ASCII merged file which may be loaded and run directly from QuickBASIC. If you lack a suitable BASIC interpreter, QuickBASIC's editor may be used to insert the rule definition lines into a loaded copy of JCRULE.BAS using the cut and paste features.

Back to Defining Rules

Onward to Own Code Evaluators

Next Previous Contents