Lindenmayer Tree

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: 

SymbolMeaningTurtle 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:

  • Represent the rules of the system.
  • Iterate the system a specified number of times.
  • Rewrite the system in each iteration. This means applying the rule with the specified probability.
  • Before applying the rule, replace the parameter $\text{a}$ for the rotation by a random angle from the $[20, 30)$ degree range.
  • When the system is generated, use turtle graphics to draw the system. This means, read the resulting string and do the corresponding action for each symbol.
  • When drawing the tree, decrement the line width (thickness) and length. For sequential segments, multiply them with 0.92 and 0.98 respectively. When branching, multiply the thickness also by 0.707. Generally you would want to do that, when you are generating the system, but for simplicity, we can currently do it, when drawing.

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.

;