All Things Runnable: May 2012

You can use the idea of L-Systems to make some great drawings in Kojo.

So what are L-Systems?

The Wikipedia article on the subject has a good explanation. For the purpose of this post, let me define the important elements of an L-System; these are:

The alphabet of the system. Some of the letters of the alphabet have a turtle graphics interpretation.
The axiom of the system (a string made out of the letters of the alphabet). This is the starting point for the evolution of the L-System.
The production rules of the system. These specify how the system evolves.
The turning angle for the system - associated with the letter of the alphabet that is interpreted as a turn command.
The base length of the lines that are drawn.
the scaling factor that determines the size of some of the lines drawn in a particular generation.

Here's how an L-System can be converted into a drawing - you start with the axiom string, and apply the production rules for a given number of generations. You then interpret the resulting string as a turtle graphics program.

In this post (and the accompanying code), the following alphabet letters have a turtle graphics interpretation:

F	Go forward by the base length
f	Same as F (sometimes you need two different drawing letters)
G	Go forward by the base length - with the pen up
\|	Go forward by the base length scaled down for the current generation
[	Save position and heading
]	Restore position and heading
+	Turn right
-	Turn left

The following is a translation of these ideas into Kojo (Scala) code:

case class LSystem(axiom: String, angle: Double, len: Int = 100, sf: Double = 0.6)(rules: PartialFunction[Char, String]) {
    var currVal = axiom
    var currGen = 0
    def evolve() {
        currGen += 1
        currVal = currVal.map { c =>
            if (rules.isDefinedAt(c)) rules(c) else c
        }.mkString.replaceAll("""\|""" , currGen.toString)
    }
    
    def draw() {
        def isDigit(c: Char) = Character.isDigit(c)
        val genNum = new StringBuilder
        def maybeDrawBar() {
            if (genNum.size != 0) {
                val n = genNum.toString.toInt
                genNum.clear()
                forward(len * math.pow(sf, n))
            }
        }
        currVal.foreach { c => 
            if (!isDigit(c)) {
                maybeDrawBar()
            }
            
            c match {
                case 'F' => forward(len)
                case 'f' => forward(len)
                case 'G' => penUp(); forward(len); penDown()
                case '[' => savePosHe()
                case ']' => restorePosHe()
                case '+' => right(angle)
                case '-' => left(angle)
                case n if isDigit(n) => genNum.append(n)
                case _ => 
            }
        }
        maybeDrawBar()
    }
}

Here, we have a class called LSystem. To create an instance, you give the constructor function an axiom, an angle (for turning left/right), a base length (for moving forward), a scaling factor (for generation specific forward movements), and some production rules. You then evolve the L-System for as many generations as we want using the evolve command. Finally, you draw the L-System using the draw command.

This code has some restrictions:

You can't use numbers as the letters of an L-System alphabet.
The production rules need to be context free and deterministic.
You can't use the | letter as the left hand side of a production rule.

Let's try the code out. I'll begin with some of the samples on the Wikipedia L-Systems page.