Turtles Part 3: L-systems

Last post we showed how you could produce some pretty neat patterns by taking simple rules, and replacing parts of that rule with something only a little more complex. Repeat that four or five times and you've got a really complex shape. This idea of rule re-writing to create complex self-similar shapes (Fractals), was developed by Astrid Lyndenmayer, so we call them L-Systems. However Lyndenmayer wasn't a mathematician or a programmer - he was a biologist!

L-Systems were developed to describe plants! Lyndenmayer realised that the branch of say a fern, basically is a small copy of the whole fern, so if he could find a way to describe that, he could use it to classify and record how plants grow.

This is a page form Lyndenmayers book "The Algorithmic Beauty of Plants" which you can download as a pdf (legitimately!). The only difference between these shapes and the ones we did last time is that these ones branch. This is pretty important if you're trying to make a tree!

The basic concept of branching in L-Systems, is that when you find a "[" in the rule that means the start of a branch. We're going to go off and draw the branch, then come back to continue drawing the rest of the L-system afterwards. That means we need to remember where we need to come back too...

To do that we make a list of numbers called "stack".

make stack list of number

..if command = "["

...add displayX to stack

...add displayY to stack

...add direction to stack

When we encounter the "[" command during drawing we record the turtle's (remember them - feels like we've forgotten all about turtles it was so long ago!) position and orientation, so we can put it back where it was later.

..if command = "]"

...set lastStack to length of stack

...set displayX to item lastStack-2 of stack

...set displayY to item lastStack-1 of stack

...set direction to item lastStack of stack

...delete lastStack of stack

...delete lastStack-1 of stack

...delete lastStack-2 of stack

...tell display to "move"

When we find a "]" command we know we've finished drawing the branch, so we get the values we recorded back from the stack, and continue on. (this code is slightly more complex than it should be, but there's a bug in Sniff, which means the simpler code doesn't work - its fixed for the next release, so once that's out I'll update this, or maybe forget).

• Axiom: F
• Angle: 45
• F=>F[+F]F

This is one of the simplest branching systems. We can think of each "F" as a segment of the plants stem. At each iteration, each stem segment doubles in length, and grows a branch half way along.

While that doesn't sound like much, the next time around each of those branches grows a new branch, and we quickly get something interesting. (If you don't get the whole thing drawn correctly remember to increase string length in $SNIFFDIR/lib/sniffDefs.h - these rules get very long)

If we look at the first example on the page above, we can see it uses a similar structure. Each stem segment becomes a segement, a branch to the left, a segment, a branch to the right, and a final segment:

• Axiom: F
• Angle: 25.7
• F=>F[+F]F[-F]F

While this might seem simple we get a pretty convincing plant from it:

These kinds or rules add branches to every stem segment, and are good for some kinds of plants, but other plants are more structured, and only branch at the ends of branchs (while older branches become longer). We can represent those just as easily by marking the active "nodes" with an X. If we look at example E.

• Axiom: X
• Angle: 25.7
• F=>FF
• X=>F[+X][-X]FX

Each "bud" marked with an X turns into a stem segment with a bud to its left, and right, followed by more stem with a single bud at the end.

While the results are a bit geometric - it doesn't help that its symetrical, its a pretty good fern. It doesn't take a lot to make something more organic like example F:

One of the great things about L-Systems is that more or less whatever you put in, you get something that looks like some kind of plant - just make up a rule and see what you get. Slightly harder is to write an L-system to look like a specific plant (start by considering is it stem branching, or bud branching).

While we've implemented the basics of L-systems, there are lots of extensions you can include, for example changing the branching angle with each generation, or adding commands to control the colour.

If you get really serious about L-systems you could make something that looks like this:

http://www.kevinmackart.com/facts-and-trivia.html

Kevin Mack won the 1999 Visual Effects Oscar by using L-systems to make this tree for the film "What Dreams May Come". In fact L-Systems are a really big deal in computer graphics, where they're used to make trees and plants for all sorts of animated and special effects movies.

That's pretty cool for a turtle!

You can download Source Code for this and the previous turtle posts here.