Lindenmayer Systems

By Sameer Puri

While playing with extensions in Inkscape, I ran into Tavmjong Bah's detailed breakdown of the Render Extensions. It got me really interested in Lindenmayer systems, which are formal grammars based on string rewriting. An L-system begins with an initial state called the axiom. Its terms (characters in a string) are iteratively replaced using a set of rules. There are two types of terms: constants which replace themselves (identity function) and variables which are replaced by a sequence of one or more terms. The system is run for a set number of iterations and can grow quite quickly.

Consider a system with the axiom "A" and the replacement rules 'A' => "AB", 'B' => "A". After one iteration, the state of the system is "AB". Then "ABA", then "ABAAB", and so on. As a quick snippet of pseudocode:

iterations = 4
axiom = "A"
state = axiom
while i < iterations
    newstate = ""
    for c in state
        if c is 'A'
            newstate += "AB"
        else if c is 'B'
            newstate += "A"
    state = newstate
print state

Aristid Lindenmayer, the name sake of L-systems, originally developed the above system to model the growth of algae. L-systems, when used with ]turtle graphics](https://en.wikipedia.org/wiki/Turtle_graphics), can actually draw fractals and other interesting patterns found in nature.

Some terms have special meaning for the purpose of the turtle graphics. Note that the use of '[' or ']' makes the system a bracketed OL-system, a refinement on L-systems.

F = move forward 1 unit
+ = increment current angle by angle
- = decrement current angle by angle
[ = save current position and angle (stack)
] = restore last saved position and angle (stack)

And now for some examples!

The well-known Sierpinski triangle, as an L-system:

axiom: "F-G-G"
rules:
    'F' => "F-G+F+G-F"
    'G' => "GG"
angle: 60
iterations: 6

Sierpinski Triangle

A realstic plant generated by an L-system:

axiom: "X"
rules:
    'X' => "F-[[X]+X]+F[+FX]-X"
    'F' => "FF"
angle: 25
iterations: 5

Plant

Stochastic L-systems, where rules are probabilistically applied, can be used to create convincing models of nature in both 2D and 3D.

Dragon trees

User:Solkoll [Public domain], via Wikimedia Commons

All L-systems that don't use '[' or ']' from the turtle graphics noted above can be drawn with a single line on paper. These would be really fun to try out with a pen plotter I've been working on for a group project, which I should be posting about in the near future.