home *** CD-ROM | disk | FTP | other *** search
/ APDL Public Domain 1 / APDL_PD1A.iso / fractal / arcaut / Info / Table3 < prev    next >
Encoding:
Text File  |  1991-07-31  |  6.2 KB  |  87 lines
  1.  
  2.   TABLE 3: The Neighbourhoods
  3.  
  4.  
  5.   ArcAut currently permits the use of two distinct neighbourhood schemes, called Moore & Margolus.
  6.   To select a particular neighbourhood for an automaton, set the system variable
  7.   called 'neig' to either 'moore' or 'margolus' within the initialisation (see table 4).
  8.   Before any neighbour can be referred to within the rules defining an automaton, the command READ_NEIG must be included.
  9.   All automatons that I have come across in magazines use the Moore neighbourhood, so i'll describe it first.
  10.  
  11.   The Moore neighbourhood:  each cell is surrounded by eight diagonally or orthogonally adjacent neighbours.
  12.                             Within automaton code these are given the following names;
  13.  
  14.                               TL   TM   TR
  15.                               ML  CELL  MR
  16.                               BL   BM   BR
  17.  
  18.                             T meaning top, M middle, B bottom, L left & R right, with respect to the central cell
  19.                             under consideration (which is called CELL).
  20.                             Many of the more colourful automatons use the Moore neighbourhood.
  21.  
  22.   The Margolus neighbourhood is rather more complex to describe; it is well suited to the programming of particle based
  23. automatons such as DLA, Brownian Motion & Sound, to name a few. It was originally devised by Norman Margolus to investigate the
  24. possibility of a reversible 'ballistic computer' automaton.
  25.  
  26.   The Margolus neighbourhood:  we ensure both the width & height of the CA universe are even. A partition is then imposed,
  27.                                dividing the universe up by a grid into blocks, each made up from 4 cells in a 2x2 arrangement
  28.                                for example in an 4x4 universe;
  29.  
  30.                                  ab  cd      We say that a grid aligned with the universe in this way has
  31.                                  ef  gh      even phase
  32.  
  33.                                  ij  kl
  34.                                  mn  op
  35.  
  36.                                Each cell has 3 other neighbours, these being the other three cells within the same block.
  37.                                All 4 cell within a particular block can be referred to by the names;
  38.  
  39.                                  UL UR
  40.                                  LL LR
  41.  
  42.                                UL meaning upper left, UR upper right, LL lower left & LR lower right
  43.                                More usefully we can refer to all four cells via their location relative to the cell under
  44.                                consideration, with the names CELL, CW, CCW & OPP
  45.                                CW meaning clockwise, CCW counter clockwise & OPP opposite
  46.                                The four possible actual orientations are;
  47.  
  48.                                  CELL   CW           CCW  CELL           OPP   CCW            CW  OPP
  49.                                   CCW  OPP           OPP    CW            CW  CELL          CELL  CCW
  50.  
  51.                                If we were to leave the partition positioned as above, then the cells in different blocks could
  52.                                never communicate & we couldn't do anything interesting. Instead, we allow the phase of the grid
  53.                                to alternate between even & odd, as the generations progress. An even partition is shown above.
  54.                                The odd partition is obtained by shifting the even grid by one cell diagonally.
  55.                                For the 4x4 universe this would give us;
  56.  
  57.                                  a  bc  d
  58.                                  
  59.                                  e  fg  h
  60.                                  i  jk  l
  61.  
  62.                                  m  no  p
  63.  
  64.                                where, using wrap around, the cells form blocks as follows;  pm  no  he  fg
  65.                                                                                             da  bc  li  jk
  66.  
  67.                                It is often useful within the automaton code to know what the phase is, or which position within
  68.                                the block CELL has. This information can be passed with the register that is referred to by
  69.                                the name FLAG. Either the phase, the orientation, both or neither are held in FLAG depending
  70.                                on the setting of the system variable flag; see table 4
  71.                                The Margolus scheme is quite different from the Moore, & at first may seem unnecessarily
  72.                                complicated & of no obvious use. To dispell this idea consider the following trivial example.
  73.                                We define a simple automaton which starts from a single white point on a black background, & then
  74.                                applies the rule (OPP ==). Imagine this yourself, acting on a small universe. It soon becomes
  75.                                clear that this results in the white point appearing to move along a diagonal - the direction it
  76.                                goes in depends on it's position within the 2x2 block containing it. Just try and design an
  77.                                automaton using the Moore neighbourhood which does this; even if you can work out how, it will
  78.                                be very cumbersome & difficult to follow (although I ought to point out that anything you can do
  79.                                with the Margolus neighbourhood can also be done with the Moore). Take a look at any of the
  80.                                automatons provided which use the margolus neighbourhood; see if you can work out what they do
  81.                                before you run them.
  82.                                While an automaton is running, you can force it to use the same phase on two succesive generations
  83.                                rather than automatically alternating, by clicking menu & then selecting the Phase option from the
  84.                                menu; either resume with Cont. or watch the action a frame at a time by clicking on Next. In some
  85.                                cases this can have a dramatic effect, even causing the automaton to run backwards! (As would be
  86.                                the case with the trivial example given above).
  87.