Langton’s Ant & Musical Patterning I

Part 1 — Langton’s Ant Variations

What is Langton’s Ant?

Langton’s Ant is a cellular automaton created by Chris Langton in 1986. It explores the idea of alife, that is artificial life or life as it ‘could be’. I think of it as a thought experiment demonstrating that complex behaviours in the universe aren’t always the result of complex systems; sometimes incredibly simple systems, rules, or behaviours when scaled can create fascinatingly complex emergent behaviours. Think of snowflakes, flocking birds, the growth of plants, and of course, ants.

How does it work?

Langton’s original model works something like this: we start with a grid of cells and an agent or cursor referred to as ‘the ant’. Each cell can have one of two possible states, let’s call them ‘white’ and ‘black’. The ant is facing one of the four cardinal directions. The model proceeds in steps. Here is what happens at each step:

• If the cell the ant is on is white, the ant makes a quarter turn right; if the cell is black, the ant makes a quarter turn left
• The cell changes state; that is, if the cell is white, it turns black and if it is black it turns white
• The ant moves forward in whatever direction it is facing to an adjacent cell

Stage 1: Animation of first 200 steps (from Wikipedia)

What happens?

This is where it gets interesting. Over repeated iterations of the rule, the ant proceeds through three stages:

• Stage 1: at first it behaves somewhat systematically, making changes in an apparently symmetrical fashion. This goes on for a few hundred steps
• Stage 2: then it ‘breaks’, for lack of a better way to put it. It behaves chaotically, changing cells from one state to another in a pseudo random fasion for roughly the next ~10,000 iterations
• Stage 3: then comes ‘the highway’ — it creates the condition for a periodic cycle (104 steps) that self-replicates and will continue on to infinity

Stage 3:Langton’s Ant around step 10,300, just after it starts its highway

Expanding the model part 1: directions and states

Langton’s model has the ant either turning left or right. There are four cardinal directions, so really the ant could turn left, right, remain the direction it is facing, or turn around 180 degrees. I’ll refer to these directions as L,R, N (for ‘no change’), and B (for ‘back’). I don’t think there is any standardized way of referring to these directions.

Also Langton’s model had only two states for the cells, but there is no reason to limit to it to two. The cells of a system could have, in theory, an arbitrary number of states and we can assign an arbitrary colour to each state. Each state has a ‘rule’, that is a relative rotation to apply to the ant, and when the ant moves into that cell we will apply the rule.

We need to advance the state of a cell when the ant enters. Let’s assume that each state is designated by an integer value. If we have three states, it will advance from 0 → 1 → 2 → 0 → 1 and so on: the order is fixed, but it will always go back to the start after the last state.

We could make a rule with 3 states R L B. The first state (white) makes a cell turn right 90°, the second (orange) makes it turn left by 90°, and the 3rd (navy) 180° around, and it would look like this:

The first fifty odd steps for the rule RLB [1,-1,2]

The rule space is infinitely large, and most rules just behave chaotically, but there are some truly fascinating behaviours for a few rules when given enough time and space to iterate. These two interesting ones:

Rule LRRRRRLLR at ~80k steps: it creates the square around itself, and forms highways within the square. Each time it reaches the surface it traverses the outer perimeter 4 times expanding the area of the square

Rule RRLLLRLLLRRR at ~60k steps: it creates a triangle shape that grows and fills

Expanding the model part 2: hexagonal and triangular tiling, and diagonal motion

We naturally think of simple square grids for cellular automata, but if we change the geometry we get different results. When I first started exploring Langton’s ant, I came across this site which demonstrated how they could be applied on a hexagonal grid which really inspired my thinking on the subject.

We need to adjust the notation a little, but only a little. An ant on a square grid had four possible directions, and on a hexagonal grid, it has six. We can move left or right by either 60° or 120°, so let’s notate these by ±1 (or R1/L1) and ±2 (R2/L2) respectively. No change is still 0 (N), and 180° will be ±3 (B).

The first ~100 steps of Hexagonal Rule RL [1,-1]

Some hexagonal grid rules can sometimes provide good examples or large scale rotational behaviour like this:

Hexagonal rule L1 L2 N U L2 L1 R2, ~80k steps, the main motion is a small spiral but it collectively forms an ever growing spiral highway

Hexagonal rule L2 N N L1 L2 L1, after ~75k steps— sadly this becomes pseudo random shortly after this point

Tiling with triangles is also possible. With triangles, as with hexagons, there are 6 possible directions — but only three are available to each orientation (note that triangles will always point in one of two directions). Since all three triangles adjacent to an left facing triangle are right facing and vice versa, 60° turns are always possible, as are 180° — but for the other directions there are no adjacent cells.

The first ~100 steps of Triangular rule RL [1,-1]

If you look at the two gifs above for Hexagonal rule RL and Triangular rule RL, you’ll notice that they are actually forming the same pattern. The patterns formed by those three directions available to triangles (60°, -60° and 180°) are identical to those same rules generated by hexagons using those same directions (hexagons also have 120°, -120° and 0° rules available to them while triangles do not). Hexagons that only turn 60°, -60° and 180° are in fact behaving as if they are on a triangular grid. They will form a ‘honeycomb’ where certain spaces are unreachable:

A honeycomb pattern created form Hexagonal Rule [R,L] after roughly 100 steps

If you divide those empty spaces in the honeycomb into 6 small triangles, and attached them to their adjacent hexagons, you can see imagine where the triangles would be (credit to The Math Hatter for that insight):

Square grid with diagonal rules

You could also use the square grid but allow rules with diagonal motion. Ants can move at 45° angles in addition to the right angles. These systems tend to not have many simple rules that generate symmetrical patterns, but a number of these rule systems will quickly generate both simple and highly complex highways.

Square grid with diagonals rule LR (where R and L here are 45° turns) — it starts by four-way symmetrical flower-like pattern, but then becomes pseudo-random, and doesn’t form a highway within any reasonable time span

Expanding the model: multiple ants

Why limit the system to a single agent? There could be as many ants as you like, each interacting with the other. Things will get really complex really fast when one ant is creating states for another.

Two ants both with the 8-way rule R3 L2 U R2 L3 R1, forming immediate simple highways, then interacting with those highways

Continued in Langton’s Ant & Musical Patterning II which focuses on musical mappings and includes a number of links.

note: apart from the Wikipedia gif credited at the top, all other images and gifs included here are original creations