A peek at L-systems

Today, let’s continue with procedural generation. So far, we have seen various tools to generate specific structures, so let’s take a look at another type of generator: L-systems.

As explained in the Wikipedia page, L-systems (or Lindenmayer systems) were designed by the Hungarian biologist and botanist Aristid Lindenmayer in 1968 who wanted to describe plant growth. Since then, they have been used to model the morphology and development of many other organisms, and to generate self-similar fractals.

Basically, those models can be interesting whenever you have recursion and self-similarity in the process you want to study (like trees, some architectural patterns…).

Here, I offer a little LSystem class programmed in Python to easily manipulate these objects. It’s not very elaborate but implements the basic behaviour of an L-system.

Note: the code comes with a requirements.txt file to help you set up all necessary libs.

Before actually getting into what an L-system is and how it works, it might be cool to look at some examples of things you can make thanks to this model.

With L-systems, you can make geometric shapes like the famous Sierpinski triangle, the Koch curve or the Cantor set:

Sierpinski triangle (6 iterations)
Cantor set (7 iterations)
Koch curve (3 iterations)

Of course, because of where the concept comes from, there are also well-known systems to generate some trees, like these:

Example of “Bushy” tree
Example of “Twiggy” tree
Example of “Conifer” tree

These animations were generated with the code I provide in this article (you’ll see below that some functions are provided in the script to help you create these easily).

Another type of system that usually presents self-similarity is a city roadmap. Many projects work on how to use L-systems to generate city maps, for example this paper by Parish and Müller, this one by Kelly and McCabe or this article by the Project Lucky Luciano team. As you can read in these references, the model can even be used to create buildings in your city!

Example of Parish and Müller’s L-system for street creation in Manhattan (figure taken from Parish and Müller’s paper)

So, what truly are L-systems?

L-systems are a kind of formal grammar where you use a starting axiom and a list of production rules to gradually rewrite a chain that represents the system.  It sounds complicated, but the concept is in fact not that complex. Simply put, the process is as follows:

  • your L-system can use a finite set of characters in its chains, called its “alphabet“; for example: X, T, [, ], -, +
  • you have a starting chain, called “axiom”; let’s say it is X
  • you have one or more “production rules” that tell you how each specific character in a chain should be transformed by the system; let’s say here we have two rules:
    1. T → TT
    2. X → T-[XT]+T

These rules can only play with the characters in your set. They usually take only one character as “starter” but may produce several characters. If a symbol is not associated with any rule, it is assumed to be a “constant” (or a “terminal“) and is left as-is in the newly evolved chain.

  • you ask your system to take N steps: at each step, the system applies all its rules simultaneously to the current chain and therefore replaces some characters by others (while leaving the terminals untouched)

So, with these axiom and rules, our L-system would evolve like this:

Initial state (axiom):X
Step #1:T-[XT]+T
Step #2:TT-[T-[XT]+TTT]+TT
Step #3:TTTT-[TT-[T-[XT]+TTT]+TTTTTT]+TTTT

Each new chain is derived from the previous one by applying all possible rules at each iteration.

Here is a little animation that sums up how this little L-system would work:

Now, this sounds nice but it’s not really fun to write up meaningless chains of characters. How do we go from there to pretty images like we saw above? A common way is to use the turtle graphics language and to interpret the chain as turtle commands. For example, the symbol T could mean “trace”, the symbol + “turn right X degrees” and the symbol - “turn left X degrees”.

In my implementation, I use the matplotlib library instead of turtle, but it is the same idea. I just replace a direct turtle command by the corresponding (x,y) point coordinates and then convert the points to the segments to draw.

Using the Python LSystem class

The Python code I provide in this article is a small script to generate and display L-systems easily. To use it, you need to give your LSystem instance one or more systems that are each defined by several parameters:

  • the axiom
  • the production rules
  • the number of generation to create
  • the angle to use when a “turn” symbol is found in the chain (fixed for one system)
  • the starting position and rotation on the drawing canvas
  • the line thickness

Some default systems are already defined, so you can even create and evolve an instance directly with no specific parameters by calling the class run method:

This will output an image of a simple 2-systems LSystem instance that looks like this:

Example of output for a LSystem instance with default settings: you get a very simple city roadmap!

Now, to pass in your own systems, use the systems parameter:

Each system is a tuple with the aforementioned properties in this order. To make things easier, there are some functions in the main.py file with a few systems that are common or that I tested out and seem to give nice outputs. These functions directly return a list of systems, so to use them, create and run a LSystem instance this way:

A cool thing with L-systems is to watch how they change from one generation to the other. You can do so by running the system with the anim parameter set to True (by default, only the final result is shown):

This gives you the following result:

Example of L-system based city map generation (with a step-by-step animation)

Finally, if you want to save your results, define an export_file. If you just want the final static image, you can save it as png, jpg (or jpeg) file. For an animation, use the gif extension. So, for example, these two calls will export two different trees; the first one is only the final result as png image and the second one is a gif animation of each step:

If you dive into the code, you will notice that there is a “clean-up” step at the end of the process. This avoids segments to be drawn multiple times for a system if the chain happens to backtrack because of its rules – and thus makes the generation of the final output a bit faster.

These are just some examples of what we can do with L-systems… I find that playing around with axioms, tweaking the rules and just randomly trying out some systems can already give you cool things! However, if you want to start with well-known systems, the Wikipedia page provides you with a list of examples.

More about L-systems

The L-systems we saw here were quite simple. They had a limited alphabet, simple deterministic rules and starters were single characters. When modelling something more complex, you may create L-systems with funkier characteristics.

For example, it is possible to create stochastic L-systems instead of deterministic ones. These use production rules where a symbol may be transformed into several different productions; the system then picks one at random when evolving, which yields way more variability but also gives you less control on the outcome. You can specify the probability for each production and thus make some more likely to appear than others.

Another question is what starters do you take for your rules? So far, we decided that one character would be transformed. But given the common applications of L-systems, where you study interconnected organisms – like plants where cells growth also depends on the state of its neighbours -, you can also devise rules where the production is a result of both a symbol and its neighbours. This is called a “context-sensitive L-system”, whereas the simpler ones shown here are “context-free“.

You can also add parameters to your symbols and production rules. This can be used to specify special production activations. For example, instead of just saying T → TT, you can define a T(b): b == True → T(true)T(false) rule. With this rule, the system will transform any T symbol into two new T symbols, but only the first one of these new symbols can be transformed again (the second one is now a terminal)!

L-systems can also be used to create self-avoiding walks: if you choose your system parameters right (and adapt its behaviour a little), you can make sure it never backtracks and thus create a sequence of moves that only goes once through each point of your grid.

References
  1. Y. Parish and P. Müller, “Procedural modeling of cities”, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.301–308, August 2001 (https://graphics.ethz.ch/Downloads/Publications/Papers/2001/p_Par01.pdf)[Online; last access 29-June-2021].
  2. G. Kelly and H. McCabe, “Citygen: An interactive system for procedural city generation”, Fifth International Conference on Game Design and Technology, p.8–16, 2007 (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.688.7603&rep=rep1&type=pdf) [Online; last access 29-June-2021].
  3. Dominicator (Project Lucky Luciano), “L-Systems Map Generation Algorithm” (https://projectluckyluciano.wordpress.com/2016/04/18/l-systems-map-generation-algorithm/), April 2016. [Online; last access 29-June-2021].
  4. I. Wikimedia Foundation, “L-system” (https://en.wikipedia.org/wiki/L-system), June 2021. [Online; last access 29-June-2021].
  5. I. Wikimedia Foundation, “Turtle graphics” (https://en.wikipedia.org/wiki/Turtle_graphics), June 2021. [Online; last access 29-June-2021].
  6. I. Wikimedia Foundation, “Self-avoiding walk” (https://en.wikipedia.org/wiki/Self-avoiding_walk), June 2021. [Online; last access 29-June-2021].

Leave a Reply

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