Skip to content
Computational Lab.

Langton’s Ant

A two-rule machine that draws highways.

Beginner / cellular-automaton / emergence

An ant on a grid follows two rules: turn right on a black cell, left on a white one, then flip the cell and step forward. For the first few hundred steps it looks lost; then it builds a recurring diagonal highway. Nothing in the rules mentions a highway.

Tagged: cellular automaton, turing machine, emergence

Live simulation

Each step applies a fixed number of ant rules.

Speed

Each step applies a fixed number of ant rules.

Mathematics

The ant implements the simplest interesting rule machine on a grid: at each step, turn right on black or left on white, flip the cell's color, move forward one cell.

direction ← rotate(direction, ±90°) on black / white

cell ← 1 − cell; position ← position + heading

after ≈ 10,000 chaotic steps: unbounded diagonal highway, period 104

The highway is the famous result: the ant's seemingly random walk spontaneously organizes into a repeating construction pattern that extends forever. It has been proved that this two-rule ant is computationally universal; it can simulate any Turing machine given the right starting configuration.

How it works

The grid is a flat Uint8Array and the ant is four integers: position and heading. Each tick applies a fixed number of moves, flipping cells and counting the black population during the pass. Leaving the grid either wraps the torus or bounces the ant, depending on the edge mode.

Start from an empty grid and step slowly: the symmetric first few hundred steps, the messy middle, and the highway's emergence are all visible within a few thousand ticks.

Implementation

src/engine/experiments/langton-ant.ts · 131 lines · the module running above

TypeScript · fixed-timestep engine

1import { BaseExperiment } from "../core/base-experiment";
2import type { ParameterDef, ThemeColors } from "../core/types";
3
4/**
5 * Langton's ant: a two-dimensional Turing machine. One tick applies a fixed
6 * number of move rules. Simple, deterministic, and a perfect demonstration
7 * that computed behavior can look designed without being designed.
8 */
9export class LangtonAntExperiment extends BaseExperiment {
10 readonly id = "langton-ant";
11
12 private cols = 0;
13 private rows = 0;
14 private offsetX = 0;
15 private offsetY = 0;
16 private cells = new Uint8Array(0);
17 private x = 0;
18 private y = 0;
19 private dir = 0; // 0 up, 1 right, 2 down, 3 left
20 private steps = 0;
21 private blackCells = 0;
22
23 protected params(): ParameterDef[] {
24 return [
25 { key: "cell", label: "Cell size", min: 3, max: 12, step: 1, defaultValue: 6, unit: "px" },
26 { key: "rate", label: "Steps per tick", min: 1, max: 100, step: 1, defaultValue: 8 },
27 { key: "density", label: "Initial noise", min: 0, max: 30, step: 1, defaultValue: 0, unit: "%" },
28 {
29 key: "edges",
30 label: "Edges",
31 options: [
32 { value: "wrap", label: "Wrap (torus)" },
33 { value: "closed", label: "Bounce" },
34 ],
35 defaultValue: "wrap",
36 },
37 ];
38 }
39
40 protected onReset(): void {
41 this.cols = Math.max(8, Math.floor(this.width / this.num("cell")));
42 this.rows = Math.max(8, Math.floor(this.height / this.num("cell")));
43 this.offsetX = Math.floor((this.width - this.cols * this.num("cell")) / 2);
44 this.offsetY = Math.floor((this.height - this.rows * this.num("cell")) / 2);
45 this.cells = new Uint8Array(this.cols * this.rows);
46 const density = this.num("density") / 100;
47 for (let i = 0; i < this.cells.length; i++) {
48 this.cells[i] = this.rng() < density ? 1 : 0;
49 }
50 this.x = this.cols >> 1;
51 this.y = this.rows >> 1;
52 this.dir = 0;
53 this.steps = 0;
54 this.blackCells = 0;
55 for (let i = 0; i < this.cells.length; i++) this.blackCells += this.cells[i];
56 }
57
58 protected onParameterChange(key: string): void {
59 if (key !== "rate") this.reset();
60 }
61
62 resize(width: number, height: number): void {
63 this.width = width;
64 this.height = height;
65 this.reset();
66 }
67
68 protected onUpdate(): void {
69 const rate = this.num("rate");
70 const wrap = this.str("edges") === "wrap";
71 for (let s = 0; s < rate; s++) {
72 const i = this.y * this.cols + this.x;
73 const black = this.cells[i] === 1;
74 // Turn right on black, left on white; then flip the cell and move.
75 this.dir = (this.dir + (black ? 1 : 3)) % 4;
76 this.cells[i] = black ? 0 : 1;
77 this.blackCells += black ? -1 : 1;
78 if (this.dir === 0) this.y -= 1;
79 else if (this.dir === 1) this.x += 1;
80 else if (this.dir === 2) this.y += 1;
81 else this.x -= 1;
82 if (wrap) {
83 this.x = (this.x + this.cols) % this.cols;
84 this.y = (this.y + this.rows) % this.rows;
85 } else {
86 if (this.x < 0 || this.y < 0 || this.x >= this.cols || this.y >= this.rows) {
87 // Bounce back into the grid and reverse.
88 this.x = Math.min(this.cols - 1, Math.max(0, this.x));
89 this.y = Math.min(this.rows - 1, Math.max(0, this.y));
90 this.dir = (this.dir + 2) % 4;
91 }
92 }
93 this.steps += 1;
94 }
95 }
96
97 render(ctx: CanvasRenderingContext2D, theme: ThemeColors): void {
98 const { cols, rows, offsetX, offsetY } = this;
99 const cell = this.num("cell");
100 ctx.fillStyle = theme.bg;
101 ctx.fillRect(0, 0, this.width, this.height);
102 ctx.fillStyle = theme.fg;
103 for (let y = 0; y < rows; y++) {
104 for (let x = 0; x < cols; x++) {
105 if (this.cells[y * cols + x] === 1) {
106 ctx.fillRect(offsetX + x * cell, offsetY + y * cell, cell - 1, cell - 1);
107 }
108 }
109 }
110 ctx.fillStyle = theme.accent;
111 ctx.fillRect(offsetX + this.x * cell, offsetY + this.y * cell, cell - 1, cell - 1);
112 }
113
114 getMetrics() {
115 return {
116 steps: this.steps,
117 blackCells: this.blackCells,
118 position: `${this.x}, ${this.y}`,
119 heading: ["up", "right", "down", "left"][this.dir],
120 };
121 }
122
123 describe(): string {
124 return `The ant has taken ${this.steps.toLocaleString("en-US")} steps and flipped ${this.blackCells.toLocaleString("en-US")} cells to black.`;
125 }
126
127 entities(): number {
128 return this.cols * this.rows;
129 }
130}
131

Performance

Time per tick
O(steps per tick) with an O(1) rule per step
Space
One byte per cell plus four integers of ant state
Notes
The initial-noise parameter tests how sturdy the highway is: scatter random black cells and the ant still finds its road.

Live numbers (FPS, frame time, steps per second, microseconds per step, entity count) are in the performance overlay on the simulation above: the pulse icon in its top-right corner.