Pierre Ysewijn - Langton's Ant

No, there's no need to look for your insecticide spray. This ant is, as Conway's Life or Silverman's WireWorld but a cellular automaton. It is even one of the simplest cellular automata. As with Life and WireWorld, an article by Ian Stewart in the July 1994 issue of Scientific American revealed it to the public. But it's origins go way back to the 80's, when Chris Langton of the Santa Fe Institute tried to prove that simple rules applied to a dynamical system can generate behaviour as complex as that shown by living organisms.

Eventually, this small "ant" became the starting point of a new and exciting field of multidisciplinary research, when Chris Langton published in 1989 his article Artificial Life. Alife, or even shorter, AL became quite interesting for evolutionary biology, ecology, biochemistry, computer science, ea.

In his 1989 article, Chris Langton defined ALife as "a synthetic approach to studying Life-as-it-could-be and viewing Life-as-it-is within a larger context". In some ways (and not only through the "artificial"), ALife is related to Artificial Intelligence, in other ways, it is quite different from Artificial Intelligence research. With some generalisation, one could say that ALife models computer programs on nature, while in the field of Artificial Intelligence people often try to model the natural brain as a computer program.

Results in this field are fairly sparse as yet. Current applications of these techniques include adaptive programs that can learn user preferences, computer game characters that evolve better responses, more realistic film animations, web robots that intelligently surf the internet and the study of evolutional processes. Tierra, developed by the ecologist Tom Ray, for instance, is an astonishing simple but very attractive model for the study of evolutional processes as such. With the help of such programs, we can, as it were, cause evolution to happen again.

Langton's ant lives on an infinite grid, composed of "white" (

) cells. In this demonstration the ant's world is limited to 80 by 80 cells (or 64 by 64 if you are viewing these pages on an 800 x 600 screen) with the borders touching one another. In its original format, the ant is represented by a "black" (

) square. On each iteration, it moves forward one square:

if it is currently on a "white" ( ) cell, the ant turns 90 degrees to the right.
if it is currently on a "black" ( ) cell, the ant turns 90 degrees to the left,
as it moves to the next square, it changes the colour of the square it is on from light to dark ( becomes ) or vice-versa ( becomes )

With this very simple set of rules, this ant is still puzzling mathematicians. It can indeed create chaos, but also order.


A symmetrical figure (after about 500 iterations)	A chaos (after about 5000 iterations)

At the beginning, the ant seems to move rather chaotically. Afterwards, from step 500 to about step 10'000, chaos installs itself. And then, suddenly, the ant starts to create order again by drawing what became known as "highways". Eventually, every possible configuration will lead to some kind of repeating pattern. For instance, two ants, facing each other with a 3 square interval, will quickly start to construct their highways already from approximately the 800th iteration.


A highway (after about 11'000 iterations)	Two highways (2 ants after about 1700 iterations)

Of course, as with every cellular automaton, many variations are possible. In this demonstration, three variations are implemented. Two of them are rather simple:

the possibility to install up to 4 ants in the same world ( and )
and the possibility to have the ant turn by steps of 90 or 45 degrees (4 or 8 cardinal directions)

The number of possible directions, the number of ants, their directions and positions can be changed any time.
The third variation, called "the painting ant", is meant to show the frequency with which the ant visits cells.

A highway drawn by a "painting ant"

Instead of colouring a cell black or white (0 or 1), the ant increases the intensity of the colour of the cell on each visit. All cells start at intensity 0 (white). On every visit the ant increases this intensity by one. If the number of visits of the cell is even, then the ant turns right; if this number is odd, then the ant turns left.