less_retarded_wiki/resnicks_termite.md

Resnick's Termite

WORK IN PROGRESS

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

Resnick's termite is a simple 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 Langton's ant but Resnick's termites are stochastic, nondeterministic, they rather show how statistics/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 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 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;
}