Jump to content
  • Advertisement

Archived

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

hello2k1

L-Grammars

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
L-systems.

Define a set of tokens, each having a meaning.
e.g. (simplisitic)

F = go forward
S = scale length down
A = scale angles down
R = rotate clockwise
L = rotate counterclockwise
() = subexpression is a ''branch'', state is restored when leaving the subexpression.

Then define substitution rules :

Start -> F
F -> 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 Start
1 F
2 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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Grammar based modeling of plants, using L-systems.
Its roots start with the logo programming language
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 this post


Link to post
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 step
F go forward
( save the state
L rotate left
A reduce the rotation angle
F go forward
) restore the state
( save the state
R rotate right
A reduce the rotation angle
F 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 this post


Link to post
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.)

Share this post


Link to post
Share on other sites
Naturewizard did a nice article on L-systems a while ago. You can find it here. It''s not terribly in-depth, but it gives a pretty complete language to use.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!