Lindenmayer Systems

Lindenmayer systems (L-systems for short) are similar to cellular automata in that you create rules that are applied iterative to a current design. L-systems, however, are based on a computational device called a “grammar”. In general, an L-system is defined with the following components:

• Variables: Symbols that will be replaced each iteration.

• Constants: Symbols that will never be replaced.

• Axiom: The initial state, a sequence of variables and constants.

• Rules: A set of rules for how to replace variables in the current state with new sequences of symbols.

Example L-system

This is an example L-system that, as it is, isn’t practical for design at all.

• Variables: \(A\) and \(B\)

• Constants: None

• Axiom: \(A\)

• Rules: \((A \rightarrow AB)\) and \((B \rightarrow A)\)

At iteration \(n = 0\), the state will only be \(A\), the axiom. It evolves as follows:

\[\begin{split}\begin{align} n=0 \; : \; &A \\ n=1 \; : \; &AB \\ n=2 \; : \; &ABA \\ n=3 \; : \; &ABAAB \\ n=4 \; : \; &ABAABABA \\ n=5 \; : \; &ABAABABAABAAB \\ n=6 \; : \; &ABAABABAABAABABAABABA \\ n=7 \; : \; &ABAABABAABAABABAABABAABAABABAABAAB \end{align}\end{split}\]

If you look at the lengths of these strings, you’ll see that they’re actually the Fibonacci sequence.

Note that at each iteration, all variables are replaced according to the rules, at the same time. Applying only a single rule to a single variable is not allowed.

Using L-Systems for Design

To get from an L-system to a design, the symbols in the system are often translated to instructions for a “turtle” to follow. Generally, these look like “move forward”, “turn”, “remember where you are”, and “go back to where you last remembered”.

As a simple example, the following L-system generates a Koch curve with only right angles:

• Variables: \(F\)

• Constants: \(+\) and \(-\)

• Axiom: \(F\)

• Rules: \((F \rightarrow F+F-F-F+F)\)

Here, \(F\) means “move forward”, \(+\) means “turn left”, and \(-\) means “turn right”. After a handful of iterations, we can draw the turtle’s path:

\(n = 0\)

\(n = 1\)

\(n = 2\)

\(n = 3\)

Multiple variables can be set to the same turtle instruction, as with the dragon curve:

• Variables: \(F\) and \(G\)

• Constants: \(+\) and \(-\)

• Axiom: \(F\)

• Rules: \((F \rightarrow F+G)\) and \((G \rightarrow F-G)\)

• Turn angle: \(90^\circ\)

Here, \(F\) and \(G\) both mean draw forward. After 10 iterations, the dragon curve can be seen by the turtle’s path:

Saving the Turtle’s Position and Rotation

In many cases, it can be helpful to save information about where the turtle is and where it’s facing. This can allow for branching behavior. This is often facilitated with a “last-in, first-out” stack. The idea of such a stack is that you can “push” the turtle’s current position and heading onto the stack and “pop” off the top of the stack to return the turtle to the most recently pushed position and heading. You can think of it like a stack of papers where you can only take off the top and add new pages to the top.

These instructions are usually assigned unique constants: \([\) for push and \(]\) for pull. This provides a convenient way to read the rules. We can see these being used in a more complicated L-system:

• Variables: \(X\) and \(F\)

• Constants: \(+\), \(-\), \([\), and \(]\)

• Start: \(-X\)

• Rules: \(\left(X \rightarrow F+\left[\left[X\right]-X\right]-F\left[-FX\right]+X\right)\) and \((F \rightarrow FF)\)

• Turn angle: \(25^\circ\)

Here, \(X\) is a “do nothing” instruction that helps facilitate the growth of the tree. After 6 iterations, the turtle’s path looks like:

Hopefully you can see that by tweaking the rules and parameters of the L-system, you can create incredibly complicated fractal designs. As with cellular automata, you could change the rules partway through the iterations or randomly select a rule to apply to each variable at each iteration, which can produce incredibly complex designs.