I’ve been covering some heavy topics lately with my Stack Machine & Compiler series, so I figured I would break things up with a light interlude on a topic that is both fascinating, easy to follow, and most of all fun: Cellular Automata.
Cellular automatons, such as John Conways “The Game of Life”, and in particular Langton’s Ant are very simple state machines – usually confined to a 2-dimensional grid – that despite their simplicity can exhibit complex “emergent behavior”. That is, by applying the rules in the state machines transition table, seemingly intelligent movements began to take place. By tweaking the rules, or running multiple state machines in parallel in the same “world”, different and even more complex behaviors can emerge.
In this post, I will piece together an implementation of Langton’s ant with extensible parameters for things like number of ants, size of grid/infinite grid, number of states, and use Java’s Swing Library to produce the output.
Langton’s Ant
In it’s most basic form Langton’s ant is confined to a 2-dimensional NxM grid comprised of tiles who’s color is either black or white. The color of the tile is one of 2 inputs to the state machine that determines the sequence of actions the ant takes next. The other input the to the state machine is an internal state relative to the ant: which direction the ant is facing. Based on the value of these two inputs, the ant can determine what to do next:
- At a white square, turn 90° clockwise, flip the color of the square, and move forward one unit
- At a black square, turn 90° counter-clockwise, flip the color of the square, and move forward one unit
You may notice that the last instruction is vague, “move forward one unit”, by using the term “forward” instead of listing one of the four cardinal directions the ant can move in, we can infer that forward is another relative state. The meaning of “forward” is entirely dependent on the internal directional state of the ant, and this is partially what leads to interesting emergent behavior.
A World for Ants
Seeing as the ant needs a world to interact with, it makes sense that we should construct the world first. Our world will be a simple class that contains the grid for the ant, and the ant itsself. The grid is made of Tiles, which are a struct with an x/y position, and a color.
// Point.java
public class Point {
public int x;
public int y;
Point(int _x, int _y) {
this.x = _x;
this.y = _y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public void setX(int _x) {
this.x = _x;
}
public void setY(int _y) {
this.y = _y;
}
}
//TileColor.java
public enum TileColor {
WHITE,
BLACK;
}
//Tile.java
public class Tile extends Point {
public TileColor tileColor;
Tile(int x, int y, TileColor color) {
super(x, y);
tileColor = color;
}
public void setTileColor(TileColor tileColr) {
this.tileColor = tileColr;
}
public TileColor getTileColor() {
return tileColor;
}
}
//Direction.java
public enum Direction {
NORTH,
SOUTH,
EAST,
WEST;
}
//World.java
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
public class World {
public static int HEIGHT;
public static int WIDTH;
public Tile[][] grid;
public List<Ant> ants;
public int numIters;
public World(int maxIters, int numAnts, int ht, int wt) {
HEIGHT = ht;
WIDTH = wt;
grid = (Tile[][]) new Tile[HEIGHT][WIDTH];
for (int i = 0; i < HEIGHT; i++) {
for (int j = 0; j < WIDTH; j++) {
grid[i][j] = new Tile(j,i , TileColor.WHITE);
}
}
numIters = maxIters;
ants = new LinkedList<Ant>();
Random rng = new Random();
for (int i = 0; i < numAnts; i++) {
ants.add(new Ant(rng.nextInt(WIDTH), rng.nextInt(HEIGHT), Direction.NORTH, HEIGHT, WIDTH));
}
}
void doStep() {
for (int i = 0; i < numIters; i++)
for (Ant ant : ants) {
ant.move(grid);
}
}
}
The doStep() function is for stepping through the iterations, or “ticks” of the world, and we also need a function for rendering the world in some visual way. We will return to both of these functions in a moment.
Bringing Ants to Life
As mentioned above, the ant interacts with its environment, making movements based on the color of the tile its standing on, and its own relative direction. This means that our Ant needs to store its current location, and its current direction.
The compass List is indexed using the Direction enum class and stores offsets for adding to the ants current location relative to the direction they should move. This is populated in the constructor, and utilized in the move function. The move method and turnRight()/turnLeft() methods is the actual transition table for changing states, using the switch case method of state machine implementation:
//Ant.java
import java.util.List;
public class Ant {
public static int HEIGHT;
public static int WIDTH;
private Point location;
private List<Point> compass;
private Direction direction;
public Ant(int sx, int sy, Direction sdirection, int ht, int wt) {
HEIGHT = ht;
WIDTH = wt;
direction = sdirection;
location = new Point(sx, sy);
compass = List.of(new Point(0, -1), new Point(0, 1), new Point(1, 0), new Point(-1, 0));
}
public void move(Tile[][] grid) {
switch (grid[location.getY()][location.getX()].getTileColor()) {
case BLACK:
turnRight();
grid[location.getY()][location.getX()].setTileColor(TileColor.WHITE);
break;
case WHITE:
turnLeft();
grid[location.getY()][location.getY()].setTileColor(TileColor.BLACK);
break;
}
location.setX(Math.abs(((location.getX() + compass.get(direction.ordinal()).getX()) + WIDTH) % WIDTH));
location.setY(Math.abs(((location.getY() + compass.get(direction.ordinal()).getY()) + HEIGHT) % HEIGHT));
}
public Point getLocation() {
return location;
}
private void turnRight() {
switch(direction) {
case NORTH:
direction = Direction.EAST;
break;
case SOUTH:
direction = Direction.WEST;
break;
case EAST:
direction = Direction.SOUTH;
break;
case WEST:
direction = Direction.NORTH;
break;
}
}
private void turnLeft() {
switch(direction) {
case NORTH:
direction = Direction.WEST;
break;
case SOUTH:
direction = Direction.EAST;
break;
case EAST:
direction = Direction.NORTH;
break;
case WEST:
direction = Direction.SOUTH;
break;
}
}
}
You can see that we do a little fancy foot work when calculating the next coordinate to place the ant, this is done because for this particular implementation I decided to “wrap” the edges of the grid to make it an “infinite” grid. This is not strictly necessary, and can be otherwise handled by using an “out of bounds” check on the proposed next location instead.
It… Is… ALIVE!!!
Ok, not quite, but we are ready to put some pep in the step of our cellular automaton. We start by peppering the grid with N ants, each facing in a random direction. We then repeatedly call Ant.move() N number of iterations for each ant see what happens.
//Langton.java
import java.awt.Color;
import java.awt.Graphics;
import javax.swing.JFrame;
import javax.swing.JPanel;
public class Langton extends JFrame {
private World world;
private JPanel panel;
private static final int ZOOM = 4;
public Langton() {
world = new World(27000, 9, 175, 300);
panel = new JPanel() {
@Override
public void paint(Graphics g) {
world.doStep();
for (int y = 0; y < world.HEIGHT; y++) {
for (int x = 0; x < world.WIDTH; x++) {
g.setColor(world.grid[y][x].getTileColor() == TileColor.WHITE ? Color.WHITE:Color.BLACK);
g.fillRect(x * ZOOM, y * ZOOM, ZOOM, ZOOM);
}
}
}
};
panel.setSize(world.WIDTH, world.HEIGHT);
add(panel);
setSize(ZOOM * world.WIDTH, ZOOM * world.HEIGHT);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
setVisible(true);
}
public static void main(String[] args) {
Langton app = new Langton();
}
}
For the first few hundred iterations, the ant makes simple geometic patterns until it reaches a threshold of black:white tiles in its immediate area, at which point it seems to devolve into chaotic random movements. This continues until it is northward of 10,000 iterations, after which something miraculous happens: The ant suddenly starts building a stable, corkscrew like pattern which radiates out from the ants jumbled path and continues indefinitely! The image below is the result of running one Ant starting from the center of the grid, facing north.
What’s interesting is that no matter the original starting direction/location, a single Langton’s ant will ALWAYS end up creating this pattern. By adding more ants to the grid, even more complex patterns and behaviors can emerge.
More Colors More States
We can also introduce other states by adding more “colors” to the types of tiles. This easily done with the code as we have it organized. To add a color, we simply add an entry to the COLOR enum. and add a corresponding rule to the switch statement in the Ant::move() method.
//TileColor.java
public enum TileColor {
WHITE,
BLACK,
GREEN,
BLUE;
}
//Ant.java
public void move(Tile[][] grid) {
switch (grid[location.y][location.x].tileColor) {
case BLACK:
turnRight();
grid[location.y][location.x].tileColor = TileColor.WHITE;
break;
case WHITE:
turnLeft();
grid[location.y][location.x].tileColor = TileColor.GREEN;
break;
case GREEN:
turnLeft();
grid[location.y][location.x].tileColor = TileColor.BLUE;
break;
case BLUE:
turnLeft();
grid[location.y][location.x].tileColor = TileColor.BLACK;
break;
}
//Infinit Grid, doesnt work so well with multiple ants, just makes a mess.
//int nextX = (Math.abs(((location.x + compass.get(direction.ordinal()).x) + WIDTH) % WIDTH));
//int nextY = (Math.abs(((location.y + compass.get(direction.ordinal()).y) + HEIGHT) % HEIGHT));
int nextX = location.x + compass.get(direction.ordinal()).x;
int nextY = location.y + compass.get(direction.ordinal()).y;
if (nextX >= 0 && nextX < WIDTH && nextY >= 0 && nextY < HEIGHT) {
location.x = nextX;
location.y = nextY;
}
}
//Langton.java
public Langton() {
world = new World(12000, 13, 125, 200);
world.doStep();
panel = new JPanel() {
@Override
public void paint(Graphics g) {
for (int y = 0; y < world.HEIGHT; y++) {
for (int x = 0; x < world.WIDTH; x++) {
switch (world.grid[y][x].tileColor) {
case WHITE:
g.setColor(Color.WHITE);
break;
case BLACK:
g.setColor(Color.BLACK);
break;
case GREEN:
g.setColor(Color.GREEN);
break;
case BLUE:
g.setColor(Color.BLUE);
break;
}
g.fillRect(x * ZOOM, y * ZOOM, ZOOM, ZOOM);
}
}
for (Ant ant : world.ants) {
g.setColor(Color.RED);
g.fillRect(ant.location.x * ZOOM, ant.location.y * ZOOM, ZOOM, ZOOM);
}
}
};
panel.setSize(world.WIDTH, world.HEIGHT);
add(panel);
setSize(ZOOM * world.WIDTH, ZOOM * world.HEIGHT);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
setVisible(true);
}
So play and explore, and if you find a cool pattern, share it in the comments below! Until then, Happy Hacking!
Further Reading
maxgoren/LangtonsAnts: An C++/NCURSES implementation of Langton’s Ants. (github.com) – An implementation using the ncurses library for output.
maxgoren/CellularAutomata: Java Swing implementation of Langtons Ant’s and other Automatonsf (github.com) – The full code of the Java/Swing implemntation shown above.
