Lindenmayer Systems

3 minute read

Published 21 April 2019

theory

A brief overview of L-systems and how they represent intricate patterns concisely.

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 namesake of L-systems, originally developed the above system to model the growth of algae. L-systems, when used with 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 semi-realistic 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.

Lindenmayer Systems

Comments🔗