Growing digital plants with a chicken turtle

This is a short post describing how to implement a simple turtle graphics engine with CHICKEN Scheme. I do love fractals and especially Lindenmayer Systems, so let's draw them with my favorite programming language.

So what's an L-System? As wikipedia tells us it is a expansion system of chars, namely F, -, +, and possibly [, ] and other letters.

The expansions are controlled by rules. Rules have the form

F -> F+F-F-F+F

meaning: "substitute each F in the original string with the characters to the right of the arrow". To begin substitution, we start with a given anchor or axiom. For example: "F". With this axiom and the substitution rule above we get a famous fractal, the Koch curve (not the snowflake though, see below for a better system for that).

So I choose to represent the L-System as a scheme struct, representing the axiom/state and the rules. Rules are simple alists of the form (( VAR . "EXPANSION")). Expanding a rule is simple:

For each char ''c'' in the current state
 if c is a VAR, then insert EXPANSION
 else insert c
into new current state

One way to write this in scheme is

(define-record l-system state rules)

(define (grow-system system)
  (let ((s (l-system-state system))
        (rules (l-system-rules system)))
    (string-fold (lambda (c s)
                   (cond ((alist-ref (string c) rules equal?)
                          => (lambda (n)
                               (string-concatenate (list s n))))
                         (else (string-concatenate (list s (string c))))))
                 ""
                 s)))

(define-syntax define-l-system
  (syntax-rules (->)
    ((_ name seed (var -> expansion) ...)
     (define name (make-l-system seed '(( var . expansion) ...))))))

The macro is syntactic sugar. To define the Koch curve from above we can say:

(define-l-system koch-curve "F" ("F" -> "F+F-F-F+F"))

Now we can expand the system (grow-system koch-curve) -> "F+F-F-F+F" as expected.

So to visualize this beauty we need a device called a turtle. Imagine a little animal with a pen in its mouth (or painted feet, or whatever). The turtle is walking on a two dimensional plane, facing in one direction (0° - 360°) and can turn left or right for a specific angle alpha and walk forward one step.

Now it is a matter of interpreting the L-System data. F means: draw one step forward, + means: turn left alpha degrees, - means turn right -alpha degrees.

For more advanced L-Systems [ pushes onto the stack, ] pops the stack. When we push the stack we remember the turtle state (direction and position) and when we pop the stack we lift the turtle up and set it back on the paper, where it was when we pushed the stack last.

Let's make a turtle:

(define-record turtle x y angle angle-step stepwidth stack)

For convenience we need some procedures to calculate the new coordinates for the position if we let it go one step in direction angle. We also need to take care of wrapping the angle to a valid degree. Easy!

(define-constant *pi* 3.14159265358979)

(define (new-angle a dir)
  (modulo (+ a dir) 360))

(define (new-coords x y alpha step)
  (let ((c (* step (cos (* (/ *pi* 180) alpha))))
        (a (* step (sin (* (/ *pi* 180) alpha)))))
    (values (+ x c) (+ y a))))

Now on to the interpreter!

(define (move-turtle! t)
  (lambda (c)
    (case  c
      ((#\[) (push-turtle-stack! t))
      ((#\]) (pop-turtle-stack! t))
      ((#\+) (turtle-angle-set! t (new-angle (turtle-angle t) (- (turtle-angle-step t)))))
      ((#\-) (turtle-angle-set! t (new-angle (turtle-angle t) (turtle-angle-step t))))
      ((#\F) (let-values (((x y) (new-coords (turtle-x t)
                                             (turtle-y t)
                                             (turtle-angle t)
                                             (turtle-stepwidth t))))
                        (draw-line (turtle-x t)
                                  (turtle-y t)
                                  x
                                  y
                                  color: solid-black)
                        (turtle-x-set! t x)
                        (turtle-y-set! t y))))))

(move-turtle!) returns then interpreter, which accepts one instruction and executes it. (draw-line) is our procedure to draw a simple and solid black line onto a canvas. Let's assume it just exists for now.

Now that we know how to grow an L-System and can convince a turtle to do the drawing for us, we need to grow the system to the wanted dimensions, drop the turtle onto the canvas and let it interpret the resulting L-System state.

(define (draw-system s iterations #!key (x 0) (y 0) (angle 0) (angle-step 0) (step-width 0))
  (let ((t (make-turtle x y angle angle-step step-width '())))
    (string-for-each (move-turtle! t)
                     (let loop ((i iterations))
                       (cond ((> 0 i) (error "Negative number of " iterations))
                             ((= 0 i) (l-system-state s))
                             (else
                              (let ((new-state (grow-system s)))
                                (l-system-state-set! s new-state)
                                (loop (sub1 i)))))))
                                (show!)))

The (show!) procedure is another magic for displaying the result for us. But where do we draw to? Let's create a doodle!

(define h 800)
(define w 800)
(define center-x (round (/ h 2)))
(define center-y (round (/ w 2)))
(new-doodle height: h width: w background: solid-white)
(draw-system koch-curve 3 x: 0 y: center-y angle: 0 angle-step: 60 step-width: 7)
(save-screenshot "koch-curve.png")

For the drawing and hiding all the complexity of instantiating a window for drawing and so on I have created an egg called doodle which is still in development but for drawings like this totally usable ;) You can install it with chicken-install. Currently you still need trunk versions of sdl and cairo but this should change very soon.

For prettier pictures try one of these and experiment!

(define-l-system koch "F++F++F" ( "F" -> "F-F++F-F")) ; the snowflake
(define-l-system dragon "FX" ( "X" -> "X+YF+") ( "Y" -> "-FX-Y"))
; some plant like things using a stack
(define-l-system grass "F" ( "F" -> "F[+F]F[-F]F"))
(define-l-system plant "F" ( "F" -> "FF-[-F+F+F]+[+F-F-F]" ))

You can find the BSD licensed code used in this piece on bitbucket:

https://bitbucket.org/ckeen/lindenmayer

Thanks dear reader for bearing with me this time and I hope I could show you how easy it is to do turtle drawings in CHICKEN scheme! If you find some interesting I will be glad to hear about it!