How to resolve the algorithm Langton's ant step by step in the Ol programming language

Published on 12 May 2024 09:40 PM
#Ol

How to resolve the algorithm Langton's ant step by step in the Ol programming language

Table of Contents

Problem Statement

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: 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.

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)..

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Langton's ant step by step in the Ol programming language

Source code in the ol programming language

#!/usr/bin/ol
(import (otus random!))

(define MAX 65536)  ; should be power of two
; size of game board (should be less than MAX)
(define WIDTH 170)
(define HEIGHT 96)

; helper function
(define (hash x y)
   (let ((x (mod (+ x WIDTH) WIDTH))
         (y (mod (+ y HEIGHT) HEIGHT)))
   (+ (* y MAX) x)))

;; ; helper function
(define directions '(
   (0 . 1) (1 . 0) (0 . -1) (-1 . 0)
))

; ---------------
(import (lib gl2))
(gl:set-window-title "Langton's Ant")

(glShadeModel GL_SMOOTH)
(glClearColor 0.11 0.11 0.11 1)
(glOrtho 0 WIDTH 0 HEIGHT 0 1)

(glPointSize (/ 854 WIDTH))

; generate random field
(gl:set-userdata
   (list->ff (map (lambda (i) (let ((x (rand! WIDTH)) (y (rand! HEIGHT)))
                                 (cons (hash x y) #t))) (iota 1000))))

(define ant (cons
   (rand! WIDTH)
   (rand! HEIGHT)))
(define dir (list (rand! 4))) ; 0, 1, 2, 3

; main game loop
(gl:set-renderer (lambda (mouse)
(let ((generation (gl:get-userdata)))
   (glClear GL_COLOR_BUFFER_BIT)

   ; draw the cells
   (glColor3f 0.2 0.5 0.2)
   (glBegin GL_POINTS)
      (ff-fold (lambda (st key value)
         (glVertex2f (mod key MAX)
                     (div key MAX))
      ) #f generation)
      (glColor3f 0.8 0.2 0.1)
      (glVertex2f (car ant) (cdr ant))
   (glEnd)

   (gl:set-userdata
      (let*((x (car ant))
            (y (cdr ant))
            (generation (case (get generation (hash x y) #f)
                           (#true ; black cell
                              (set-car! dir (mod (+ (car dir) 1) 4))
                              (del generation (hash x y)))
                           (#false
                              (set-car! dir (mod (+ (car dir) 7) 4))
                              (put generation (hash x y) #true)))))
         (set-car! ant (mod (+ x (car (lref directions (car dir)))) WIDTH))
         (set-cdr! ant (mod (+ y (cdr (lref directions (car dir)))) HEIGHT))
         generation))


)))

You may also check:How to resolve the algorithm Hello world/Standard error step by step in the C# programming language
You may also check:How to resolve the algorithm Bitmap step by step in the M2000 Interpreter programming language
You may also check:How to resolve the algorithm Trigonometric functions step by step in the Maxima programming language
You may also check:How to resolve the algorithm Poker hand analyser step by step in the C programming language
You may also check:How to resolve the algorithm Pathological floating point problems step by step in the Sidef programming language