L-Systems

L-Systems are a type of fractal, well, that’s not really true; L-systems are a formalism for constructing rules for iterated systems, such as plant growth and turning those into images. But what’s interesting is that they’re actually remarkably simple to implement the evaluation of.

So let’s look at one of the simpler ones, the binary tree. It has two replacement rules. (I am taking these from wikipedia)

1→11
0→1[0]0
Starting with a string equal to "0" string

The first 3 iterations are equivalent to

1[0]0
11[1[0]0]1[0]0
1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0 

But that doesn’t really do us any justice does it? That’s a nice string and all, but it’s not an image as was promised. But we haven’t even gone over the rules yet. In this system we assume that we have a turtle that has a position and an angle that draws lines. The turtle has a stack of positions and angles that it keeps and can return to.

Before we get to that we should probably implement the turtle code as it’s fairly simple. We’ll use my library because I’m the one writing the blog post

(require :img-genner)

(defparameter *image* (img-genner:make-image 640 480))
;; The turtle's stack
(defparameter *stack* nil)
(defparameter *lines* nil)
(defparameter *turtle-x* 320.0)
(defparameter *turtle-y* 0.0)
(defparameter *turtle-angle* 0.0)
(defun deg2rad(n)
  (* n (/ (coerce pi 'single-float) 180)))
(defun turn(d)
  (incf *turtle-angle* d))
(defun forward(amount line)
  (let ((sx *turtle-x*) (sy *turtle-y*))
    (setf *turtle-x* (+ *turtle-x* (* amount (cos *turtle-angle*)))
          *turtle-y* (+ *turtle-y* (* amount (sin *turtle-angle*))))
    (when line
      (push (list sx sy *turtle-x* *turtle-y*) *lines*))
    )
  )
(defun push-turtle()
  (push (list *turtle-x* *turtle-y* *turtle-angle*) *stack*))
(defun pop-turtle()
  (destructuring-bind (x y a) (pop *stack*)
      (setf *turtle-x* x *turtle-y* y *turtle-angle* a)))

(defun stroke-drawing(stroker)
  (loop for (x1 y1 x2 y2) in *lines*
        do(stroke-line *image* x1 y1 x2 y2 stroker)
        ))

As it turns out the rule handling is even simpler if we store it as a little association-list.

(defparameter *rules* nil)
(defparameter *forward-amount* 4.0)
(defun define-rule(name execution replacement)
  (push `(,name . (,execution . ,replacement)) *rules*))
(defun run-replacements(state)
  (loop for i in state
        for (_name . (_execution . replacement)) = (or (assoc i *rules* ) i)
        appending replacement))
(defun execute-rules(state)
  (loop for i in state
        for (_name . (execution . _replacement)) = (assoc i *rules*)
        do(funcall execution)))
(define-rule 0 (lambda()(forward *forward-amount* t)) '(1 #\[ 0 #\] 0 ))
(define-rule 1 (lambda()(forward *forward-amount* t)) '(1 1))
(define-rule #\[ (lambda() (push-turtle)
                   (turn (deg2rad 45.0)))
  '(#\[))
(define-rule #\] (lambda() (pop-turtle)
                   (turn (deg2rad -45.0)))
  '(#\]))

And now we can write our video generation function. Since the number of frames will be fairly small, we will turn on ffmpeg’s motion interpolation to smooth it out and increase the framerate.

(defun iterate-n-then-execute(n tape)
  (loop repeat n
        with ffmpeg = (uiop:launch-program "ffmpeg -r 20 -f png_pipe -i - -y -vf \"minterpolate='me=umh:search_param=32:fps=30'\"  -c:v h264 -b:v 3M -preset placebo L-system.mp4" :input :stream)
        with stroker = (img-genner:static-color-stroker (img-genner:rgb 255 0 0))
        for state = tape then (run-replacements state)
        do(reset-turtle)
        finally(progn
                 (execute-rules state)
                 (loop for (sx sy ex ey) in (reverse *lines*)
                       do(img-genner:stroke-line *image* sx sy ex ey stroker)
                         do(img-genner:stroke-line *image* (1+ sx) sy (1+ ex) ey stroker)
                         do(img-genner:save-image *image* (uiop:process-info-input ffmpeg)))
                 (uiop:close-streams ffmpeg)
                 (uiop:wait-process ffmpeg))))

So now if we run (iterate-n-then-execute 7 '(0)) we should get the following

There’s a lot more that can be done with L-systems if you are willing to experiment with what kinds of drawing operations it encodes.

Edit: A redditor mentioned a relevant piece of software on the post I made for this, L-lisp. It also happens to show just why L-systems are still relevant to game programming, it compiles with a bit of modification.

Edit Edit: I have addressed the compilation issues that caused issues before.