L-systems : draw nice fractals and plants (part I)
Note: part II is available here.
In 1968, Hungarian botanist Aristid Lindenmayer developed a grammar-based system to model the growth patterns of plants. Lindenmayer systems — or L-systems for short — were originally conceived as a mathematical theory of plant development. However, we are going to use them generate self-similar fractal patterns.
Fractals are mathematical object whose structure stays the same after changing the scale. As described by Benoit Mandelbrot, it is “a rough or fragmented geometric shape that can be split into parts, each of which is (at least approximately) a reduced-size copy of the whole.”
On one side, a central concept of L-systems is that of rewriting. It is a technique for defining complex objects by successively replacing parts of a simple initial object using a set of rewriting rules.
On the other side, a fundamental component of fractals geometry is recursion, which is the repeated application of a rule to successive results. Therefore, the rewriting concept of L-systems is an efficient mechanism to apply recursion in order to achieve complex fractals.
For now, let’s take the L-system in their most basic form: a method to generate a sentence using rules. We will see later how to explore this to generate shapes instead of words and sentences.
L-systems involves three main components:
1. Alphabet: a set of valid characters that can be included in a “sentence”. For example, if the alphabet is “ABC”, any valid “sentence” will contain the three characters : A, B and C.
2. Axiom: The sentence that describes the initial state of the system. For example, using the alphabet “ABC,” some example axioms are “AAA” or “B” or “ACBAB.”
3. Rules: they are applied to the axiom and then applied recursively, generating new sentences over and over again. An L-system rule includes two sentences, a “predecessor” and a “successor.” For example, with the Rule “A → AB”, whenever an “A” is found in a string, it is replaced with “AB.”
Let’s begin with a very simple L-system. (This is, in fact, Lindenmayer’s original L-system for modeling the growth of algae.)
Alphabet : A B
Axiom : A
Rules : ( A -> AB) ( B -> A )
We take the axiom sentence and apply the rule to it to get a new sentence : that is the first generation. We reapply the rules to each generation and each time we get a new sentence.
Now, you may be asking what all of this has to do with fractal generation? The answer of this question is that we can replace each letter of the alphabet with an action. For example, A can be used to draw a line and B can be used to move without drawing.
Example 1: Cantor set
Let’s take our first example with shapes.
Alphabet: A B
Axiom: A
Rules: ( A -> ABA ) ( B -> BBB )
A: Draw a line forward.
B: Move forward without drawing.
Let’s look at the output of a few generations:
Generation 0: A
Generation 1: ABA
Generation 2: ABABBBABA
Generation 3: ABABBBABABBBBBBBBBABABBBA
Now, let’s replace each letter of the alphabet with its corresponding action. We get the Cantor set, which is one of the first fractals discovered in modern mathematics. It was developed in 1883 by the German mathematician George Cantor.
After this basic example, let’s tackle to more interesting examples. For the next examples, we will use the following alphabet which is often used with L-systems : “FG+-[]”, with :
F: Draw a line and move forward
G: Move forward (without drawing a line)
+: Turn right
-: Turn left
[: Save current location
]: Restore previous location
This type of drawing framework is called “Turtle graphics”, it is like having a turtle in the screen and being able to command it to move in different directions. We need to adjust some parameters before using this alphabet such as the length of the line that should be drawn, the angle of rotation while turning, and we can also add a scale factor to scale down the length of lines in each generation.
Example 2: Snowflake curve
To generate the snowflake curve we are going to use two shapes : an initiator and a generator. The generator is applied to each line of the initiator, then we get the first generation. We apply this rule again to get the next generations and each time we scale down the generator in order to have the same length as the lines.
As we are going to use an L-system to generate this snowflake curve. Our axiom is going to be the sentence representing the initiator. Then, we have to figure out the rule that transforms a line to the generator shape.
Let’s begin by translating the generator to a rule. We need to write a sentence capable of transforming a line to the shape corresponding to the generator.
It is the following rule : ( F -> F-F++F-F ). With an angle of rotation of 60 degrees, which correspond to the angle of an equilateral triangle. A scaling factor of 1/3 has been added to each generation to ensure that the length of the shape remains the same in each generation.
For the initiator, we will use the following axiom : F++F++F which correspond to drawing a vertical line, then making a 120 degrees rotation and drawing a line, then rotating 120 degrees again and drawing the final line to complete the triangle.
Alphabet : F G + — [ ]
Axiom : F++F++F
Rule : ( F -> F-F++F-F )
Now as we generated the snowflake curve with an L-system, we have seen how it is possible to reproduce shapes from nature with a recursive system. Let’s try to go further by reproducing a plant shape with an L-system.
Other Examples:
Koch Curve:
Alphabet : F G + — [ ]
Axiom : + F
Rule : ( F -> F+F−F−F+F)
Sierpinski triangle:
Alphabet : F G + — [ ]
Axiom : F
Rule : ( G -> F-G-F) ( F -> G+F+G)
Try it yourself !
If you want to experiment yourself with L-systems, you can use my Python code to draw your own fractals. Check this at my Github project : https://github.com/hhassen/L-system
Feel free to share your fractals, to improve the code or to share your suggestions.
Conclusion
L-system is a powerful system that can allow us to generate fractals, as well as plants (as we are going to see in the next article).
L-systems are used today not only to generate 2d fractals and plants, but also to generate 3d shapes and even generate a whole world in video games. For instance, “No Man’s Sky” developers took the approach of L-systems and extended its use to generate a procedural game world which feels deep and coherent.
References :
“The Nature of Code” by Daniel Shiffman
“The Algorithmic Beauty of Plants” by Przemyslaw Prusinkiewicz & Aristid Lindenmayer
