# 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!

You’re currently reading “Branching L-Systems”, an entry on Visual Gratis

- Published:
- 04.20.10 / 11pm

- Category:
- AS3, Actionscript, Experiments, Flash

- Tags:

- Post Navigation:
- « Dreams on Twitter

Beautiful Skateboard »