Job Talle

On AI, Art & Algorithms

Lindenmayer systems

Natural patterns

Lindenmayer systems were originally conceived by Hungarian biologist Aristid Lindenmayer while studying algae growth. He developed L-systems as a way to describe the growth process of algae and simple plants. The result was a type of language in which the recursive and self similar properties of organism growth can be expressed. Indeed, L-systems can be used to generate natural patterns, but well known mathematical patterns can also be written as an L-system. In this article, I will explain different flavors of L-systems, and I will demonstrate them by rendering 2D Lindenmayer systems and 3D Lindenmayer systems using turtle graphics.

The language is very simple. It consists of symbols (the alphabet) and production rules. The first state of the sentence is called the axiom. The production rules can be applied repeatedly on this axiom to evolve or grow the system. A simple example would be a system with the axiom $A$, and the rule $A \to ABA$. After the first iteration (the first time the rule is applied), the sentence will be changed to $ABA$. After the second iteration, the sentence will be $ABABABA$ and so forth. You can see how a self expanding sentence can be analogous to cell division in plants and other biological processes.

[A...Z]

+

-

[

]

Rendering sentences

After a system has been defined and iterated, we have a large sentence with interesting properties. To visualize these properties, a method to render them needs to be devised. In this article, I render the system using turtle graphics.

Turtle graphics are rendered by placing a "turtle" on a cartesian plane and passing instructions to this turtle. The turtle moves according to the instructions it receives. The turtle draws by leaving a trail behind it. In this case, every symbol from an L-system sentence is sent to the turtle. In the short example above, my sentence is a bit simple. It only contains letters. It is hard to translate a string of letters to interesting turtle instructions. Therefore, special symbols are defined to encode turtle commands. Figure 1 shows the key for my turtle language.

I added an interactive 2D Lindenmayer system renderer below. A number of examples are provided, but custom systems can be defined for up to six production rules. Note that I added the field constants, which can contain a string of symbols. When the turtle renders a string, symbols that are constants will be ignored by the turtle. Symbols that are constants are still subject to the rules. The field angle denotes the number of degrees the turtle will rotate when either + or - is encountered. In the rule fields, the constant AXIOM can be used. It will be replaced by the original axiom. This is used in several examples.

The source code for this javascript example can be found in this repository. The provided example systems show some possibilities of Lindenmayer systems, ranging from noisy random-like patterns to rigid geometric patterns. All systems show self-similarity; when the number of iterations becomes high, the small details they produce are no longer noticable. In theory however, one could zoom in infinitely while increasing precision along the way. This is a well known property of fractals. Zooming in on fractals will often reveal patterns that were also visible at larger scales.

Adding dimensions

The example above is fully capable of demonstrating Lindenmayer systems, but I'd like to add a few features to make the algorithm more powerful. I'm personally very interested in using 3D Lindenmayer systems to generate plants and natural systems. A very interesting source of information on this topic is the website of the Biological Modeling and Visualization research group at the university of Calgary. There are many papers available on this topic, which can be found at their website.

I'd like to keep my system as simple as possible, but I am missing some features I need to make more complex systems. I would like to model at least the following things:

• Some degree of randomization should be possible, because I assume some form randomness exists in nature
• I want symbols to be able to keep track of their age, since cells in nature may also behave differently depending on age
• Production rules should take symbol context into account
• I want to keep track of the distance to the root cell
• The turtle should move in three dimensions to allow for more complex shapes

Moving in three dimensions is not hard. Instead of moving on a cartesian plane like I did in the example above, the turtle will now be a position with a quaternion. Every step, I will add a unit vector (pointing upwards) rotated by this quaternion to the turtle position, and the quaternion will be rotated when rotation symbols are encountered. Modelling the other features as simple as possible is a bit more tricky.

[A...Z]

+

-

/

\

^

_

[

]

Parametric grammar

To facilitate the new features, I need to extend my alphabet and syntax. Figure 2 shows the key for this new system. The new symbols in this table are rotation symbols required for moving the turtle in 3D space.

Randomness can easily be modelled by adding multiple ambiguous production rules for the same symbol. When multiple rules exist for a symbol, a random one is chosen.

To model cell age and distance to root, I could add two variables to each symbol. If I would then like to add more properties, I need to add more variables. This is not very flexible and oddly specific. Luckily, a general solution is available: parametric Lindenmayer systems. In parametric L-systems, each symbol is succeeded by a list of parameters (if it has any). Production rules may only be valid for symbols with a specific set of parameters or for certain conditions of these parameters, and the symbols resulting from the rule can have parameters too.

I will demonstrate this new system with an example of a symbol with one parameter, which is its age in iterations. Suppose the axiom is $A(0)$, and one production rule $A(x) \to A(x + 1)$. For every iteration, every symbol $A$ will have its parameter increased by one. Now I want to change every $A$ to a $B$ when it is eight iterations old. The production rule for this would be $A(x) : x == 8 \to B$. If I would define the production rule $A(x, y) \to C$ for the described system, it would never fire; no $A$ with more than one parameter exists in this sytem. Note that $x$ and $y$ in these examples are chosen arbitrarily; they are used to do something with the values of the parameters. These parameters have no specific names, $x$ and $y$ are just variables and can be any symbol.

I have now added two syntax rules to the language; brackets behind a symbol contain a number of parameters separated by commas, and the first operand of a production rule can be succeeded by a $:$ symbol if it should only fire when the condition after this symbol is met. Parametric grammar allows for many more features than just the ones I initially required.

Context sensitive grammar

The system is almost complete. One last thing I would like to encode is context. The context of a symbol should be able to influence what rules are applied to it. I could in theory encode context in symbol parameters, but this would result in a very complex system of rules and parameter lists. Instead, I add one last syntax rule to the production methods.

Suppose I have an axiom consisting of a number of $A$'s and one $B$ at the beginning, and I want the $B$ to move one step to the right on each iteration, without changing the sentence length. This can be done with a context sensitive rule. The first rule I introduce is $B < A \to B$. This should be read as follows: $A \to B$ if $A$ is preceded by $B$. Every iteration this rule is applied, every $A$ with a $B$ to the left will change to a $B$. Now I only want the $B$ to move, so after every iteration the $B$ should become an $A$ again to prevent every $A$ from becoming a $B$ over time. The simple rule $B \to A$ does this. Figure 1 shows this system evolving for eleven iterations, where the initial axiom was $BAAAAAAAAA$.

This context sensitive grammar is compatible with the parametric grammar described earlier. Suppose I have a sentence of several instances of $A(x)$ where the value of $x$ varies between symbols. I want to make a context sensitive production rule which changes $A$ to $B$ only if $A$ is surrounded by other instances of $A$ whose parameters are equal; in other words, there must be an $A$ on the left and an $A$ on the right with the same parameter values. The production rule looks like this:

$$A(x) < A(y) > A(z) : x == z \to B$$

So the final addition to the grammar are the $<$ and $>$ symbols. If the left operand of a production rule is preceded by $<$, it requires the symbol before $<$ as context. If it is succeeded by $>$, it requires the symbol after $>$ as context. Production rules can also have no required context or only left or only right context.

A 3D context sensitive parametric Lindenmayer system

Everything is now in place for a 3D context sensitive parametric Lindenmayer system renderer, which I have implemented below. All features described in this article are present. Most of the fields from the 2D renderer included earlier in this article are copied, but this system also includes a button to evolve for one step at a time, and the resulting sentence is printed. The parser for context sensitive parametric lindenmayer systems can be found in this repository.

Several rendering modes are included. The generated 3D image can be rotated by dragging the mouse (or finger on a touch screen), and the mouse wheel can zoom in or out on the image. The source code for this renderer can be found on GitHub. Press the Go button to generate the current system.

Conclusion

Lindenmayer systems can produce very interesting and life like patterns, which can be useful in many applications. Besides modelling fractals, it can also be used to generate natural looking content like trees and plants. Another application would be procedural environment generation, where context sensitive rules would play an important role. I also suspect lindenmayer systems can be evolved using genetic algorithms by slightly mutating the production rules. This would be a very interesting way to evolve plants, and I'd like to experiment with this if I find the time. (Update: in 2020, I published an article on simulating plant evolution with Lindenmayer systems, this blog post contains that research.)

L-systems appear to be able to model nature at least to some degree. I'm curious to what extent they are really able to model natural growth processes with the simple rules I've been able to find.