Where there is a Will

Many moons ago I implemented Langton Ants on a ZX Spectrum 48K, and I have been fascinated by it ever since. I thought it would be fun to implement it in PyGame.

Langton ants are simple creatures. They live in a grid of squares that can be one of two colors, and follow these two simple rules.

• Am I on color 1? Flip the square, turn 90 degrees right, move forward 1 square.

• Am I on color 2? Flip the square, turn 90 degrees left, move forward 1 square.

That is all they do. They don’t ponder the meaning of life or current affairs, they just check the color of the square they are on and then turn and move. You would think that something this simple would quickly get in to a cyclical pattern, but it turns out that Langton ants like to make crazy complex patterns and don’t repeat themselves. Humor me, while I write a Python script to test it.

First thing we need to do is define a few constants for use in the script, as follows.

GRID_SIZE = (160, 120)
GRID_SQUARE_SIZE = (4, 4)
ITERATIONS = 1
ant_image_filename = "ant.png"

The grid will be 160×120 squares, with squares that are 4×4 pixels (so that it fits inside a 640×480 pixel screen). The value of ITERATIONS is the number of moves an ant does each frame, increase it if you want the ants to move faster. Finally we have the filename of an image to represent the ant. I will be using this image: .

Next we import PyGame in the usual manner.

import pygame
from pygame.locals import *

We will represent the grid with a class that contains a two dimensional list (actually a list of lists) of bools, one for each square, where False is color 1, and True is color 2. The AntGrid class is also responsible for clearing the grid, getting the square color at a coordinate, flipping a square color and drawing itself to a PyGame surface. I chose white for color 1 and dark green for color 2, but feel free to change it if you want something different.

class AntGrid(object):
 
    def __init__(self, width, height):
 
        self.width = width
        self.height = height
        self.clear()
 
    def clear(self):
 
        self.rows = []
        for col_no in xrange(self.height):
            new_row = []
            self.rows.append(new_row)
            for row_no in xrange(self.width):
                new_row.append(False)
 
    def swap(self, x, y):
        self.rows[y][x] = not self.rows[y][x]
 
    def get(self, x, y):
        return self.rows[y][x]
 
    def render(self, surface, colors, square_size):
 
        w, h = square_size
        surface.fill(colors[0])
 
        for y, row in enumerate(self.rows):
            rect_y = y * h
            for x, state in enumerate(row):
                if state:
                    surface.fill(colors[1], (x * w, rect_y, w, h))

Now that we have a grid, we can create a class for the ants. The move function in the Ant class implements the two rules, and the render function draws a sprite at the ants location so we can see where it is.

class Ant(object):
 
    directions = ( (0,-1), (+1,0), (0,+1), (-1,0) )
 
    def __init__(self, grid, x, y, image, direction=1):
 
        self.grid = grid
        self.x = x
        self.y = y
        self.image = image
        self.direction = direction
 
    def move(self):
 
        self.grid.swap(self.x, self.y)
 
        self.x = ( self.x + Ant.directions[self.direction][0] ) % self.grid.width
        self.y = ( self.y + Ant.directions[self.direction][1] ) % self.grid.height        
 
        if self.grid.get(self.x, self.y):
            self.direction = (self.direction-1) % 4
        else:
            self.direction = (self.direction+1) % 4                
 
    def render(self, surface, grid_size):
 
        grid_w, grid_h = grid_size
        ant_w, ant_h = self.image.get_size()
        render_x = self.x * grid_w - ant_w / 2
        render_y = self.y * grid_h - ant_h / 2
        surface.blit(self.image, (render_x, render_y))

Finally in the script, the run function handles the guts of the simulation. It sets up the screen, creates the the grid object then enters the main loop. Inside the main loop there are event handlers so that you can drop ants with the left mouse button, clear the grid with the C key and start the simulation with the SPACE key. The remaining portion of the run function moves all the ants and renders the screen.

def run():
 
    pygame.init()
    w = GRID_SIZE[0] * GRID_SQUARE_SIZE[0]
    h = GRID_SIZE[1] * GRID_SQUARE_SIZE[1]
    screen = pygame.display.set_mode((w, h), 0, 32)
 
    ant_image = pygame.image.load(ant_image_filename).convert_alpha()    
 
    default_font = pygame.font.get_default_font()
    font = pygame.font.SysFont(default_font, 22)    
 
    ants = []
    grid = AntGrid(*GRID_SIZE)
    running = False
 
    total_iterations = 0
 
    while True:
 
        for event in pygame.event.get():
 
            if event.type == QUIT:
                return
 
            if event.type == MOUSEBUTTONDOWN:
 
                x, y = event.pos
                x /= GRID_SQUARE_SIZE[0]
                y /= GRID_SQUARE_SIZE[1]                
 
                ant = Ant(grid, int(x), int(y), ant_image)
                ants.append(ant)
 
            if event.type == KEYDOWN:
 
                if event.key == K_SPACE:
                    running = not running
 
                if event.key == K_c:
                    grid.clear()
                    total_iterations = 0
                    del ants[:]
 
        grid.render(screen, ((255, 255, 255), (0, 128, 0)), GRID_SQUARE_SIZE)
 
        if running:
            for iteration_no in xrange(ITERATIONS):
                for ant in ants:
                    ant.move()
            total_iterations += ITERATIONS
 
        txt = "%i iterations"%total_iterations
        txt_surface = font.render(txt, True, (0, 0, 0))
        screen.blit(txt_surface, (0, 0))
 
        for ant in ants:
            ant.render(screen, GRID_SQUARE_SIZE)
 
        pygame.display.update()
 
if __name__ == "__main__":
    run()

And thats our finished Langton Ant simulation. Have a play with it, then come back and explain to me how two simple rules can create such a complex pattern.

Download langtonants.zip

Update: Here’s a screenshot!

This entry was posted on Friday, May 18th, 2007 at 10:04 pm and is filed under PyGame, Python. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.