home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 1: Amiga / FrozenFish-Apr94.iso / bbs / alib / d5xx / d502 / cells.lha / CELLS / CELLSSource.lzh / cCells.c < prev    next >
C/C++ Source or Header  |  1991-04-20  |  9KB  |  361 lines
  1. /*
  2.  *  CELLS       An Implementation of the WireWorld cellular automata
  3.  *              as described in Scientific American, Jan 1990.
  4.  *
  5.  *              Copyright 1990 by Davide P. Cervone.
  6.  *  You may use this code, provided this copyright notice is kept intact.
  7.  *  See the CELLS.HELP file for complete information on distribution conditions.
  8.  */
  9.  
  10. /*
  11.  *  File:   cCells.c        Handles cellular finite-state machine.
  12.  *                          To change the propagation rules, change this file.
  13.  */
  14.  
  15.  
  16. #include "Cells.h"
  17. #include "cMemory.h"
  18.  
  19.  
  20. static int ErrorReported;                   /* only give error once */
  21. int GenerationDelay = 6;                    /* Delay() time between updates */
  22.  
  23.  
  24. /*
  25.  *  The electron head and tail cells are stored in a linked list so that
  26.  *  the entire array need not be scanned during each generation.  This 
  27.  *  structure holds the position of the cell, and a pointer to the next cell.
  28.  */
  29.  
  30. struct Electron
  31. {
  32.    struct Electron *Next;
  33.    short x,y;
  34. };
  35.  
  36. static struct Electron *FreeList;   /* the list of free Electron structures */
  37. static struct Electron *HeadList;   /* the list of Electron Head cells */
  38. static struct Electron *TailList;   /* the List of Electron Tail cells */
  39. static struct Electron *NewHead;    /* the new list of electron head cells */
  40.  
  41. /*
  42.  *  Offsets used to find the adjacent cells to a given electron head
  43.  */
  44.  
  45. short OffX[] = {-1,  0,  1,  1,  1,  0, -1, -1};
  46. short OffY[] = {-1, -1, -1,  0,  1,  1,  1,  0};
  47.  
  48.  
  49. /*
  50.  *  NewElectron()
  51.  *
  52.  *  Get a new Electron structure.  First check to see if one is available 
  53.  *  in the free list (the free electron list is used to prevent unnecessary
  54.  *  memory-management overhead), and if none is available, allocate a new
  55.  *  structure.  If we couldn't get a new electron (an no error was already
  56.  *  reported) put up a message about low memory, otherwise set the electron
  57.  *  X and Y values, and add it to the specified electron list.
  58.  */
  59.  
  60. static void NewElectron(X,Y,theList)
  61. short X,Y;
  62. struct Electron **theList;
  63. {
  64.    struct Electron *theElectron;
  65.  
  66.    if (FreeList)
  67.    {
  68.       theElectron = FreeList;
  69.       FreeList = FreeList->Next;
  70.    } else {
  71.       NEWSTRUCT(Electron,theElectron);
  72.    }
  73.  
  74.    if (theElectron)
  75.    {
  76.       theElectron->x = X;
  77.       theElectron->y = Y;
  78.       theElectron->Next = *theList;
  79.       *theList = theElectron;
  80.    } else  if (ErrorReported == FALSE) {
  81.       DoError("Can't get Memory for Electron");
  82.       ErrorReported = TRUE;
  83.    }
  84. }
  85.  
  86.  
  87. /*
  88.  *  FreeEntireList()
  89.  *
  90.  *  Frees every electron in an electron list, and sets the list
  91.  *  pointer to NULL.
  92.  */
  93.  
  94. static void FreeEntireList(theList)
  95. struct Electron **theList;
  96. {
  97.    struct Electron *theElectron;
  98.    
  99.    while (*theList)
  100.    {
  101.       theElectron = *theList;
  102.       *theList = (*theList)->Next;
  103.       FREESTRUCT(Electron,theElectron);
  104.    }
  105. }
  106.  
  107.  
  108. /*
  109.  *  ClearLists()
  110.  *
  111.  *  Clears the Electron Head, Electron Tail and New Electron Head lists.
  112.  *  If the ClearFreeList flag is set, then also clear all free electrons
  113.  *  as well (e.g., as part of the clean-up operations when the program
  114.  *  exits).  Clear the cirucit boundary values to their minimum (no circuit)
  115.  *  in preparation for searching a grid for non-blank cells.
  116.  */
  117.  
  118. void ClearLists(ClearFreeList)
  119. int ClearFreeList;
  120. {
  121.    if (FreeList && ClearFreeList) FreeEntireList(&FreeList);
  122.    if (HeadList) FreeEntireList(&HeadList);
  123.    if (TailList) FreeEntireList(&TailList);
  124.    if (NewHead)  FreeEntireList(&NewHead);
  125. }
  126.  
  127.  
  128. /*
  129.  *  SetupLists()
  130.  *
  131.  *  Clear any old lists, then look through the specified grid for
  132.  *  non-blank cells.  Add them into the boundary values, and add HEAD and
  133.  *  TAIL cells into their proper lists.
  134.  */
  135.  
  136. void SetupLists(Grid)
  137. UBYTE Grid[];
  138. {
  139.    short X,Y;
  140.    short i = 0;
  141.    
  142.    ClearLists(FALSE);
  143.    for (Y=0,i=0; Y<MAXGRIDH; Y++)
  144.    {
  145.       for (X=0; X<MAXGRIDW; X++,i++)
  146.       {
  147.          switch(Grid[i])
  148.          {
  149.             case TAIL:
  150.                NewElectron(X,Y,&TailList);
  151.                break;
  152.  
  153.             case HEAD:
  154.                NewElectron(X,Y,&HeadList);
  155.                break;
  156.          }
  157.       }
  158.    }
  159. }
  160.  
  161.  
  162. /*
  163.  *  CheckWire()
  164.  *
  165.  *  Attempt to propagate an Electron Head cell to an adjacent wire cell.
  166.  *  First check to see that the cell had not already been turned into
  167.  *  an electron head (the NewGen cell must still be a wire).  If not, then
  168.  *  look at the cells adjacent to the wire cell and count how many Electron
  169.  *  Head cells there are.  If there are more than two, stop counting and
  170.  *  set the count to 0.  If there were 1 or 2 adjacent Electron Head cells, 
  171.  *  the set the cell to an Electron Head in the new generation grid, and
  172.  *  add the cell to the new Electron Head list.
  173.  */
  174.  
  175. static void CheckWire(X,Y)
  176. short X,Y;
  177. {
  178.    short i;
  179.    short count = 0;
  180.  
  181.    if (CellColor(NewGen,X,Y) == WIRE)
  182.    {
  183.       for (i=0; i<8; i++)
  184.       {
  185.          if (CellColor(CurGen,X+OffX[i],Y+OffY[i]) == HEAD)
  186.             if (++count > 2) {i = 8; count = 0;}
  187.       }
  188.       if (count)
  189.       {
  190.          SetCell(NewGen,X,Y,HEAD);
  191.          NewElectron(X,Y,&NewHead);
  192.       }
  193.    }
  194. }
  195.  
  196.  
  197. /*
  198.  *  PropagateHead()
  199.  *
  200.  *  Check the cells adjacent to the Electron Head.  If any are wire cells,
  201.  *  then check attempt to propagate the electron into those cells.
  202.  */
  203.  
  204. static void PropagateHead(X,Y)
  205. short X,Y;
  206. {
  207.    short i;
  208.    short x,y;
  209.    
  210.    for (i=0; i<8; i++)
  211.    {
  212.       x = X + OffX[i];
  213.       y = Y + OffY[i];
  214.       if (CellColor(CurGen,x,y) == WIRE) CheckWire(x,y);
  215.    }
  216. }
  217.  
  218.  
  219. /*
  220.  *  UpdateGrid()
  221.  *
  222.  *  For every cell in the Tail list, set the new generation cell to WIRE
  223.  *  For every cell in the Head list, set the new generation cell to TAIL
  224.  *  and attempt to propagate the Electron Head to adjacent Wire cells.
  225.  */
  226.  
  227. static void UpdateGrid(OldGrid,NewGrid)
  228. UBYTE OldGrid[],NewGrid[];
  229. {
  230.    struct Electron *theElectron;
  231.    
  232.    for (theElectron=TailList; theElectron; theElectron=theElectron->Next)
  233.       SetCell(NewGrid,theElectron->x,theElectron->y,WIRE);
  234.  
  235.    for (theElectron=HeadList; theElectron; theElectron=theElectron->Next)
  236.    {
  237.       SetCell(NewGrid,theElectron->x,theElectron->y,TAIL);  
  238.       PropagateHead(theElectron->x,theElectron->y);
  239.    }
  240. }
  241.  
  242.  
  243. /*
  244.  *  UpdateElectrons()
  245.  *
  246.  *  For each cell in the list,
  247.  *    get the cell's array posoition (guaranteed to be in range?)
  248.  *    set the screen cell to the specified color
  249.  *    update the current cell state
  250.  *  return the last electron in the list
  251.  */
  252.  
  253. static struct Electron *UpdateElectrons(theElectron)
  254. struct Electron *theElectron;
  255. {
  256.    register short i;
  257.    register struct Electron *LastElectron = NULL;
  258.  
  259.    while (theElectron)
  260.    {
  261.       i = theElectron->x + theElectron->y * MAXGRIDW;
  262.       ColorScreenCell(theElectron->x-GridX,theElectron->y-GridY,NewGen[i]);
  263.       CurGen[i] = NewGen[i];
  264.       LastElectron = theElectron;
  265.       theElectron = theElectron->Next;
  266.    }
  267.    return(LastElectron);
  268. }
  269.  
  270.  
  271. /*
  272.  *  UpdateBoard()
  273.  *
  274.  *  Update the cells in the Tail List, the Head List and the New Head List
  275.  *  (these are exactly the cells that have changed since the last generation).
  276.  *  Add the Electron Tail list to the Free List.
  277.  *  Turn the Electron Head list into the Electron Tail list, and the
  278.  *  New Electron Head list into the current Electron Head list.
  279.  *  Update the screen to show the new changes.
  280.  */
  281.  
  282. static void UpdateBoard()
  283. {
  284.    struct Electron *LastElectron = NULL;
  285.    
  286.    LastElectron = UpdateElectrons(TailList);
  287.    UpdateElectrons(HeadList);
  288.    UpdateElectrons(NewHead);
  289.    if (LastElectron)
  290.    {
  291.       LastElectron->Next = FreeList;
  292.       FreeList = TailList;
  293.    }
  294.    TailList = HeadList;
  295.    HeadList = NewHead;
  296.    NewHead = NULL;
  297.    UpdateScreen();
  298. }
  299.  
  300.  
  301. /*
  302.  *  RunCells()
  303.  *
  304.  *  Clear the error flag so that the first memory error will be displayed.
  305.  *  Copy the current state of the grid to the new generation grid (only the
  306.  *  electron cells will be changed).  Idea:  Hold onto the NewHead, HeadList,
  307.  *  and TailList lists and use them to update the screen instead; this
  308.  *  should speed things up even more, and would mean we don't need to worry
  309.  *  about the boundary stuff.
  310.  *  Setup the electron lists and get the boundary or the circuit.
  311.  *
  312.  *  While we are still running,
  313.  *    propagate the electrons
  314.  *    update the screen
  315.  *    delay if necessary
  316.  *    check to see if any button have been pressed
  317.  *    if there are no tails left (i.e., there were no heads during the
  318.  *      last generation) then stop running
  319.  *  Clear all lists (including the free list)
  320.  */
  321.  
  322. short RunCells(NotDone)
  323. short NotDone;
  324. {
  325.    ErrorReported = FALSE;
  326.    CopyGrid(CurGen,NewGen);
  327.    SetupLists(CurGen);
  328.    while (NotDone && Running)
  329.    {
  330.       UpdateGrid(CurGen,NewGen);
  331.       UpdateBoard(CurGen,NewGen);
  332.       if (GenerationDelay > 0) Delay(GenerationDelay);
  333.       NotDone = CheckForAction(NotDone);
  334.       if (TailList == NULL) SetStopped();
  335.    }
  336.    ClearLists(TRUE);
  337.    return(NotDone);
  338. }
  339.  
  340.  
  341. /*
  342.  *  StepCells()
  343.  *
  344.  *  Clear the error flag so that the first memory error will be reported.
  345.  *  Setup the new generation (only electron cells are modified)
  346.  *  Setup the electron lists
  347.  *  Propagate the electrons
  348.  *  Update the screen
  349.  *  Clear all the electron lists
  350.  */
  351.  
  352. void StepCells()
  353. {
  354.    ErrorReported = FALSE;
  355.    CopyGrid(CurGen,NewGen);
  356.    SetupLists(CurGen);
  357.    UpdateGrid(CurGen,NewGen);
  358.    UpdateBoard(CurGen,NewGen);
  359.    ClearLists(TRUE);
  360. }
  361.