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.
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 "" or "", 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 represents that the symbol transforms into the symbols on every iteration. The length of derivation, or the number of iterations, is represented by . Given a word and productions and , the following illustrates how the word transforms over several iterations, from to .
L-systems are formalized as a tuple with the following definition:
Where the components are:
- , the alphabet, or all potential symbols in the string.
- , the starting word, also known as the axiom, comprised of symbols from .
- , a series of productions describing the transformations or rules.
The L-system in Figure 1 can be formalized by defining its axiom () and a series of productions () as:
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 and , 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 , 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:
- move forward by units while drawing a line.
- rotate left by angle .
- rotate right by angle .
The variables and 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, and symbols are replaced with more , and symbols. With the angle defined as 90, this results in recursively generated square wave shape along a curve. While , and are interpreted by the turtle, other symbols can be used for productions. In this case, and 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 and in the production rule, adjacent to the predecessor. In Figure 5, the first production rule only matches when the symbol is immediately after , thus replacing the predecessor with its successor, . This results in the symbol moving towards the right:
A similar system could be defined that propagates from right to left, defined via production , replacing when there is a 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 will be replaced by successor when it is between an 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, has a 50% chance to be rewritten as , and a 50% chance to be rewritten as .
This non-determinism is useful for procedurally creating variety and the seemingly random results of nature.