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.


 
 
.orig x3000
ld r1, ASCIIDIFF1
 
; user input for grid size
lea r0, STGRIDSIZE
puts
in
 
add r0, r0, r1
add r0, r0, #-1
brz SELECTED100
ld r0, GRID300
st r0, GRIDSIZE
brnzp GRIDSELECTED
 
SELECTED100
ld r0, GRID100
st r0, GRIDSIZE
 
GRIDSELECTED
 
; User input for number of additional ants
lea r0, STHOWMANY
puts
in
add r1, r1, r0 ; r1 = number of additional ants
add r1, r1, #1
st r1, LIVINGANTS
 
; INITIALIZE FIRST ANT
and r7, r7, x0
add r7, r7, #9 ; loop counter for the other ants
 
and r1, r1, x0  ; x and y coordinates go in here
and r3, r3, x0  ; to be mapped to a cell id
 
; check grid size for starting coordinates
ld r4, GRIDSIZE
ld r6, GRID100
not r6, r6
add r6, r6, #1
add r6, r6, r4  ; grid size - 100
brz GRID100B
 
ld r1, START300
ld r3, START300
brnzp FIRSTANTCOORDINATES
 
GRID100B
ld r1, START100
ld r3, START100
 
FIRSTANTCOORDINATES
 
JSR MAPPY   ; takes r1 and r3 values, converts to cell id in r5
 
ld r6, LIVEANTTEMPLATE  ; = x8000, alive and facing north
add r6, r6, r5  ; complete antword for ant 1
lea r4, ANTWORD
str r6, r4, #0  ; put first ant in base address of ANTWORD array
 
 
ld r2, LIVINGANTS
ANTSETUPLOOP
add r4, r4, #1  ;   increment address of ant
 
add r2, r2, #-1
brnz INITIALIZEDEAD
JSR ANTCOORDS
JSR MAPPY
ld r6, LIVEANTTEMPLATE
add r6, r5, r6
brnzp READYTOSTORE
 
INITIALIZEDEAD
and r6, r6, x0
 
READYTOSTORE
str r6, r4, #0
 
 
add r7, r7, #-1
brnz DONESETUP
brnzp ANTSETUPLOOP
 
DONESETUP
 
 
 
 
 
 
 
BIGMOVELOOP ; one iteration of this loop moves all 10 ants (doing nothing if they're dead)
ld r1, LIVINGANTS
brz EVERYONEISDEAD
ld r1, ANTWORD
 
 
; FOR LOOP TO MOVE ALL 10 ANTS
 
 
 
 
 
ld r1, STEPCOUNT
add r1, r1, #1
st r1, STEPCOUNT
 
BRNZP BIGMOVELOOP
EVERYONEISDEAD ; :(
 
 
 
 
halt
STGRIDSIZE .stringz "Grid size? 1 for 100, 3 for 300 "
STHOWMANY .stringz "How many additional ants? "
ASCIIDIFF1 .fill #-48
SUBTEMP1 .fill #0
LIVINGANTS .fill #0
GRIDSIZE .fill #0
GRID100 .fill #100
GRID300 .fill #300
STEPCOUNT .fill #0
ANTWORD .blkw #10
START100 .fill #50
START300 .fill #150
LIVEANTTEMPLATE .fill x8000
ANTCOORDTEMP .fill #0
ANTCOORDTEMP2 .fill #0
 
 
 
 
 
 
 
 
 
;************************************************************************
;************************************************************************
;                             SUBROUTINES
;************************************************************************
;************************************************************************
 
; SUBROUTINE
ANTSONTHEMOVE
; [1] check if dead
; [2] extract current location
; [3] extract current direction
; [4] check current colour
; [5] turn
; [7] change location or kill
 
; INPUT: R1:
address of ant
;        R4:
grid size
 
; LOCAL: R2: ant word
;           R3: cell id of ant
 
st r2, MOVETEMP2
st r3, MOVETEMP3
st r5, MOVETEMP5
st r6, MOVETEMP6
st r7, MOVETEMP7
ldr r2, r1, #0  ; r2 = copy of ant-word
 
; [1] CHECK FOR DEATH. word for dead ants == x0000
add r2, r2, #0
brz ENDOFMOVE ; if ant-word + 0 == 0, ant is dead.
 
; [2] extract current location
ld r3, IDMASK ; for getting rid of first 3 bits of ant-word, leaving only location
and r3, r2, r3 ; r3 = cell id of ant
 
; [4] check current colour and flip it
 
 
jsr FLIPPITY    ; flips bit, puts original colour in R5
                ; white/0: turn right; black/1: turn left
 
; [5] turn the ant according to pre-flipped colour
 
add r0, r5, #0
brnp LEFTTURN
 
jsr TAKEARIGHTTURN
brnzp DONETURNING
 
LEFTTURN
jsr TAKEALEFTTURN
DONETURNING
 
; [7] change location and kill
 
ldr r2, r1, #0 ; reload modified antword from memory
 
ld r5, SOUTH    ; butmasks
ld r6, EAST
 
and r5, r5, r2
and r6, r6, r2  ; isolating the two direction bits, 2b and 3b, to determine direction
 
add r5, r5, #0  ;    check if 2b is 0
brnp SECTIOND   ;
add r6, r6, #0  ;   check if 3b is 0
brnp SECTIONC
 
 
; if both are zero, direction is north
;; if cell id <= grid size, ant is already at the top and will die
not r0, r4
add r0, r0, #1  ; r0 = negative grid size
add r3, r0, r3  ; r3 = cell id - grid
brn ANTDEATHISPERMANENT ; if negative, kill it
add r2, r2, r0  ; antword - grid size
brnzp ENDOFMOVE
 
 
 
SECTIONC
; if direction is 01, ant faces east
;; if (cellID % grid != grid -1)
;; then cellid++, else die
not r0, r4
add r0, r0, #1
 
add r5, r3, #0  ;    copy celll id to r5 to repeatedly subtract grid size
EASTMODLOOP
add r5, r5, r0  ;   cell id - grid
add r5, r5, #1  ; if this is 0, then r5 == grid - 1
brz ANTDEATHISPERMANENT
add r5, r5, #-1 ; but if not, undo it and re-loop
brn MOVEEAST    ; if negative, allowed to move east
                ; if equal to grid-1, ant is on eastern border and will die
 
BRNZP EASTMODLOOP
 
MOVEEAST
add r2, r2, #1  ; move east: CellID++
brnzp ENDOFMOVE
 
SECTIOND    ; first direction bit is 1
add r6, r6, #0  ; check if second bit is 0
brnp SECTIONF
; if it is 0, then direction is 10 = south
; if ant is on southern border, it dies
; if cellID >= grid^2-grid, then ant is on southern border
 
ld r0, N100
add r0, r0, r3  ; checking if grid size = 100
brz GRIDIS100
ld r0, GRIDSQ300HALF
add r3, r3, r0
add r3, r3, r0
add r3, r3, r0
add r3, r3, r0
brzp ANTDEATHISPERMANENT
add r2, r2, r4
brnzp ENDOFMOVE
 
GRIDIS100
ld r0, GRIDSQ100
add r3, r3, r0
brzp ANTDEATHISPERMANENT
add r2, r2, r4
brnzp ENDOFMOVE
 
 
SECTIONF
; direction bits are 11 = WEST
; if cellID % grid != 0, ant can go west, otherwise dead
 
add r6, r3, #0  ; copy cell id to r6
not r0, r4
add r0, r0, #1  ; r0 = -grid
WESTMODLOOP
add r6, r6, r0
brz ANTDEATHISPERMANENT
brn CANMOVEWEST
brp WESTMODLOOP
 
CANMOVEWEST
add r2, r2, #-1
brnzp ENDOFMOVE
 
 
ANTDEATHISPERMANENT
and r2, r2, #0
ld r7, LIVINGANTS
add r7, r7, #-1
st r7, LIVINGANTS
 
ENDOFMOVE
str r1, r2, #0  ;    double check this syntax
ld r2, MOVETEMP2
ld r3, MOVETEMP3
ld r5, MOVETEMP5
ld r6, MOVETEMP6
ld r7, MOVETEMP7
RET
 
N100 .fill #-100
GRIDSQ100 .fill #-9900
GRIDSQ300HALF .fill #-22425
MOVETEMP3 .fill #0
MOVETEMP2 .fill #0
MOVETEMP4 .fill #0
MOVETEMP5 .fill #0
MOVETEMP6 .fill #0
MOVETEMP7 .fill x0
IDMASK .fill x1FFF    ;   for extracting bits 12-0, the cell ID of the ant
 
; end of ANTSONTHEMOVE subroutine
 
 
 
 
 
FAKEXOR ; subroutine
 
; XOR of two registers
; INPUT r2, r4
; OUTPUT r6 = r2 XOR r4
 
; A in r4, not A in r5
; B in r2; not B in r6
; r4 XOR r2
 
st r5, XORTEMP5
 
not r6, r2
and r6, r6, r4  ; r6 = a & ~b
not r6, r6      ; r6 = ~(a & ~b)
 
not r5, r4      ; r5 = ~ a
and r5, r5, r2  ; r5 = ~a & b
not r5, r5      ; r5 = ~(~a & b)
and r6, r5, r6  ; r6 = ~(a & ~b) & ~(~a & b)
not r6, r6      ; r6 = ~( ~(a & ~b) & ~(~a & b) ) = a XOR b
 
ld r5, XORTEMP5
 
RET 
 
XORTEMP5 .fill #0
 
 
; SUBROUTINE
 FLIPPITY
; Takes a cell id and flips the bit in the grid, returns the original colour
; INPUT     r1: cell id
; LOCAL     r2: which bit to flip, then bitmask
;           r3: quotient, then address of byte to change
; OUTOUT    r5: original colour of cell id, before flipping. 1 if black, 0 if white.
;
; First, get byte (GRID + OFFSET)
; CELL ID / 16
 
st r4, FLIPTEMP4
st r5, FLIPTEMP5
st r6, FLIPTEMP6
 
and r3, r3, #0
add r2, r1, #0  ; copy cell id into r2
 
; loop to divide cellid by 16
FLIPLOOP
add r2, r2, #-16 ; cell id - 16
brn FLIPLOOPDONE    ; if negative, division done
add r3, r3, #1      ; if not negative, increment quotient and subtract again
BRNZP FLIPLOOP
 
FLIPLOOPDONE
add r2, r2, #8      ; add 16 back to negative number to get cellid % 16
add r2, r2, #8      ; this is which bit within the byte that the cell ID refers to
 
lea r4, GRID        ; starting address of GRID array
add r3, r3, r4      ; r3 = address of byte that will be changed = GRID base address + CELL ID / 16
 
 
lea r4, BM1         ; r4 = address of butmask array
add r4, r4, r2      ; r4 + which bit to flip = address of appropriate bitmask
ldr r2, r4, #0      ; r2 = bitmask to flip one bit
 
ldr r4, r3, #0      ; r4 = byte to be changed
 
and r0, r2, r4      ; indicates original colour of bit. 0 if white, non-zero if black
 
; A in r4, not A in r5
; B in r2; not B in r6
; r4 XOR r2
not r6, r2
and r6, r6, r4  ; r6 = a & ~b
not r6, r6      ; r6 = ~(a & ~b)
 
not r5, r4      ; r5 = ~ a
and r5, r5, r2  ; r5 = ~a & b
not r5, r5      ; r5 = ~(~a & b)
and r6, r5, r6  ; r6 = ~(a & ~b) & ~(~a & b)
not r6, r6      ; r6 = ~( ~(a & ~b) & ~(~a & b) ) = a XOR b
 
 
str r6, r3, #0
 
ld r4, FLIPTEMP4
ld r6, FLIPTEMP6
 
add r5, r0, #0  ; move colour of bit into r5 for output
 
ret
GRID .fill x8000
FLIPTEMP4 .fill #0
FLIPTEMP5 .fill #0
FLIPTEMP6 .fill #0
 
; bitmasks for flipping one bit
BM1 .fill x8000
BM2 .fill x4000
BM3 .fill x2000
BM4 .fill x1000
BM5 .fill x0800
BM6 .fill x0400
BM7 .fill x0200
BM8 .fill x0100
BM9 .fill x0080
BM10 .fill x0040
BM11 .fill x0020
BM12 .fill x0010
BM13 .fill x0008
BM14 .fill x0004
BM15 .fill x0002
BM16 .fill x0001
 
; END OF FLIPPITY SUBROUTINE
 
 
 
 
 
; SUBROUTINE
TAKEALEFTTURN
; turns the ant 90 degrees left
 
; INPUT R1: address in memory of ANT
; LOCAL R2: ant
;       R3: bitmask
;       R4: 3rdbit
;       R5: 2nd and 3rd bit
;       R6:
;       R7:
;       R0:
 
st r2, LEFTTURNTEMP2
st r3, LEFTTURNTEMP3
st r4, LEFTTURNTEMP4
st r6, LEFTTURNTEMP6
st r7, LEFTTURNTEMP7  ;  store r7, load before RET
ldr r2, r1, #0  ;  load ant into r2
ld r3, EAST
and r4, r2, r3 ; r4 = 3rdbit
 
ld r3, WEST
;and r5, r2, r3 ; r5 = 2nd and 3rd bits
 
 
add r4, r4, #0 ; check if 3rd bit is 0
brnp THIRDBIT1  ; If so, continue. If not, jump to next part.
; 3rd bit is 0, so XOR r2 ant-word with WEST bitmask, already in R3
 
BRNZP LEFTTURNEND
 
THIRDBIT1
; third bit is 1, so use EAST bitmask
ld r3, EAST
 
LEFTTURNEND
 
add r0, r4, #0  ; move r4 3rdbit into r0 temporarily
add r4, r3, #0  ; move r3 bitmask into r4 for the XOR subroutine
JSR FAKEXOR   ; r6 = r2 XOR r4
              ; flips the correct bit to turn left
 
add r3, r4, #0 ; moves r4 bitmask back into r3
add r4, r0, #0  ; moves r0 3rdbit back into r3
 
str r6, r1, #0  ; store tweaked ant-word with new direction back in memory
 
ld r2, LEFTTURNTEMP2
ld r3, LEFTTURNTEMP3
ld r4, LEFTTURNTEMP4
ld r6, LEFTTURNTEMP6
ld r7, LEFTTURNTEMP7
RET
 
 
WEST .fill X6000
EAST .fill x2000
NORTH .fill x0000
SOUTH .fill x4000
 
LEFTTURNTEMP2 .fill #0
LEFTTURNTEMP3 .fill #0
LEFTTURNTEMP4 .fill #0
LEFTTURNTEMP6 .fill #0
LEFTTURNTEMP7 .fill #0
 
; end of TAKEALEFTTURN subroutine
 
 
 
; SUBROUTINE
TAKEARIGHTTURN
; turns the ant 90 degrees right
 
; INPUT R1: address in memory of ANT
; LOCAL R2: ant
;       R3: bitmask
;       R4: 3rdbit
;   R5: 2nd and 3rd bit
;   R6:
;   R7:
;   R0:
 
st r2, RIGHTTURNTEMP2
st r3, RIGHTTURNTEMP3
st r4, RIGHTTURNTEMP4
st r6, RIGHTTURNTEMP6
st r7, RIGHTTURNTEMP7  ;  store r7, load before RET
ldr r2, r1, #0  ;  load ant into r2
ld r3, EAST
and r4, r2, r3 ; r4 = 3rdbit
 
;ld r3, WEST
;and r5, r2, r3 ; r5 = 2nd and 3rd bits
 
 
add r4, r4, #0 ; check if 3rd bit is 0
brnp THIRDBIT1RIGHT  ; If so, continue. If not, jump to next part.
; 3rd bit is 0, so XOR r2 ant-word with EAST bitmask
ld r3, EAST
 
BRNZP RIGHTTURNEND
 
THIRDBIT1RIGHT
; third bit is 1, so use WEST bitmask
ld r3, WEST
 
RIGHTTURNEND
 
add r0, r4, #0  ; move r4 3rdbit into r0 temporarily
add r4, r3, #0  ; move r3 bitmask into r4 for the XOR subroutine
JSR FAKEXOR   ; r6 = r2 XOR r4
              ; flips the correct bit to turn right
 
add r3, r4, #0 ; moves r4 bitmask back into r3
add r4, r0, #0  ; moves r0 3rdbit back into r3
 
str r6, r1, #0  ; store modified ant-word with new direction back in memory
 
ld r2, RIGHTTURNTEMP2
ld r3, RIGHTTURNTEMP3
ld r4, RIGHTTURNTEMP4
ld r6, RIGHTTURNTEMP6
ld r7, RIGHTTURNTEMP7
RET
 
RIGHTTURNTEMP2 .fill #0
RIGHTTURNTEMP3 .fill #0
RIGHTTURNTEMP4 .fill #0
RIGHTTURNTEMP6 .fill #0
RIGHTTURNTEMP7 .fill #0
 
; end of TAKEARIGHTTURN subroutine
 
 
 
 
 
 
 
 
 
; SUBROUTINE
ANTCOORDS
; INPUT     r2: index of ant
; OUTPUT    r1: x coordinate value
;           r3: y coordinate value
; "Enter x coordinates for ant #whatever"
 
st r4, COORD2
 
ld r0, NEWLINE
out
lea r0, ENTERXCOORDS
puts
ld r3, ASCIIPLUS
;add r0, r2, r3
;out
ld r0, NEWLINE
out
 
 
ld r5, ASCIIDIFF 
getc
out
add r4, r0, r5  ; r4 holds first digit of x
 
add r1, r4, r4  ; r1 = 2 * r4
add r1, r1, r1  ; r1 = 4 * r4
add r1, r1, r1  ; r1 = 8 * r4
add r1, r1, r4  ; r1 = 9 * r4
add r1, r1, r4  ; r1 = 10 * r4
 
 
 
getc
out
add r4, r0, r5  ; r4 holds 2nd digit of x
add r1, r1, r4  ; full value of x coordt
st r1, COORD1
 
 
; "enter y coords"
ld r0, NEWLINE
out
lea r0, ENTERYCOORDS
puts
ld r3, ASCIIPLUS
;add r0, r2, r3
;out
ld r0, NEWLINE
out
 
ld r5, ASCIIDIFF 
getc
out
add r4, r0, r5  ; r4 holds first digit of y
 
add r1, r4, r4  ; r1 = 2 * r4
add r1, r1, r1  ; r1 = 4 * r4
add r1, r1, r1  ; r1 = 8 * r4
add r1, r1, r4  ; r1 = 9 * r4
add r1, r1, r4  ; r1 = 10 * r4
 
 
getc
out
add r4, r0, r5  ; r4 holds 2nd digit of y
add r3, r1, r4  ; full value of y coord
ld r1, COORD1
ld r4, COORD2
RET
 
 
ENTERXCOORDS .STRINGZ "Enter x coordinates for ant "
ENTERYCOORDS .STRINGZ "Enter y coordinates for ant "
ASCIIDIFF .fill #-48
ASCIIPLUS .fill #48
COORD1 .fill #0
NEWLINE .fill #10
COORD2 .fill #0
COORD3 .fill #0
 
; END OF ANT_COORDINATES_SUBROUTINE
 
 
 
 
MAPPY
; Maps the coordinates of the ant
; Input:  R1: x coord
;  R3: y coord
;  R4: grid size
; Output: R5: Cell ID
; Cell ID = grid size * y coord + x coord
 
st r6, MAP1
st r7, MAP2
 
; multiply by 100
add R0, R3, R3 ; 2y
add R0, R0, R0 ; 4y
add R6, R0, R0 ; 8y
add R6, R6, R6 ; 16y
add R6, R6, R6 ; 32y
add R0, R0, R6 ; 36y
add R6, R6, R6 ; 64y
add R0, R0, R6 ; 100y
 
ld R7, N100a
add R7, R4, R7
 
brz GRID100a
add R0, R0, R0 ;200y
add R0, R0, R3 ;300y
 
GRID100a
Add R5, R0, R1  ; OUTPUT: R5 = grid*y + x
 
 
ld r6, MAP1
ld r7, MAP2
RET
N100a .fill #-100
MAP1 .fill #0
MAP2 .fill #0
 
; END OF MAPPY SUBROUTINE
 
 
 
.end
 