Difference between revisions of "Introduction to L-system trees"

Revision as of 15:54, 26 January 2015

Minetest has two types of trees built in: Small simple ones like the trees in the vanilla Minetest game, 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, it is called the turtle. It can be moved and rotated, and place none, one or more nodes in each step, depending on the used command:

Symbol	Action
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

Symbol	Action
+	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 means “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

Symbol	Action
[	Push/save current state into stack
]	Pop/recover current state from stack

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 a “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 [ and ] 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

Replacing

A L-system “program” consists of the axiom and replacement rules. In addition to above, turtle commands the letters A, B, C, 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. The capital letters will always be replaced with the rule, the lowercase letters will only be replaced by chance, and are ignored otherwise.

Symbol	Action
A	Replace with rule A
B	Replace with rule B
C	Replace with rule C
D	Replace with rule D

Example

Let's say we want to create a fractal “Y” shape: It looks like a “Y” but both ends of it are themselves shaped like “Y”s. With 3 recursions this should give us a total of 8 (2³) 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]

Let's 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:

Replacing by chance

The symbols a, b, c, d work like the symbols A, B, C, and D, respectively, but they will only be replaced by chance.

Symbol	Action
a	Replace with rule A with a 90% chance, do nothing otherwise
b	Replace with rule B with a 80% chance, do nothing otherwise
c	Replace with rule C with a 70% chance, do nothing otherwise
d	Replace with rule D with a 60% chance, do nothing otherwise

@@ Line 1: / Line 1: @@
-Minetest has two types of trees built in: small ones similar like in minecraft, and more complex ones
+Minetest has two types of trees built in: Small simple ones like the trees in the vanilla Minetest game, 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.
@@ Line 5: / Line 5: @@
 The following chat log might be helpful in understanding how L-system trees work: [http://irc.minetest.ru/minetest/2013-08-08#i_3250058 #minetest 2013-08-08]
-'''turtle graphics'''
+== Turtle graphics ==
-the L-system (short for Lindenmayer system) is much like turtle graphics: there is a cursor, its called the turtle.
+The L-system (short for Lindenmayer system) is much like turtle graphics: there is a cursor, it is 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
+{| class="wikitable"
-: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)
+! Symbol !! Action
-:T move forward one unit with the pen down drawing trunks only
+|-
-:R move forward one unit with the pen down placing fruit
+| 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
+{| class="wikitable"
-:- yaw the turtle left by angle parameter
+|-
-:& pitch the turtle down by angle parameter
+! Symbol !! Action
-:^ pitch the turtle up by angle parameter
+|-
-:/ roll the turtle to the right by angle parameter
+| + || Yaw the turtle right by angle parameter
-:<nowiki/>* roll the turtle to the left 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
+|-
+| <nowiki/>* || Roll the turtle to the left by angle parameter
+|}
 The turtle always starts facing up.
-'''axiom'''
+== 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.
+If the axiom is <code>TTTT</code> 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 means “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.
+With the axiom <code>TTTTT&TTTTT&TTTTT&TTTTT</code> 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'''
+== Stack ==
-:[ save in stack current state info
+{| class="wikitable"
-:] recover from stack state info
+|-
+! Symbol !! Action
+|-
+| [ || Push/save current state into stack
+|-
+| ] || Pop/recover current state from stack
+|}
-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.
+With these commands it is possible to save and recover both position and direction of the turtle. The axiom <code>TTTTT[^TTTTT][&TTTTT]</code> with the angle set to 60 degrees makes a “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 <code>[</code> and <code>]</code> 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'''
+== Lindenmayer basics ==
+=== Replacing ===
+A L-system “program” consists of the axiom and replacement rules. In addition to above, turtle commands the letters A, B, C, 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. The capital letters will always be replaced with the rule, the lowercase letters will only be replaced by chance, and are ignored otherwise.
-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.
+{| class="wikitable"
+|-
+! Symbol !! Action
+|-
+| A || Replace with rule A
+|-
+| B || Replace with rule B
+|-
+| C || Replace with rule C
+|-
+| D || Replace with rule D
+|}
-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.
+==== Example ====
+Let's say we want to create a fractal “Y” shape: It looks like a “Y” but both ends of it are themselves shaped like “Y”s. With 3 recursions this should give us a total of 8 (2<sup>3</sup>) 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].
+Here is the axiom: <code>TTTTTA</code>
+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: <code>[^TTTTTA][&TTTTTA]</code>
-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:
+Let's 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: <code>TTTTT[^TTTTTA][&TTTTTA]</code> (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]]
+<code>TTTTT[^TTTTT[^TTTTTA][&TTTTTA]][&TTTTT[^TTTTTA][&TTTTTA]]</code>
-and after the 3rd recursion this is the result:
+And after the 3rd recursion this is the result:
 [[File:mtwikitreegen.png|frameless|recursive y]]
+=== Replacing by chance ===
+The symbols a, b, c, d work like the symbols A, B, C, and D, respectively, but they will only be replaced by chance.
+{| class="wikitable"
+|-
+! Symbol !! Action
+|-
+| a || Replace with rule A with a 90% chance, do nothing otherwise
+|-
+| b || Replace with rule B with a 80% chance, do nothing otherwise
+|-
+| c || Replace with rule C with a 70% chance, do nothing otherwise
+|-
+| d || Replace with rule D with a 60% chance, do nothing otherwise
+|}