Creating a Parametric L-System in C#

Hello! I have been working on creating an L-system for use in a game that involves many different species of plants.

Here’s some background: an L-system is a way of generating a string by using a replacement rule. For example A → AB. This can be iterated creating an increasingly large string. Then you can interpret this string into objects or directions. For example ‘F’ may mean draw a line of length x and ‘-’ may mean change angle by -x degrees, so the string “F-F” would mean draw a line of length x, change angle by -x, and then draw another line of length x.

Now from this you can create more complex L-systems, in the literature one of these more complex models is called a “parametric L-system”. A normal L-system is a string built of characters, a parametric one is a list made of modules. For example a module might be F(l) l being a float representing the length. So you could have a list of modules something like F(5)-F(3) which would be interpreted as: draw a line of length 5, change angle by -x, and then draw a line of length 3.

Now that seems simple enough but the problem comes in when you want to iterate on this list. What I’m wondering is how you might write a rule that says F(l) → F(l/2).

If anyone has ideas or can point me in the right direction it would be much appreciated Ty!

This is actually a quite pointless substitution rule:

F(l) -> F(l/2)

You probably mean something like

F(I) -> F(I/2) + F(I/2)

Otherwise the result will always be just one single “F” and iterating that system just makes the parameter smaller.

However the main question is what you want to use this for? For example if you want to use it to actually perform the resulting “command string” it would make more sense to already use actual objects / classes for each module. Because when using an actual string you have the following problems:

  • strings can’t be changed. So when you modify them you have to recreate the string. The larget the string gets the more garbage you create each iteration.
  • strings require you to constantly parse the string, extract the module identifies, split off their parameters and when done re-assemble the string.

If each module is an actual class instance, you can keep the parameters as fields of each module instance. That simplifies the sustitution process and makes it easier to actually do something with the result.

As for how the substitution rule can be processed, it’s just the same as without parameters, You first substitude the modules by their names and finally process the parameters. A rule usually specifies arbitrary placeholders for each parameter which can be used in an expression in the substitution parameters.

If you need a simple expression parser, have a look at my ExpressionParser.

I would probably allow the rules to be written as string and parse them into some structured way.

public enum EModuleType

public class Module
    public EModuleType type;
    public List<float> parameters;
public class LSystem
    public List<Module> content;

public class Substitution
    public EModuleType type;
    public List<Expression> parameterExp;

public class Rule
    public EModuleType type;
    public Expression condition = null;
    public List<Substitution> replacement;

So the “Module” class represents a single “symbol” in our alphabet including the parameters. The enum just specifies the type of symbol. An “LSystem” instance is an actual string which might be iterated to refine the system. “Rule” is a class that represents a single rule definition. The type specifies which module this rule will replace. An optional “condition” expression might be used to activate / deactivate that rule based on the parameters. A “Substitution” instance is a single replacement module. However it doesn’t specify parameters directly but each parameter is represented by an expression which is based on the rule parameter variables. So a Substitution instance can be used to create the actual replacement Module based on the source module parameters.

This is of course one way you can accomplish such a system. Of course you can go the string parsing route as well. It highly depends on your goals. How large strings do you want to support? How should the system be defined? How should the rules be defined? Which parts do you want to be dynamic?

I actually have refined my original ExpressionParser to allow logical expression as well. It supports comparising operators like (==, >, <, !=, …) which can compare number expressions and return a “logic result” (aka boolean). It also supports logic operators like (&&, and, ||, or, !, not, ^, xor). However the parser is still in an experimental state and not ready to be published.

I finally had some time to clean up my LogicExpressionParser. I can’t guarantee it works 100% but in my tests everything works as it should. Keep in mind the parser uses a quite strict syntax. If unsure just put some additional pairs of brackets ^^. Note that it does not perform an implicit multiplication. So 2x should be 2*x. Also “unary minus” need to be inside brackets. This does not work: a * -b. It should be a * (-b).

At the same time i made a string based Lindenmayer system. It also contains a parser that can parse a simple text based definition into an LSystem.

I didn’t really test this system to the bone, but i’ve done some complex testing systems. I also created a simple non parametric sample (HilbertCurve). It properly generates a texture that looks like this(upscaled image).

I’ve added some documentation in comments that should be enough to understand how it’s supposed to work. The main classes (LSystem and Module) have an overridden ToString so it makes it easier to visualize the result of an iteration for testing purposes. Though note that the more complex a system is and the more iteration you run the longer the results get. So be careful. For a simple A–>A; A the growth is 2^X

A parametric example would be:

Axiom: A(0, 2)
Count: 5
    A(a, b): a<4 --> B(b); A(a+1, b^2 + 2*b); B(b)
    A(a, b): a>=4 --> 
    B(val) --> Plot(val)

This willl produce:

Plot(2); Plot(8); Plot(80); Plot(6560); Plot(6560); Plot(80); Plot(8); Plot(2)

“a” is basically used as counter. There are two rules that involve “A” but with different conditions. Note that only one rule is applied at a time. If two rules would match, only the first one is applied.

Note that this is just a pointless example ^^. After the 5 iterations the system enters a stable state and more iterations don’t do anything as all rule symbols are vanished.