Langton's ant is a cellular automaton that models an ant sitting on a plane of cells, all of which are white initially, the ant facing in one of four directions.

Each cell can either be black or white.

The ant moves according to the color of the cell it is currently sitting in, with the following rules:

   If the cell is black, it changes to white and the ant turns left;
   If the cell is white, it changes to black and the ant turns right;
   The ant then moves forward to the next cell, and repeat from step 1.

This rather simple ruleset leads to an initially chaotic movement pattern, and after about 10000 steps, a cycle appears where the ant moves steadily away from the starting location in a diagonal corridor about 10 cells wide.
Conceptually the ant can then walk infinitely far away.



Task

Start the ant near the center of a 100x100 field of cells, which is about big enough to contain the initial chaotic part of the movement.

Follow the movement rules for the ant, terminate when it moves out of the region, and show the cell colors it leaves behind.



The problem has received some analysis; for more details, please take a look at the Wikipedia article   (a link is below)..



See also

   Wikipedia:   Langton's ant.


Related task

   Rosetta Code:   Conway's Game of Life.


 
'
' Langton's ant
'
' World is a global boolean array, 100x100 in size
width%=100
height%=100
DIM world!(width%,height%)
ARRAYFILL world!(),FALSE
' Time in world
time%=0
' Ant is represented by a global three-element array
' holding: x, y, direction [0=north,1=west,2=south,3=east]
DIM ant%(3)
'
@setup_ant
@run_ant
@display_world
'
' Displays the world to file "langton.out": . for false, # for true
'
PROCEDURE display_world
  LOCAL i%,j%
  OPEN "o",#1,"langton.out"
  PRINT #1,"Time in world: ";time%;" ticks"
  FOR i%=0 TO width%-1
    FOR j%=0 TO height%-1
      IF world!(i%,j%)
        PRINT #1,"#";
      ELSE
        PRINT #1,".";
      ENDIF
    NEXT j%
    PRINT #1,""
  NEXT i%
  CLOSE #1
RETURN
'
' Set up the ant to start at (50,50) facing north
'
PROCEDURE setup_ant
  ant%(0)=50
  ant%(1)=50
  ant%(2)=0
RETURN
'
' check if ant position is within world's bounds
'
FUNCTION ant_in_world
  RETURN ant%(0)>=0 AND ant%(0)<width% AND ant%(1)>=0 AND ant%(1)<height%
ENDFUNC
'
' Turn ant direction to left
'
PROCEDURE ant_turn_left
  ant%(2)=(ant%(2)+1) MOD 4
RETURN
'
' Turn ant direction to right
'
PROCEDURE ant_turn_right
  ant%(2)=(ant%(2)+3) MOD 4
RETURN
'
' Ant takes a step forward in current direction
'
PROCEDURE ant_step_forward
  SELECT ant%(2)
  CASE 0
    ant%(0)=ant%(0)+1
  CASE 1
    ant%(1)=ant%(1)+1
  CASE 2
    ant%(0)=ant%(0)-1
  CASE 3
    ant%(1)=ant%(1)-1
  ENDSELECT
RETURN
'
' Run the ant until it falls out of the world
'
PROCEDURE run_ant
  WHILE @ant_in_world
    time%=time%+1
    IF world!(ant%(0),ant%(1)) ! true for white
      world!(ant%(0),ant%(1))=FALSE
      @ant_turn_left
    ELSE ! false for black
      world!(ant%(0),ant%(1))=TRUE
      @ant_turn_right
    ENDIF
    @ant_step_forward
  WEND
RETURN
 