Lindenmayer systems are used to generate and describe self-similar objects. These systems can be created with a varying level of complexity and categorization. Here we will create a 0-context stochastic system, with just one rule. That rule will be:
$\text{A} \xrightarrow{\frac{1}{3}} \text{F[+(a)FA][-(a)FA]A}$
$\text{A} \xrightarrow{\frac{1}{3}} \text{F[+(a)FA]A}$
$\text{A} \xrightarrow{\frac{1}{3}} \text{F[-(a)FA]A}$
These rules specify, that we have a $\frac{1}{3}$ change of generating two branches, $\frac{1}{3}$ chance of generating a left branch, and $\frac{1}{3}$ chance of generating a right branch. The symbols are fairly standard and specify:
Symbol | Meaning | Turtle interpretation |
---|---|---|
A | Bud, that generates to a next part of the tree in a later iteration. | – |
F | One segment of a branch / trunk. | Draw a line forward. |
+(a) | Rotate left by the angle a. | |
-(a) | Rotate right by the angle a. | |
[ | Start of a branch. | Save the current state. |
] | End of a branch. | Load the last state. |
You can see similar symbols also in Lindenmayer's The Algorithmic Beauty of Plants (PDF page 221).
In this task, we will write a program to iterate the system starting from just one axiom (bud) $\text{A}$. In order to draw the system, we will use the concept of turtle graphics. This means, that we have an imaginary turtle, who is drawing lines to the paths it moves on. The turtle knows how to draw a line forward, turn left or right. We can also use a stack to save and load turtle's position (just like we used a matrix stack before).
As you probably have noticed, we only have one rotation here. This means, that we are using 2D to represent our trees. The parameter $\text{a}$ for the rotation, will be a random angle from the range $[20, 30)$ degrees.
The final result can look similar to this:
Each row here, shows the same system generated with a different number of iterations.
Here is a list of things to do:
You can also use some other grammar and rules, or other coefficients, if you want.
Because this is 2D, then we get to use the canvas drawing for JavaScript and Allegro for C++ again.
JavaScript
The base code is located at:
https://cglearn.codelight.eu/files/course/12/2/LindenmayerTreeJS.zip
We are encoding the JSON of the turtle to a string in order to save (copy) it to the stack.
C++
The base code is located at:
https://cglearn.codelight.eu/files/course/12/2/LindenmayerTreeCPP.zip
Here we are using mostly the standard library components (map, vector, stack, string, random). There seems to be a problem with using the stof() function to convert string to a float (when reading the system). This seems to be a bug with Windows and CodeBlock's compiler. I created a work-around with a string stream.
Also, the [SPACE] key will regenerate the trees here.