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.

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.

## Resources

Support #BlackLivesMatterWays you can help