#### Archived

This topic is now archived and is closed to further replies.

# L-Grammars

This topic is 5711 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I have heard that one could use something called "L-Grammars" to create tree effects in games. I have done a few searches, and could not find any good explanations. Does anyone here know how L-Grammars work, or have a URL to a page that explains them?

##### Share on other sites
L-systems.

Define a set of tokens, each having a meaning.
e.g. (simplisitic)
F = go forwardS = scale length downA = scale angles downR = rotate clockwiseL = rotate counterclockwise() = subexpression is a ''branch'', state is restored when leaving the subexpression.

Then define substitution rules :
Start -> FF -> SF(LAF)(RAF)

Set a recursion threshold (ex: 3)
Set the global parameters (here length, angle)
(they could be part of the expression itself)

Do the substitutions, generate the figure. Here:
0 Start1 F2 SF(LAF)(RAF)3 SSF(LASF(LAF)(RAF))(RASF(LAF)(RAF))

Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]

##### Share on other sites
Thanks for the speedy response =)

But, is that just an example, or the equasion? That''s kind of like what I found on the web.. but I don''t really get what you mean.

##### Share on other sites
I hate the Internet. I typed in a nice reply, hit go, then ERROR: no post for you! Argggg.

But here is the gist.

Fruny is right. L-grammer is the language structured used to define Lindenmayer Systems, aka L-systems, which can be used to model flora, trees, and such. Some work has been done by Dr. P. Prusinkiewicz and students from the University of Calgary. They have some publications available in PDF format, here:

www.cpsc.ucalgary.ca/Redirect/bmv/papers/

See especially the most recent SIGGRAPH 2001 publication at the top of the list, titled "The use of positional information in the modeling of plants."

The papers are quite technical, but I''m not sure you''re going to find a satisfactory article that doesn''t get technical.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

##### Share on other sites
Grammar based modeling of plants, using L-systems.
for kids (the one with the turtle). There
are a lot of good references on it. One of the projects
I was thinking of doing was building a parser
to read in the language and produce an opengl rendered
image. Pretty cool stuff, and you can make very
detailed models with little grammer code.

Here is a link to my professors powerpoint presentation.
He went over it the last week, and it definetely peeked
my interest.

http://www.cs.uml.edu/~hmasterm/Charts/week13.ppt

(I keep getting an error posting this thing...)

##### Share on other sites
It''s an example, there is no ''equation''.

The whole idea is that you do substitutions in a string according to a set of rules you define (usually as a context-free grammar... a whole topic unto itself). Then you ''interpret'' the resulting string to generate a figure.

In my simplistic example, each step you replaced ''F'' (go forward) with ''SF(LAF)(RAF)''
S  reduce the size of the forward stepF  go forward(  save the stateL    rotate leftA    reduce the rotation angleF    go forward)  restore the state(  save the stateR    rotate rightA    reduce the rotation angleF    go forward)  restore the state

Therefore, in the figure, every straight line ''|'' was replaced with a ''Y'' branch. If you do that recursively, you get a ''tree''.

Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]

##### Share on other sites
The production rules you use determine what sort of tree you get. The tokens listed by Fruny (forward, new branch, rotate, etc.) will stay roughly the same throughout implementations (you definitely need ''forward'' ''new branch'', and variants on the rotation bit.)

I''ve got some sample code for you to play around with over here (C++ and OpenGL/GLUT).

I defined the tokens as follows:

F = go forward
[ = start new branch (push it onto the stack)
] = end of branch (pop last result - move back)
-,+, < > = rotate in one of four directions

In my example code I scaled each branch automatically - that is, the [ token implies "start a new branch, glScalef". This meant I didn''t use an explicit token for scaling down.

Now, get the code and play around with the variable "lstring". Try the following and understand the results:

char lstring[20] = "F";
// or...
char lstring[20] = "F[-F]";
// or...
char lstring[20] = "F[-F+F]";
// or...
char lstring[20] = "F[-F][F]";

etc. The lstring here represents the production rule to generate the tree. You can see that by changing the string you get different trees. (Also, note that the above trees will be two dimensional because I haven''t used the < and > tokens.)