ARM Club 1/ARM_CLUB_CD.iso/contents/apps/fractal/progs/fractal4/arcaut/Info_Info

Text File | 1992-01-15 | 19.5 KB | 334 lines

  Most readers of this magazine will, at one time or another, have come
across a cellular automaton. The most famous of these is John Conway`s
'Life' created way back in the early 70`s; more recently Archimedes World
carried a version of 'RugWorld', another & quite different cellular
automaton.

  To the uninitiated, a cellular automaton (CA) is a simulation. The space
in which this takes place is called the CA universe; this is frequently a
rectangular grid, like a chess board. Each position in the grid is called a
cell. An individual cell can exist in any of a number of predefined states,
the total number of which depends on the particular CA in question. For
example, in 'Life' there are only two states called dead & alive, while in
'Rugworld' there can be up to 256 distinct states.
  At any moment in time, the configuration of cells in the universe is
called a generation. Usually the screen is used to display the current
generation, with each cell being represented by a single pixel; different
colours corresponding to different states.
  The CA consists of a collection of rules which tell you & the computer how
to calculate what the next generation will look like; this depends only on
the current generation. The simulation simply involves setting up an initial
configuration of cells and then iterating or repeating the application of
these rules to create successive generations; in practice, if we can do this
fast enough, the cell states can be seen to evolve in what looks like a
continuous manner, in the same way that by moving a sprite one pixel across
the screen at a time, we can make it appear to move smoothly. This can
produce some quite stunning results.

  Normally certain restrictions are imposed on the rules we are allowed to
use to define a CA. They must be both local and translation invariant. The
former means that the new state of each cell is only allowed to depend on
the prior state of cells nearby, while the latter says that the way each
cell develops does not depend on where that cell is, so if we have the same
pattern of cells at two different locations on screen, then they will both
behave in the same manner.

  In order to permit the investigation of general automata, I have written
ArcAut. It is a cellular automaton laboratory, which allows you to experiment
with virtually any rules you can think of, quickly & easily.
  In ArcAut, each automaton is defined in a single text file: this contains
the name & if desired, a description of the automaton; the Basic routine
used to set up any parameters needed by the automaton (this may involve
getting the user to input some values); the routine needed to set up the
screen for the first generation; & finally the code which actually defines
the rules governing the automaton.
  An automaton can be treated as an ordinary text file, for viewing &
editing purposes, using for instance !Edit. To execute the automaton it is
only necessary to install !ArcAut on the icon bar by double clicking on it's
filer icon, & then to drag the textfile onto the !ArcAut icon, either from a
filer window, or from the save dialogue box in say, !Edit. You can
immediately run any of the automatons provided, in this manner.

  ArcAut currently allows two different ways of referring to neighbours,
take a look at table 3; for the moment you need only consider the Moore
neighbourhood scheme - if you are viewing these instructions as text within
the desktop environment, then I would recommend you use Mode 16 to read the
tables as they need more than 80 columns.

  To clarify the ideas so far covered, let`s consider the classic example of
Life. In this CA, we have only two states, dead & alive. The rules governing
growth are:
 If a cell is alive and has two or three living neighbours then it remains
alive, else it dies;
 If a cell is dead and has precisely three living neighbours then a new
living cell is born, else it remains dead.
  And that is all there is to it. Extremely simple, yet the resulting
behaviour can be very complex. In fact, for the benefit of any doubters
reading this, A CA universe running Life is capable of solving any
computable problem! you could 'easily' simulate the entire operations of
your Archimedes within such an environment (although you would need a pretty
big grid - possibly bigger than any which would fit into the biggest
computer currently in existence). This is only of theoretical importance,
nevertheless, the pictures which you can obtain from a simulation running on
an Archimedes do exhibit astonishing complexity.

  If you haven't ever seen 'Life' or are curious about the possibilities for
other CA, then I suggest you take a look at ArcAut now, if you haven't
already done so; if you aren't curious, then why are you reading this?
  As Life is so familiar I would advise you take a look at the text file
which implements it, to get some idea of how an automaton definition is put
together, & perhaps try running several of the automatons.
  The rules are specified in a reasonably easily readable format which I
will explain later, so you don't need to know any assembly programming. When
an automaton is executed, ArcAut compiles the rules into assembly. This
ensures that the CA will work at a good speed; often this is comparable with
a purpose written assembly equivalent. ArcAut then takes over the full
screen; this may not keep to the spirit of Risc OS, but is quite adequate
when you want to use the full power of your Arc to work with automata;
terminating the run of a particular automaton will take you back to the
desktop at the point that you left it. This allows you to try out automatons
while you are in the process of editing them.

  When an automaton is run, you are prompted for a series of values
including the size of the window within which the CA will run; default
values are indicated within { } brackets, & can be selected by pressing just
return. The smaller the window, the faster the CA will progress; although
you sometimes need windows of a certain minimum size in order to observe all
the properties of that automaton. Pressing Menu while the automaton is
running will give you a list of options. This will give you the chance to
freeze the action. The current automaton can be restarted (Again), or the
present generation can be saved as a screen (Save) or replaced with one on
disc (Load); (Next) lets you advance a single generation, while (Cont.)
allows you to resume the run where you left off. (Phase) is described in
table 3. Finally, (Quit) returns control, as previously described, to the
desktop.

  To give you some idea of what to expect & what is going on, I have
included a brief description of each automaton provided here (there are
about 24!), within the automaton files. You might care to do this yourself,
with any automatons you devise, if you intend passing them on to anyone
else.

  If you have already examined any of the automatons then you will have some
idea of the format in which they are stored.
  Each automaton has the following syntax:

 AUTOMATON*
 <name>
 INITIALISATION*
 <basic1>
 SCREEN*
 <basic2>
 CODE*
 <code>
 END*

  <name> must contain no spaces, if it is made from several words these
should be separated by '_' characters; each word should contain no more than
7 characters. Any text following <name> is ignored so you may include a
description of the automaton here.

  <basic1> & <basic2> both have the same format. They are both Basic
routines, stored in text form. Line numbers must be used, & should start
with a number no smaller than 10. The main routine to be executed in each
case should be enclosed within the definition of a procedure called 'do'.
  The first is executed at the start of an automaton run, & should set up
any parameters & input any data required from the user. Data can be passed
to the other routine & automaton code, using system variables. Certain
system variables used by ArcAut, need to be set up - see table 4 & take a
look at some examples.
  The purpose of the second is to set up the screen for the first
generation. A graphics window has already been created limiting commands to
the region of the CA universe. A number of useful library routines are
provided & can be used in both sections of Basic code, though they are
probably of most use when setting up the screen (there is no need to load
the library - it will be present); see table 5. Notice that the numerical
values of cell states are in fact the colour values as stored in screen
memory, & not the GCOL values. Thus if you wish to draw a circle on screen
corresponding to cells of state 45, you need to first convert this to a GCOL
number & then select this colour. A function to do this is provided; it is
described in table 5.

  The last section, <code>, defines the rules governing the automaton. These
are enclosed within a pair of ( ) brackets. You are free to add as many
spaces & carriage returns between instructions to aid legibility; surplus
separators will be ignored by ArcAut.
  The code consists of a series of commands & a few elementary arithmetic &
logic operators, together with a single simple means of conditional
execution of parts of the code.
  Before describing this you need to understand the principal underlying the
passing of data to operators. The system known as Reverse Polish Notation is
used; this may sound complex & at first seem unnatural but it is quite easy
to get used to. It is the system that most calculators use. Consider the
following simple example.
 To add two numbers together in Basic you would use something like: 2+3
 In RPN this becomes: 2 3 +
 If you want to do 2*(3+5) in Basic you need the brackets to select the
correct order of precedence for the calculations.
 In RPN all you need to do is: 3 5 + 2 *
             or alternatively: 2 3 5 + *
 It is much easier to understand how this works if you know how the computer
goes about evaluating an expression. RPN relies on a stack. A stack is
simply a long list or pile of items. This could be a stack of plates or
books. The main feature of a stack is that you can only access the item at
the top. Similarly items can only be put onto the top of the stack; you
can't insert an item part way down. In this context we are dealing with a
stack of numbers.
  Let us consider the expression '2 3 5 + *' again.
  When the computer comes across the number 2 it places this onto the top of
the stack (which begins empty); the same thing happens as it gets to the
numbers 3 & 5. So by the time we reach the + sign the stack has three items
on it. 5 at the top, then 3, & 2 at the bottom. Now + has the effect of
making the computer take the top two items off the stack, add them & then
place the result on top of the stack. Hence after the + has been executed we
have two items on the stack: 8 at the top & 2 beneath. * works in a similar
way, so at the end we have a single number stored on the stack, 16, the
correct answer.
  This may seem like a very drawn out & unnecessary explanation. If you
already know about RPN then all well & good. It is however worthwhile to
give an elementary explanation as it is impossible to write the code for
CA's if you don't understand these principles. All calculations are done
with RPN. Parameters are passed & returned from commands in the same way.
  In ArcAut you are subject to the rather unusual restriction of only being
allowed upto 3 items on the stack at any one time. This is because the stack
is not stored in memory, but directly in three registers; as such the stack
doesn't actually exist. The reason for this is simple: speed; using a real
stack would slow down the program by a large factor. Also of course, this
has only been done because being restricted to three items is still
practical; you can still write the code for most automatons that you care to
think of, as the examples have already demonstrated. If this is beginning to
confuse you (it confuses me), don't think about it. You will be okay, as
long as you behave as if you were using a stack, but one which can only hold
at most three numbers.
  As the rules for a CA don't depend on where the cell is, & do depend on no
more than the current cell state & those of it's immediate neighbours, all
we need to do is describe a procedure which calculates a cell state in terms
of up to these 9 parameters. To do this you need to be able to refer to
these values.
  The current cell state is referred to by the name CELL.
  All commands & values should be separated by spaces or carriage returns.
  Before you can access the values of the neighbouring cells, or you use any
command which uses these values, you must issue the command READ_NEIG.
  The positions & names of the neighbouring cells depends on which of the
two neighbourhoods has been selected in the initialisation procedure. Table
3 describes both possibilities.
  You can't assign values to these names (other than by READ_NEIG), they may
only be read for the purpose of calculations.
  A list of operators is given in table 1 together with their meaning & the
number of stack items they require & return.
  A similar list of commands with their purpose is given in table 2.
  All arithmetic is limited to dealing with integers. There are however
further restrictions on the numbers you are allowed to specify in
instructions. Numbers greater than 256 must be a multiple of 4, those
greater than 1024 must be a multiple of 16 & so on. So if you want to add
257 to the top stack item you would need to do '256 + 1 +'. If you only need
a number of roughly a certain size then FNround(x) can be used to round down
the number x, to one which meets these restrictions. To make the code easier
to read you can embed conventional basic expressions which evaluate to give
a numerical result, in the code using [ ] brackets. System variables can be
accessed simply by enclosing them within < > signs; for example if you
wanted to multiply the top stack item by the value of x^2 where x is a
system variable you could use '[<x>^2] *'. Numbers may also be specified
using system  variables without the [ ]; so to subtract x from the top item
'<x> -' is all that is necessary. The same restrictions on the values of
variables & [ ] expressions exist as for numbers directly specified. This
isn't usually a problem as you are normally working with values that lie in
the range -255 to 255
  When your calculation has finally come up with the value that is to be
used for the new cell state the command == terminates the code. This has the
effect of returning the top stack item as the new cell state. Hence once
this is encountered, subsequent instructions in your code have no effect.
  The last thing you need to know about is the IF statement.
  This is the only control structure provided & is the only means of making
parts of your code conditional. It takes one of two forms.
 'IF (code A)'  and 'IF (code A) ELSE (code B)'
  The condition is provided in the state of the top stack item. 'IF' removes
the top stack item, & proceeds to execute 'code A' if this value is non zero
or 'code B' if present & the value is zero. 'code A' & 'code B' may be any
collection of automaton code including further, nested IF clauses. Usually
the code in an IF clause will eventually terminate with ==, but occasionally
you may want the instructions to alter the state of the stack & then resume
execution after the conditional section. In this case there is a further
restriction. You must ensure that the number of items on the stack after the
conditional code has executed & returned control to the following code, is
the same as if it had not been executed.

  If all this is becoming confusing don't worry. In practice the rules for
CA's can be expressed very simply & you won't have the chance to get bogged
down as a result of any of these restrictions & complications, & in a moment
I'll go step by step through an example. If you can follow that, you'll be
able to implement code for your own automatons.

  If you make any mistakes then something unpleasant may go wrong. Errors
due to commands/operators not finding enough data on the stack, or running
out of room on the stack for an answer, should be correctly reported. Any
other errors, however, are likely to create an error somewhere else in the
program, & this won't give you much idea what is wrong with your code.
ArcAut has been well tested (over several months) so you can be reasonably
sure that if any strange errors appear they are due to your automaton code,
especially if that is the first time you've attempted to try it out.

  Now for the example I promised. We shall go back to 'Life' for this.
  Here is a description of the rules again, followed by some suitable code:

 If a cell is alive and has two or three living neighbours then it remains
alive, else it dies; If a cell is dead and has precisely three living
neighbours then a new living cell is born, else it remains dead.

 alive always has the value 255 (white)
 dead always has the value 0 (black)

 READ_NEIG             get the state of the neighbouring cells
 alive SCOUNT_NEIG     count how many are alive & leave on stack
 CELL IF (DUP          If cell<>0 (cell is alive) then DUP # of living neig.
 2 = IF (alive ==)                if also # living=2 then leave cell alive
 3 = IF (alive ==)             or if also # living=3 then leave cell alive
 dead ==)                    else doesn't have 2 or 3 live neig. so kill it
 ELSE (                else cell=0 (cell is dead)
 3 = IF (alive ==)                if also # living=3 then new live cell born
 ELSE (dead ==)              else doesn't have 3 live neig. so remains dead
 )

  Now consider what the stack contents look like as this is executed.
 alive SCOUNT_NEIG leaves the number of living neigbours on the top of the
stack. CELL IF puts one value on the stack & then takes it off, so the top
stack item is still the number of living neighbours, regardless of whether
the cell is alive or not.
  If the cell is alive then the number of living neigbours is duplicated;
this is so we can make a comparison with both the values 2 and 3. If the
number of living neighbours is 2 we return with the new cell state of a
living cell; if not then the first of our two copies has been removed & we
are left with one. If this value is 3 then the new cell is alive, otherwise
we know cell is alive & doesn't have 2 or 3 living neighbours so we kill it.
  On the other hand, if the original cell was dead we need only compare the
number of living neighbours (which is still on the top of the stack,
remember) with 3. If it is equal to 3 then the new cell is brought to life,
otherwise it remains dead, & we have accounted for all the possible cases,
so are finished.

  Think about that for a moment if it isn't clear. Believe me, if you have
understood that then you will have no problems writing your own code. When
thinking about the state of the stack take another look at tables 1 & 2 to
remind yourself about how many operands each of the operators/procedures use
& leave.

  It might be a good idea now to see if you can figure out what the code
defining the other automatons does. The descriptions of several of the
automatons incorporate a wordy explanation of the action of the rules; see
if you can work out how the code executes the algorithm as described in
English.

  Hopefully, if you've got this far, you'll soon be writing your own
automatons. ArcAut gives you the flexibility to try out various ideas
quickly, but you'll need some inspiration or imagination to devise something
original. I'm sure that if you do come up with anything exciting, Archimedes
World would be interested to see it & perhaps pass it on to the rest of us.
Also should you find any bugs (I'm sure there aren't any?), then please let
me know.

  Good Bye & Good Luck.

Bibliography:    Cellular Automata Machines
              by Tommaso Toffoli & Norman Margolus.