/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.

A rendering of several L-systems.

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 “

aa

” or “

ababaabaaaaababaabaaaa

“, 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

aaba longrightarrow ab

represents that the symbol

aa

transforms into the symbols

abab

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

nn

. Given a word

aa

and productions

aaba longrightarrow ab

and

bab longrightarrow a

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

n=0n=0

to

n=4n=4

.

aababaabaababaabababegin{aligned}
&a \
&ab \
&aba \
&abaab \
&abaababa \
end{aligned}

Figure 1 Word a transforming over 4 iterations of an L-system with the productions a → ab and b → a.

Formalizing L-systems

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

G=V,w,PG = langle V, w, P rangle

Where the components are:


  • VV

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


  • ww

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

    VV

    .


  • PP

    , a series of productions describing the transformations or rules.

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

ww

) and a series of productions (

p1,...,pnp_{1}, …, p_{n}

) as:

w:ap1:bap2:aabbegin{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.

aaa 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

xx

and

yy

, 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

FF

,

++

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:


  • FF

    move forward by

    dd

    units while drawing a line.


  • ++

    rotate left by angle

    δdelta

    .


  • rotate right by angle

    δdelta

    .

The variables

δdelta

and

dd

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.

FFFFFFF+F+FFFFFFFFF-FF-F-F+F+FF-F-FFF

Figure 2 Visualizing the movement of a turtle and the line it creates from parsing the above string. From The Algorithmic Beauty of Plants Figure 1.5b.

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.

An L-system generated by Twitter bot LSystemBot 2.0, tweeting an L-system and it’s production rules every few hours.

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.

δ:90w:Xp1:X+YFXFXFY+p2:YXF+YFY+FXbegin{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}

Figure 3 An L-system definition for a space-filling Hilbert Curve, animated over 7 iterations.

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,

XX

and

YY

symbols are replaced with more

FF

,

XX

and

YY

symbols. With the angle

δdelta

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

FF

,

++

and

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

XX

and

YY

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.

δ:90w:Xp1:XXFXFXF//XFX&F+//XFXF/X/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}

Figure 4 A space-filling Hilbert Curve from 1 to 4 iterations in 3D.

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.

Figure 5 Animated branching L-systems, from 1 to 5 iterations. Definitions from The Algorithmic Beauty of Plants Figure 1.24.

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.

w:baaaap1:b<abp2:babegin{aligned}
w &: baaaa \
p_{1} &: b < a longrightarrow b \
p_{2} &: b longrightarrow a \
end{aligned}

Figure 5 A context-sensitive L-system simulating signal propagation.

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

aa

symbol is immediately after

bb

, thus replacing the

aa

predecessor with its successor,

bb

. This results in the

bb

symbol moving towards the right:

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

A similar system could be defined that propagates

bb

from right to left, defined via production

a>bba > b longrightarrow b

, replacing

aa

when there is a

bb

after it in the string.

Figure 6 Animated variants of context-sensitive L-systems, iterations 1 to 35. Definition from A model study on biomorphological description, illustrated in Figure 1.31 from The Algorithmic Beauty of Plants.

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>BYA < X > B longrightarrow Y

This production rule indicates that the predecessor

XX

will be replaced by successor

YY

when it is between an

AA

and a

BB

.

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,

XX

has a 50% chance to be rewritten as

AA

, and a 50% chance to be rewritten as

BB

.

X.5AX.5Bbegin{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.

w:Fp1:F.33F[+F]F[F]Fp2:F.33F[+F]Fp3:F.33F[F]Fbegin{aligned}
w &: F \
p_{1} &: F xrightarrow{.33} F[+F]F[-F]F \
p_{2} &: F xrightarrow{.33} F[+F]F \
p_{3} &: F xrightarrow{.33} F[-F]F \
end{aligned}


Figure 7 A stochastic L-system animating over several variants. Definition from The Algorithmic Beauty of Plants Figure 1.27.

Resources

© 2018-2019 Jordan Santell, All Rights Reserved

Original Source