Procedural Generation Using L-Systems

lindenmayer system from shadertoy

Cover photo credits: https://www.shadertoy.com/view/XtyGzh

Lindenmayer system (L-system) is a representation of how plants and some other biological structures grow. If we look at its text form, it is simply a sequence of simple characters called the initial state of the system. We also have a axiom (a rule) that defines what a particular character in initial string should be replaced with. If we apply our rule to the initial string, our string gets transformed. We cycle this transformed string again through the process, and eventually we recursively get a beautiful pattern if we visualize it in graphical form.

When translating the resulting string into graphical representations, such as lines in turtle graphics, you can observe complex patterns that resemble plant structures. The symbols in the L-system string are interpreted as commands for drawing, rotating, and branching, leading to the creation of natural-looking shapes.

Plant Generation

L-systems can be used for procedural generation of trees, plants or other patterns. In games, we need to somehow represent them in form of 3d mesh or 2d image. For this, we can sample 3D scalar field using L-systems & then apply marching cubes to generate the geometry from this scalar field.

Alternately, we can use other methods to create geometry from this representation.

import turtle

# Define L-system rules for generating the plant
def apply_rules(ch):
    if ch == 'F':
        return 'F[+F]F[-F]F'
    else:
        return ch

# Generate the L-system string after applying rules for a given number of iterations
def generate_l_system(axiom, iterations):
    result = axiom
    for _ in range(iterations):
        result = ''.join(apply_rules(ch) for ch in result)
    return result

# Convert L-system string to turtle commands
def convert_to_commands(l_system_string):
    commands = []
    for char in l_system_string:
        if char == 'F':
            commands.append('forward')
        elif char == '+':
            commands.append('rotate_pos')
        elif char == '-':
            commands.append('rotate_neg')
        elif char == '[':
            commands.append('push')
        elif char == ']':
            commands.append('pop')
    return commands

# Generate the turtle graphics for the given L-system commands
def generate_turtle_graphics(axiom, iterations, angle):
    l_system_string = generate_l_system(axiom, iterations)
    commands = convert_to_commands(l_system_string)

    turtle.speed(0)
    turtle.up()
    turtle.setheading(90)
    turtle.goto(0, -400)
    turtle.down()

    stack = []
    for command in commands:
        if command == 'forward':
            turtle.forward(5)
        elif command == 'rotate_pos':
            turtle.right(angle)
        elif command == 'rotate_neg':
            turtle.left(angle)
        elif command == 'push':
            stack.append((turtle.xcor(), turtle.ycor(), turtle.heading()))
        elif command == 'pop':
            x, y, heading = stack.pop()
            turtle.up()
            turtle.goto(x, y)
            turtle.setheading(heading)
            turtle.down()

    turtle.done()

# Generate the turtle graphics
axiom = 'F'
iterations = 4
angle = 25
generate_turtle_graphics(axiom, iterations, angle)
L-systems plant

In above code, if you modify the axiom, you can see different patterns forming.

Other Use Cases

We can use the concept for procedural generation of:

  1. Cave networks: The Perlin-noise based scalar field can be modified based on the l-systems (by overriding scalar values of points returned by l-systems) such that the marching cubes algorithm later applied will make assume them to be outside the surface and thus will result in caves.
  2. Roads
  3. Rivers/streams

One idea is to take into account game world’s features in place of axioms. So for example we take into account terrain normals, weather, objects density and so on to generate new things accordingly to make everything more compatible with the environment.

More Reading

  1. Generating A Forest with L-Systems in 3D
  2. Procedural Roads Networks

Leave a Reply

Your email address will not be published. Required fields are marked *