L-Systems

We've established that drawing the tree will use the concept of self-similarity. To put this in action, we're going to use what's called an L-System. Here's a crash-course...

Firstly, we establish that we have a "pen" that at any given time has a current position and a current heading/angle. It's always touching the paper, so when it moves forward, you get a line drawn. If you ever learned LOGO in school, this will be familiar.

Let's define a very simple set of operations.

So if we feed something like "F+F+F+F" to our pen, we'll get a square, provided the angle that "+" uses is 90 degrees.

Take something a little more complex, such as "F[-F][+F]". This will draw a Y shape; walk it through on paper and see. The key thing to connect at this point is that the "[" and "]" characters are perfectly represented by a recursive call to the same function that's doing the drawing. Save that for later.

So we have our set of operators, we need one more thing: A way to generate an interesting string of operations that will draw the tree. The way we do that is by defining two things:

1. A starting point; an "axiom".
2. A rule (or set of rules) that transform a given set of operations into a new set of operations.

We then keep applying these rules to the resultant set of operations (starting with the axiom) as many times as we want. For example:

• Axiom: F
• Rule: F => +FF (this reads as: "Every time you see an 'F', replace it with '+FF'")

Execution example:

Feed the final string above into our "pen", and it will draw stuff. Not a tree though; not with that rule. If you want a tree, go with a rule like this:

• F => FF-[-F+F+F]+[+F-F-F]

Wait, what?! Doesn't look anything like a tree, does it? But it turns out that when you apply that rule a few times to the axiom "F", it generates a set of operations that draws something very similar to a tree (depending on what angle you rotate with each +/-).

Check it out:

There is no randomness in this image; it's a direct drawing of the above rule (with 3-4 iterations of the rule), using a fixed distance for F and a fixed angle for +/-. Altering the distance that the pen moves with each F will make a larger/smaller tree; altering the angle can make a profound difference to the shape.

There are different rules that will produce different looking plants. For more examples, see this page.

To me, this is mind-blowing. That such a simple system with such basic rules and operations can generate something that looks so eerily "natural" is a little spooky. And reminds me that I had the same effect with the physics tutorial: Simple rules can make complex behaviour. I think there's some deep philosophical insight buried there.

What's left to do now is take this knowledge and apply it to a Silverlight program that can allow the user to alter the parameters in real-time, introduce some randomness, and maybe a little more life to the image.

Stay tuned...

Avi