Introduction to L-Systems

A Lindenmayer system is "a parallel rewriting system and a type of formal grammar". Theorized by Aristid Lindenmayer in 1968, they are a way of modeling the growth of an organism or generating fractals.

Definition of an L-System

An L-System is composed of an alphabet, some constants, an axiom describing the initial state and evolution rules for each variable.

For instance, here is Lindenmayer's original L-System modeling the growth of an algae:

Lindenmayer's Algae

Axiom: A

Variables:

  • A =>: AB
  • B =>: A

The evolution rules then allow us to iterate this L-System as such:

  1. Generation 0 state: A
  2. Generation 1 state: AB
  3. Generation 2 state: ABA
  4. Generation 3 state: ABAAB
  5. Generation 4 state: ABAABABA
  6. Generation 5 state: ABAABABAABAAB
  7. Generation 6 state: ABAABABAABAABABAABABA

...and so on.

Rendering

Now that we have a "growing" iterative L-System, we need to somehow render it to the screen. How do we do that?

Turtles all the way down

Inspired by the Logo programming language's Turtle graphics module, we need to use a visual "cursor" which has a position (X and Y) and an angle.

We move the turtle forward when encountering a variable, and perform operations for constants: rotation and saving/restoring the turtle's state to/from a stack.

From any given state and its associated set of rules, we can now compute a set of coordinates to be drawn sequentially as line segments.

This is done internally by the traceLSystem function, which outputs coordinates then rendered with d3.js in a purpose-made Svelte component.

Sierpinski's Triangle

Let's apply this "tracing then rendering" logic to a new L-System.

This one is a slightly more evolved L-System than our algae. We now have constants, + and -, to angle the trajectory of our turtle:

Sierpinski Triangle

Axiom: F-G-G

Constants:

  • +: Turn counterclockwise by X°.
  • -: Turn clockwise by X°.

Variables:

  • F =>: F-G+F+G-F
  • G =>: GG

Let's see what this gives us after several iterations (you can control the current generation with the slider):

Generation: 

It appears that this L-System describes, in fact, a fractal.

Applications

Of course, L-Systems have real-word applications beyond just making pretty fractals.

By introducing 3D logic to our turtle system, randomization parameters and improving the renderer (dynamic colors and stroke widths, textures, etc.) you can get pretty realistic procedural content generation of many real-life things.

Here are a few examples.

Fractals

You thought we were done?

Fractal-like forms are often easy to describe as L-Systems due to their mathematical properties.

We saw Sierpinski's Triangle just above, here is another famous example:

Koch's Snowflake

Axiom: F

Constants:

  • +: Turn counterclockwise by X°.
  • -: Turn clockwise by X°.

Variables:

  • F =>: F+F--F+F
Generation: 

Plants

Tree

Axiom: X

Constants:

  • +: Turn counterclockwise by X°.
  • -: Turn clockwise by X°.
  • [: Save the current turtle's state to the stack.
  • ]: Restore the turtle's state from the stack.

Variables:

  • X =>: F-[[X]+X]+F[+FX]-X
  • F =>: FF
Generation: 

Cities

L-Systems can be applied to city generation by producing roads and even buildings.

For instance, Parish and Müller's Procedural Modeling of Cities paper extends L-Systems to allow for realistic generation of roads and buildings.

Sources