Langton's Ant

Introduction

Picture a tiny ant standing on an infinite grid of white squares. It follows exactly two rules, applied on every step:

On a white square — turn right 90°, flip the square to black, move one step forward.
On a black square — turn left 90°, flip the square to white, move one step forward.

That is the whole program. No memory, no goal, no randomness. Langton's ant, invented by computer scientist Christopher Langton in 1986, is one of the simplest imaginable two-dimensional automata.

For the first few hundred steps it seems aimless. By step 500 it has scratched out a roughly symmetric scribble. By step 5,000 it looks pure chaos — an apparently random smear of black and white. Then, somewhere between step 9,000 and 11,000, something unexpected happens. The ant locks into a fixed 104-step cycle that carries it diagonally across the grid forever. Researchers call this the highway.

Nobody predicted the highway from the rules. It was discovered by running simulations. And despite decades of study, we still cannot prove — from the rules alone — that the highway always appears, or predict exactly when it starts. That gap between rules and outcome is the deep story here.

Watch the Highway Emerge

Run the simulation below. The ant starts at the centre of the grid facing up. Use the buttons to step slowly through the chaos phase, then jump ahead and watch the highway snap into place.

<div class="controls">
  <button id="btn-step" type="button">Step</button>
  <button id="btn-run" type="button">Run</button>
  <button id="btn-pause" type="button" disabled>Pause</button>
  <button id="btn-jump" type="button">Jump to ~10k</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div class="info-bar">
  <span id="step-count">Step: 0</span>
  <span id="phase-label" class="phase chaos">Phase: chaos</span>
</div>
<canvas id="canvas" width="380" height="300"></canvas>
<p class="hint">Watch the ant wander chaotically, then snap into a repeating diagonal highway around step 10,000.</p>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; background: #fff; }
.controls { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui, sans-serif; padding: .38rem .75rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 7px; cursor: pointer; transition: opacity .15s; }
button:disabled { opacity: .4; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }
.info-bar { display: flex; gap: 1rem; align-items: center; margin-bottom: .4rem;
            font-size: .88rem; font-weight: 600; }
#step-count { color: #444; }
.phase { padding: .15rem .55rem; border-radius: 99px; font-size: .8rem; }
.phase.chaos { background: #fde8e8; color: #b91c1c; }
.phase.highway { background: #d1fae5; color: #065f46; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; display: block;
         image-rendering: pixelated; width: 380px; height: 300px; }
.hint { font-size: .82rem; color: #555; margin: .5rem 0 0; line-height: 1.4; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Langton's Ant simulation
// Rules: on WHITE turn right, flip to BLACK, step forward.
//        on BLACK turn left, flip to WHITE, step forward.
// After ~10,000 steps the ant enters a 104-step repeating "highway" cycle.

const CANVAS_W = 380, CANVAS_H = 300;
const CELL = 4;                      // pixels per cell
const COLS = Math.floor(CANVAS_W / CELL);   // 95
const ROWS = Math.floor(CANVAS_H / CELL);   // 75

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

// Grid stored as a flat Uint8Array (0=white, 1=black)
let grid, antX, antY, antDir, stepCount, running, timer;

// Directions: 0=up, 1=right, 2=down, 3=left
const DX = [0, 1, 0, -1];
const DY = [-1, 0, 1, 0];

function init() {
  grid = new Uint8Array(COLS * ROWS);  // all white
  antX = Math.floor(COLS / 2);
  antY = Math.floor(ROWS / 2);
  antDir = 0; // facing up
  stepCount = 0;
  running = false;
  clearInterval(timer);
  document.getElementById('btn-pause').disabled = true;
  document.getElementById('btn-run').disabled = false;
  updateInfoBar();
  draw();
}

function step() {
  const idx = antY * COLS + antX;
  const color = grid[idx];

  // Turn: white -> right (+1), black -> left (-1)
  antDir = (antDir + (color === 0 ? 1 : 3)) % 4;

  // Flip cell
  grid[idx] = color === 0 ? 1 : 0;

  // Move forward
  antX += DX[antDir];
  antY += DY[antDir];

  // Wrap (toroidal grid so ant doesn't vanish off edge)
  antX = ((antX % COLS) + COLS) % COLS;
  antY = ((antY % ROWS) + ROWS) % ROWS;

  stepCount++;
}

function draw() {
  // Draw the grid
  const imgData = ctx.createImageData(CANVAS_W, CANVAS_H);
  const data = imgData.data;

  for (let row = 0; row < ROWS; row++) {
    for (let col = 0; col < COLS; col++) {
      const cell = grid[row * COLS + col];
      const r = cell === 1 ? 30 : 240;
      const g = cell === 1 ? 40 : 245;
      const b = cell === 1 ? 58 : 250;
      for (let py = 0; py < CELL; py++) {
        for (let px = 0; px < CELL; px++) {
          const pi = ((row * CELL + py) * CANVAS_W + col * CELL + px) * 4;
          data[pi] = r; data[pi+1] = g; data[pi+2] = b; data[pi+3] = 255;
        }
      }
    }
  }
  ctx.putImageData(imgData, 0, 0);

  // Draw ant as a red dot
  ctx.fillStyle = '#e63946';
  ctx.beginPath();
  ctx.arc(antX * CELL + CELL/2, antY * CELL + CELL/2, CELL * 0.7, 0, Math.PI * 2);
  ctx.fill();
}

function isHighway() {
  // After 10,450+ steps the ant has reliably started the highway
  return stepCount >= 10450;
}

function updateInfoBar() {
  document.getElementById('step-count').textContent = fmt('Step: %stepCount%', { stepCount: stepCount.toLocaleString() });
  const lbl = document.getElementById('phase-label');
  if (isHighway()) {
    lbl.textContent = 'Phase: highway!';
    lbl.className = 'phase highway';
  } else {
    lbl.textContent = 'Phase: chaos';
    lbl.className = 'phase chaos';
  }
}

document.getElementById('btn-step').addEventListener('click', () => {
  if (running) return;
  step();
  draw();
  updateInfoBar();
});

document.getElementById('btn-run').addEventListener('click', () => {
  if (running) return;
  running = true;
  document.getElementById('btn-run').disabled = true;
  document.getElementById('btn-pause').disabled = false;
  // Run ~30 steps per frame for smooth animation
  timer = setInterval(() => {
    for (let i = 0; i < 30; i++) step();
    draw();
    updateInfoBar();
  }, 33);
});

document.getElementById('btn-pause').addEventListener('click', () => {
  running = false;
  clearInterval(timer);
  document.getElementById('btn-run').disabled = false;
  document.getElementById('btn-pause').disabled = true;
});

document.getElementById('btn-jump').addEventListener('click', () => {
  // Jump to step 10,500 quickly without drawing intermediate frames
  if (running) {
    clearInterval(timer);
    running = false;
    document.getElementById('btn-run').disabled = false;
    document.getElementById('btn-pause').disabled = true;
  }
  const target = 10500;
  while (stepCount < target) step();
  draw();
  updateInfoBar();
});

document.getElementById('btn-reset').addEventListener('click', init);

init();

<div class="controls">
  <button id="btn-step" type="button">Step</button>
  <button id="btn-run" type="button">Run</button>
  <button id="btn-pause" type="button" disabled>Pause</button>
  <button id="btn-jump" type="button">Jump to ~10k</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div class="info-bar">
  <span id="step-count">Step: 0</span>
  <span id="phase-label" class="phase chaos">Phase: chaos</span>
</div>
<canvas id="canvas" width="380" height="300"></canvas>
<p class="hint">Watch the ant wander chaotically, then snap into a repeating diagonal highway around step 10,000.</p>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; background: #fff; }
.controls { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui, sans-serif; padding: .38rem .75rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 7px; cursor: pointer; transition: opacity .15s; }
button:disabled { opacity: .4; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }
.info-bar { display: flex; gap: 1rem; align-items: center; margin-bottom: .4rem;
            font-size: .88rem; font-weight: 600; }
#step-count { color: #444; }
.phase { padding: .15rem .55rem; border-radius: 99px; font-size: .8rem; }
.phase.chaos { background: #fde8e8; color: #b91c1c; }
.phase.highway { background: #d1fae5; color: #065f46; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; display: block;
         image-rendering: pixelated; width: 380px; height: 300px; }
.hint { font-size: .82rem; color: #555; margin: .5rem 0 0; line-height: 1.4; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Langton's Ant simulation
// Rules: on WHITE turn right, flip to BLACK, step forward.
//        on BLACK turn left, flip to WHITE, step forward.
// After ~10,000 steps the ant enters a 104-step repeating "highway" cycle.

const CANVAS_W = 380, CANVAS_H = 300;
const CELL = 4;                      // pixels per cell
const COLS = Math.floor(CANVAS_W / CELL);   // 95
const ROWS = Math.floor(CANVAS_H / CELL);   // 75

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

// Grid stored as a flat Uint8Array (0=white, 1=black)
let grid, antX, antY, antDir, stepCount, running, timer;

// Directions: 0=up, 1=right, 2=down, 3=left
const DX = [0, 1, 0, -1];
const DY = [-1, 0, 1, 0];

function init() {
  grid = new Uint8Array(COLS * ROWS);  // all white
  antX = Math.floor(COLS / 2);
  antY = Math.floor(ROWS / 2);
  antDir = 0; // facing up
  stepCount = 0;
  running = false;
  clearInterval(timer);
  document.getElementById('btn-pause').disabled = true;
  document.getElementById('btn-run').disabled = false;
  updateInfoBar();
  draw();
}

function step() {
  const idx = antY * COLS + antX;
  const color = grid[idx];

  // Turn: white -> right (+1), black -> left (-1)
  antDir = (antDir + (color === 0 ? 1 : 3)) % 4;

  // Flip cell
  grid[idx] = color === 0 ? 1 : 0;

  // Move forward
  antX += DX[antDir];
  antY += DY[antDir];

  // Wrap (toroidal grid so ant doesn't vanish off edge)
  antX = ((antX % COLS) + COLS) % COLS;
  antY = ((antY % ROWS) + ROWS) % ROWS;

  stepCount++;
}

function draw() {
  // Draw the grid
  const imgData = ctx.createImageData(CANVAS_W, CANVAS_H);
  const data = imgData.data;

  for (let row = 0; row < ROWS; row++) {
    for (let col = 0; col < COLS; col++) {
      const cell = grid[row * COLS + col];
      const r = cell === 1 ? 30 : 240;
      const g = cell === 1 ? 40 : 245;
      const b = cell === 1 ? 58 : 250;
      for (let py = 0; py < CELL; py++) {
        for (let px = 0; px < CELL; px++) {
          const pi = ((row * CELL + py) * CANVAS_W + col * CELL + px) * 4;
          data[pi] = r; data[pi+1] = g; data[pi+2] = b; data[pi+3] = 255;
        }
      }
    }
  }
  ctx.putImageData(imgData, 0, 0);

  // Draw ant as a red dot
  ctx.fillStyle = '#e63946';
  ctx.beginPath();
  ctx.arc(antX * CELL + CELL/2, antY * CELL + CELL/2, CELL * 0.7, 0, Math.PI * 2);
  ctx.fill();
}

function isHighway() {
  // After 10,450+ steps the ant has reliably started the highway
  return stepCount >= 10450;
}

function updateInfoBar() {
  document.getElementById('step-count').textContent = fmt('Step: %stepCount%', { stepCount: stepCount.toLocaleString() });
  const lbl = document.getElementById('phase-label');
  if (isHighway()) {
    lbl.textContent = 'Phase: highway!';
    lbl.className = 'phase highway';
  } else {
    lbl.textContent = 'Phase: chaos';
    lbl.className = 'phase chaos';
  }
}

document.getElementById('btn-step').addEventListener('click', () => {
  if (running) return;
  step();
  draw();
  updateInfoBar();
});

document.getElementById('btn-run').addEventListener('click', () => {
  if (running) return;
  running = true;
  document.getElementById('btn-run').disabled = true;
  document.getElementById('btn-pause').disabled = false;
  // Run ~30 steps per frame for smooth animation
  timer = setInterval(() => {
    for (let i = 0; i < 30; i++) step();
    draw();
    updateInfoBar();
  }, 33);
});

document.getElementById('btn-pause').addEventListener('click', () => {
  running = false;
  clearInterval(timer);
  document.getElementById('btn-run').disabled = false;
  document.getElementById('btn-pause').disabled = true;
});

document.getElementById('btn-jump').addEventListener('click', () => {
  // Jump to step 10,500 quickly without drawing intermediate frames
  if (running) {
    clearInterval(timer);
    running = false;
    document.getElementById('btn-run').disabled = false;
    document.getElementById('btn-pause').disabled = true;
  }
  const target = 10500;
  while (stepCount < target) step();
  draw();
  updateInfoBar();
});

document.getElementById('btn-reset').addEventListener('click', init);

init();

Result

Console

Notice the moment the highway begins: the grid goes from looking random to moving in a perfectly repeating diagonal stripe. The Step button lets you advance one move at a time. Run plays it at speed. Jump to ~10k skips straight to where the highway usually appears. Reset starts fresh.

The two rules are entirely deterministic — if you re-run with the same starting position you get exactly the same path. Yet predicting the highway's start time without running the simulation is, as far as we know, impossible.

The Real Complexity

How hard is reasoning about Langton's ant?

Checking one step is trivial: look at the current colour, apply the rule, flip, move. $O(1)$ per step.
Simulating n steps costs $O(n)$ time — straightforward but provides no shortcut to the answer.
It is Turing-complete. In 2002 Gajardo, Moreira, and Goles proved that a slight generalisation of Langton's ant can simulate any Turing machine. This means the ant can, in principle, compute anything a computer can. It also means that general questions about its long-run behaviour are undecidable — no algorithm can decide, for every possible starting configuration, whether a given cell will ever turn black.
The highway conjecture is open. The widely observed fact that every symmetric starting configuration eventually enters highway mode has never been proved. Proving or disproving it may require fundamentally new mathematics.

The situation is structurally similar to the halting problem: two lines of rules, infinite consequences, no shortcut. Turing-completeness is the reason simple systems can be so hard to reason about — they have enough power to encode any computation, and therefore any undecidable question.

Compare this with cellular automata: like the Busy Beaver function, the ant's long-run behaviour can grow in complexity far beyond what any finite analysis can capture.

Where It Matters

"Simple local rules that produce unexpected global structure" is one of the central themes of modern computer science and mathematics, and Langton's ant is its most vivid demonstration:

Emergent computation: the ant shows that you do not need to program order — it can arise spontaneously. This underpins cellular automata research, artificial life, and the study of how biological complexity can evolve from chemical rules.
Swarm robotics: robots with simple collision-avoidance rules can collectively solve navigation problems that none could solve alone. The ant is a minimal proof-of-concept for this idea.
Network and traffic modelling: self-organising routing protocols borrow the intuition that local decisions can globally optimise flow without central coordination.
Cryptography and pseudorandomness: the long chaotic phase before the highway looks statistically random. Understanding when and why such phases end connects to questions about deterministic generators of randomness.
Teaching undecidability: unlike the abstract halting problem, Langton's ant makes undecidability concrete and visual — you can watch it happen.

The ant also has a place in physics: its behaviour is studied alongside thermodynamic reversibility (each step is reversible) and entropy, connecting computational and physical notions of order and disorder.

Conclusion

Langton's ant is a masterclass in humility. Two rules, deterministic, no hidden state — and yet it produces thousands of steps of apparent chaos before snapping into an ordered highway that no one proved would come. It is Turing-complete, so questions about its ultimate behaviour are in the same undecidable territory as the halting problem.

The lesson is not that the ant is complicated. The lesson is that complexity is not a property of rules — it is a property of the interaction between rules and time. Given enough steps, even the simplest program can outpace our ability to reason about it without just running it.

That is the quietly alarming thing the ant demonstrates: in a deterministic universe, surprise is still possible — and sometimes, provably unavoidable.

Comments

Loading comments...

https://www.kipuhub.com/en/article/langtons-ant/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Two rules. Ten thousand steps of chaos. Then a highway that never ends.