# More L-System Images

Some more L-System images. A little background on L-Systems, if you care. Basically, L-Systems are a means to procedurally generate trees. It can be used to generate various fractal or repeating imagery, but mostly I’m interested in using it to generate trees and plants.

The idea is simple, you have a string made up of symbols (called a “sentence”) and the sentence tell a plotter how to draw something. Imagine the plotter like this: you’re holding a pen on a sheet of paper and someone is giving you basic drawing instructions. “Draw forward 10 inches. Turn 90 degrees left. Then, draw forward 10 inches. And so on. A sentence to a plotter could look like this:

FF[+F]FF[-F]F

‘F’ tells the plotter to draw a line forward (for some arbitrary length, let’s say 10 units. ‘+’ Tells the plotter to turn right by 90 degrees. The ‘-’ tells the plotter to turn 90 degrees left. The square brackets tell the plotter that this is a new “branch” of a tree. So in this example, the plotter would start at the origin and then move foward 20 units (“FF”) and then encounter a new branch (“[+F]“). The plotter knows then to make a new branch with the open square bracket (‘[‘), turn 90 degrees (‘+’), and draw 10 units. It encounters the closing square bracket and goes back to the main trunk (“FF”) and continues to plot from there.

L-System Alphabet

How do you generate the strings for the plotter?

First specify an alphabet, which is what symbols you’ll include when you make new strings and what each symbol will mean to your plotter. In our case:

‘F’ – draw forward 10 units

‘+’ – turn 90 degrees right (+90 degrees)

‘-’ – turn 90 degrees left (-90 degrees)

‘f’ – move forward 10 units — don’t draw anything.

The alphabet is arbitrary. You can add more symbols and have new meanings for them as well, but this is simple enough to get started with.

Building L-System Sentences with Productions

From the alphabet you make “productions” or statements that describe how certain alphabetical characters expand into sentence parts. An example:

F -> F+F-F

Here’s the break down of what that means: to the left of the arrow you have the “predecessor” symbol in this case ‘F’. The arrow (“->”) means “expands into” and the stuff on the right hand side is the “successor” and that is the sentence that the predecessor becomes. If the sentence builder encounters the letter ‘F’ it will expand that into “F+F-F”.

To kick of generating an L-System structure you give it a root. So you might start with ‘F’. You also tell the L-System builder how many times to iterate through the string it’s building for the plotter.

The builder starts with ‘F.’

The first iteration through it’ll expand F into “F+F-F”

A second iteration would make that “(F+F-F)+(F+F-F)-(F+F-F)” — I’ve put each expansion into parentheses so you can visualize it easier, but the builder will not add ‘(‘ or ‘)’.

You can imagine what a third iteration through would do… it gets complex for anyone’s brain to fathom. At least my brain.

This string  is fed to a parser or directly into a renderer which will plot out a line following the instructions of each character in the final sentence.

Makes sense? Probably not, since I’m describing this off the top of my head. If you want more information and a detailed breakdown of what I outlined above, you can download the free PDF of The Algorithmic Beauty of Plants. It’s a fun little coding project to put together. Certainly everything I’ve done here in 2D also works in 3D.Идея за подаръкикониикониПравославни икони

# SDL and L-Systems

I’ve been coding again with some of my free time. I feel like there are dormant parts of my brain re-engaging with this craft and it feels good to actually hack something from scratch and get it to work in an afternoon. My weapons of choice: Simple DirectMedia Layer (SDL), XCode 3.2, and C++.

My only goal is to understand more about how to structure and build a simple game engine. No OpenGL, shaders, concurrency, etc. I’m trying to keep it simple for the time being. I’m trying to keep it as portable too — that is, I’m not putting a lot of specific Mac OS X code into it and I’m trying to keep SDL down in the dungeon. I might or might not be doing a good job at it, but I’m also hacking this thing together for the sheer fun of it. To show you the images above, wouldn’t do the actual code justice; they’re just static images that show Koch curves made using a simple “turtle pen” algorithm, which is the foundation of an L-System. It’s hardly perfect, but these screenshots were the best of the best of what I could output when I was done this afternoon. Some of the other ones look messed up probably due to floating point errors when calculating the pen’s rotation angle. I’ll get it next time.

For this L-System demo I ended up writing Bresenham’s line algorithm. Yeah, yeah, silly I know, especially since there’s supposedly an SDL package that contains line drawing. I think I had tried to get it to work with XCode but it barfed on me. If you got it to work, my hats off to you. I also realize I could use OpenGL to do line/polygon rendering, but like I said, I’m trying to keep it simple.

I’ve been building a whole slew of other little features: logging, math functionality, the ability to take screenshots, and the list goes on and on. It’ll be nice to have a little toolbox like this as time goes on.