langtons_ant.md

   1 # Langton's Ant
   2
   3 Langton's ant (also *virtual ant* or *vant*) is a simple [zero player](zero_player.md) [game](game.md) and [cellular automaton](cellular_automaton.md) simulating the behavior of an ant that behaves according to extremely simple rules but nevertheless builds a very complex structure. It is similar to [game of life](game_of_life.md). Langton's ant is **[Turing complete](turing_complete.md)** (it can be used to perform any computation that any other computer can).
   4
   5 **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.
   6
   7 These simple rules produce a quite complex structure, seen below. The interesting thing is that initially the ant behaves **[chaotically](chaos.md)** 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.
   8
   9 ```
  10 ...........................................................................
  11 .............................................................##............
  12 ............................................................##......##.....
  13 ...........................................................#.##.#..#..#....
  14 ...........................................................#..#.###..###...
  15 .....##.....................................................#.##..####.#...
  16 ....##........................................................##...........
  17 ...#.##.#.....................................................##.##.##.....
  18 ...#..#.##................................................#.##.#..####.....
  19 ....#.A.#.#................................##....##....##.###.##.#####.....
  20 ....#...#.##..............................##..####....##..#.##.#.#..#......
  21 ...###..#.#.#............................#.##..####....####.###.####.......
  22 ...#####.#..##......................##...#.......##..##....#...#.###.......
  23 ....#..###..#.#....................#..#..#......#..##..##...##.####........
  24 .....###...#..##..................#..#...#.......##.##...#..#..##.#........
  25 ......#..###..#.#.................#..#....#.########.#.#.##..####.#........
  26 .......###...#..##..........##..##.#.#.#....##.##.#.#.##..#..##..##........
  27 ........#..###..#.#........#####.#..##...##.#...#....#.#..#..#..#.#........
  28 .........###...#..##......#.##...##...#..#...####..#...##.####.##..........
  29 ..........#..###..#.#.....#....#...####.#..#####.##...##########...##......
  30 ...........###...#..##....#.....#.##.#####.##..#.#...#..#..##.#..#..#......
  31 ............#..###..#.#...#.....#####.#.#####.....#.#..##.#....##...#......
  32 .............###...#..##...#..#.######.##.#.##.#.#....###.###...##...#.....
  33 ..............#..###..#.#...##..#.##...##.##.###.###...#..#.##..####.#.....
  34 ...............###...#..##......#.####..##..#########..#..##....#..##......
  35 ................#..###..#.#..#...##..###########.#..####..#....#....#......
  36 .................###...#..##.###..##.#...##.......####.####...#......#.....
  37 ..................#..###..#.#.#..#.###.#.#.##......##...#.#.#....#...#.....
  38 ...................###...#.....#.##.#.##..##..#####.####..####.##...#......
  39 ....................#..###..#.##....#..#.###..#......###.##.#..#..##.......
  40 .....................###...#...#.#..#.#.####.##..#.##.###..#.....#.........
  41 ......................#..###..##...##.##...###..#....#..##.####...#........
  42 .......................###...#.#.##.###..#..##.....#...###.##..##.#........
  43 ........................#..#.........##.##...#..##.....##.#.....##.........
  44 ...........................#.#...#.##.###...#...#.#..####....#.##..........
  45 .......................#.###.#.##.#.#.##.##.##.#...#####.###.##............
  46 .......................###.##...#.####..##.##.######.#.###.#...#...........
  47 ........................#.....#...#####.#.#..####..#...###.#.#.#...........
  48 ..........................#.###.##..#.##..###.#.#.....###...###............
  49 ..........................#.#..###..##.####.##...#.#..#.##..##.............
  50 .........................###.#..#...#.....#.....##.##..###.................
  51 ............................##..##.#.#.........###.......#.................
  52 ................................#.#..#.........#..#....#...................
  53 ................................###...##............##.#...................
  54 .................................#..####..........#..##....................
  55 ..................................##..############..##.....................
  56 ...........................................................................
  57 ```
  58
  59 *Langton's ant after 11100 steps, `A` signifies the ant's position, note the chaotic region from which the highway emerges left and up.*
  60
  61 The Langton's ant game can be extended/modified, e.g. in following ways:
  62
  63 - **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.).
  64 - **multiple ants**: called colonies
  65 - **different grid**: e.g. hexagonal or 3D
  66 - **multiple ant states**: Besides having a direction the ant can have a more complex state. Such ants are called **[turmites](turmite.md)** (Turing termite).
  67
  68 The ant was invented/discovered by [Christopher Langton](langton.md) in his 1986 paper called *Studying Artificial Life With Cellular Automata* where he calls the ants *vants* (virtual ants).
  69
  70 ## Implementation
  71
  72 The following is a simple [C](c.md) implementation of Langton's ant including the extension to multiple colors (modify `COLORS` and `RULES`).
  73
  74 ```
  75 #include <stdio.h>
  76 #include <unistd.h>
  77
  78 #define FIELD_SIZE 48
  79 #define STEPS 5000
  80 #define COLORS 2      // number of colors
  81 #define RULES 0x01    // bit map of the rules, this one is RL
  82
  83 unsigned char field[FIELD_SIZE * FIELD_SIZE];
  84
  85 struct
  86 {
  87   int x;
  88   int y;
  89   char direction; // 0: up, 1: right, 2: down, 3: left
  90 } ant;
  91
  92 int wrap(int x, int max)
  93 {
  94   return (x < 0) ? (max - 1) : ((x >= max) ? 0 : x);
  95 }
  96
  97 int main(void)
  98 {
  99   ant.x = FIELD_SIZE / 2;
 100   ant.y = FIELD_SIZE / 2;
 101   ant.direction = 0;
 102
 103   for (unsigned int step = 0; step < STEPS; ++step)
 104   {
 105     unsigned int fieldIndex = ant.y * FIELD_SIZE + ant.x;
 106     unsigned char color = field[fieldIndex];
 107
 108     ant.direction = wrap(ant.direction + (((RULES >> color) & 0x01) ? 1 : -1),4);
 109
 110     field[fieldIndex] = (color + 1) % COLORS; // change color
 111
 112     // move forward:
 113
 114     switch (ant.direction)
 115     {
 116       case 0: ant.y++; break; // up
 117       case 1: ant.x++; break; // right
 118       case 2: ant.y--; break; // down
 119       case 3: ant.x--; break; // left
 120       default: break;
 121     }
 122
 123     ant.x = wrap(ant.x,FIELD_SIZE);
 124     ant.y = wrap(ant.y,FIELD_SIZE);
 125
 126     // draw:
 127
 128     for (int i = 0; i < 10; ++i)
 129       putchar('\n');
 130
 131     for (int y = 0; y < FIELD_SIZE; ++y)
 132     {
 133       for (int x = 0; x < FIELD_SIZE; ++x)
 134         if (x == ant.x && y == ant.y)
 135           putchar('A');
 136         else
 137         {
 138           unsigned char val = field[y * FIELD_SIZE + x];
 139           putchar(val ? ('A' + val - 1) : '.');
 140         }
 141
 142       putchar('\n');
 143     }
 144
 145     usleep(10000);
 146   }
 147
 148   return 0;
 149 }
 150 ```
 151
 152 ## See Also
 153
 154 - [Resnick's termite](resnicks_termite.md)
 155 - [game of life](game_of_life.md)
 156 - [turmite](turmite.md)
 157 - [rule 110](rule_110.md)
 158 - [cellular automaton](cellular_automaton.md)
 159 - [turtle graphics](turtle_graphics.md)