5

This is my first post in stackover flow. Recently I started reading the book called "Algorithmic beauty of plants" where, in chapter 1, he explains L system. (You can read the chapter here).

So as I understand there are two types of L systems. Edge rewriting and Node rewriting.

Edge rewriting is relatively very simple. There is a initial starter polygon and a generator. Each edge(side) of the initial polygon will be replaced with the generator.

But this node rewriting is very confusing. From what I gathered, there are two or more rules and with each iteration replace the variables in the rules with their constant counterparts.

With turtle interpretation these are standard rules

F : Move turtle forward in current direction (initial direction is up)
+ : rotate turtle clock wise
- : rotate turtle anti clock wise
[ : Push the current state of the turtle onto a pushdown operations stack. 
    The information saved on the stack contains the turtle’s position and orientation, 
    and possibly other attributes such as the  color and width of lines being drawn.
] : Pop a state from the stack and make it the current state of the turtle

So consider the example as shown in this website. http://www.selcukergen.net/ncca_lsystems_research/lsystems.html

Axiom     : FX
Rule      : X= +F-F-F+FX 
Angle     : 45

so at n=0 (ignore the X in axiom)

its just F that means a straight line pointing up.

at n=1

replace X in axiom with rule

F+F-F-F+F (ignoring the X in the end again)

output is this

http://www.selcukergen.net/ncca_lsystems_research/images/noderewrite.jpg

a simple example with one rule is ok. but in the book "Algorithmic beauty of plants" at page 25 there are some rules I'm not sure how to interpret.

X
X = F[+X]F[-X]+X
F = FF

See this image.

https://lh6.googleusercontent.com/g3aPb1SQpvnzvDttsiiBgiUflrj7R2V29-D60IDahJs=w195-h344-no

at n=0

just 'X'. not sure what this means

at n=1

applying rule 1 (X->F[+X]F[-X]+X) : F[+]F[-]+ ignoring all X. this is just a straight line.

applying rule 2 (F->FF) : FF[+]FF[-]. this is just a straight line.

Final output should be turtle moving four times in up direction as for my understanding. Or at most the final output should contain just four lines.

I found a online L-system generator which i thought will help me in understanding this better so i inputted the same values and here is how the output looks like at n=1

https://lh6.googleusercontent.com/-mj7x0OzoPk4/VK-oMHJsCMI/AAAAAAAAD3o/Qlk_02_goAU/w526-h851-no/Capture%2B2.PNG

output is definitely not a straight line and worst part it has 5 lines that means there should be 5 F in the final output equation.

Help me understanding this node rewriting. Without understanding this i cant read further into the book.

Sorry for the long post, and for links in pre tag. i cant post more than 2 links. Thanks for having patience of reading it from top to bottom.

Plato Manchi
  • 59
  • 7
  • It is important to distinguish commands (letters in your case) that dictate how to draw the fractal from those only used in rule mutation. The `X` here is the latter whereas the rest is the former. As such you cannot just "ignore" the X, but you don't draw it, it has no visible impact on the fractal on your screen, but it will be used during rule mutation to obtain the next generation. So `FX` means draw a line, and ignore the X. But then you mutate and F means F and X means `+F-F-F+FX`. – Lasse V. Karlsen Jan 09 '15 at 10:23
  • yes. i meant ignoring to draw on screen but it will be used while generating the next mutation rule. i understood this from the first example. but the look at the example from the book. i'm unable to understand how the iterations happen.if you can show me what the first iteration and second iteration looks like that would be really helpful. thanks – Plato Manchi Jan 09 '15 at 11:53
  • It is a simple substitution rule. When generating n(x) you take n(x-1) and for each character in it that you have a substitution rule, you substitute it for the rule value. With n(0) = "FX" and "X=+F-F-F+FX", n(1) becomes "F+F-F-F+FX". n(2) becomes "F+F-F-F+F+F-F-F+FX", every time you replace every X with its value (which includes a new X). There may be more than one substitution rule so you would generally loop through the input one character at a time, and if you have a substitution for that character, output that, otherwise just output the character. – Lasse V. Karlsen Jan 09 '15 at 13:39

1 Answers1

6

L systems are very simple and rely on text substitutions.

With this starting information:

Axiom     : FX
Rule      : X= +F-F-F+FX

Then basically, to produce the next generation of the system you take the previous generation and for each character in it you apply the substitutions.

You can use this algorithm to produce a generation:

  • For each character in the previous generation:
    • Check if we have a substitution rule for that character
      • YES: Append the substitution
      • NO: Append the original character

Thus:

n(0) = FX

            +-- from the X
            |
        v---+---v
n(1) = F+F-F-F+FX
       ^
       +- the original F

If you had this start instead:

Axiom : ABA
Rule  : A = AB

Then you would have this:

        +--------+
        |        |
n(0) = ABA       |
       | |       |
       | ++      |
       |  |      |
       vv vv     |
n(1) = ABBAB     |
         ^       |
         +-------+

Basically:

  • For every A in generation X, when producing generation X+1, output AB
  • For every other character without a rule, just output that character (this handles all the B's)

This would be a system that doubles in length for every generation:

Axiom : A
Rule  : A = AA

would create:

n(0) = A
n(1) = AA
n(2) = AAAA
n(3) = AAAAAAAA
Lasse V. Karlsen
  • 380,855
  • 102
  • 628
  • 825
  • with these rules in mind can you please tell me the n(1) and n(2) iterations please. X X = F[+X]F[-X]+X F = FF according to my understanding i just have to replace n(0) = X n(1) = FF[+X]FF[-X]+X if i draw this then it will look like straight line pointing up with 4 units length. but in the generator the output looks different. n(2) = – Plato Manchi Jan 09 '15 at 13:59
  • sorry my bad. the actual n(2) equation is giving the correct output as the one shown in the l-system online generator at iteration 1. that is source of all my confusion thanks for that explanation. made lots of things clear for me. (http://www.kevs3d.co.uk/dev/lsystems/) – Plato Manchi Jan 09 '15 at 14:10
  • one doubt though, if there are more than 1 rule does the order of substitution has to be same as order of rules? or it can be of any order? – Plato Manchi Jan 09 '15 at 14:14
  • There cannot be more than one rule per character. And since you're doing a per-character substitution, order means nothing. – Lasse V. Karlsen Jan 09 '15 at 14:47