September 12, 1999
This paper introduces a new methodology for low level cellular automata rule specification: Animation-Reduction Cellular Automata (ARCA) rule specification. Fast programmable cellular automata (CA) implementations result from straightforward application of this methodology. ARCA methodology allows specification and implementation of CA's which are impractical to implement using the more traditional result table based (RTB) methodology.
This paper also introduces a new programming language based upon animation-reduction rule specification: Animation-Reduction Cellular Automata Language (ARCAL). ARCAL is designed to run efficiently on just about any microprocessor or general purpose computer. It is particularly well suited to the commonly available desktop architectures of the late nineties: fast uniprocessors with plenty of main memory, fast on chip primary cache memory, and indexed video display. ARCAL also works quite effectively and efficiently on machines with very little memory, since it requires only a single frame buffer for cell state value storage.
ARCAL overcomes two of the more severe limitations of traditional RTB CA methodology. It easily allows creation of efficient CA's with relatively large numbers of potential states, and it doesn't at all restrict the spatial interconnections of cells to a particular neighborhood. ARCAL can be used to create many CA's which are entirely impractical to create using RTB CA methodology, such as CA's which model complex motion of particles or agents. Virtual Ant CA's are an excellent example of this. ARCAL is particularly well suited to CA simulations in which the active population is small compared to the total number of cells. Small glider formations in Life can appear to move very quickly indeed. Small Virtual Ant populations quickly rack up millions of generations.
I have made available a Windows 32-bit program, Super Animation-Reduction Cellular Automata Simulator (SARCASim), which can execute ARCAL programs. SARCASim may be found on my cellular automata web page at www.collidoscope.com/ca.
Animation-Reduction Cellular Automata specifications are cellular automata specifications which:
In an ARCA specification, a cell's state value determines whether state transition computations are performed on the cell or its neighbors. State values which are active are always involved in computation, while those which are deactivatable are potentially not involved in computation. Deactivatable cells with only deactivatable neighbors are not allowed to change state in an ARCA.
ARCA implementations have the potential to be computationally efficient for certain classes of CA, because the CA specification itself can provide a blueprint for computational optimization.
Since ARCA specifications don't require intergroup state value transitions, any non-ARCA specification can be trivially rewritten as an ARCA specification with a single deactivatable state value which is never used, either in the CA's cells or in its rules. Non-ARCA's thus may be considered special cases of ARCA's.
ARCAL is a simple programming language used to specify the potential states of an ARCA and its algorithm for next generation computation. It is a very low level language. It can be thought of as a machine language for reduced instruction set CA's.
ARCAL's basic operation is the table lookup, of which there are two kinds. The first kind of lookup involves replacing a cell's state value by a value obtained by indexing into a lookup table using the cell's previous state value as an index. The second kind of lookup uses a cell's state value to select the effects which the cell has upon its neighbors. Since ARCAL has no other notion of operations other than table lookup, doing things such as counting neighbors must be performed by stringing together a series of table lookups. Table lookups are particularly efficient on modern processors when the table fits easily into the processor's primary cache.
It is possible to create compilers for higher level CA specifications which produce ARCAL as output.
An ARCAL program starts with a specification of the states available for use in the CA. ARCAL provides four different kinds of state value.
ARCAL's live state values are active and therefore can affect neighboring cells during next generation calculation. ARCAL's dead state values are deactivatable and can be involved with calculation only if they are a neighbor to a cell with an active state value.
Like live state values, temporary state values are active and can affect neighboring cells. Temporary state values are used for storage of intermediate results during calculation of a CA's next generation. ARCAL programs are restricted from producing temporary state values as the end result of next generation calculation. ARCAL programs are not required to define or use temporary states. Still, most of the states used in a typical ARCAL program are temporary states. For example, an ARCAL Life program will typically use at least eight temporary states.
Finally, ARCAL provides inert state values, which are not only deactivatable but are also restricted from ever changing. Inert cells are never involved in computation. ARCAL implementations use inert state values as borders which restrict a CA population and its effects to a specific area of memory. This makes special handling of the edge cells for a finite simulation unnecessary, leading to greater runtime efficiency. If an ARCAL program doesn't explicitly declare any inert state values, ARCAL provides one, named inert.
ARCAL as implemented by SARCASim allows up to 64 different state values to be defined and used. At least one of these state values must be an inert state value.
Calculation of a CA's next generation is specified in ARCAL as a sequence of steps. Each step is characterized as either an animation or a reduction. Animations potentially make cells active, whereas reductions potentially make them deactivatable. Many ARCAL programs, including Life, consist of a single animation step followed by a single reduction step.
An ARCAL animation specifies the effect of an active source cell on its neighbors. The source is allowed to change the state of its neighbor cells in such a way that the result state is active. Animations with deactivatable source states are not allowed. Also disallowed are animations in which a result cell changes state from active to deactivatable.
An ARCAL reduction does not affect a cell's neighbors. Instead, it specifies state conversions to be applied to active source cells. ARCAL reductions with deactivatable source states are not allowed.
I assume that the reader is familiar with Conway's game of Life. The rest of this section demonstrates each of ARCAL's six constructs using an implementation of Life.
An ARCAL program starts with a definition of the states which are available for use in the rest of the program.
Here are the states for Life:
states
dead dead
live live
temporary d1 d2 d3 d4 ; dead cells w/live neighbor count
L1 L2 L3 L4 ; live cells w/live neighbor count
end
This defines ten different state values for use, eight of which are temporary states. In this model the "d3" state is a temporary state which represents a dead cell which has so far counted three live neighbor cells, while the "L4" state represents a live cell which has so far counted four or more neighbors. Note that for Life there is no need to count more than four neighbors per cell, since a cell with at least four live neighbors will die regardless of the number of additional live neighbors it might have.
An ARCAL transition definition is used for specifying the effect an active cell has upon a single neighboring cell. It represents a simple table lookup, where the neighboring cell's state value is replaced by a value obtained by indexing into the table using the neighboring cell's current state value as the index. Transitions are used to build animations.
Here is the only transition definition needed for Life:
transition count-live
make d4 from d3 from d2 from d1 from dead
make L4 L3 L2 L1 live ; the from can be implicit
end
This is used for counting the neighbors of a "live" cell. If this operation is applied to a cell which has state "d2" its new state value will be "d3". If it is applied to a cell which has state "d4" the new state value will remain at "d4". Once a state value gets to "d4" or "L4" it is effectively stuck there. Again, for Life, more than four neighbors for a cell do not need to be counted.
Transitions have the same restrictions as the animations they are used to build. They are allowed to make deactivatable states active, but they are not allowed to make active states deactivatable.
An ARCAL map definition associates ARCAL transitions with each of the neighbors of an active cell (one with active state).
Here is the only map definition needed for Life:
map count-live
use count-live for NW N NE W E SW S
use count-live for SE ; different transitions allowed
end
This specifies that the count-live transition is to be applied to neighbor cells to the northwest, north, northeast, west, east, southwest, south, and southeast. Notice that ARCAL lets you choose the same name for your map specification as you chose for your transition specification. ARCAL allows you to apply a different transition to each neighbor. Finally, ARCAL neighbor specifications are not restricted to the eight cells surrounding a particular cell. For example, displacement to a neighbor cell two cells north would be specified using NN.
ARCAL does not allow the same neighbor address to be specified more than once in a map specification.
An ARCAL animation specifies associations between the current state values of an active cell and corresponding ARCAL maps. It represents a using the active cell's state value as an index into a lookup table of maps.
Here is the only animation needed for Life:
animation count-live
use count-live when live L1 L2 L3
use count-live when L4 ; different maps allowed
end
This says that the count-live neighborhood mapping will be applied to a cell's neighbors only if the cell has a value which is "live", "L1", "L2", "L3", or "L4". Notice that different neighborhood rules may be specified depending upon the state of the source cell being examined.
ARCAL animations are not allowed to apply any mapping to the neighbors of a deactivatable cell. Only live and temporary state values may appear in the animation's "when" clause.
Reductions are similar to transitions, but are restricted in the opposite direction. They are allowed to convert active state values to be deactivatable, but are not allowed to make deactivatable states active.
Here is Life's reduction:
reduction decide
make dead from live or L1 or L4 or d1 or d2 or d4
make live from d3 L2 L3 ; the or can be implicit
end
Applying this reduction to a cell with "d2" state will result in the cell's state being set to "dead".
An ARCAL rules definition defines a named ARCAL program and specifies its steps. Each step may be either an ARCAL animation step or an ARCAL reduction step. Animations and reductions are therefore not allowed to have the same names. The first step of an ARCAL program is always an animation step. Reduction steps in an ARCAL program must be immediately preceeded by animation steps.
Finally Life is complete:
rules Life
count-live decide
end
This states that to compute the next generation using the rules of Life the count-live animation is first applied and then the decide reduction is applied. Many ARCAL programs consist of a single animation followed by a single reduction. ARCAL programs are also allowed to have more than one rule. The Time Tunnel CA has a both a forward rule and a reverse rule. The N of 8 CA has a different rule for each value of N.
Rule specifications complete the lexicon of ARCAL.
ARCAL does not specify the cell ordering used when an ARCAL step is being applied. It also does not require that the results of a ARCAL step be consistent for all possible cell orderings. Because of this some ARCAL programs will produce different results depending upon the order in which steps are applied to cell values. For example, evaluating new cell state values by column instead of by row might produce different results given identical starting populations. ARCAL does not restrict a user from creating such non-deterministic programs.
Storing a cell's history in an ARCA is done by devoting a portion of the state value space to history maintainance. For Life With History, for instance, there is an additional dead state, "once-live" and an additional live state, "long-lived", which provide history support. Time Tunnel and Brian's Brain are other CA's which use state values for maintaining temporal information.
In some CA's, such as Lichens, there is no death. Growth is ever increasing and cells remain alive forever after they become live. In such cases it may be advantageous to define an inert state value which represents live cells which can no longer affect their neighbors. Such a state value could be used to represent a live cell with all live neighbors.
This simple tactic works but the increase in speed may be small! Once a cell becomes inert it cannot affect its neighbors to make them inert, so very few cells become inert. A different approach is used in Fast Lichens, where the "dormant" state is dead instead of inert. A second animation step is added so that dormant cells which are next to "live" cells (and thus have state "dormant+") have a chance to contribute to the neighbor count of the "live" cells. This allows more "live" cells to become "dormant". Using SARCASim this speedup is dramatic when simulations are run with the active cell list option enabled.
Particle systems need to conserve particles, and thus some form of collision detection must be built into the CA, so that each cell is occupied by at most one particle. To make this work the following technique is used in the Virtual Ants CA. Two animations are used, back to back. The first is a peek into the neighboring cell where the vant will attempt to move. The second animation is a feedback to the vant doing the peeking. Empty cells which are probed by exactly one vant send feedback to the source cell of the vant so that it may be emptied. Vants which do not receive feedback from the cell they are facing don't move into that cell.
ARCAL was designed with a particular implementation architecture in mind. A typical ARCAL implementation will model the CA's cells with an array of eight byte quantities which can quickly be displayed on a computer's color monitor.
More importantly, ARCAL makes it easy to implement an efficient CA using a list of active cell addresses. Each step in a ARCAL program corresponds to a traversal of the active cells in the list. Animations potentially add newly active cell addresses to the end of the list, for use in subsequent steps. Reductions remove newly deactivatable cell addresses from the middle of the active cell list. The restrictions placed upon animations and reductions trivialize the task of active cell list management.
While ARCAL was designed with active cell list implementations in mind, it also can be used to produce efficient CA implementations in which there is no explicit active cell list maintained. Instead of traversing an active cell list all of the CA board's cells are traversed. In essence the CA's board itself represents the active cell list.
When large numbers of cells are active it becomes far more efficient to run without using an active cell list. But a lot of CAs, including Life, run faster when using an active cell list. SARCASim supports both modes of operation.
Even simple low level languages like ARCAL are ameniable to optimizations!
SARCASim restricts ARCAL pixel values to multiples of four to make animations more efficient. An animation involves using a cell's pixel value to index into a table of longwords to find the address of a map. Restricting the pixel values to multiples of four simplifies the address arithmetic needed to find the map. In effect the state pixel values are pre-shifted for this operation.
Other table lookups involve indexing into tables of byte quantities. Since state pixel values are multiples of four, SARCASim interleaves such result tables so that they are more space efficient and more likely to fit completely into primary cache. The C code for ARCAL Life example illustrates use of interleaved result tables.
ARCAL is designed in such a way that when implemented without use of an active cell list the ARCAL program may be transformed by the trailing reduction optimization, in which two steps, an animation followed by a reduction, are replaced with a single animation-like step which may operate on a few additional cells. Many CA's, including Life, are thus reduced to a single step.
Consider the relative neighborhood of cells which may be affected by the application of an animation to a source cell with arbitrary value. In any implementation which traverses the cells in a fixed order one cell in this relative neighborhood is the trailing cell. If the next generation is calculated by row top to bottom and each row is calculated by column left to right then the upper-left-most neighbor is the trailing neighbor.
The idea of the trailing reduction elimination is that the original animation and the reduction which follows it are combined to synthesize a new single step animation-like entity, by replacing the trailing transition with a new transition like entity which is the old transition catenated with the reduction step which follows. The low level C code which is responsible for advancing by a generation remains exactly the same! The new transition-like step must be applied to more than just the cells of the board. It must be applied to extra bordering cells in such a way that each cell of the board has a chance to be the trailing cell. For Life this amounts to traversing an extra row and an extra column.
Assuming the NW neighbor of a cell is the trailing neighbor, here is how the results of applying the trailing reduction elimination optimization might be expressed in an ARCAL-like language:
;
; Trailing Reduction Elimination Optimization Example: Life
; This is NOT a legal ARCAL program!
;
transition count-dead-last
make dead from dead make dead from live
make dead from d1 make dead from L1
make dead from d2 make live from L2
make live from d3 make live from L3
make dead from d4 make dead from L4
end
transition count-live-last
make dead from dead make dead from live
make dead from d1 make live from L1
make live from d2 make live from L2
make dead from d3 make dead from L3
make dead from d4 make dead from L4
end
map count-live-last
use count-live-last for NW
use count-live for N NE W E SW S SE
end
map count-dead-last
use count-dead-last for NW
end
animation Life
use count-live-last when live L1 L2 L3 L4
use count-dead-last when dead d1 d2 d3 d4 inert
end
rules Life Life end
The C code for ARCAL Life example illustrates the result of applying the trailing reduction elimination optimization.
When an ARCAL implemention is using an active cell list it may be possible to eliminate an animation's first lookup, which dispatches to the neighbor map for the source cell. This is the dispatch elimination optimization. For this to be performed all active cell state values and transformations of those values must use the same neighbor map.
Life is amenable to dispatch elimination. In SARCASim the size of its generated ARCAL code shrinks from 180 bytes to a mere 132 bytes once this optimization is applied. On a historic note, the prototypical ARCAL program was a hand coded version of Life which had no dispatch. Dispatches were added to support the Brian's Brain CA and later CA implementations without active cell lists. Brian's Brain is not amenable to dispatch elimination, since its "LIVE" and "REFRACT" states do not share the same map, as specified in its "COUNT" animation.
Branching while doing active cell list management in an ARCAL implementation can be avoided by use of the following technique, used in SARCASim. ARCAL transition tables and reduction tables are interleaved with accompanying increment tables. If the address of the transition or reduction is X then the address of its increment table will be X+1. Each increment will be a byte quantity with a value of either zero or four (the size of a cell address in the active cell list).
Each step represents a traversal of the active cell list. During execution of each step a pointer will be maintained which points to the next slot into which the address of an active cell will be stored. Cells which are being placed onto the list for the first time increment the pointer, while those that are aren't being added don't affect it. In SARCASim each and every cell visited has its address stored using this pointer, which is then unconditionally incremented by the amount retrieved from the increment table. This reduces the amount of branching needed to evaluate a generation. For implementations in which memory is slow it may be more advantageous to branch so as to avoid redundant memory stores.
The book Cellular Automata Machines describes hardware implementation of a programmable cellular automata machine (CAM) which is result table based. The old state value of a cell and the old state values of its neighbors are combined together to form an index into a result table. The indexed table entry specifies the new value for a cell's state. In a software implementation of a RTB CA the new state values must be kept separate from the old state values, usually by utilizing two distinct cell buffers.
Take Life as an example. Given that a cell can only have one of two distinct states, live or dead, a nine bit quantity (representing the one bit value of a cell and the one bit values of its eight neighbors) is used to index into a result table. This means that the table contains 2^9 = 512 result values. Note that this result table is of reasonable size and will easily fit into the primary cache of most modern CPU's.
Traditional RTB CA methodology has been well established over the last twenty years, and it has been quite successful at creating a wide variety of interesting CA's. Except for the Virtual Ants CA each of the CA's discussed in this paper has an equivalent specification in Cellular Automata Machines. However, traditional RTB CA methodology imposes severe limitations on the kinds of CA's which can be defined. Efficiency concerns also arise when implementing RTB CA's on today's general purpose processors.
The RTB approach to implementing fast programmable CA's suffers a glaring weakness: the size of its lookup tables is exponentially related to the number of state values in use. In particular:
entries = states^(neighbors+1)
This strongly discourages the use of many distinct state values, and indeed it makes straightforward implementation of many interesting CA's quite impractical. I call this effect state starvation.
Consider adding support for a cell's history to Life, to tell whether dead cells were ever once alive and whether live cells are newly birthed. Gliders will leave trails. A straightforward way to attempt this might be to add two additional state values, as Life With History does. However, the result table of the RTB CA would then contain a whopping 4^9 = 262144 entries.
Traditional RTB CA methodology can support up to about four distinct states. This is done by restricting the number of neighbors that a cell has to the four cells that are directly horizontally and vertically adjacent. This restriction once again makes the size of the result table manageable. Now it only contains 4^5 = 1024 result values.
It is notable that the CAM implementations of Brian's Brain and Life With History each use a secondary buffer as opposed to using more than two state values. CAM's restrict the size of a result table to 4096 entries. Memory was expensive when CAM's were designed.
Today's CPUs are fastest when the program and its data fit easily into the CPU's primary cache storage. Primary cache misses can extract a significant performance penalty on a CA implementation, since memory subsystems are slower than primary cache. Primary cache implementations are typically small (far less than a megabyte) and they limit the number of places where a particular addressed value may be stored.
Traditional software RTB CA implementations are most efficient when the result table easily fits entirely in primary cache, leaving plenty of room for other data. Very poor performance may result if the result table is the same size as or larger than the primary cache, because thrashing will occur.
The use of additional buffers in a CA implementation can adversely impact performance. Each additional buffer put to use increases the probability of cache thrashing.
Traditional RTB CA methodology uses a result table whose size is exponentially related to the allowed number of states. In an ARCAL program the size cost of adding an extra state is linearly related to the number of tables in the program. There is very little penalty for using additional states in an ARCAL program. ARCAL is state rich.
We can do things with lots of states. For a virtual ant CA each cell is either red or black (as in a checkerboard) and it is either empty or it contains a virtual ant facing in one of four directions. At least ten different cell state values are needed to simulate virtual ants. A RTB CA result table needs to contain 10^5 (100000) entries. Handling virtual ant collisions properly requires that neighbor cells two neighbors away must be examined before the fate of a virtual ant can be resolved. Thus a RTB CA implementation must either use multiple result tables or a much larger table with 10^13 entries, a size which is quite impractical. Because ARCAL is state rich, it can be used to program a fast implementation of virtual ants.
When states are cheap and plentiful we can partition them into disjoint subsets, where transitions from one subset to another are not allowed. A cell's state value will always stay in the same subset. Then we can use the state subsets to represent spatial information, such as the relative position of a cell within an initial grid. This eliminates the need for the alternating grids which the CAM's use to model simple particle systems.
Typical ARCAL programs I have written to date produce about 200 bytes of output tables. The Virtual Ant CA produces by far the largest amount of output, either 1104 or 1436 bytes, depending upon whether an active cell list is being used. The size of these tables places minimal demands upon a processor's data cache. Also, the core ARCAL interpreter code is simple and small (just over 100 bytes of Pentium object code) and easily fits entirely within a processor's instruction cache.
ARCAL uses a single cell state value buffer, whereas traditional RTB CA's typically utilize at least two buffers. A single buffer is obviously the optimal number of buffers to use from a size viewpoint. ARCAL effectively uses temporary state values to replace the traditional secondary result buffer.
Many interesting CA's can be specified as ARCA's consisting of a single animation step followed by a single reduction. The same CA's can of course be implemented using traditional RTB CA methodology. What can be discovered by "rigorous" analysis of the memory utilization of such equivalent CA's? Assume each CA operates on Life's three by three neighborhood. Let the total number of cells be denoted by N and the population of active cells be denoted by P.
A traditional RTB CA will require at least three memory references per cell (into the row above, the current row, and the row below) to construct a result table index. Accessing the result table and storing the result constitute the forth and fifth memory access per cell. Thus the total number of memory operations needed to compute a generation using traditional result tables is:
Operations(RTB) = 5*N
Now consider the equivalent ARCAL CA consisting of two steps, an animation followed by a reduction. Assume no active cell list so that trailing reduction elimination may be applied, resulting in a single animation-like step. For each cell a dispatch table lookup will need to be performed to find the map used for the cell. For deactivatable cells three more memory operations are performed on its trailing neighbor (fetch neighbor's value, index into result table, store new neighbor value). For active cells the same three memory operations are applied to each neighbor, resulting in another 24 * P memory operations. The total number of memory operations needed to compute a generation using ARCAL without an active cell list is thus:
Operations(ARCAL) = N + 3*(N-P) + 24*P
or
Operations(ARCAL) = 4*N + 21*P
Combining the two equations it is shown that the ARCAL CA will be more memory operation efficient than the RTB CA if:
P < N/21
Now Life, when started with a random 10% live cell distribution, usually takes only a couple of generations to reach the point where at most 4% of the cells are live. By the time steady state occurs only about 2.8% of the cells are live. So for Life at least it may safely be stated that ARCAL is more memory operation efficient than a traditional RTB CA.
For CA's in which each cell has only four neighbors the ARCAL CA will be more memory operation efficient than the RTB CA if:
P < N/9
Parity and Time Tunnel are examples of CA's which utilize a four-cell neighborhood.
Animation-Reduction cellular automata specification provides a powerful alternative to traditional result table based specification of CA's. It provides for straightforward implementation of fast programmable CA's, including CA's which use more than two states.
; ; Copyright (c) 1995 - 1998 by George Maydwell ; May be freely reproduced and modified for noncommercial use. ; All other rights reserved. ; states dead dead live live temporary d1 d2 d3 d4 l1 l2 l3 l4 end transition count make d4 from d3 from d2 from d1 from dead make l4 from l3 from l2 from l1 from live end map count use count for NW N NE W E SW S SE end animation count use count when live l1 l2 l3 l4 end reduction decide make dead from live or l1 or l4 or d1 or d2 or d4 make live from d3 or l2 or l3 end rules Life count decide end
;
; Copyright (c) 1997, 1998 by George Maydwell.
; May be freely reproduced and modified for noncommercial use.
; All other rights reserved.
;
states
dead dead
live live long-lived
dead once-live
temporary d1 d2 d3 d4
l1 l2 l3 l4
ll1 ll2 ll3 ll4
ol1 ol2 ol3 ol4
end
transition count
make d4 d3 d2 d1 dead
make l4 l3 l2 l1 live
make ll4 ll3 ll2 ll1 long-lived
make ol4 ol3 ol2 ol1 once-live
end
map count
use count for NW N NE W E SW S SE
end
animation count
use count when live l1 l2 l3 l4 long-lived ll1 ll2 ll3 ll4
end
reduction decide
make once-live from live long-lived
make dead from d1 d2 d4
make live from d3
make once-live from l4 l1 ll4 ll1
make long-lived from l3 l2 ll3 ll2
make once-live from ol4 ol2 ol1
make live from ol3
end
rules LifeWithHistory
count decide
end
; ; Copyright (c) 1998 by George Maydwell. ; May be freely reproduced and modified for noncommercial use. ; All other rights reserved. ; states dead READY live LIVE REFRACT temporary R1 R2 R3 end transition COUNTLIVE make R3 from R3 from R2 from R1 from READY end map COUNTLIVE use COUNTLIVE for NW N NE W E SW S SE end animation COUNT use COUNTLIVE when LIVE end reduction DECIDE make READY from R1 or R3 make LIVE from R2 make REFRACT from LIVE make READY from REFRACT end rules brians COUNT DECIDE end
;
; Copyright (c) 1998 by George Maydwell
; May be freely reproduced and modified for noncommercial use.
; All other rights reserved.
;
states
dead dead
live live
temporary d1 d2 d3 d4 d5 d6 d7 d8
end
transition count
make d8 from d7 from d6 from d5 from d4
from d3 from d2 from d1 from dead
end
map count
use count for NW N NE W E SW S SE
end
animation count
use count when live
end
reduction decide
make live from live or d3 or d7 or d8
make dead from d1 or d2 or d4 or d5 or d6
end
rules Lichens count decide end
;
; Copyright (c) 1998 by George Maydwell
; May be freely reproduced and modified for noncommercial use.
; All other rights reserved.
;
states
dead dead
live live
dead dormant
temporary dormant+
temporary d1 d2 d3 d4 d5 d6 d7
temporary L1 L2 L3 L4 L5 L6 L7 L8
end
transition count-live
make d7 from d6 from d5 from d4 from d3
from d2 from d1 from dead
make dormant+ from dormant
end
map count-live
use count-live for NW N NE W E SW S SE
end
animation count-live
use count-live when live or dormant+
end
transition count-determined
make L8 from L7 from L6 from L5 from L4
from L3 from L2 from L1 from live
end
map count-determined
use count-determined for NW N NE W E SW S SE
end
animation count-determined
use count-determined when live L1 L2 L3 L4 L5 L6 L7 L8 dormant+
end
reduction decide
make dead from d1 d2 d4 d5 d6
make live from d3 d7
make live from live L1 L2 L3 L4 L5 L6 L7
make dormant from L8 dormant+
end
rules Fast-Lichens count-live count-determined decide end
; ; Copyright (c) 1998 by George Maydwell. ; May be freely reproduced and modified for noncommercial use. ; All other rights reserved. ; states dead dead live live temporary d1 d2 d3 d4 d5 d6 d7 d8 end transition count make d8 d7 d6 d5 d4 d3 d2 d1 dead end map count use count NW N NE W E SW S SE end animation count use count live end reduction decide-1 make live d1 make dead d2 d3 d4 d5 d6 d7 d8 end reduction decide-2 make live d2 make dead d1 d3 d4 d5 d6 d7 d8 end reduction decide-3 make live d3 make dead d1 d2 d4 d5 d6 d7 d8 end reduction decide-4 make live d4 make dead d1 d2 d3 d5 d6 d7 d8 end rules 1-of-8 count decide-1 end rules 2-of-8 count decide-2 end rules 3-of-8 count decide-3 end rules 4-of-8 count decide-4 end
; ; Copyright (c) 1998 by George Maydwell. ; May be freely reproduced and modified for noncommercial use. ; All other rights reserved. ; states dead dead live live temporary d1 d2 d3 d4 L1 L2 L3 L4 end transition count make d4 from d4 from d3 from d2 from d1 from dead make L4 from L4 from L3 from L2 from L1 from live end map count use count for N W E S end animation count use count when live L1 L2 L3 L4 end reduction decide make dead from L1 or L3 make dead from d2 or d4 make live from d1 or d3 make live from live or L2 or L4 end rules parity count decide end
;
; Copyright (c) 1997, 1998 by George Maydwell.
; May be freely reproduced and modified for noncommercial use.
; All other rights reserved.
;
states
dead dd
live ll ld dl
temporary dd1 dd2 dd3 dd4 ld1 ld2 ld3 ld4
dl1 dl2 dl3 dl4 ll1 ll2 ll3 ll4
end
transition count
make dd4 dd3 dd2 dd1 dd
make ld4 ld3 ld2 ld1 ld
make dl4 dl3 dl2 dl1 dl
make ll4 ll3 ll2 ll1 ll
end
map count
use count for N W E S
end
; Forward
animation forward-count
use count when ld ld1 ld2 ld3 ld4 ll ll1 ll2 ll3 ll4
end
reduction forward-decide
make ld from dd1 dd3 dl2 dl4 dl
make dd from dd2 dd4 dl1 dl3
make ll from ll1 ll3 ld2 ld4 ld
make dl from ll2 ll4 ld1 ld3 ll
end
rules Forward
forward-count forward-decide
end
; Reverse
animation reverse-count
use count when dl dl1 dl2 dl3 dl4 ll ll1 ll2 ll3 ll4
end
reduction reverse-decide
make dl from dd1 dd3 ld2 ld4 ld
make dd from dd2 dd4 ld1 ld3
make ll from ll1 ll3 dl2 dl4 dl
make ld from ll2 ll4 dl1 dl3 ll
end
rules Reverse
reverse-count reverse-decide
end
/*
* Advance - Advances an ARCAL cellular automata by one generation.
* (Cellular Automata source code for C/C++ programmers)
*
* Copyright (c) 1998 by George Maydwell.
* May be freely reproduced and modified for noncommercial use.
* All other rights reserved.
*
* Assumes that the trailing reduction elimination optimization
* has been applied, so that there are no reductions in program.
*/
void Advance(unsigned char* first, unsigned char* past, long* program)
{
for (long nSteps = *program++; nSteps > 0; nSteps--) {
long dispatch = *program++;
for (unsigned char* curr = first; curr < past; curr++) {
long cellValue = *curr; /* cellValue is a multiple of 4 */
long* inst = (long*) *((long*) (dispatch + cellValue));
do {
unsigned char* neighborAddr = curr + *inst++;
unsigned char* transition = (unsigned char*) *inst++;
*neighborAddr = transition[*neighborAddr];
}
while (inst[0]);
}
}
}
/*
This should be sufficient for just about anyone to get up and
running with a fast Life implementation. Note that each cell
will have a value of 0 if it is dead, 4 if it is live, and 40
if it is inert. Only these cell values are legal. Other cell
values can cause the ARCAL interpreter to trash random areas
of memory and/or crash. The definition of ROWBYTES will need
to be changed to match what you desire.
The CA's board storage must be bounded by buffers of inert
values on either side. The buffer with a lower address must
contain r+1 values, where r is the length of a row. The buffer
with the higher address must contain 2*(r+1) values. These
buffers of inert values prevent the trashing of non-CA board
memory by the ARCAL interpreter.
*/
enum { DEAD = 0, LIVE = 4, D1 = 8, D2 = 12, D3 = 16,
D4 = 20, L1 = 24, L2 = 28, L3 = 32, L4 = 36, INERT = 40 };
static unsigned char lookupTable[44] =
{
/* original count last-dead last-live unused */
/*----------------------------------------------*/
/* DEAD */ D1, DEAD, DEAD, 'G',
/* LIVE */ L1, DEAD, DEAD, 'e',
/* D1 */ D2, DEAD, DEAD, 'o',
/* D2 */ D3, DEAD, LIVE, 'M',
/* D3 */ D4, LIVE, DEAD, 'a',
/* D4 */ D4, DEAD, DEAD, 'y',
/* L1 */ L2, DEAD, LIVE, 'd',
/* L2 */ L3, LIVE, LIVE, 'w',
/* L3 */ L4, LIVE, DEAD, 'e',
/* L4 */ L4, DEAD, DEAD, 'l',
/* INERT */ INERT, INERT, INERT, 'l'
};
#define COUNT_LIVE ((long) (lookupTable))
#define COUNT_LAST_DEAD ((long) (lookupTable)) + 1
#define COUNT_LAST_LIVE ((long) (lookupTable)) + 2
#define ROWBYTES 512
static long deadMap[3] =
{
-ROWBYTES - 1, COUNT_LAST_DEAD,
0
};
static long liveMap[17] =
{
-ROWBYTES - 1, COUNT_LAST_LIVE,
-ROWBYTES, COUNT_LIVE,
-ROWBYTES + 1, COUNT_LIVE,
-1, COUNT_LIVE,
1, COUNT_LIVE,
ROWBYTES - 1, COUNT_LIVE,
ROWBYTES, COUNT_LIVE,
ROWBYTES + 1, COUNT_LIVE,
0
};
typedef long* mapPtr;
static mapPtr dispatch[11] =
{
deadMap, liveMap,
deadMap, deadMap, deadMap, deadMap,
liveMap, liveMap, liveMap, liveMap,
deadMap
};
static long lifeProgram[2] = { 1, (long) dispatch };
void Life(unsigned char* first, unsigned char* past)
{
Advance(first, past, lifeProgram);
}
Toffoli, Tommaso and Margolus, Norman, Cellular Automata Machines: A New Environment For Modeling, The MIT Press (1987).