Langton's Ant
This article describes a uLisp program to explore Langton's Ant, a simple automaton that walks on a grid of black and white square cells:
The above photograph shows the program running on an Adafruit PyBadge, using the uLisp Graphics extensions. It takes advantage of the read-pixel function added in uLisp Release 4.9.
Introduction
Langton's Ant [1] is a two-dimensional automaton based on two simple rules but complex emergent behaviour. It was invented in 1986 by Chris Langton, an American computer scientist who worked at Los Alamos National Laboratory.
Rules
The ant starts in the centre of the display. The rules are:
- On a black square turn left, change the square to white, and move forward one square.
- On a white square turn right, change the square to black, and move forward one square.
After a few hundred moves, a large, irregular pattern of black and white squares appears. The ant traces a path that looks random until around 10,000 steps. Finally the ant heads off into the distance along a highway pattern of 104 steps that repeats indefinitely.
The program
Here's the program:
(defun langton-ant ()
(fill-screen)
(bind (xsize ysize) (display-size)
(let ((white #xffff) (black 0)
(x (truncate xsize 2))
(y (truncate ysize 2))
(dx 1) (dy 0) temp)
(loop
(cond
((not (and (< -1 x xsize) (< -1 y ysize))) (return))
((= (read-pixel x y) black)
(setq temp dx dx dy dy (- temp)) ; Left
(draw-pixel x y white))
(t ; White
(setq temp dy dy dx dx (- temp)) ; Right
(draw-pixel x y black)))
(incf x dx) (incf y dy)
(delay 5)))))
The program checks whether the ant has reached the edge of the screen, and if so, stops.
Extensions
The idea can be extended to multiple colours, with a different direction associated with each colour. For more details see the Wikipedia article.
- ^ Langton's Ant on Wikipedia.