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:
- If the ant is on a white square: turn the square black, turn to the right, move forward one tile.
- 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.