L-systems and procedural generation

L-systems are a generation system that uses a simple descriptor to define fractal patterns that can be useful for many things, like trees, streets and more. This post goes over the way they look and how they work.


Axioms

If you have never seen or heard of L-Systems, it is a fractal generator that can take a number of axioms and generate output in a fractal approach. It can almost be described as a simple language, that describes what happens to some lines as they spread out. Let's see how this works, here is an example axiom set :

Instructions (axiom)
+A-B

A set of items
A = FFFF[--AE]F[+++AE]FFF
B = FFFF

This looks a bit like variables in programming, A and B contain values, and they are replaced in the generation step by their contents.

We start at a single point and "step" outward, following the instructions in the axiom above.

Here is the output, which I will explain below.

+FFFF[--FFFF[--AE]F[+++AE]FFF[---F][--FF][-FFF][+++F][++FF][+FFF]FFF]F[+++FFFF[--AE]F[+++AE]FFF[---F][--FF][-FFF][+++F][++FF][+FFF]FFF]FFF-FFFF

We have control over the angle the step lines will happen, and the number of times to run over the step. Remember this is fractal, so things repeat on themselves. We have a small set of rules which determine what happens, at each step. For example, a - step, means that the angle at which we draw the line changes. It's like a small language saying "add the direction, then move and draw, then move and draw, then create a leaf, then move and draw".

The point of an l-system generator is to generate a final 'instruction list' at the end of the generator, which we can loop over and use, for drawing or other structures.

Instructions?

The little 'language' the above is using is relatively simple, for example, a - means that the direction the line is moving at should be changed ( -angle ), and + means the direction will add the angle we specify in the system ( +angle ).

A lowercase letter (between a and z) will move the line point but will not draw, leaving gaps in the system.

An uppercase letter will move the line point, and draw the line.

A ' will change the color you are drawing with.

A [ will create a “root node” that can have children, and a ] terminates the current root node. In other words, the [] makes a tree branch that can have its own children.

l-systems 1

What does it look like?

Remember now, that this is a fractal system, and can iterate recursively (making smaller leaves on branches, and even smaller ones under that) all using the same system. This gives the system the following parameters : 

axiom : +A-B
angle : 10
iterations : 2
linelength : 16 (pixels) 

This generates the following : 

l-system 2

Next, I simply changed the angle to 30 : 

And then 60 : 

What did I do with this?

Long ago, I was working on a small 2D game with a city component. I wanted the city streets to be generated dynamically so that the city will be somewhat interesting and unique. Take a look at the outputs when you set the angle to 90, and what do you see? Looks like streets to me!

Conclusion

The nice thing about the system is that you have complete control over the patterns (using the simple axioms), and can even generate those procedurally.
This in turn seeds the city streets, and in fact, the rest of the city.

Below are some examples with the parameters changed, all using the same axiom. The grid size changes, maybe generating blocks/business districts can be used with a larger step in the grids,        

Or maybe it can be used to determine density in population,

But for now, it is just a simple street system,

Results

The outcome is used as streets, along these lines :

Here are some resources I used to get here :

Sol Graphics Tutorials on L-Systems
In browser canvas generator with parameters
An amazing city generated with similar systems (subversion/introversion)