Sunday, May 20, 2012

Playing with L-Systems in Kojo

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.

Sierpinski triangle 

This is Example 6 on the Wikipedia page.

Kojo Code:

val sierp_wp6 = LSystem("F", 60, 2) {
    case 'F' => "f+F+f"
    case 'f' => "F-f-F"
} 

And the corresponding drawing:


Dragon Curve

This is Example 7 on the Wikipedia page.

Kojo Code:

val dragon_wp7 = LSystem("FX", 90, 10) {
    case 'X' => "X+YF"
    case 'Y' => "FX-Y"
}  


And the corresponding drawing:



Fractal Plant

This is Example 8 on the Wikipedia page.

Kojo Code:

val fplant_wp8 = LSystem("X", 25, 4) {
    case 'X'=> "F-[[X]+X]+F[+FX]-X"
    case 'F' => "FF"
}


And the corresponding drawing:




The next few examples are from the book - The Computational Beauty of Nature.

Tree-2

Kojo Code:

val tree2 = LSystem("G", 8, 100, 0.35) {
    case 'G' => "|[+++++G][-------G]-|[++++G][------G]-|[+++G][-----G]-|G"
}


And the corresponding drawing:



 

Carpet

Kojo Code:

val carpet = LSystem("F-F-F-F", 90, 1) {
    case 'F'=> "F[F]-F+F[--F]+F-F"
}


And the corresponding drawing:



Runnable code for this post is here: https://gist.github.com/2757241. To play with the code, copy it into Kojo and hit the Run button. Then tweak the code and re-run as desired.

Enjoy!

Related Links
The Wikipedia L-Systems page
The Computational Beauty of Nature
Neat Graphics with Scala Processing

No comments: