The last view days were full of work and so I enjoyed the few free hours yesterday. And because I had no time for coding and blogging, I decided to implement a problem that a friend introduced to me last weekend - Langton’s Ant.
Langton’s Ant is a very simple problem invented by Chris Langton in 1986. It basically covers a set of rules which together determine the behaviour of an ant that colors the ground while moving. Even though the rules used are very simple, the resulting behavior of the ant is very complex. The most interesting is, that the ant’s movement results in a recurring structure after a couple of steps (about 10000). The idea of this kind of simulation has been extended in many different ways. The most popular extended version of Langton’s Ant are Turmites which basically extend the coloring rule of Langton’s Ant.
The idea of traditional Langton’s Ant is very simple. The ant moves on a grid. If it stands on a white field, it colors it black, turns left by 90 degrees and moves one step forward. If it currently stands on a black field, it colors it white, turns right by 90 degrees and moves one step forward.
Since this problem is so simple and much fun, I decided to implement it. And of course the language of my choice was Monty’s Python. You see, I am currently working with a whole zoo.
To complete this zoo I would like to introduce another animal to you - the Ninja Turtle. Turtle is a very easy to use python library that perfectly fits the needs when implementing drawing problems. Turtle offers a little turtle that could programmatically be moved forward and backward, turned around by an arbitrary angle and draw in different colors. The cool thing about turtle is that the drawing process could be animated, so you could watch Langton’s ant moving around.
The code of this ‘short’ program you could find below. I think it is completely self explaining, so I will just cover the usage of the program and not the code itself.
#!/usr/bin/python
from Tkinter import *
from turtle import *
import turtle
import getopt
import sys
class Langton(object):
def __init__(self, iterations, blockSize, gridSize):
self.iterations = iterations
self.blockSize = blockSize
self.gridSize = gridSize
self.stepSize = blockSize
self.posStack = dict()
self.black = (0.0, 0.0, 0.0)
self.white = (1.0, 1.0, 1.0)
self.width = self.height = blockSize * gridSize
def draw(self, outputFile):
# Setup turtle, ...
turtle.setup(self.width, self.height)
# ... create a new window ...
window = turtle.Screen()
window.screensize(self.width, self.height)
# ... and setup a new ninja turtle.
raphael = turtle.Turtle()
raphael.pensize(self.blockSize)
raphael.hideturtle()
raphael.tracer(13, 0)
raphael.speed(0)
for i in range(self.iterations):
# Fetch the current position ...
pos = (int(raphael.pos()[0]), int(raphael.pos()[1]))
# ... and fetch the current color.
color = self.white
if self.posStack.has_key(pos):
color = self.posStack[pos]
# Fetch the new color and update the direction.
if color == self.white:
raphael.left(90)
color = self.black
else:
raphael.right(90)
color = self.white
# Fill the current cell, ...
raphael.pencolor(color)
raphael.dot(self.blockSize)
# ... update the position stack ...
self.posStack[pos] = color
# ... and move one step.
raphael.up()
raphael.forward(self.stepSize)
raphael.down()
if outputFile != None:
ts = raphael.getscreen()
ts.getcanvas().postscript(file=outputFile, colormode='color')
window.onkey(window.bye, "q")
window.listen()
turtle.mainloop()
def usage():
print "Usage: python langton.py [-i iterations] [-s blockSize] [-g gridSize] [-o outFile] [-h]\n\n" \
"-i\tNumber of iterations.\n" \
"\tDefault is 10000.\n\n" \
"-s\tSize of the fields.\n" \
"\tDefault is 3 (3x3 px).\n\n" \
"-g\tSize of the drawing grid.\n" \
"\tDefault is 500 (500x500 px).\n\n" \
"-o\tPath to the eps output file.\n" \
"\tDefault is no output.\n\n" \
"-h\tShows this help";
def main(argv):
try:
opts, args = getopt.getopt(argv, "hi:s:g:o:", ["help", "iterations=", "size=", "grid=", "output="])
except getopt.GetoptError as err:
# Print usage information and exit.
print(err)
usage()
sys.exit(2)
iterations = 10000
blockSize = 3
gridSize = 500
outputFile = None
for o, a in opts:
if o in ("-h", "--help"):
usage()
sys.exit(0)
elif o in ("-i", "--iterations"):
iterations = int(a);
elif o in ("-s", "--size"):
blockSize = int(a);
elif o in ("-g", "--grid"):
gridSize = int(a);
elif o in ("-o", "--output"):
outputFile = a;
else:
assert False, "unhandled option"
# Do something!
langton = Langton(iterations, blockSize, gridSize)
langton.draw(outputFile)
if __name__ == "__main__":
main(sys.argv[1:])In order to use this program we should take a short look at the parameters accepted by it. You could specify the number of iterations (steps) the ant should do, the size of the world (grid) the ant could move around in, the size of a single cell (blockSize) and an output file in postscript format, the result should be written to.
So if you want to create a world with 300x300 cells of a size of 3x3 pixel, the ant should do 15000 steps and the resulting image should be stored in the file langton.eps, you could use the following command:
python langton.py -i 15000 -s 3 -g 300 -o langton.eps
I hope you enjoyed this short introduction to Langton’s Ant and the example of how to use the turtle graphics library. I will present another example using the turtle library in a few days when I finished my Lindenmeyer program. The Lindenmeyer systems are another class of problems that were introduced and developed in 1968 by Aristid Lindenmayer. The systems are based on a set of rules, which allow the user to draw arbitrary structures by directing an ant or turtle. A simple example that were first described by the German mathematician David Hilbert in 1891, you could see on the right side. Here you see an screenshot of a simple prototype, which will be extended to allow the drawing of more complex Lindenmeyer systems.
So stay tuned and until next time, happy coding.