Langton's Ant

A virtual ant lives on an infinite board, divided into square cells. Each cell can be either black or white. For starters, we can consider an empty (all-white) board with an ant residing in its arbitrary location. The ant operates according to the following rules:
1. If the cell under the ant is white, the ant turns 90° to the right, makes the cell black, and moves one cell forward.
2. If the cell under the ant is black, the ant turns 90° to the left, makes the cell white, and moves one cell forward.
At a glance, this description does not look quite right for a proper cellular automaton: the rules are supposed to specify how a cell switches from one state to another on the basis of cell neighborhood, rather than direct a moving creature over a board. However, the rules of Langton’s ant can be rewritten to follow the usual conventions. Each cell of the board has 10 possible states: (white, no ant), (white, ant looks left), (white, ant looks up), and so on. In other words, a cell state is a combination of its color and ant status. Then the next state of a cell indeed entirely depends on its neighborhood. Say, a cell with the ant will have the opposite color and no ant on the next turn. Similarly, a cell having a left white neighbor with the up-looking ant will have the same color and the right-looking ant on the next turn.

import turtle
from dataclasses import dataclass


H = 81
W = 81
SLEEP_MS = 20
CELL_SIZE = 5
SHAPE_SIZE = CELL_SIZE / 20


@dataclass
class SimState:
    to_exit: bool
    paused: bool

    def exit(self):
        exit()

    def pause_resume(self):
        self.paused = not self.paused

    @classmethod
    def setup(cls):
        r = cls(False, False)
        turtle.listen()
        turtle.onkeypress(r.pause_resume, "space")
        turtle.onkeypress(r.exit, "e")
        turtle.onkeypress(r.exit, "E")
        return r


@dataclass
class CellShape:
    shape: turtle.Turtle

    @classmethod
    def create(cls, x, y):
        p = turtle.Turtle()
        p.penup()
        p.shape("circle")
        p.shapesize(SHAPE_SIZE)
        p.goto(x, y)
        p.hideturtle()
        return cls(p)

    def is_black(self):
        return self.shape.isvisible()

    def flip(self):
        if self.is_black():
            self.shape.hideturtle()
        else:
            self.shape.showturtle()


def make_ant(x, y):
    p = turtle.Turtle()
    p.penup()
    p.shape("turtle")
    p.shapesize(SHAPE_SIZE / 2)
    p.goto(x, y)
    p.color("red")
    return p


@dataclass
class WorldState:
    board: list
    ant: turtle.Turtle
    step: int = 0

    def update(self):
        self.step += 1
        if self.step % 1000 == 0:
            print(f"Performing step: {self.step}")

        x = round(self.ant.xcor())
        y = round(self.ant.ycor())
        turn = 90 if self.board[x][y].is_black() else -90

        self.board[x][y].flip()
        self.ant.left(turn)
        self.ant.forward(1)

    @classmethod
    def setup(cls):
        board = [[CellShape.create(x, y) for y in range(H)] for x in range(W)]
        ant = make_ant(W // 2, H // 2)
        return cls(board, ant)


def setup_screen(title):
    turtle.setup(W * CELL_SIZE, H * CELL_SIZE)
    turtle.tracer(0, 0)
    turtle.title(title)
    turtle.setworldcoordinates(0, 0, W, H)


setup_screen("Langton's ant")
sim_state = SimState.setup()
world_state = WorldState.setup()


def tick():
    if not sim_state.to_exit:
        if not sim_state.paused:
            world_state.update()
            turtle.update()
        turtle.ontimer(tick, SLEEP_MS)


tick()
turtle.done()

zzh@ZZHPC:/zdata/Github$ /home/zzh/.pyenv/versions/3.12.3/bin/python /zdata/Github/playful-python-modeling-animation/grid/langton_ant.py
Performing step: 1000

zzh@ZZHPC:/zdata/Github$ /home/zzh/.pyenv/versions/3.12.3/bin/python /zdata/Github/playful-python-modeling-animation/grid/langton_ant.py
Performing step: 1000
Performing step: 2000
Performing step: 3000
Performing step: 4000
Performing step: 5000
Performing step: 6000
Performing step: 7000
Performing step: 8000
Performing step: 9000
Performing step: 10000
Performing step: 11000

The screenshot in Figure 6.18 shows the situation on the board after the first 1000 steps. This picture shows the lack of any conceivable patterns behind the ant’s trajectory. This impression is even stronger if the ant is watched in real time: its nearly random movements do not seem to form regular shapes. This effect shows the emergence of complex behavior from a set of simple rules, which is actually the whole point of the system. The situation becomes even more complex if we consider the interaction between several ants forming a colony. Interestingly, the trajectory of an ant on an empty board eventually stabilizes after around 10,000 iterations, when the ant begins building a straight “path”, consisting of smaller segments, each taking 104 steps to make (see Figure 6.19). Later experiments showed that Langton’s ant, like many other cellular automata (including “Life”), exhibits a property of computational universality. It means that an ant can theoretically perform any computational algorithm, encoded along with its input data in the initial configuration of the board.