Langton's ant

From TheAlmightyGuru
Jump to: navigation, search
The first 200 steps of Langton's ant.

Langton's ant is a type of cellular automaton devised by Chris Langton in 1986 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 and can be turned into an interesting sandbox game.

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 (reverse right on black and left 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).

Additional Rules

Although Langton's ant was originally devised on a grid with only 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?

Media

Examples

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.

Videos

Numberphile.
Coding Challenge.
Description of multiple ants.
A Langton's ant computer circuit.

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 interesting 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 
' trails to bitmaps to help you find interesting results.
' 
' 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

Links

Link-Wikipedia.png