Branching L-Systems

I’ve been trying to figure out L-Systems now for a while after I read about it on Joshua Davis’ now defunct diary a few years ago. Stumbled upon it again on Keith Peters’ Chaos-101 site and felt like looking it up on Wikipedia. Lo and behold, I somehow managed (painstakingly) to figure it out for AS3! You can download the source here. The following is a brief overview of the puzzles i encountered and my solutions.

What is an L-System?
It’s a way of describing plants in a series of letters and symbols (6 to be exact). The symbols are the following:

• F - draw forward
• L - move forward
• + - rotate right by X degrees
• - - rotate left by X degrees
• [ - push (saves the current position and starts a new branch)
• ] - pop (resumes the last saved position starts growing again from there

WTF?

Basically, you’ll start off with a string, like say “L”…think of it as our seed. Now, this is at generation 0 (or N=0). What’s so awesome about L-Systems, is that it’s a parallel rewriting system, meaning, as we iterate through each generation, we replace certain symbols from the previous generation. Here are the rules for what i have in my example above:
L → F-[[L]+L]+F[+FL]-L
F → FF

This means that if we start with L as the first generation, this is what our progression will look like:

• N=0 : L
• N=1 : F-[[L]+L]+F[+FL]-L
• N=2 : :FF-[[F-[[L]+L]+F[+FL]-L]+F-[[L]+L]+F[+FL]-L]+FF[+FFF-[[L]+L]+F[+FL]-L]-F-[[L]+L]+F[+FL]-L
• N=3 : so on and so forth…

I used simple Regular Expression (which is a whole other language that’s foreign to me at the moment) to execute the string replacement. For more on RegEx, see this nifty site. I also found a little nifty free app for practicing RegEx (highly recommended, it’s free!).

After doing the replacement, you have your completed L-System!

Turtle Graphics

The L-system in itself won’t give us any visual rendering. What we do is use the method of Turtle Graphics:

Turtle graphics is a term in computer graphics for a method of programming vector graphics using a relative cursor (the “turtle”) upon a Cartesian plane. [Wiki]

to draw this puppy onto the screen. It’s relatively straight forward until the “pushing to stack” and “popping from stack” bits. Here’s an excerpt from the file you can download, I hope the comments explain it clearly (my apologies for the shitty code formatting, must find a new code plugin, any suggestions?).

//PUSH--------
case "[":
//start a new sub branch
var subsystem:String = "";
//used to determine where the subsystem branch begins and ends
var openCount:uint = 0;
var closeCount:uint = 0;
//saves the current x,y and rotation so we can come back to this point after we finish brancing
tree.stack.push( [ tree.cursorX, tree.cursorY, tree.cursorR + ((Math.random()*30 - 15 )*DEGREE_TO_RADIAN ) ] );
//get all the information between this opening [ and closing ]
for( var j:uint = i+1; j < numInstructions; ++j ){
//get the character at j
var c:String = system.charAt(j);
//if it's an opening bracket... +1 to the number of brackets open
if(c == "[") ++openCount;
//if it's a closing bracket... +1 to the number of brackets closed
else if(c == "]") ++closeCount;
//if the number of open brackets is greater than the number of closed brackets, add the character to the substring
if ( openCount < closeCount ) subsystem += c; else break;
}
//start new branch
render( tree, subsystem );
break;
//POP--------
case "]":
//OMITTED LEAF CODE...see source file for that...
//retrieve the information from the stack so we can resume branching
var stackData:Array = tree.stack.pop();
tree.cursorX = stackData[0];
tree.cursorY = stackData[1];
tree.cursorR = stackData[2];
g.moveTo( tree.cursorX, tree.cursorY );
break;


I accidentally discovered that a “pop” character also corresponds to a “leaf” node or the end of a branch. That’s where I put the leaves and cherries in my demo. Suuuwheeaat. I also managed to simulate this thing swaying in the wind using perlin noise, will release one of these days.

I threw in a little bit of randomness in my example as well to come up with a different tree everytime

Go ahead and download the source. Have fun and have a great day!