Ant Highway No Blueprint

Christopher Langton introduced this system in a 1986 Physica D paper titled "Studying Artificial Life with Cellular Automata." The rules fit in a single sentence: on a white cell, turn right, flip the cell to black, step forward; on a black cell, turn left, flip to white, step forward. Two states, two turns, one step. That's the entire specification.

The ant's trajectory passes through three distinct regimes. For the first few hundred steps it traces small symmetric patterns. Then chaos: a growing, irregular blob that looks random. Around step 10,000 something unexpected happens. The ant breaks free of the blob and begins constructing a diagonal highway, a repeating 104-step cycle that extends forever. Nobody proved this must happen until 2000 (Cohen and Kong, Annals of Combinatorics), and the proof required showing the highway pattern is an attractor for every finite initial perturbation tested. A general proof for arbitrary initial conditions remains open.

The implementation in the gallery runs the core loop as a tight for over all active ants each frame:

function tick(){
  for(const a of ants){
    const i=a.y*cols+a.x;
    const s=grid[i];
    // RL rule: state 0 turn right (+1), state 1 turn left (-1)
    a.d=((a.d+(s===0?1:-1))+4)%4;
    grid[i]=1-s;
    a.x=(a.x+DX[a.d]+cols)%cols;
    a.y=(a.y+DY[a.d]+rows)%rows;
  }
  step++;
}

The direction update (a.d+(s===0?1:-1)+4)%4 encodes the entire RL rule table in one expression. Grid cells are a Uint8Array toggled with 1-s, so the whole simulation stays branch-free per cell. Rendering writes directly into an ImageData buffer, one pass per pixel, which keeps the frame budget tight enough to run 50 steps per animation frame on a phone.

Langton's original interest was self-reproduction, following von Neumann's tradition of asking what minimal systems can compute. The ant sits at the boundary: simple enough to state on a napkin, complex enough that predicting whether the highway emerges from a given starting configuration is undecidable in general. It belongs to the same family as the Wolfram and Life artifacts in this gallery, each one a different answer to the question of how much structure two or three rules can generate from nothing.