Drawing Fractal Trees - Part 2
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.
| Operator | Meaning |
| F | Move forward by a fixed amount. |
| + | Turn a little to one side. |
| - | Turn a little to the other side. |
| [ | Remember your current position and heading, and store in a stack for later retrieval. |
| ] | Retrieve the previous position/heading from the stack. |
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:
- A starting point; an "axiom".
- 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:
| Iteration # | Current Set of Operations |
| 0 | F |
| 1 | +FF |
| 2 | ++FF+FF |
| 3 | +++FF+FF++FF+FF |
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
