Langton’s Ant was invented by Christopher Langton in 1986.
Here are the simple steps to generate Langton’s Ant.
1. Start with a blank 2D grid of white cells/pixels.
2. Place a virtual ant in the middle cell.
3. If the ant is on a white cell it turns the pixel black, turns 90 degrees right and then moves one cell forward.
4. If the ant is on a black cell it turns the pixel white, turns 90 degrees left and then moves one cell forward.
5. Step 3 and 4 are repeated for as long as required.
Here is a nice GIF file courtesy of Wikipedia that shows how the first 200 steps of Langton’s Ant evolve.
At first the ant travels around in a roughly blob shaped random pattern, but after a while (around 10,000 steps) the ant starts to build a structured pathway as in the following GIF animation.
Structures like that are referred to as highways. The above highway would continue to grow forever on a large enough grid.
Rule strings for a wider variety of Ants
Langton’s Ant can be represented by the rule “RL” which is the direction the ant turns depending on the underlying cell color. R for a black cell and L for a blue cell (as in the above animation).
An extension to Langton’s Ant is to allow more than 2 characters. For example, if you try RRLL as a rule it gives the following cardioid like structure over time (click for a larger detailed image).
With more characters in the rule string you use more colors. In the above cardioid example the first R character is black and then the other 3 colors are shaded between a light and dark blue.
A simple way of referring to the different rules is to use a rule number. To get a rule number, you follow these steps;
1. Convert the rule string into a binary string. RRLL -> 1100.
2. Convert that binary string into a decimal number. 1100 = 12.
Here are some other examples with their rule numbers showing the variety of patterns that can emerge from these very simple rules. Click on each of the images to see the higher resolution originals.
Rule 262 – Diagonal scaffolding like structures
Rule 908 – Builds a rougher jagged highway
Rule 1080 – Spiral
Rule 8383 – Build Sierpinski Triangle patterns as it grows
There are more examples in my Ant Automaton Gallery.
3D Ant Automata
The next logical step was to extend into 3D space. I was trying to work out how to handle and program an ant turning in 3 dimensions when I came across Dr Heiko Hamann‘s page on 3D Langton’s Ants. He generously provides some source code here that has the required matrix manipulation required to get the ant turning in 3D space. Have a look if you are interested in implementing your own 3D version of Langton’s Ant.
Once I got the code working I ran a brute force search over the first 20,000 rule numbers. It is harder to see structures within the blobs of random that tend to emerge, but a few interesting results did occur. One thing you get is a lot of very basic highways, so the same emergence of highways in 2D does carry over to 3D.
Here are a few examples I found so far and their corresponding rule numbers. Click to see the larger original images.
Rule 318 – An example of one of the many highways
Rule 1042 – Creates more cubic structures and then builds a vertical highway
Rule 4514 – Slowly builds a complex vertical highway
Rule 6046 – Builds a vertical sprouting highway from a virtual seed
Rule 6738 – Corkscrew highway
Rule 9513 – Zigzag highway
Rule 10952 – After a long time building a seemingly random blob it starts generating a triangle shaped highway
Rule 17416 – Generates plate like interlocking 3D puzzle pieces and then a complex highway
Visions Of Chaos also supports exporting the 3D Ant Automata to OBJ files. Here are some examples of 3D Ants exported to OBJ files and imported into and rendered in Blender. I really am a total amateur with Blender but these images show some potential with nice ambient occlusion.
Experiment with Ant Automata
If you want to see any of these automata being built or want to experiment with other rules, download Visions Of Chaos.
If you find any new interesting rules let me know.