Resnick's Termite

   WORK IN PROGRESS

   { Found this in the book The Computational Beauty of Nature. --drummyfish
   }

   Resnick's termite is a simple [1]cellular automaton simulating behavior of
   ants, demonstrating how even a very dumb behavior of a single agent can
   lead to higher collective intelligence once we increase the number of the
   agents. The simulation was made by Mitchel Resnick, the theme is similar
   to that of [2]Langton's ant but Resnick's termites are [3]stochastic,
   [4]nondeterministic, they rather show how statistics/[5]randomness in
   behavior help many ants build tunnels in sand. The game demonstrates how
   randomly scattered chips start getting chunked together and form tunnels
   once we let ants with extremely simple behavior work together on moving
   the chips. Besides this demonstration however there doesn't seem to be
   anything more interesting going on (at least until we start to modify and
   tweak the thing somehow).

   The system is defined quite simply: we have a world made of cells, each
   cell can be either empty or have a wooden chip on it. In this world we
   have a number of ants, each of which behaves by the following
   [6]algorithm:

    1. Randomly walk around until you bump into a chip.
    2. If you are not carrying a chip, pick up the one you bumped into,
       otherwise drop the chip you are carrying. Go to step 1.

   The original implementation had ants who had direction (up, right, down,
   left) and on each step could make a random turn to the right or left. If
   an ant bumped into a chip it turned 180 degrees. These things prevented
   some annoying patterns like an ant just picking up a chip and immediately
   dropping it etc. Some further modifications were suggested like giving the
   ants some simple sense of sight or teleporting them randomly after
   dropping the chip.

 iteration 0:
  ----------------------------------------------------------------
 |   ,  ,     '   '    , '    , ; ;    ' ',,''    ',  '     '     |
 |  '  ,     ,    ' ' '  ',,   ;'      ,,,  ,,,    ;       '  ;,  |
 |,     ,   ',  ; '  ' ',   '  ,   ' ','   '          ,, ''  ,  ',|
 |    ' ,;''   ,  ,',    ,     ,  ' ,  '','    '',; '   , ,, ',   |
 |  , ',,  ,,', ,  , ;     ;', ,';'    ,',    '   ,  '   ;;   ',  |
 | ',   ' ' ;  ,,       ,     ,  , '       ,  , '    , ,   ,  '   |
 | ,  ,',    ,'      ' ''   ' ,' '  ; , ' ' ; , , '   ,,   ,   , '|
 |    ,  '' ''    ' ,   ;        ;   ,;' '' ; ;            '     '|
 | ,  ,,      ;''  ', ;       '  '   ' ,' ,,,, , , ',    ,',,';   |
 | '    '',,'    , '    '   ,  '',,  ,,  ,','  '  ; '    '  ,;    |
 |',,   '   , ,   ,    ' , , ' ;,,  '  '  ,, ,';,  , ;     ;, '  ;|
 |,   '   '  ' ' ;, ,,,; ',   ;   '   ,  '  ';  ,  '  ; , ';,   , |
 |  ' ,' ', ' , , '  ', ''    ' ,  ;     ;    ,, ,,, ;, ','  ', ' |
 |',,   '     ,  '''     '   ,, ','   ' ' ''  ,,   ,  ',  '   ',''|
 |     , ,    ,   ,,';,;,, ,    , ' ,'    ',  '   ;     '         |
 | ,  '  ,'  , ;       '  , , ,   , ' , ';  ,,    ,  ','',        |
 |         ,',   ,' ' ,,    '''  ,       '  ' ', ',     ,,,     ',|
 |      ,',, ,, '; ,' '  '  ',       '   ,  ' ,        '  ,;  ; ' |
 |''  ','  ' ,    ' ,, , '    , ;  '   ,''       ,  ,'  ;     ,', |
 |   ,     ' ; , '    ''';   ,      '','  , '   ,    '' '     ',  |
 |    '   ,   '    ' '    ,  ,    ' ,'      ''   ,',  ,  ;,',,', '|
 |   '   ', '''';   '''     , '  ,',    ,'' ;'   ,   , '    , ,  ;|
 |,,  , ', '  ,   ;''   '     '      ,',    '    ,  ,'  ,,  '  ,  |
 |  ',', '       , ','    ,;,   ,; ',,, '             ',    ' ;   |
 |' ,  '  ,    ' ,  '     '      ,  ;   ' '  , ;  ,;   '' '  ,''  |
 |   ;  ,  ,;,;   '     , ' ''    ,     ,   ,    ,   ,,,'  ' ,,' ,|
 | '     ,'  ''      ',,       '  ',      '   ; ;       , ,, ' ,  |
 |    ,  ; , ,;'  , '  , '' '   '',   ,    ;   , ,       ,'''  ' '|
 |, ;,     ,         ' ,, ; ',,;,;';        ; ; , ''   ,       ', |
 |,' ';  ,  ,       ,,  '   ,' ''     ' ,' ,  '' ' ,,   , ', ,    |
 |; '  '''    '   ,  ,  ,     '           '     , ,,         ,'   |
 |;  , '           '  '   '    ', ''',,    ',       , '  ,      ,'|
  ----------------------------------------------------------------

 iteration 5963776:
  ----------------------------------------------------------------
 |   , ;;';   '    ;';   ';,,   ,       '   , ,         ;'   ,''; |
 |    ';, ;  ,,,  , ,,  ;,,'',          ,,,              ,;   ;   |
 |    ,          ' ,'       ,,       '';'   '      ' ,     ' ' '';|
 |, ,,          ,   ,,              ''; ,         ;        ,';;,; |
 |'  ,            ,,,''             '' '  ' ' '  ''       ;'  ,'''|
 |, '';             ,,             ,'; , ;, ,,    ; ;     ,, ;    |
 |  ' ,      '' ' ';,               '  ',;    ;   '';,   ,'       |
 | '',  '   ',     ,               ; '',  ''  '     , '',,,  '  ,'|
 |, ;       ,        ;'                 ' ;    ,       ; ;;  ,,  ;|
 |, ;        ';     ,            '     ,;' ;;'         ,'';       |
 |                   '           ,      ';  ;,            ' '''   |
 |;            ',' ,';,;' '             ,,      ,  ' ;   ',       |
 |;,   ,,    '      ',;, ,                         ;,,'           |
 |         ,';'   ;';  '                 ,,,         ';          '|
 |,, ,  '   ,  '  ;'''',    '                         ;  , '      |
 |'  ;,,;' '' ';,, '       ,, ;       ';'    '''      ,,   ,,,   ,|
 |,,    ;,     , ';;     , ;   ;,    ',  ,, ;'    ,,            ;;|
 |         ;, ,;,;',  '  ;;,  ''    ', ;                          |
 |  ; ,  ' ,'' ,,'    ,,      ;'  ;;,;;    ' ',,;''          ,    |
 |  ,;   ,  ,       ''           '  ,;,    ,,   '''        ' ;'   |
 | ; ,;,         , ''  '        ;; ;; ; '  ' ,,'    ''    ,,; ,' ,|
 | ,              ''   ';;     '''  ,,;' '''     ' ' ;     ;;'    |
 | ,; '     ;;;  ,,             ,,'';    ; ;',    ;,,;          , |
 |'  ,;      ,' '                          ,           ;     ' ' ,|
 |'' ,;,, '';                                       ' ''   '' ,,  |
 |''    ;,            ,,, ;'          '';,,        ;'  ,        , |
 | ,, '    ';;'                       ,'                      ';, |
 |  ,    ,  ,           ',,;             ;'                  ';   |
 | ,,  ;; ,              ,               '                    ;,  |
 |     ,  ',     ''                , ;     ,   ;,             ;,  |
 |     '',,''   '' ,'       '                     ;,    ''        |
 |   ,,'' ,,  '      ;  ''  '   ;  ';'      ' '     '   ,,  , ; ' |
  ----------------------------------------------------------------

   Here is an extremely basic implementation in [7]C (without the fancy
   behavior improvements mentioned above, to keep the code short):

 #include <stdlib.h>
 #include <stdio.h>

 #define WORLD_SIZE 64
 #define ANTS 200
 #define CHIP_DENSITY 5

 unsigned char world[WORLD_SIZE * WORLD_SIZE]; // 0: empty, 1: chip

 typedef struct
 {
   int pos;
   unsigned char chip;
 } Ant;

 Ant ants[ANTS];

 void printHBorder(void)
 {
   for (int i = 0; i < WORLD_SIZE + 2; ++i)
     putchar((i != 0 && i != WORLD_SIZE + 1) ? '-' : ' ');

   putchar('\n');
 }

 void printWorld(void)
 {
   printHBorder();

   for (int y = 0; y < WORLD_SIZE; y += 2)
   {
     putchar('|');
     for (int x = 0; x < WORLD_SIZE; ++x)
     {
       int n = y * WORLD_SIZE + x;

       switch ((world[n] << 1) | (world[n + WORLD_SIZE]))
       {
         case 1: putchar('\''); break;
         case 2: putchar(','); break;
         case 3: putchar(';'); break;
         default: putchar(' '); break;
       }
     }

     putchar('|');
     putchar('\n');
   }

   printHBorder();
 }

 void updateAnts(void)
 {
   for (int i = 0; i < ANTS; ++i)
   {
     int newPos = // this just randomly moves in one direction
       (WORLD_SIZE * WORLD_SIZE +
       ants[i].pos +
       ((rand() % 2) ? ((rand() % 2) ? -1 : 1) :
       ((rand() % 2) ? -1 * WORLD_SIZE : WORLD_SIZE)))
       % (WORLD_SIZE * WORLD_SIZE);

     if (world[newPos]) // stepped on a chip?
     {
       if (ants[i].chip)
       { // has chip; drop the chip
         if (!world[ants[i].pos])
         {
           ants[i].chip = 0;
           world[ants[i].pos] = 1;
         }
       }
       else
       { // no chip; pick up the chip
         world[newPos] = 0;
         ants[i].chip = 1;
       }
     }
    
     ants[i].pos = newPos;
   }
 }

 int main(void)
 {
   srand(123);

   for (int i = 0; i < WORLD_SIZE * WORLD_SIZE; ++i)
     world[i] = (rand() % CHIP_DENSITY) == 0;

   for (int i = 0; i < ANTS; ++i)
   {
     ants[i].pos = rand() % (WORLD_SIZE * WORLD_SIZE);
     ants[i].chip = 0;
   }
      
   int i;
 
   while (1)
   {
     if (i % 65536 == 0)
     {
       printf("iteration %d:\n",i);
       printWorld();
     }

     updateAnts();
     i++;
   }

   printWorld();
   return 0;
 }

Links:
1. cellular_automaton.md
2. langtons_ant.md
3. stochasticism.md
4. determinism.md
5. randomness.md
6. algorithm.md
7. c.md