Langton's Ant
2015.09.15.
Introduction
Here's the next one in a seemingly never-ending series of grids that I've written. Similarly to my previous project, Queens, it was inspired by a recent Numberphile video, this time featuring Katie Steckles (and Audrey). You probably haven't heard of this one yet, but it's a grid being manipulated by a very simple set of rules just like in Game of Life. This one has an ant though.
Description
So here's Langton's ant in a nutshell.
- Take a grid (you can have coloured and plain squares in it, this program starts with all plain), put an ant on one of the squares.
- If the square it's on is coloured, turn right 90 degrees, otherwise turn left 90 degrees. Move to the square the ant is looking at.
- Toggle the colour of the square that the ant just left.
Repeat the above as many times as you'd like. After a while (somewhere above 10000 iterations) the ant gets into a loop and starts building a repeating pattern called the highway. This is believed to be an attractor - meaning that no matter the starting configuration, the ant will end up building this highway after a certain number of steps - but this isn't proven or disproven yet.
Turing completeness
One of the interesting things about this ant is that given the right starting configuration it's a universal Turing machine. If you haven't come across this topic yet, here's a Computerphile video explaining Turing completeness briefly. Loosely put, a machine is Turing complete if it can be used for general purpose computation (i.e. it can run any algorithm).
This probably isn't all that surprising though considering that Minecraft, Apache Rewrite Rules, Magic: The Gathering, and C++ templates are also Turing complete.
Usage
This program gives the ant a 60x60 field to run around on, which is just enough to see the highway form before the ant reaches the edge of the board and the program stops. Hitting a key or closing the SDL window at any time will exit the program.
There is a light and a dark colour theme included, for Windows, you can download the executable with either option. If you want to self-compile this project, you can change the theme in the beginning of the source by commenting or uncommenting a define statement.
Development
Very straightforward, very quick. I thought about adapting the GoL project that I already had, but there was so little to make that it was easier to write it from scratch than to remove and change things in that one. The project needs -std=c++11 because it uses C++11 enums out of all things that could require it.
It's short, it's commented better than the average of my published projects. I didn't generate the documentation for this one either yet, I might add that later.
Downloads
Downloading the zip file that contains the executable results in a warning (at least in Chrome) as a security measure, but you can choose to "Keep" it.