Langton’s Ant is a turmite governed by simple rules whose outcome is both unpredictable and intresting. The path taken by the ant generates some surprising shapes, never appearing when you would expect them to, but a seemingly random moments. This article describes the rules behind Langton’s Ant, shows some of the images formed and provides a Python programme to simulate the ant.
Chris Langton is a biologist, and the founder of the field of artificial life. One of his simplest and most intresting creations is Langton’s Ant. It is quite important theoretically, but it also has some intresting practical applications.
The ant’s world consists of a grid, possibly infinite, but limited in our example:
The ant always moves through this grid one step at a time. It’s direction and it’s effect on the grid is defined by 3 simple rules:
- If the ant is on a black square, it turns right 90 degrees.
- If the ant is on a white square, it turns left 90 degrees.
- When the ant leaves a square, it inverts colour.
It is fairly obvious that the ant’s movement will leave a coloured trail. When asked, most people would guess that either no patterns show or that some basic symmetric images appear. What actually happens is this.
For the first 50 or so steps, it just seems to move around randomly, and then at step 52, you get a heart:
For the next 300 or so steps, the ant seems to draw random shapes, ofter erasing what it had drawn before. At about step 383 you get something that looks like this:
By now, you are probably thinking: “Well yes. Simple rules, so at first you get simple patterns, but as the board gets more and more complex, the simple rules can’t handle it, so the ant moves randomly”. Well that’s right, up until about step 10000; that is when you start getting highways.
The highways the ant draws are intresting shapes. You can see one at the bottom of the next image. It is the diagonal bit going down and right. To build then, the ant seems to move in circles, the last row forcing it to draw the next. Thus, the ant continues to draw until something gets in its way. In this simulation, because the screen wraps around, the ant eventually gets back to the mess, where it starts moving randomly again.
What’s intresting is that, after some time, the ant starts building highways again. Actually, there is no known way to stop it. The only hindrance here is that the board is finite so it has a tendency to fill up. Anyway, here’s what the board looks like at step 97049:
The variables that control the display and the board are at the top of the programme. They are heavily commented so there shouldn’t be any problems.
Here’s the code in Python (langton.py):
#************************************************ # Rules of the game # 1. If the ant is on a black square, it turns # right 90 and moves forward one unit # 2. If the ant is on a white square, it turns # left 90 and moves forward one unit # 3. When the ant leaves a square, it inverts # colour # # SEE: http://mathworld.wolfram.com/LangtonsAnt.html #************************************************ import sys, pygame from pygame.locals import * import time dirs = ( (-1, 0), (0, 1), (1, 0), (0, -1) ) cellSize = 12 # size in pixels of the board (4 pixels are used to draw the grid) numCells = 64 # length of the side of the board background = 0, 0, 0 # background colour; black here foreground = 23, 23, 23 # foreground colour; the grid's colour; dark gray here textcol = 177, 177, 177 # the colour of the step display in the upper left of the screen antwalk = 44, 88, 44 # the ant's trail; greenish here antant = 222, 44, 44 # the ant's colour; red here fps = 1.0 / 40 # time between steps; 1.0 / 40 means 40 steps per second def main(): pygame.init() size = width, height = numCells * cellSize, numCells * cellSize pygame.display.set_caption("Langton's Ant") screen = pygame.display.set_mode(size) # Screen is now an object representing the window in which we paint screen.fill(background) pygame.display.flip() # IMPORTANT: No changes are displayed until this function gets called for i in xrange(1, numCells): pygame.draw.line(screen, foreground, (i * cellSize, 1), (i * cellSize, numCells * cellSize), 2) pygame.draw.line(screen, foreground, (1, i * cellSize), (numCells * cellSize, i * cellSize), 2) pygame.display.flip() # IMPORTANT: No changes are displayed until this function gets called font = pygame.font.Font(None, 36) antx, anty = numCells / 2, numCells / 2 antdir = 0 board = [[False] * numCells for e in xrange(numCells)] step = 1 pause = False while True: for event in pygame.event.get(): if event.type == QUIT: return elif event.type == KEYUP: if event.key == 32: # If space pressed, pause or unpause pause = not pause elif event.key == 115: pygame.image.save(screen, "Step%d.tga" % (step)) if pause: time.sleep(fps) continue text = font.render("%d " % (step), True, textcol, background) screen.blit(text, (10, 10)) if board[antx][anty]: board[antx][anty] = False # See rule 3 screen.fill(background, pygame.Rect(antx * cellSize + 1, anty * cellSize + 1, cellSize - 2, cellSize - 2)) antdir = (antdir + 1) % 4 # See rule 1 else: board[antx][anty] = True # See rule 3 screen.fill(antwalk, pygame.Rect(antx * cellSize + 1, anty * cellSize + 1, cellSize - 2, cellSize - 2)) antdir = (antdir + 3) % 4 # See rule 2 antx = (antx + dirs[antdir]) % numCells anty = (anty + dirs[antdir]) % numCells # The current square (i.e. the ant) is painted a different colour screen.fill(antant, pygame.Rect(antx * cellSize + 1, anty * cellSize + 1, cellSize -2, cellSize -2)) pygame.display.flip() # IMPORTANT: No changes are displayed until this function gets called step += 1 time.sleep(fps) if __name__ == "__main__": main()
It is intresting to note that although you know all the rules that govern the ant’s universe, you cannot predict its movement without resorting to simulation. This just goes to show that knowing the rules of the components at the lowest level might not help you understand the system as a whole.
That’s it. Have fun with the code. Always open to comments.