Continuing on with the theme of universal Turing machines, Langton’s ant is as simple as it is clever.

A two-dimensional grid with an ant as our protagonist. Each square in the grid is either black or white. If the ant is on a white square it turns 90° clockwise and moves forward. If the ant is on a black square it turns 90° counter-clockwise and moves forward. Whichever square the ant lands on the colour of the square is flipped.

The code

All the code I’ve written in this blog can be found and executed here.

Most of the code written I’d stolen from The Game of Life blog as much of the boiler-plate can be used in both.

The code is relatively simple, the first step is to create the grid and initialise each square in the grid. Each square in my implementation is either 0,1,2 where 0 is white, 1 is black and 2 is the ant. As you can see, I am setting the entire grid to black, to begin with.

On each iteration — each execution of the draw function — I’m grabbing the square the ant is currently on currentSquare. I then check to see if that square is white or black, then either rotate left or right.

Fun fact: did you know that JavaScript cannot handle modulus for a negative number? So for the example -1 % 4 which should = 3, JavaScript returns -1. Hence the addition of a mod() function.

let grid;
let columns;
let rows;
let size = 20;
let dirs = ['N', 'E', 'S', 'W'];
let ant = { x: 10, y: 10, d: 'N'};

function setup() {
  createCanvas(800, 600);
  columns = width / size;
  rows = height / size;
  grid = createGrid();
  
  
  for (let i = 0; i < columns; i++) {
    for (let j = 0; j < rows; j++) {
      grid[i][j] = 1;
    }
  }
}

function draw() {
  background(0);
  let currentSquare = grid[ant.x][ant.y];
  grid[ant.x][ant.y] = 3;
  for (let i = 0; i < columns; i++) {
    for (let j = 0; j < rows; j++) {
      let x = i * size;
      let y = j * size;
      if (grid[i][j] == 3) {
        fill(0, 255, 255);
        stroke(0, 255, 255);
        rect(x, y, size, size);
      } 
      
      if (grid[i][j] == 1) {
        fill(0, 0, 0);
        stroke(0, 0, 0);
        rect(x, y, size, size);
      } 
      
      if (grid[i][j] == 0) {
        fill(255, 255, 255);
        stroke(255, 255, 255);
        rect(x, y, size, size);
      } 
    }
  }
  
  let newDirection;
  if (currentSquare == 0) { // white
    grid[ant.x][ant.y] = 1;
    let direction = ant.d;
    let newDirectionIndex = mod(dirs.findIndex(e => e == direction) + 1, 4);
    newDirection = dirs[newDirectionIndex];
    

  } else {
    grid[ant.x][ant.y] = 0;
    let direction = ant.d;
    let newDirectionIndex = mod(dirs.findIndex(e => e == direction) - 1, 4);
    newDirection = dirs[newDirectionIndex];
  }
  
  if (newDirection == 'N') {
    ant.y = mod(ant.y - 1, rows);
  } else if (newDirection == 'E') {
    ant.x = mod(ant.x + 1, columns);
  } else if (newDirection == 'W'){
    ant.x = mod(ant.x - 1, columns);
  } else {
    ant.y = mod(ant.y + 1, rows);
  } 
  ant.d = newDirection;
  
}

function  mod(n, m) {
  var remain = n % m;
  return Math.floor(remain >= 0 ? remain : remain + m);
}

function createGrid() {
  let arr = new Array(columns);
  for (let i = 0; i < arr.length; i++) {
    arr[i] = new Array(rows);
  }
  return arr;
}

Seeing it in action

Okay, that’s not gonna cut it. We need more. There’s just not enough room, to see any emergent patterns. Let’s update the code:

let grid;
let columns;
let rows;
let size = 4;
let dirs = ['N', 'E', 'S', 'W'];
let ant = { x: 10, y: 10, d: 'N'};

function setup() {
  createCanvas(800, 600);
  columns = width / size;
  rows = height / size;
  grid = createGrid();
  
  
  for (let i = 0; i < columns; i++) {
    for (let j = 0; j < rows; j++) {
      grid[i][j] = 1;
    }
  }
}

function draw() {
  for (let i = 0; i < 50; i++) {
    
    let currentSquare = grid[ant.x][ant.y];
    grid[ant.x][ant.y] = 3;
    let newDirection;
    if (currentSquare == 0) { // white
      grid[ant.x][ant.y] = 1;
      let x = ant.x * size;
      let y = ant.y * size;
      fill(0, 0, 0);
      stroke(0, 0, 0);
      rect(x, y, size, size);
      let direction = ant.d;
      let newDirectionIndex = mod(dirs.findIndex(e => e == direction) + 1, 4);
      newDirection = dirs[newDirectionIndex];


    } else {
      grid[ant.x][ant.y] = 0;
      let x = ant.x * size;
      let y = ant.y * size;
      fill(255, 255, 255);
      stroke(255, 255, 255);
      rect(x, y, size, size);
      let direction = ant.d;
      let newDirectionIndex = mod(dirs.findIndex(e => e == direction) - 1, 4);
      newDirection = dirs[newDirectionIndex];
    }

    if (newDirection == 'N') {
      ant.y = mod(ant.y - 1, rows);
    } else if (newDirection == 'E') {
      ant.x = mod(ant.x + 1, columns);
    } else if (newDirection == 'W'){
      ant.x = mod(ant.x - 1, columns);
    } else {
      ant.y = mod(ant.y + 1, rows);
    } 
    ant.d = newDirection;
  }
}

function  mod(n, m) {
  var remain = n % m;
  return Math.floor(remain >= 0 ? remain : remain + m);
}

function createGrid() {
  let arr = new Array(columns);
  for (let i = 0; i < arr.length; i++) {
    arr[i] = new Array(rows);
  }
  return arr;
}

This should do it:

How cool is that! Just from two very simple rules, such complicated, symmetrical patterns emerge.

Langtons ant has 3 stages: Simplicity (above), Chaos and emergent order.

Chaos

This stage is… chaos.

Emergent order

The final stage is emergent order, the ant builds itself a recurrent highway. All configurations eventually end up with the same pattern, supposedly. Olivier Beuret and Marco Tomassini state in their paper:

If the initial configuration of black and white cells are different, for example if there are scattered black cells in the grid at the beginning, the ant always ends up building the highway, at least on the many simulations that have been done, although nobody exactly knows if this is necessarily always the case.

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.179&rep=rep1&type=pdf

However, after running my simulation for over an hour I’ve not yet hit the pattern!

Conclusion

There’s so much more that can be done with this, countless different variations we can experiment with. I’ll explore some extensions to Langdon’s ant in a future blog!

If you liked this blog then please sign up for my newsletter and join an awesome community!!