Ant Automata

Langton’s Ant

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.

Langton's Ant

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).

Ant Automaton

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 9
Ant Automaton

Rule 262 – Diagonal scaffolding like structures
Ant Automaton

Rule 908 – Builds a rougher jagged highway
Ant Automaton

Rule 1080 – Spiral
Ant Automaton

Rule 8383 – Build Sierpinski Triangle patterns as it grows
Ant Automaton

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
Ant Automaton

Rule 1042 – Creates more cubic structures and then builds a vertical highway
Ant Automaton

Rule 4514 – Slowly builds a complex vertical highway
Ant Automaton

Rule 6046 – Builds a vertical sprouting highway from a virtual seed
Ant Automaton

Rule 6738 – Corkscrew highway
Ant Automaton

Rule 9513 – Zigzag highway
Ant Automaton

Rule 10952 – After a long time building a seemingly random blob it starts generating a triangle shaped highway
Ant Automaton

Rule 17416 – Generates plate like interlocking 3D puzzle pieces and then a complex highway
Ant Automaton

OBJ Export

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.

3D Ant Automaton

3D Ant Automaton

3D Ant Automaton

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.

Jason.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s