# L-systems

L-systems are used to describe and generate branching structures or geometric objects that exhibit self-similarity. Such structures may be 2D, 3D, or potentially in higher dimensions. L-systems are frequently used to generate computer graphic renderings of trees, bushes, grasses, and other plant life. L-systems can also be used in the exploration of fractals.

The "L" in "L-system" refers to its inventor Aristid Lindenmayer. Such systems produce a string expression that can be rendered into graphics. The string is essentially a series of commands for moving a virtual pen. The commands are executed from left to right. (From a historical perspective this is similar to Logo's "turtle graphics").

## Rendering L-system Command Expressions

Introductory example

To render an L-system expression both a set of system constants and a set of command symbols must first be defined. The following example demonstrates the rendering of a typical basic L-system result.

System Constants

• δ = angle increment
• d = step size (length increment)

Basic Commands

• F is move forward with length d with pen down
• f is move forward with length d with pen up
• + is turn left by angle δ
• - is turn right by angle δ
• [ pushes current state down the stack (i.e. saves position and heading)
• ] pops the current state off the stack (i.e. gets position and heading)

Example - How to Interpret a String

```δ = 45°
d = 2
F[+F]F[-F]F
``` Example showing string interpretation

## How L-systems Grow

String rewriting/substitution

L-systems "grow" via iterative string substitution. The system initially has three components.

System Constants

• n = number of times to apply production rules
• δ = angle increment
• d = step size (length increment)

Axiom

• an initial string expression typically labeled as "w:"

Production Rules

• rules for applying string substitutions typically labeled as p#: and applied "n" times.
• uses the syntax "Sym1 → Str1" meaning "When Symbol 1 is found substitute String 1."

Example

```n = 3
δ = 25.7°
d = 1

w: F (Axiom)

p: F → F[+F]F[-F]F (Production Rule)

n = 0; F
n = 1; F[+F]F[-F]F
n = 2; F[+F]F[-F]F[+F[+F]F[-F]F]F[+F]F[-F]F[-F[+F]F[-F]F]F[+F]F[-F]F
``` Example showing string substitution

## Null Symbols

L Systems can also have symbols that have no drawing operations associated with them, but add complexity when applying production rules.

Example

``` w: X
p1: X → F[+X]F[-X]+X
p2: F → FF

n = 0; X
n = 1; F[+X]F[-X]+X
n = 2; FF[+F[+X]F[-X]+X]FF[-F[+X]F[-X]+X]+F[+X]F[-X]+X
``` Example showing string substitution with symbols

## Examples of Branching Structures

How production rules create form Branching Structures

## Stochastic L-systems

L-systems combined with chance operations

Like typical L-systems, but with multiple production rules for a single expression, each with a probability. The sum of all the probabilities must total to 1.

Syntax Added to the Production Rules

"Sym1 (.#)→ Str1" = "When Symbol 1 is matched there is a .# probability that String 1 should be substituted"

Example

```w: F
p1: F (0.33)→ F[+F]F[-F]F
p2: F (0.33)→ F[+F]F
p3: F (0.33)→ F[-F]F
``` Stochastic L-system

Example Stochastic L-system

## Context Sensitive L-systems

Simulating hormones and chemical triggers

Context sensitive L-systems can create signals (sub-strings) that travel the length of the branching structure string as it grows. The signals can, in turn, determine the location of new branches, flowers, buds, etc.

Syntax Added to the Production Rules

"*" = matches any symbol

"Sym1 < Sym2 > Sym3 → Str1" = "When Symbol 2 has Symbol 1 to the left and Symbol 3 to the right, substitute String 1 for Symbol 2." Context Sensitive L-systems Context Sensitive L-systems

## Genetic L-systems

Systems that allow the evolution of form

L-systems can be combined with genetic algorithms. It is typically very difficult to start with a given plant or intended form and invent a set of production rules that will produce it. By encapsulating the L-system within an evolutionary system one can "navigate" the design space and guide the system towards the intended result without having to understand or inspect the actual production rules.

For genetic L-systems:

• Initial condition, axioms and production rules must be translated into gene representation
• Genetic operations must be adapted for L System genes
• Mutation: mutations can be applied to a string converted to a parsed tree representation a la Karl Sims. Care must be taken to not generate syntactically incorrect command strings.
• Crossover: crossover is even more prone to creating syntax problems. Note again Karl Sims' work with mathematical image processing expressions. Alternately, crossover can be achieved by swapping individual production rules without altering individual production rules.