Langton's Ant Algorithm

Langton's Ant, Chris Langton proposed in 1986, is a cellular automaton (Cellular Automata) system that is simple in structure yet can produce complex patterns.

So what is a cellular automaton?

A cellular automaton is the name given to discrete dynamic systems that operate under a set of rules. Clusters of cells placed on a grid—which you can think of as the universe they live in—take on one or more colors representing their current state, and over the interval from time "t" to "t+1" they influence one another and exhibit their own behavior.

Langton's Ant also runs on three basic rules, listed below: 

• If the ant lands on an orange square, turn 90° left and move forward,
• If the ant lands on a purple square, turn 90° right and move forward,
• The ant paints the square it leaves purple; if it returns to the same square, it flips it to orange. (Each time it visits a square, it inverts the color before moving on.)

The algorithm that follows these rules produces highly chaotic results even though the rules themselves are very simple. Interestingly, though, after roughly its 11,000th move the algorithm settles into a fixed cycle of 104 steps and starts drawing a vertical "highway." Some who lean toward the philosophical side of this describe it as order emerging from chaos (disorder) (see The Game of Life).

- Langton's Ant Visual -

Its universality was proven in 2000. Langton's Ant, has been tested in many ways by adding multiple states and colors, and every time the ant somehow settles into a fixed cycle, builds a regular pattern, and keeps going without breaking that pattern.

I had already been combining the p5.js library—which I also used in my article "Training Flappy Bird with AI"—with Angular to visualize algorithms when I came across this curious one. Of course I was less interested in the philosophy than in visualizing the algorithm, and p5.js felt like the right tool for that. Finding it a thoroughly enjoyable project, I wanted to share the app I built with AngularJS and p5.js under the rules above at "http://langtonsant.fatihbostanci.com/". Follow the link to try the Angular app and share your thoughts with me. 

Thanks for reading—take care, and see you in the next posts!