Introduction to L-system trees

Minetest has two types of trees built in: small ones similar like in minecraft, and more complex ones generated using a L-system and a tree definition. L-system trees can be spawned with minetest.spawn_tree and are defined by a treedef table.

The following chat log might be helpful in understanding how L-system trees work: #minetest 2013-08-08

turtle graphics

the L-system (short for Lindenmayer system) is much like turtle graphics: there is a cursor, its called the turtle. It can be moved and rotated, and place none, one or more nodes in each step, depending on the used command:

G move forward one unit with the pen up

F move forward one unit with the pen down drawing trunks and branches

f move forward one unit with the pen down drawing leaves (100% chance)

T move forward one unit with the pen down drawing trunks only

R move forward one unit with the pen down placing fruit

+ yaw the turtle right by angle parameter

- yaw the turtle left by angle parameter

& pitch the turtle down by angle parameter

^ pitch the turtle up by angle parameter

/ roll the turtle to the right by angle parameter

* roll the turtle to the left by angle parameter

The turtle always starts facing up.

axiom

if the axiom is TTTT the result is four vertically stacked nodes of trunk material. the turtle starts at its spawn position, and does the step T four times. T is "move forward one unit with the pen down drawing trunks only". Because the turtle is initially facing up, the resulting structure is vertical.

With the axiom TTTTT&TTTTT&TTTTT&TTTTT and the angle set to 90 degrees the result is a square of trunk material. After this program the turtle will be back on its spawn position, lying on its side, facing left.

stack

[ save in stack current state info

] recover from stack state info

with these commands it is possible to save and recover both position and direction of the turtle. The axiom TTTTT[^TTTTT][&TTTTT] with the angle set to 60 degrees makes Y shape. As always the turtle starts at spawn position, facing up. it goes forwards (up!) 5 times, placing trunks. then the position and rotation are saved. The part wrapped in [] is done, and the turtle is back to the position we saved before. Now the 2nd branch is done, starting from the same pos as the first.

Lindenmayer basics

A L-system 'program' consists of the axiom and replacement rules. In addition to above turtle commands the letters A, B, C and D and a, b, c, and d can be used in L-systems. Everytime one of those letters is found in the axiom, it will be replaced with the whole corresponding rule. this will be done until there are no more replacements to do or the maximum recursion depth is reached.

Lets say we want to create a fractal Y shape: its like a Y but both ends of it are themselves shaped like Ys. With 3 recursions this should give us a total of 8 (2^3) ends.

here is the axiom: TTTTTA now rule A needs to create the branch. If rule A itself uses an A at its end, that will be replaced again, and so on... rule a is this: [^TTTTTA][&TTTTTA].

lets look at it step by step: first we do the axiom, just a vertical trunk. then on its top is added one V shape (rule A). All in all the tree now looks like this: TTTTT[^TTTTTA][&TTTTTA] (the first A has been replaced by the whole of rule A). in the next step both A's at the end of the branches are replaced, again with the whole of rule A, giving this: TTTTT[^TTTTT[^TTTTTA][&TTTTTA]][&TTTTT[^TTTTTA][&TTTTTA]]

and after the 3rd recursion this is the result: