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.


' version 16-10-2016
' compile with: fbc -s gui
 
' a cell size of 4 x 4 pixels is used
' In FreeBASIC the 0,0 is the top left corner
 
ScreenRes 400,400,8 ' give a 100 by 100 field
Dim As UByte Ptr p = ScreenPtr
If p = 0 Then End ' p does not point to screen
 
Palette 0,       0,   0,   0      ' index 0 = black
Palette 255,   255, 255, 255      ' index 225 = white
 
Line (0, 0) - (799, 799), 255, bf   ' draw box and fill it with white color
 
Dim As Integer count, offset, x = 199, y = 199
Dim As UByte col   ' = color
' direction, 0 = up, 1 = right, 2 = down, 3 = left
Dim As UByte d     ' d = 0, looking up
 
Do
  offset = x + y * 400
  col = p[offset]
 
  If col = 0 Then
    d = (d -1) And 3
  Else
    d = (d +1) And 3
  EndIf
 
  col = col Xor 255 ' flip the color
 
  ScreenLock        ' don't update screen while we are drawing
 
  ' draw a 4*4 block and paint it with palette color [0 | 255]
  Line (x, y) - (x +3, y -3), col, bf
 
  ScreenUnLock    ' allow screen update's
 
  'Sleep 100       ' slow the program down if needed
 
  ' true = 0, false = -1
  If (d And 1) = 1 Then
    x = x + (d = 1) * 4 - (d = 3) * 4
  Else
    y = y - (d = 0) * 4 + (d = 2) * 4
  End If
 
  count += 1
  ' update step count window title bar
  WindowTitle "Langton's ant step: " + Str(count)
 
  ' has user clicked on close window "X" then end program
  If InKey = Chr(255) + "k" Then End
 
Loop Until x < 1 Or x > 398 Or y < 1 Or y > 398
 
' display total count in window title bar
WindowTitle "Langton's ant has left the field in " + Str(count) + " steps"
 
' empty keyboard buffer
While InKey <> "" : Wend
'Print : Print "hit any key to end program"
Sleep
End