/L-systems

L-systems

Notes published

Biologist Aristid Lindenmayer created Lindenmayer systems, or L-systems, in 1968 as a way of formalizing patterns of bacteria growth. L-systems are a recursive, string-rewriting framework, commonly used today in computer graphics to visualize and simulate organic growth, with applications in plant development, procedural content generation, and fractal-like art.

The following describes L-system fundamentals, how they can be visually represented, and several classes of L-systems, like context-sensitive L-systems and stochastic L-systems. Much of the following has been derived from Przemyslaw Prusinkiewicz and Lindenmayer’s seminal work, The Algorithmic Beauty of Plants.

String Rewriting

Fundamentally, an L-system is a set of rules that describe how to iteratively transform a string of symbols. A string, in this context, is a series of symbols, like “

$a$

” or “

$ababaabaaaa$

“, and can be thought of as a word comprised of characters. Each rule, known as a production, describes the transformation of one symbol to another symbol, series of symbols, or no symbol at all. On each iteration, the productions are applied to each character simultaneously, resulting in a new series of symbols.

Productions in this rewriting system can be described with “before” and “after” states, often described as the predecessor and successor; for example, the production

$a longrightarrow ab$

represents that the symbol

$a$

transforms into the symbols

$ab$

on every iteration. The length of derivation, or the number of iterations, is represented by

$n$

. Given a word

$a$

and productions

$a longrightarrow ab$

and

$b longrightarrow a$

, the following illustrates how the word transforms over several iterations, from

$n=0$

to

$n=4$

.

Formalizing L-systems

L-systems are formalized as a tuple with the following definition:

$G = langle V, w, P rangle$

Where the components are:

• $V$

, the alphabet, or all potential symbols in the string.

• $w$

, the starting word, also known as the axiom, comprised of symbols from

$V$

.

• $P$

, a series of productions describing the transformations or rules.

The L-system in Figure 1 can be formalized by defining its axiom (

$w$

) and a series of productions (

$p_{1}, …, p_{n}$

) as:

begin{aligned}
w &: a \
p_{1} &: b longrightarrow a \
p_{2} &: a longrightarrow ab \
end{aligned}

The alphabet of all valid symbols can be inferred. It is implied that a symbol without a matching production has an identity production, e.g.

$a longrightarrow a$

.

D0L-systems

This fundamental form of an L-system is described as a deterministic, context-free L-system, or D0L-system (or sometimes DOL-system). 0L-systems are context-free, meaning that each predecessor is transformed regardless of its position in the string and its neighbors. Deterministic L-systems always produce the same result given the same configurations, as there is only one matching production for each predecessor.

Graphical Representation of L-systems

L-systems can be represented visually via turtle graphics, of Logo fame. While L-systems are string rewriting systems, these strings are comprised of symbols, each which can represent some command. A turtle in computer graphics is similar to a pen plotter drawing lines in a 2D space. Imagine giving instructions to a pen plotter to draw a square: “draw 1cm. turn right. draw 1cm. turn right. draw 1cm. turn right. draw 1cm“. Though plotters don’t really have an orientation, an L-system’s turtle can be represented by Cartesian coordinates

$x$

and

$y$

, and an angle

$alpha$

that describes its forward direction. From there, symbols in a string can represent commands to change the state of the turtle.

To move a turtle around in 2D, symbols must be chosen to represent movement and rotation. The symbols

$F$

,

$+$

and

$–$

will be used here, as they are commonly selected for these commands in L-system interpreters. After deriving the result of an L-system using its production rules, the string can then be parsed from left to right, with the following symbols modifying the turtle state:

• $F$

move forward by

$d$

units while drawing a line.

• $+$

rotate left by angle

$delta$

.

• $–$

rotate right by angle

$delta$

.

The variables

$delta$

and

$d$

are global values indicating the magnitude of each symbol’s rotation or movement. In non-parametric L-systems, each symbol’s rotation and movement magnitude is a constant in the system.

Following the line in Figure 2 from the bottom left corner, the string can be read as “forward, forward, forward, right, forward, forward, right…” and so on.

A turtle may be decoupled from an L-system. The L-system has a starting string and a set of productions and outputs the resulting string. A turtle may take that final string as an input, and output some visual representation. For example, many of the illustrations shown here use the same L-system solvers, while using different turtles where appropriate, like one turtle built using CanvasRenderingContext2D and another using WebGL.

Space-Filling Curves

Space-filling curves can be formalized via L-systems, resulting in a recursive, fractal-like pattern. More specifically, FASS curves, defined as space-filling, self-avoiding, simple, and self-similar. That is, a single, non-overlapping, recursive, continuous curve.

begin{aligned}
delta &: 90 \
w &: X \
p_{1} &: X longrightarrow + Y F – X F X – F Y + \
p_{2} &: Y longrightarrow – X F + Y F Y + F X – \
end{aligned}

The Hilbert Curve (Figure 3) is an example of a FASS curve that can be represented as an L-system. Considered a Node-rewriting technique, this L-system’s productions declare that on each iteration,

$X$

and

$Y$

symbols are replaced with more

$F$

,

$X$

and

$Y$

symbols. With the angle

$delta$

defined as 90, this results in recursively generated square wave shape along a curve. While

$F$

,

$+$

and

$–$

are interpreted by the turtle, other symbols can be used for productions. In this case,

$X$

and

$Y$

are ignored when rendering, and only relevant when rewriting the string and matching productions.

3D Interpretation

In addition to a turtle traversing on a 2D plane, symbols may be introduced that instruct the turtle to draw in 3D. The Algorithmic Beauty of Plants uses the following symbols to control rendering in three dimensions:

• $+$

turn left by angle

$delta$

.

• $–$

turn right by angle

$delta$

.

• $&$

pitch down by angle

$delta$

.

• $wedge$

pitch up by angle

$delta$

.

• $backslash$

roll left by angle

$delta$

.

• $/$

roll right by angle

$delta$

.

• $|$

turn around by 180°.

Like the 2D Hilbert Curve (Figure 3), a three-dimensional version can also be created (Figure 4) using these additional symbols, resulting in a 3D FASS curve.

begin{aligned}
delta &: 90 \
w &: X \
p_{1} &: X longrightarrow & wedge backslash X F wedge backslash X F X \
& & – F wedge / / X F X \
& & & F + / / X F X \
& & – F / X – / \
end{aligned}

Bracketed L-Systems

The space-filling Hilbert curve can be represented as a single, continuous line. For organic, tree-like structures, branching is used to represent a diverging fork. Two new symbols, square brackets, are introduced to represent a tree in an L-system’s string, with an opening bracket indicating the start of a new branch, with the remaining symbols between the brackets being members of that branch. Symbols after the end bracket indicate returning to the point of the branch’s origin. A stack is used to implement branching, storing the state of the turtle on the stack.

• $[$

push the current turtle state onto the stack.

• $]$

pop the top state from the stack and this becomes the current turtle state.

Symbols in a branch are transformed and replaced just as they were outside of a branch. This allows recursive, fractal-like behavior, with each branch forking into more branches, and so on.

Context-sensitive L-systems

Rather than productions evaluating symbols in isolation (context-free), rules may be defined that only matches a symbol when it proceeds or succeeds another specific symbol.
Context-sensitive L-systems contain production rules that specify symbols that must come before or after the predecessor in order to match, as opposed to context-free systems that evaluate predecessors in isolation.

These context rules are defined using

$<$

and

$>$

in the production rule, adjacent to the predecessor. In Figure 5, the first production rule only matches when the

$a$

symbol is immediately after

$b$

, thus replacing the

$a$

predecessor with its successor,

$b$

. This results in the

$b$

symbol moving towards the right:

begin{aligned}
&baaaa \
&abaaa \
&aabaa \
&aaaba \
&aaaab \
end{aligned}

A similar system could be defined that propagates

$b$

from right to left, defined via production

$a > b longrightarrow b$

, replacing

$a$

when there is a

$b$

after it in the string.

L-systems with these one-sided context productions may be considered 1L-systems. Productions may also have both a before-context and an after-context in systems considered 2L-systems. They can be represented as:

$A < X > B longrightarrow Y$

This production rule indicates that the predecessor

$X$

will be replaced by successor

$Y$

when it is between an

$A$

and a

$B$

.

Stochastic L-systems

The previously described systems are all deterministic; the same system with the same input will always generate the same result. Stochastic L-systems are non-deterministic, defined by several productions that match the same predecessor, chosen randomly given their weight on each iteration. The following production rules define that on each iteration,

$X$

has a 50% chance to be rewritten as

$A$

, and a 50% chance to be rewritten as

$B$

.

begin{aligned}
X & xrightarrow{.5} A \
X & xrightarrow{.5} B \
end{aligned}

This non-determinism is useful for procedurally creating variety and the seemingly random results of nature.