L-Systems (part 1)
In this series of blog posts I will describe the theory and implementation (in Clojure, C# and Scala) of Lindenmayer systems. I will start out by explaining the basics about L-Systems.
What are L-Systems?
A Lindenmayer system (or L-System) is a formal system that was invented by the Hungarian biologist Aristid Lindenmayer. He used it to formally describe the growth of plants. Nowadays, it is used for drawing pretty fractals (like the Koch snowflake, the Dragon curve and others) and generating trees and plants for computer graphics. The ultimate resource on L-Systems and their many different versions is the book The Algorithmic Beauty of Plants by Lindenmayer and Prusinkiewicz. It's a very good book, however it might be a little daunting to jump into as a newcomer.
An L-Sytem builds up a string of characters by a set of rules, starting with an axiom. Those characters will later be drawn to the screen by iterating over them and executing some action for each character in the string, such as drawing 5 pixels forward or rotating by 90 degrees. Formally, an L-System consists of a set of rules, an axiom (a string to start out with) and an alphabet of characters.
Application of rules
Rules can look something like this:
X → X+YF+ Y → -FX-Y
That means, if we encounter an X in our current state string, we replace it by the right hand side of the matching rule (X+YF+). For example, starting out with the axiom FX and the rules described above:
FX ↑
We look through the rules but find no matching character on the left hand sides of all the rules. That means it is left as it is.
Current state: F
FX ↑
Excellent, there is a matching rule! That means we replace the X in our current state by the right hand side of the matching rule. With that, our state string becomes:
FX+YF+
This completes one iteration of applying the rules to the state. One more iteration:
FX+YF+ ↑
Current state: F
FX+YF+ ↑
Current state: FX+YF+
FX+YF+ ↑
Current state: FX+YF++
FX+YF+ ↑
Current state: FX+YF++-FX-Y
FX+YF+ ↑
Current state: FX+YF++-FX-YF
FX+YF+ ↑
Current state: FX+YF++-FX-YF+
So, what we've been doing was the following, in imperative pseudo-code:
# State is a string, rules is a map from characters to strings # Does one iteration of the rules on the state string. function stepOnce(state, rules): newState = "" for c in state: if rules.contains(c): newState += rules[c] else: newState += c return newState # Given an axiom, a map of rules # and a number of desired iterations, # produces a state string. function stepN(axiom, rules, numIterations): state = axiom for i in (0 until numIterations): state = stepOnce(state, rules) return state
I realize this might be a little (very) dry, but those character strings have a meaning as well. In fact, the character string we just generated, will later on be used to draw a Dragon curve, which looks like this:
How to draw the L-System
Now that we have our state string, we need to get to drawing the turtle on screen. For this, we need Turtle graphics. A turtle is basically a cursor that can move around in the 2D plane and draw lines on that plane. Our version of turtle graphics has three attributes: A location (a pair of integers), an orientation or angle (a floating point number) and a stack, which saves the state of the turtle, so you can restore it later. The operations that a turtle can perform (that we need) are drawing forward a given amount of pixels, rotating by a given angle, saving its current state to a stack and restoring the state from the stack.
We can now look at the alphabet for the Dragon curve that we examined earlier and assign a turtle action to each symbol in the alphabet:
F: Draw forward +: Increase the turtle's angle by 90° -: Decrease the turtle's angle by 90° X, Y: Do nothing
Now, once we have our full state string, we can step through the string character by character and execute a turtle action based on each character. In pseudocode, it would look something like this:
function draw(state, turtle, distance, angle): for c in state: c match: # An F in the state string moves the turtle forward # while drawing a line. case 'F' => turtle.forward(distance) # A + sign increases the turtle's angle by an amount # that is specified in the L-System. case '+' => turtle.rotate(angle) case '-' => turtle.rotate(-angle) # Ignore all other characters. case _ => ()
The angle for the dragon curve is 90°, the distance can be chosen based on the size of the image and the number of iterations. For a L-System that also uses the stack operations, we can expand our pseudocode like the following:
function draw(state, turtle, distance, angle): for c in state: c match: case 'F' => turtle.forward(distance) case '+' => turtle.rotate(angle) case '-' => turtle.rotate(-angle) # An open square bracket signifies that we want # to save the current state of the turtle to the stack. case '[' => turtle.push() # A closed suqare bracket restores the turtle's state # from the stack. case ']' => turtle.pop() case _ => ()
In the next part, we will look at implementations of the turtle's functions and its state.