A little while ago I came across the topic of Cellular Automata. I was fascinated about the idea that complex (and even Turing-complete) behavior can come from a system that follows a few simple rules.

One of the more simple types of cellular automaton is Langton’s ant. This type seemed like a good choice to start with. I’ve been wanting to get into Python for a while now so I figured this would be a good project to get my feet wet.

Langton’s ant has a simple setup: an “ant” exists on a two-dimentional grid of tiles. Each tile has two possible colors. They all start out white. The ant also has an orientation (up/down/left/right). Put the ant somewhere near the middle of the grid and then start looping through the steps.

During each step one of two things can happen:

1. If the ant is on a white square: turn the square black, turn to the right, move forward one tile.
2. If the ant is on a black square: turn the square white, turn to the left, move forward one tile.

That’s it, that’s all there is to it. The thing I find so interesting about this system though is that the behavior looks so complex. The ant performs about 10,000 steps before settling into a cycle. So the behavior of the ant appears much more complex than the rules that govern it. In fact the Python code for the program (including handling keyboard input and drawing the information to the screen) is only about 110 lines and 3500 characters long including whitespace:

import sfml as sf

UP = 0
RIGHT = 1
DOWN = 2
LEFT = 3

# Window / tile sizes
SIZE = 4
WIDTH = 300
HEIGHT = 300

class Langton:
def __init__(self):
self.win = sf.RenderWindow(sf.VideoMode(WIDTH, HEIGHT), "Langton's Ant")
self.win.display()
self.paused = False
self.finished = False
self.is_running = True
self.step = False
self.win.show()
self.ant_x = (WIDTH//SIZE)//2
self.ant_y = (HEIGHT//SIZE)//2
self.ant_dir = RIGHT

self.ant_rekt = sf.RectangleShape()
self.ant_rekt.position = ((SIZE * self.ant_x) + 1, (SIZE * self.ant_y) + 1)
self.ant_rekt.size = (SIZE/2, SIZE/2)
self.ant_rekt.fill_color = sf.Color.RED

# create grid
self.tiles = []
for y in range(HEIGHT//SIZE):
row = []
for x in range(WIDTH//SIZE):
rekt = sf.RectangleShape()
rekt.position = (SIZE * x, SIZE * y)
rekt.size = (SIZE, SIZE)
rekt.fill_color = sf.Color.WHITE
row.append(rekt)
self.tiles.append(row)

def run(self):
while self.is_running:
self.handle_events()
if not self.paused and not self.finished:
self.update()
elif self.step:
self.step = False
self.update()
self.draw()

self.win.close()

def update(self):
rekt = self.tiles[self.ant_y][self.ant_x]
is_white = rekt.fill_color == sf.Color.WHITE
rekt.fill_color = sf.Color.BLACK if is_white else sf.Color.WHITE

# turn right on white, left on black, then move forward one unit
if self.ant_dir == UP:
self.ant_dir = RIGHT if is_white else LEFT
elif self.ant_dir == RIGHT:
self.ant_dir = DOWN if is_white else UP
elif self.ant_dir == DOWN:
self.ant_dir = LEFT if is_white else RIGHT
elif self.ant_dir == LEFT:
self.ant_dir = UP if is_white else DOWN

# move ant
if self.ant_dir == UP:
self.ant_y -= 1
elif self.ant_dir == RIGHT:
self.ant_x += 1
elif self.ant_dir == DOWN:
self.ant_y += 1
elif self.ant_dir == LEFT:
self.ant_x -= 1

self.ant_rekt.position = ((SIZE * self.ant_x) + 1, (SIZE * self.ant_y) + 1)

if self.ant_x < 0 or self.ant_x >= WIDTH//SIZE or self.ant_y < 0 or self.ant_y >= HEIGHT//SIZE:
self.finished = True

def handle_events(self):
for event in self.win.events:
if type(event) is sf.CloseEvent:
self.is_running = False
if type(event) is sf.KeyEvent and event.pressed:
if event.code == sf.Keyboard.ESCAPE:
self.is_running = False
if event.code == sf.Keyboard.SPACE:
self.paused = not self.paused
if event.code == sf.Keyboard.RIGHT and self.paused:
self.step = True

def draw(self):
self.win.clear(sf.Color.WHITE)
# draw board
for y in range(HEIGHT//SIZE):
for x in range(WIDTH//SIZE):
tile = self.tiles[y][x]
self.win.draw(tile)

self.win.draw(self.ant_rekt)
self.win.display()

if __name__ == '__main__':
l = Langton()
l.run()

The code uses Python 3.3 and Python-SFML. There’s a gist of it here. Esc closes the program. Space pauses it. The right arrow key will perform a single step while it’s paused.

Here’s a step I thought was pretty cool because of the symmetry:

And here’s what it looks like when it’s finished:

Around the 10,000 step mark the ant begins to create the “highway” seen on the top of the image, moving up and to the left.

This is really just barely touching the subject of cellular automata, and when you add in multiple ants the interactions become much more fascinating. Adding more states and behaviors (see: Turmite) also produces quite interesting results. It’s a neat topic to read about, and seems to naturally point toward the subject of emergence.