Langton's Ant

Langton's Ant is a simulation which has a simple set of rules, which can produce surprisingly complicated results. It is a great example of a Chaotic System, as is the case with most Cellular Automata.

Try it in your browser now

This project includes:

1. The core simulation engine
2. A website which can run and render the simulation
3. A specification, syntax and compiler for a simple language to express the rules of such a system

• Introduction
• Example Simulations
• Ant Programs
  • The Transformation Matrix
  • Program Syntax
  • Shorthand Ant Programs
• Developing
  • Running the Code
  • Deploying the Code
  • CI/CD
  • URL Parameters
• References

Introduction

Clone the code and run:

npm i && npm start

To run the project locally, and check the Developer Guide to see how to work with the code.

Example Simulations

Some interesting example simulations are below.

Screenshot	Description
	Langton's Ant For the first few moves, shows simple patterns. Quickly becomes chaotic, then forms a highway after about 10,000 moves. LR Open In Browser
	Fibonnaci Spiral This is actually a Turmite program. It forms an ever growing Fibonacci Spiral: (1,L,1),(1,L,0) (0,R,1),(1,0,1) Open In Browser
	Symmetric Growing Lines A pair of lines which grow forever. (1, 0, 1), (1, L, 1) (0, R, 1), (1, 0, 1) Open In Browser
	Magic Pyramid A pyramid which grows one side at a time. (1, 0, 1), (0, L, 1) (0, R, 1), (1, 0, 1) Open In Browser
	Snail Shell A snail shell. (1,R,0) (0,L,1) (0,L,1) (1,R,1) Open In Browser
	Spiral A spiral, weirdly resilient to traps, toggling tiles in the path of the ant has minor effects, but I have not been able to shake it off the spiral path, which is bizarre. (1,0,1) (0,L,0) (0,R,1) (1,0,1) Open In Browser

Ant Programs

Langton's Ant is a trivial example of a Turmite. To allow different configurations to easily be conastructed and shared, I have defined a syntax for a 'program'. A program is simply the set of rules for the system.

The program syntax is designed to make it easy to express the rules of the system with plain text, in a readable format:

The simulation applies the rules of the matrix to a given state, producting a new state.

An interface is layered on top. It renders the state, runs the simulation and provides controls to configures parameters.

The Transformation Matrix

Before understanding how a program works, it is important to understand the transformation matrix.

The transformation matrix is the complete set of rules for a turmite or ant simulation. The universe looks like this:

An element of the transformation defines that when the ant is in a given ant state and on a tile with a given tile state, what ant direction change will be made, and what tile state change will occur on the tile the ant leaves. This is a three-tuple:

(Ant State Change, Ant Direction Change, Tile State Change)

For example:

• (1, 90, 0): Ant State increases 1, Ant turns 90 clockwise, Tile State increases 0
• (0, -90, 1): Ant State increases 0, Ant turns 90 counter-clockwise, Tile State increases 1

The Transformation Matrix is the complete set of state transformations which are required to define a complete set of rules.

For example:

|      | T: 0      | T: 1      |
|------|-----------|-----------|
| a: 0 | (1,-90,1) | (1,-90,0) |
| a: 1 | (0,90,1)  | (0,0,1)   |

In this matrix (which defines a Fibonacci Spiral Turmite) we see the transformations which are applied for every combination of ant state and tile state.

Directions can be specified in degrees (as above), or using L for left, R for right and U for U-turn (-90, 90 and 180 degrees respectively).

Program Syntax

A program is just a representation of each element in the matrix. For example, the spiral matrix above can be written as:

(1,-90,1) (1,-90,0)
(0,90,1)  (0,0,1)

One of the goals of this project is to facilitate the easy sharing of this matrix. Readability and compactness are important. The compiler which builds the matrix from the input follows the following rules:

0. If the program only contains L or R characters, it is expanded from shorthand, as described in the section on Shorthand Ant Transformation Matrices
1. Any semi-colon is converted into a newline (allowing a program to be written on a single line if needed
2. All whitespace is eliminated, except the newline at the end of each row
3. Commas are optional between tuples
4. If the matrix is not rectangular, or there are an incorrect number of tuples, an error is thrown

The compiler itself can be used with the following code:

const { compiler } = require('langtonsant');

const input = `
  (1, L, 1) (1, L, 1)
  (1, R, 1) (0, 0, 0)
`;

const matrix = compiler(input);

console.log(matrix);

Shorthand Ant Programs

The Langton's Ant transformation matrix is just a trivial form of a Turmite transformation matrix. An Ant is a Turmite which only has one state.

An ant program can be expressed using the full syntax above, or in a more compact form, composed just of Ls and Rs, e.g:

LLRL

Which is just shorthand for the following matrix:

|      | T: 0        | T: 1        | T: 2        | T: 3        |
|------|-------------|-------------|-------------|-------------|
| a: 0 | (0, -90, 1) | (0, -90, 1) | (0, +90, 1) | (0, -90, 1) |

i.e.          L             L             R             L

Developing

Running the Code

Just clone the repo, then run:

npm install && npm start

To install dependencies and run the simulation in development mode.

Deploying the Code

The site is published to GitHub Pages at dwmkerr.github.io/langtonsant. Every push to master that passes lint and tests builds dist/ and deploys it; there is nothing to run by hand. To check the production build locally:

make serve

CI/CD

The pipeline is a single GitHub Actions workflow, main.yml:

1. Every push and pull request lints and tests.
2. A push to master that passes deploys to GitHub Pages.
3. Pushing a semver tag (v*) publishes to NPM (needs the NPM_TOKEN secret).

Bump the version with npm run release.

URL Parameters

A set of parameters can be provided in the URL.

Parameter	Usage
p	The program string, e.g. LLRL.

References

Very useful information came from:

• https://github.com/rm-hull/turmites