# Difference between revisions of "Langton's ant"

The first 200 steps of Langton's ant.

Langton's ant is a type of cellular automaton devised by Chris Langton where an imaginary ant leaves a trail as it moves around a gird according to a simple set rules which govern its movement. Despite a simple rule set, the path left behind by the ant demonstrates emergent behavior.

## Rules

The rules for the ant are:

1. If the ant is at a white square, rotate 90 degrees right, if it's at a black square, rotate left.
2. Change the color of the square in the ant's current position (black turns to white, white turns to black).
3. Move forward one space.
4. Repeat these steps.

Using these basic rules, an unexpected pattern emerges. During the first hundred steps, the ant creates a symmetrical trail. However, after a few hundred steps, the pattern devolves into chaos. But then, at around 10,000 steps, the ant begins repeating the same 104-step pattern and continues moving in the same diagonal direction forever.

Langton's ant permutations.

Because the ant's movement is determined, the trail it leaves behind is entirely based on the ant's starting conditions. If you rotate the ant's starting direction (north, east, south, or west) you will also rotate the resulting trail. Likewise, if you mirror the ant's turn rule (change right on black, left on white to left on black, right on white) you will also mirror the resulting trail on the axis opposite to the starting direction's axis. Thus, if the starting direction is on the Y axis (north/south), the trail will be mirrored on the X axis (west/east).

Although Langton's ant was originally devised to perform in a grid with binary values (black and white), the rule set can be easily altered to handle any number of cell values (usually depicted with multiple colors). When the ant encounters these additional colors, it will turn according to an expanded rule set.

This expanded rule set can be described with a series of Rs and Ls. For example, the original rule set is "RL." This means, turn right on the first color (white) and left on the second color (black). By adding a third color, gray, the rule set must also be three letters long. Thus, "RLR" would mean turn right on the first color (white), left on the second color (gray), and right on the third color (black). As the ant moves through the grid, it will loop through the colors. Instead of white to black and back to white with two colors, it will change white to gray, gray to black, and black back to white. Using this system, any number of colors and turn rules can be used, so "RLRRLLLLL" becomes a valid rule set.

It's also possible to run multiple ants in the same grid at the same time with different starting conditions. If the path of the ants converge, they will affect each other's movement.

Another alternate way of processing Langton's ant is by using a grid that isn't empty, but instead has cells filled in already. In fact, by starting with a very specific set of filled in cells and running multiple ants, you can use the ants to perform Boolean logic, and, therefore, they behave as a Turing-complete computer.

Like other cellular automata, Langton's ant can also be adapted to girds made from other shapes like triangles and hexagons and it can be adapted to concave or convex three dimensional surfaces.

One of the interesting things about Langton's ant is, despite behaving according to simple determined rules, it's extremely hard to predict the shape of the resulting trail over even a short number of steps. For each set, you can ask yourself the following questions:

• Will the path's shape be symmetrical? For how long?
• Will the path's shape be round, square, triangular, chaotic?
• Will a highway be generated?
• If there is a highway, how many steps will it take before it begins?
• If there is a highway, will it expand in size or remain a constant width?
• Will the path's shape grow quickly or slowly?
• Will the ant get stuck in an area and never leave?
• Will the path's shape have fringe around it?

## Gallery

These screenshots were taken from the program I wrote below to process Langton's ant.

The program I wrote also supports non-typical rules like forward (F) and backward (B) in addition to turning left and right. The following screenshots take these additional rules into account.

## Programs

These are FreeBASIC programs I have written that will allow you to play with Langton's ant. The simple program performs the standard rule set, the complex program adds multiple rules and states beyond the standard set. The image generator renders ant paths to bitmap images so you can run it at night and see thousands of pre-rendered paths to find interesting combinations.

### Simple

' -= Langton's Ant =- Copyright 2018, Dean Tersigni.
'
' Controls:
' 1-5 - Change Speed (1 slowest, 5 fastest)
' ESC - Quit
'
' The program will automatically stop if the ant reaches the edge of the screen.

' Setup the screen size and scale factor.
Dim As Integer ScreenWidth = 600, ScreenHeight = 600
Dim As Integer Scale = 5
ScreenRes ScreenWidth, ScreenHeight, 32

' Setup the Ant.
' The ant begins at the center of the screen facing north.
Dim As Byte AntDirection = 0
Dim As Integer AntX = (ScreenWidth / 2) / Scale
Dim As Integer AntY = (ScreenHeight / 2) / Scale
Dim As LongInt AntColor = RGB(255, 0, 0)

' Setup some variables for work.
Dim As LongInt TileColor, NewColor
Dim As Double Start, Delay = 0.1
Dim As String Key

Do
' Get the color of the current tile.
TileColor = Point(AntX * Scale, AntY * Scale)

If TileColor = RGB(0, 0, 0) Then
' Tile is black, turn to the right 90 degrees.
AntDirection = AntDirection - 1
If AntDirection = -1 Then AntDirection = 3
NewColor = RGB(255, 255, 255)
Else
' Tile is white, turn to the left 90 degrees.
AntDirection = AntDirection + 1
If AntDirection = 4 Then AntDirection = 0
NewColor = RGB(0, 0, 0)
End If

' Change the color of the tile.
Line(AntX * Scale, AntY * Scale)-(AntX * Scale + (Scale - 1), AntY * Scale + (Scale - 1)), NewColor, BF

' Move the ant.
Select Case AntDirection
Case 0  ' Up
AntY = AntY - 1
Case 1  ' Right
AntX = AntX + 1
Case 2  ' Down
AntY = AntY + 1
Case 3  ' Left
AntX = AntX - 1
End Select

' Get the color of the new position so we can erase the ant's highlight later.
TileColor = Point(AntX * Scale, AntY * Scale)

' Highlight the ant's position with the ant's color.
Line(AntX * Scale, AntY * Scale)-(AntX * Scale + (Scale - 1), AntY * Scale + (Scale - 1)), AntColor, BF

' Stop the program if the ant reaches the edge of the screen.
If AntX < 0 Or AntY < 0 Or (AntX * Scale) >= ScreenWidth Or (AntY * Scale) >= ScreenHeight Then
Exit Do
End If

Key = Inkey
Select Case Key
Case Chr(27)
Exit Do
Case "1"
Delay = 0.1
Case "2"
Delay = 0.01
Case "3"
Delay = 0.001
Case "4"
Delay = 0.0001
Case "5"
Delay = 0
End Select

' Delay long enough for the user to see what's happening.
Start = Timer
Do: Loop While (Timer - Start) < Delay

' Erase the ant highlight.
Line(AntX * Scale, AntY * Scale)-(AntX * Scale + (Scale - 1), AntY * Scale + (Scale - 1)), TileColor, BF
Loop

Sleep

### Complex

' -= Langton's Ant =- Copyright 2018, Dean Tersigni.
'
' Controls:
'  +   - Increase the ant's speed.
'  -   - Decrease the ant's speed.
'  M   - Set the ant to maximum speed.
'  P   - Toggle pause.
'  ESC - Quit the program.
'
' The program will automatically stop if the ant reaches the edge of the screen. You
' can get more working space by increasing the screen's width and height variables
' and decreasing the scale.

' Setup the screen size and scale factor.
Dim As Integer ScreenWidth = 600
Dim As Integer ScreenHeight = 600
Dim As Integer Scale = 3
ScreenRes ScreenWidth, ScreenHeight, 32

' Setup the Ant.
' The ant begins at the center of the screen facing north.
Dim As Byte AntDirection = 0
Dim As Integer AntX = (ScreenWidth / 2) / Scale
Dim As Integer AntY = (ScreenHeight / 2) / Scale
' Setup the ant's trail color and highligh color.
Dim As Integer AntRandomColor = True
Dim As LongInt AntColor = RGB(255, 0, 0)
' Setup the ant's turning rules.
Dim As String AntTurnRules = "RL"

' The default Langton's ant system uses the Turn Rules: RL. This means, when it encounters
' black, it turns right, when it encounters white, it turns left. By adding rules, you can
' alter how the ant behaves. For example RLL will use black, gray, and white. When the ant
' encounter black it will turn right, when it encounters gray, left, and white, left.
' All sorts of different results occur when you modify the turn rules. For example:
'
'  RL   - Begins symmetrically, becomes chaotic, but eventually becomes a repeating highway.
'  RLR  - Chaotic growth.
'  RLL  - Grows a blob, but with right angle edges.
'  RRRL - Forms a highway very quickly.
'  RRLL - Creates a symmetrical peach-shaped growing blob.
'  RLLR - As the trail grows, the left side has right angles, but the center stays chaotic.
'  RRLRR - Grows a pretty clean square.
'  RLLLR - Makes a very slow-growing box with a chaotic circle in the center.
'  RLLRRLLR - A multi-colored growing box.
'  LRRRRRLLR - Makes bouncing highways in a ever-growing square.
'  LLRRRLRLRLLR - Creates a very interestinf highway.
'  RRLLLRLLLRRR - Creates a growing triangle.
'
' My program accepts additional commands beyond the official Langton's ant rules.
'
'  F - Move forward without changing direction.
'  B - Move backward (return to the square you just came from).
'
' Some examples with these additions include:
'  FL - Instant highway
'  LFL - Creates a slowly growing vertical line
'  LBL - Move away and covers up it's tracks.
'  RBL - Forms a shape very similar to RL, but gets stuck for a moment.
'  LBBR - Begins a blob, but gets stuck in the center.
'  LLBR - Makes long arms of growth.
'  LBBBBR - Grows in spurts after getting stuck for awhile.
'  LFFFFFFFFFFFFFFFFFFFFR - Noisey blob with tendrils along the edge.
'  LFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFR - Layered blob with increasing noise.

' Calculate the total number of colors and their hues based on the AntTurnRules.
Dim As Integer TotalColors = Len(AntTurnRules)
If TotalColors < 2 Or TotalColors > 255 Then
Print "Must have at least 2-255 turn rules.": Sleep: End
End If
Dim As LongInt ColorValues(0 To TotalColors - 1)
Dim As Integer ColorIndex, ColorWork
Randomize Timer
Dim As Byte ColorRandom = Int(Rnd * 6)

ColorValues(0) = Point(0, 0)
For ColorIndex = 1 To TotalColors - 1
ColorWork = (255 / (TotalColors - 1)) * ColorIndex
If AntRandomColor = True Then
' Use a random color set for the ant, and make the ant's color contrast it.
Select Case ColorRandom
Case 0
ColorValues(ColorIndex) = RGB(ColorWork, 0, 0)              ' Red
AntColor = RGB(0, 255, 255)
Case 1
ColorValues(ColorIndex) = RGB(0, ColorWork, 0)              ' Green
AntColor = RGB(255, 0, 255)
Case 2
ColorValues(ColorIndex) = RGB(0, 0, ColorWork)              ' Blue
AntColor = RGB(255, 255, 0)
Case 3
ColorValues(ColorIndex) = RGB(ColorWork, ColorWork, 0)      ' Yellow
AntColor = RGB(255, 0, 0)
Case 4
ColorValues(ColorIndex) = RGB(ColorWork, 0, ColorWork)      ' Magenta
AntColor = RGB(0, 255, 0)
Case 5
ColorValues(ColorIndex) = RGB(0, ColorWork, ColorWork)      ' Cyan
AntColor = RGB(255, 0, 0)
End Select
Else
' Just use chades of gray.
ColorValues(ColorIndex) = RGB(ColorWork, ColorWork, ColorWork)
End If
Next ColorIndex

' Setup some variables for work.
Dim As LongInt TileColor
Dim As String TurnDirection
Dim As Double Start
Dim As Double Delay = 0.01
Dim As String Key
Dim As Byte Quit, Pause

Do
' Get the color of the current tile.
TileColor = Point(AntX * Scale, AntY * Scale)

' Find the color in our index.
For ColorIndex = 0 To TotalColors - 1
If TileColor = ColorValues(ColorIndex) Then
Exit For
End If
Next ColorIndex

' Determine the new direction based on the color index.
ColorIndex = ColorIndex + 1
TurnDirection = Mid(AntTurnRules, ColorIndex, 1)

' Turn the ant based on the turn direction.
Select Case TurnDirection
Case "R"
' Turn to the right 90 degrees.
AntDirection = AntDirection - 1
If AntDirection = -1 Then AntDirection = 3
Case "L"
' Turn to the left 90 degrees.
AntDirection = AntDirection + 1
If AntDirection = 4 Then AntDirection = 0

' The following commands are not part of the official Langton's ant rules.
Case "F"
' Go forward (no change in direction).
Case "B"
' Go backward (180 turn).
AntDirection = AntDirection + 2
If AntDirection > 3 Then AntDirection = AntDirection - 4
Case Else
' Protect against typos.
Print "Invalid direction: " + TurnDirection
Exit Do
End Select

' Set the current cell to the new color.
If ColorIndex = TotalColors Then
TileColor = ColorValues(0)
Else
TileColor = ColorValues(ColorIndex)
End If
Line(AntX * Scale, AntY * Scale)-(AntX * Scale + (Scale - 1), AntY * Scale + (Scale - 1)), TileColor, BF

' Move the ant.
Select Case AntDirection
Case 0  ' Up
AntY = AntY - 1
Case 1  ' Right
AntX = AntX + 1
Case 2  ' Down
AntY = AntY + 1
Case 3  ' Left
AntX = AntX - 1
End Select

' Get the color of the new position so we can erase the ant's highlight later.
TileColor = Point(AntX * Scale, AntY * Scale)

' Highlight the ant's position with the ant's color.
Line(AntX * Scale, AntY * Scale)-(AntX * Scale + (Scale - 1), AntY * Scale + (Scale - 1)), AntColor, BF

' Stop the program if the ant reaches the edge of the screen.
If AntX < 0 Or AntY < 0 Or (AntX * Scale) >= ScreenWidth Or (AntY * Scale) >= ScreenHeight Then
Quit = True
End If

Do
' Handle user input.
Key = Inkey
Select Case Key
Case "=", "+"
' Speed up the ant.
Delay = Delay - 0.001
If Delay < 0.0001 Then Delay = 0.0001
Case "-", "_"
' Slow down the ant.
Delay = Delay + 0.001
If Delay > 1 Then Delay = 1
Case "M", "m"
' Set the ant to maximum speed.
Delay = 0
Case "P", "p"
' Toggle pause.
Pause = Not Pause
Case Chr(27)
Quit = True
End Select
Loop Until Pause = False Or Quit = True

' Delay long enough for the user to see what's happening.
Start = Timer
Do: Loop While (Timer - Start) < Delay

' Erase the ant highlight, but only if we're not quitting. We want to know the ant's last location.
If Quit = False Then
Line(AntX * Scale, AntY * Scale)-(AntX * Scale + (Scale - 1), AntY * Scale + (Scale - 1)), TileColor, BF
End If
Loop While Quit = False

Sleep

### Image Generator

' -= Langton's Ant: Bitmap Generator =- Copyright 2018, Dean Tersigni.
'
' The program will run variations of Langton's ant and output their resulting
'
' It will run each rule set until the ant reaches the edge of the screen, or
' until it reaches 100,000,000 steps, whichever happens first.
'
' The program skips rule sets that are guaranteed to produce limited or no
' output like LL or RRR. It also skips rule sets that are the opposite of
' existing sets. For example, if it renders RLLR, it won't render LRRL, since
' it is just the mirror image of the first. However, it won't skip rule sets
' that are multiple duplicates of existing rules like "RL" and "RLRL".

Declare Function NextRule(Rule As String, Position As Integer) As String

' The output path to save the bitmaps:
Dim As String OutputPath = "C:\Ant\"

' The total number of images you want to render:
Dim As Integer TotalImages = 500

' The maximum number of steps to take before rendering:
Dim As LongInt MaxSteps = 100000000

' The size of the bitmap to render:
Dim As Integer ScreenWidth = 500
Dim As Integer ScreenHeight = 500

' The size multiplier of the ant's trail:
' 1 = One pixel, 2 = Four-pixel square, 3 = Nine-pixel square, etc.
Dim As Integer Scale = 1

' The starting rule set to use:
' Sets are increased according to the following pattern:
' R, LL, RL, RR, LLL, RLL, LRL, LLR, RLR, LRR, RRR, LLLL, etc.
Dim As String AntTurnRules = "L"

ScreenRes ScreenWidth, ScreenHeight, 32

Dim As Byte AntDirection
Dim As Integer AntX
Dim As Integer AntY

ReDim As String SavedRules(1)
Dim As Integer Saved = 1
Dim As LongInt CurrentStep

Dim As Integer TotalColors
Dim As LongInt ColorValues(0 To TotalColors - 1)
Dim As Integer ColorIndex, ColorWork
Dim As Byte ColorSet

Dim As LongInt TileColor
Dim As String TurnDirection
Dim As Byte Done
Dim As Integer RuleIndex
Dim As String MirrorRule

Open Cons For Output As #1

Do
' Clear the screen.
CLS

' Reset the ant.
AntDirection = 0
AntX = (ScreenWidth / 2) / Scale
AntY = (ScreenHeight / 2) / Scale

' Get the next turn rule set.
AntTurnRules = NextRule(AntTurnRules, 1)

Print #1, AntTurnRules

' Skip rule sets that won't do anything.
If AntTurnRules = String(Len(AntTurnRules), "L") Or _
AntTurnRules = String(Len(AntTurnRules), "R") Then
Print #1, "Skipped"
Continue Do
End If

' Skip rules that are mirrors of existing rules.
MirrorRule = ""
For RuleIndex = 1 To Len(AntTurnRules)
If Mid(AntTurnRules, RuleIndex, 1) = "L" Then
MirrorRule = MirrorRule + "R"
Else
MirrorRule = MirrorRule + "L"
End If
Next RuleIndex
For RuleIndex = 1 To UBound(SavedRules)
If SavedRules(RuleIndex) = MirrorRule Then
' This rule is a mirror of a rule we already rendered. Skip it.
Print #1, "Skipped"
Continue Do
End If
Next RuleIndex

' Setup the new color set.
TotalColors = Len(AntTurnRules)
ReDim ColorValues(0 To TotalColors - 1)

ColorValues(0) = Point(0, 0)
For ColorIndex = 1 To TotalColors - 1
ColorWork = (255 / (TotalColors - 1)) * ColorIndex
Select Case ColorSet
Case 0 ' Red
ColorValues(ColorIndex) = RGB(ColorWork, 0, 0)
Case 1 ' Green
ColorValues(ColorIndex) = RGB(0, ColorWork, 0)
Case 2 ' Blue
ColorValues(ColorIndex) = RGB(0, 0, ColorWork)
Case 3 ' Yellow
ColorValues(ColorIndex) = RGB(ColorWork, ColorWork, 0)
Case 4 ' Magenta
ColorValues(ColorIndex) = RGB(ColorWork, 0, ColorWork)
Case 5 ' Cyan
ColorValues(ColorIndex) = RGB(0, ColorWork, ColorWork)
Case 6 ' White
ColorValues(ColorIndex) = RGB(ColorWork, ColorWork, ColorWork)
End Select
Next ColorIndex

' For the next rendering, use the next color set.
ColorSet = ColorSet + 1
If ColorSet > 6 Then
ColorSet = 0
End If

' Begin rendering the ant's path.
Done = False
CurrentStep = 0
Do
' Get the color of the current tile.
TileColor = Point(AntX * Scale, AntY * Scale)

' Find the color in our index.
For ColorIndex = 0 To TotalColors - 1
If TileColor = ColorValues(ColorIndex) Then
Exit For
End If
Next ColorIndex

' Determine the new direction based on the color index.
ColorIndex = ColorIndex + 1
TurnDirection = Mid(AntTurnRules, ColorIndex, 1)

' Turn the ant based on the turn direction.
Select Case TurnDirection
Case "R"
' Turn to the right 90 degrees.
AntDirection = AntDirection - 1
If AntDirection = -1 Then AntDirection = 3
Case "L"
' Turn to the left 90 degrees.
AntDirection = AntDirection + 1
If AntDirection = 4 Then AntDirection = 0
End Select

' Set the current cell to the new color.
If ColorIndex = TotalColors Then
TileColor = ColorValues(0)
Else
TileColor = ColorValues(ColorIndex)
End If
Line(AntX * Scale, AntY * Scale)-(AntX * Scale + (Scale - 1), AntY * Scale + (Scale - 1)), TileColor, BF

' Move the ant.
Select Case AntDirection
Case 0  ' Up
AntY = AntY - 1
Case 1  ' Right
AntX = AntX + 1
Case 2  ' Down
AntY = AntY + 1
Case 3  ' Left
AntX = AntX - 1
End Select

' Stop the program if the ant reaches the edge of the screen.
If AntX < 0 Or AntY < 0 Or _
(AntX * Scale) >= ScreenWidth Or (AntY * Scale) >= ScreenHeight Then
Done = True
End If

CurrentStep = CurrentStep + 1
Loop While Done = False And CurrentStep < MaxSteps

' Save the screen as a bitmap image.
BSave OutputPath + Str(Saved) + " - " + AntTurnRules + ".bmp", 0

' Check to see if we've saved all the images.
Saved = Saved + 1
If Saved > TotalImages Then
End
Else
' Record this rule set so we can skip its mirror set.
ReDim Preserve SavedRules(1 To Saved)
SavedRules(Saved) = AntTurnRules
End If
Loop

' This function generates the next rule.
Function NextRule(Rule As String, Position As Integer) As String
If Position > Len(Rule) Then
Rule = String(Len(Rule) + 1, "L")
Else
If Mid(Rule, Position, 1) = "L" Then
Rule = Left(Rule, Position - 1) + "R" + Mid(Rule, Position + 1)
Else
Rule = Left(Rule, Position - 1) + "L" + Mid(Rule, Position + 1)

' Recurse the function.
NextRule(Rule, Position + 1)
End If
End If

Return Rule
End Function