Langton's Ant
Hi there. It's been a while since I posted something. As far as I remember my last post is more than 2 years ago and was about game developing with C++ and Irrlicht. And that is almost the amount of time I didn't do anything regarding that topic :D
I took a deeper look into the secrets of theoretical computer science. To be more exact: graph theory (which is also the topic my master thesis), cellular automatons and some fun stuff like game of life evaluation or generic map creation. One of the more interesting issues was without a doubt Langton's Ant. So I will make this the main topic of my latest blog entry.
For those who never heard of Langton's ant I will give a short description (for a more detailed version consider this article).
Langton's ant is basicly a 2 dimensional cellular automaton, operated from an ant (as you might guess from the name). This ant follows some rules, which are defined in before hand. A cycle is a sequence of actions, which are
- The ant takes a step depending on its facing direction
- The ant analyzes the color of the tile on which the ant is currently standing
- Depeding on the color the ant changes its facing direction and the color of the tile
This cycle may go on forever or stop at a certain point (depending on what you want to do with the ant). The rules that we mentioned earlier are a list of tuples, which describe how the facing direction of the ant and the color of the tile will change. Take a look at the example:
{
"start": "white", "direction": "left", "end": "red"
},
{
"start": "red", "direction": "right", "end": "white"
}
Whenever the ant is analyzing a white tile, it will turn 90° left and will change the tile to red. On the other side, whenever it is located on a red tile, it'll change the tile to a white one and will turn 90° right. All not visited tiles (especially the first one) are considered as white.
So depending on the rules we provide, we can achieve some interesting behaviour of the automaton. There are rules, which lead to a non repeating behaviour (at least we do not know yet if it somehow contains a repeating pattern), where as some rules lead to a quite repetitive pattern. The most common recurring pattern is a highway (consider the pictures below for an example of a highway).
You may wonder what the big idea behind this concept is. First of all it's very fun to code and to watch as well. An implementation in python takes less than 200 lines of code, where at least 30% deals only with drawing and window creation stuff. Secondly searching for patterns or determing if there are loops in a certain ruleset is also interesting as well and may have some practical use cases.
Imagine a level editor, which bases on langton's ant. Each color is identified with a specific texture, which is mapped on the tile later on. Depending on the rule set, we could create basic layouts (e.g. highways ;)) or some ambient second layer sets (dirt, grass, decoration, ...). For this we would need a proper ruleset though. However we could use a layout produced by a ruleset and tune it manually afterwards. It takes more in-depth research to decide whether langton's ant could (automatically) produce decent tilemaps.
We also can extend langton's ant in many ways. First of all we could use multiple ants running parallely. The next we could change for more fun is the probability of changing the facing and color (e.g. the ant analyzing a red tile will turn left by 20% of the cases and turn right in 80% of the cases). However this would make searching for loops more complicated, since we would have to deal with multi states. Another easy to evaluate modification would be adding more directions (e.g. stay, turn backwards). Combining all these extensions langton's ant could produce complex structures.
As you can see langton's ant is a pretty interesting thing, which is widely unterrated. I attended 3 practical courses (in my currenty university), where I learned functional and dynamically typed programming languages (namely Haskell, Clojure and Python). In all of them I had to implement Conway's game of life, which is also another interesting cellular automaton. But I wish I had to implement langton's ant in at least one of these courses instead of writing another game of life clone. So please spread the word. Let langton's ant live and be a more valuable part in our lifes!
