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⟶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
b⟶a, the following illustrates how the word transforms over several iterations, from
L-systems are formalized as a tuple with the following definition:
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 (
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.
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
y, and an angle
α 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
− 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 δ.
− rotate right by angle δ.
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 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.
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,
Y symbols are replaced with more
Y symbols. With the angle
δ defined as 90, this results in recursively generated square wave shape along a curve. While
− are interpreted by the turtle, other symbols can be used for productions. In this case,
Y are ignored when rendering, and only relevant when rewriting the string and matching productions.
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 δ.
− turn right by angle δ.
& pitch down by angle δ.
∧ pitch up by angle δ.
roll left by angle δ.
/ roll right by angle δ.
∣ 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.
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.
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
> 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:
A similar system could be defined that propagates
b from right to left, defined via production
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:
This production rule indicates that the predecessor
X will be replaced by successor
Y when it is between an
A and a
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
This non-determinism is useful for procedurally creating variety and the seemingly random results of nature.