L System Node Rewriting example

Question

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.

Answer 1

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