Jordan Santell open web engineer

L-systems

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.

Several L-systems rendered
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.

aababaabaababaababa\begin{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:

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:aab\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. 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:

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.

A directed line traversing a cartesian graph 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.

A tweet from @LSystemBot visualizing the L-System: {"start":"HHQ","rules":{"F":"[QN]F+F+","N":"[]++[HNQ]", "Q":"[F[]QFH++N]","H":"-FQNF[-]H"},"a":60,"iter":6}
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+FX\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}
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:

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:X\XF\XFXF//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.

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:ba\begin{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:

baaaaabaaaaabaaaaabaaaaab\begin{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.5B\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.

w:Fp1:F.33F[+F]F[F]Fp2:F.33F[+F]Fp3:F.33F[F]F\begin{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