Langton's Ant

   Langton's ant (also virtual ant or vant) is a simple [1]zero player
   [2]game and [3]cellular automaton simulating the behavior of an ant that
   behaves according to extremely simple rules but nevertheless builds a very
   complex structure. It is similar to [4]game of life. Langton's ant is
   [5]Turing complete (it can be used to perform any computation that any
   other computer can).

   Rules: in the basic version the ant is placed in a square grid where each
   square can be either white or black. Initially all squares are white. The
   ant can face north, west, south or east and operates in steps. In each
   step it does the following: if the square the ant is on is white (black),
   it turns the square to black (white), turns 90 degrees to the right (left)
   and moves one square forward.

   These simple rules produce a quite complex structure, seen below. The
   interesting thing is that initially the ant behaves [6]chaotically but
   after about 10000 steps it suddenly ends up behaving in an ordered manner
   by building a "highway" that's a non-chaotic, repeating pattern. From then
   on it continues building the highway until the end of time.

 ...........................................................................
 .............................................................##............
 ............................................................##......##.....
 ...........................................................#.##.#..#..#....
 ...........................................................#..#.###..###...
 .....##.....................................................#.##..####.#...
 ....##........................................................##...........
 ...#.##.#.....................................................##.##.##.....
 ...#..#.##................................................#.##.#..####.....
 ....#.A.#.#................................##....##....##.###.##.#####.....
 ....#...#.##..............................##..####....##..#.##.#.#..#......
 ...###..#.#.#............................#.##..####....####.###.####.......
 ...#####.#..##......................##...#.......##..##....#...#.###.......
 ....#..###..#.#....................#..#..#......#..##..##...##.####........
 .....###...#..##..................#..#...#.......##.##...#..#..##.#........
 ......#..###..#.#.................#..#....#.########.#.#.##..####.#........
 .......###...#..##..........##..##.#.#.#....##.##.#.#.##..#..##..##........
 ........#..###..#.#........#####.#..##...##.#...#....#.#..#..#..#.#........
 .........###...#..##......#.##...##...#..#...####..#...##.####.##..........
 ..........#..###..#.#.....#....#...####.#..#####.##...##########...##......
 ...........###...#..##....#.....#.##.#####.##..#.#...#..#..##.#..#..#......
 ............#..###..#.#...#.....#####.#.#####.....#.#..##.#....##...#......
 .............###...#..##...#..#.######.##.#.##.#.#....###.###...##...#.....
 ..............#..###..#.#...##..#.##...##.##.###.###...#..#.##..####.#.....
 ...............###...#..##......#.####..##..#########..#..##....#..##......
 ................#..###..#.#..#...##..###########.#..####..#....#....#......
 .................###...#..##.###..##.#...##.......####.####...#......#.....
 ..................#..###..#.#.#..#.###.#.#.##......##...#.#.#....#...#.....
 ...................###...#.....#.##.#.##..##..#####.####..####.##...#......
 ....................#..###..#.##....#..#.###..#......###.##.#..#..##.......
 .....................###...#...#.#..#.#.####.##..#.##.###..#.....#.........
 ......................#..###..##...##.##...###..#....#..##.####...#........
 .......................###...#.#.##.###..#..##.....#...###.##..##.#........
 ........................#..#.........##.##...#..##.....##.#.....##.........
 ...........................#.#...#.##.###...#...#.#..####....#.##..........
 .......................#.###.#.##.#.#.##.##.##.#...#####.###.##............
 .......................###.##...#.####..##.##.######.#.###.#...#...........
 ........................#.....#...#####.#.#..####..#...###.#.#.#...........
 ..........................#.###.##..#.##..###.#.#.....###...###............
 ..........................#.#..###..##.####.##...#.#..#.##..##.............
 .........................###.#..#...#.....#.....##.##..###.................
 ............................##..##.#.#.........###.......#.................
 ................................#.#..#.........#..#....#...................
 ................................###...##............##.#...................
 .................................#..####..........#..##....................
 ..................................##..############..##.....................
 ...........................................................................

   Langton's ant after 11100 steps, A signifies the ant's position, note the
   chaotic region from which the highway emerges left and up.

   The Langton's ant game can be extended/modified, e.g. in following ways:

     * multiple colors: Squares can have more colors than just black/white
       that are cycled by the ant. Here we also need to specify which way the
       ant turns for each color it steps on, for example for 4 colors we may
       specify the rules as LRLL (turn left on 1st color, right on 2nd color
       etc.).
     * multiple ants: called colonies
     * different grid: e.g. hexagonal or 3D
     * multiple ant states: Besides having a direction the ant can have a
       more complex state. Such ants are called [7]turmites (Turing termite).

   The ant was invented/discovered by [8]Christopher Langton in his 1986
   paper called Studying Artificial Life With Cellular Automata where he
   calls the ants vants (virtual ants).

Implementation

   The following is a simple [9]C implementation of Langton's ant including
   the extension to multiple colors (modify COLORS and RULES).

 #include <stdio.h>
 #include <unistd.h>

 #define FIELD_SIZE 48
 #define STEPS 5000
 #define COLORS 2      // number of colors
 #define RULES 0x01    // bit map of the rules, this one is RL

 unsigned char field[FIELD_SIZE * FIELD_SIZE];

 struct
 {
   int x;
   int y;
   char direction; // 0: up, 1: right, 2: down, 3: left
 } ant;

 int wrap(int x, int max)
 {
   return (x < 0) ? (max - 1) : ((x >= max) ? 0 : x);
 }

 int main(void)
 {
   ant.x = FIELD_SIZE / 2;
   ant.y = FIELD_SIZE / 2;
   ant.direction = 0;

   for (unsigned int step = 0; step < STEPS; ++step)
   {  
     unsigned int fieldIndex = ant.y * FIELD_SIZE + ant.x;
     unsigned char color = field[fieldIndex];

     ant.direction = wrap(ant.direction + (((RULES >> color) & 0x01) ? 1 : -1),4);

     field[fieldIndex] = (color + 1) % COLORS; // change color

     // move forward:

     switch (ant.direction)
     {
       case 0: ant.y++; break; // up
       case 1: ant.x++; break; // right
       case 2: ant.y--; break; // down
       case 3: ant.x--; break; // left
       default: break;
     }

     ant.x = wrap(ant.x,FIELD_SIZE);
     ant.y = wrap(ant.y,FIELD_SIZE);

     // draw:

     for (int i = 0; i < 10; ++i)
       putchar('\n');

     for (int y = 0; y < FIELD_SIZE; ++y)
     {
       for (int x = 0; x < FIELD_SIZE; ++x)
         if (x == ant.x && y == ant.y)
           putchar('A');
         else
         {
           unsigned char val = field[y * FIELD_SIZE + x];
           putchar(val ? ('A' + val - 1) : '.');
         }

       putchar('\n');
     }

     usleep(10000);
   }

   return 0;
 }

See Also

     * [10]Resnick's termite
     * [11]game of life
     * [12]turmite
     * [13]rule 110
     * [14]cellular automaton
     * [15]turtle graphics

Links:
1. zero_player.md
2. game.md
3. cellular_automaton.md
4. game_of_life.md
5. turing_complete.md
6. chaos.md
7. turmite.md
8. langton.md
9. c.md
10. resnicks_termite.md
11. game_of_life.md
12. turmite.md
13. rule_110.md
14. cellular_automaton.md
15. turtle_graphics.md