Building Tree’s Part 2: L-Systems

This is part two of a tutorial series, I highly suggest checking out part one first (its way more interesting). Find it here: https://mjm.itch.io/tree-game/devlog/59221/building-trees-part-1-runtime-meshes

I once again apologise for the formatting, one day I will learn, but until then... Im so

But now, to the main focus of this installment. Tree Game, is built on the back of one particular algorithm; what is called an L-System. Or as they are actually named; Lindenmayer systems. On a high level L-Systems are made of two parts, the rules and axiom that generate a string, and the actions that each of these characters represents in order to visualize this string as something.

L-Systems are a super versatile tool that can generate all kinds of cool fractals, alongside being able to make some seemingly very “real” organic shapes. The way we will be using them is in creating Tree’s, so that we can have a general idea of what a particular kind of tree will look like, but that each tree generated by a particular ruleset will be slightly different.

In order to make sense of this we will start with the rules. A rule in an L-System is basically just a replacement. As an example a rule could be a goes to ax. Along with this we have an Axiom (what we will start from), let’s say it can be a. What we do now is go through the string we have (a) and replace letter according to our rule (a -> ax). So we end up going from a to ax.

We then keep doing this, recycling the new set of letters we made each time. As an example take this:

For the rules: (a -> ax) and (x -> a) and a start of (a)

Generation 1: a
Generation 2: ax
Generation 3: axa
Generation 4: axaax
Generation 5: axaaxaxa

To break this down a little further let's look at generation 4 to generation 5. What we are doing is going through the whole string, looking at each letter, and then referring to that letters rule, and replacing its with that. So each a becomes an ax and each x becomes an a.

Now that we have that down pat, we can move on to the next step of this which is going from the letters what they represent when we actually make a tree from them.

To create a tree from this we need to treat each character as actions that our program will take. In the case of the above example, let's say that a represents a step forward, and x represents turning 45 degrees to the right. Now as we go through each letter in a generation, our computer has a way of displaying that too us.

What we have now is a way to take our string; and then turn it into some kind of visual representation. Next we can start adding some more complex rules to build more organic looking shapes, these can be things for creating branches, for leaves or for different kinds of movement. But at its core, all an L-System is is a set of rules for swapping out letters in a growing string, coupled with a way to turn those characters into actions a computer can understand.

For now though, let's have a look at one more basic L-Systems before we dive into making L-Systems work in our program. This will add just a little bit more complexity to our current L-System, and is called a binary Tree.

Rules: 
a ->aa
x -> a[x]x

Axiom: x

Generation 1: x
Generation 2: a[x]x
Generation 3: aa[a[x]]a[x]x
Generation 4: aaaa[aa[a[x]x]]aa[a[x]x]a[x]x

At the moment this looks very similar to what we have already done, the part where this changes comes in how we now interpret this when drawing it out. We will treat both a and x the same as we have been. But the new symbols [ and ] will be used to create branches.

They way we do this, is that whenever we encounter [ as we move through the string, we we take out current position in the drawing, and put it into a stack (a first in last out way of holding things. Think of it like a literal stack, but you can only take the thing on top of it. Ie the thing you last put in). Then whenever we encounter a ] we will take the last point we put in the stack out, and go back to that position, and draw from there.

Enough talking about it, lets see how this actually looks:

And with that we should have enough of a grasp of how L-Systems work to be able to start making them ourselves. So now we can start busing a way to make them in code.

To do this we are going to need a few things, a set of rules, and an axiom (starting string).

For the rules we will make a custom data type that contains what we want to replace with each rule, and what we are replacing it with.

[System.Serializable]
public class LSystemRule
{
    public string from;
    public string too;
}

We store the rules this way so that we can edit them in unity’s editor without having to go a fight the editor UI system. Note we marked the custom data type System.Serializable; this is what will allow unity to display it in editor.

Now we have our data types ready, all we need to do is create a method to go from our axiom to each of our generations. To do this we need to go through each character in the current generation, and based on that replace it with its corresponding rule. In code, we actually do something slightly different.  First what we do is we set up two new strings, one is our current generation (we let that equal our axiom because at the start that is our first generation), and the other will be our next generation, ie. the one currently being made.

From here we loop through each letter in our current generation; then for each of these letters we check it against our rules by looping through them and comparing the current letter, to each rule.

Ok, so now we have a way of looking at each letter, and then seeing if one of our rules pertains to it. Now we need to actually check if it needs to needs to be changed or added to. To do this we add a new if function; here we compare the letter to the rule, and if they match we add that rules output to our next generation string.

Then we add a break function, because we already know we have found a match, and can leave the loop.

Now all we have to do, is after running through each letter in our current generation make our current generation equal the next generation, clear the next generation so its ready to be added to again, and then start all over, looping through each letter and adding to the next generation as we go.

Phew that was a lot, but here it all is:

    string axiom;
    LSystemRule[] rules;
    string generateString(string currentAxiom, LSystemRule[] currentRules)
    {
        string currentGeneration = currentAxiom, nextGeneration = "";
        for(int i = 0; i < currentGeneration.Length; i++)
        {
            for(int n = 0; n < currentRules.Length; n++)
            {
                if(currentRules[n].from == currentGeneration[i].ToString())
                {
                    nextGeneration += currentRules[n].too;
                    break;
                }
            }
            currentGeneration = nextGeneration;
            nextGeneration = "";
        }
        return currentGeneration;
    }

Our code works, but it has a fairly large flaw. What if a letter in our generation does not match a rule? At the moment it would disappear, as it would never be added back into the next generation. So in order to get rid of this bug, we need some way of knowing if no rule was triggered.

To do this we add a new boolean, but we create it inside the character loop. We do this because  this boolean only matters to whether or not we have triggered a rule, and so can be reset each loop through. When we create, we will also set it to false.

    string axiom;
    LSystemRule[] rules;
    string generateString(string currentAxiom, LSystemRule[] currentRules)
    {
        string currentGeneration = currentAxiom, nextGeneration = "";
        for(int i = 0; i < currentGeneration.Length; i++)
        {
            bool foundRule = false;
            for(int n = 0; n < currentRules.Length; n++)
            {
                if(currentRules[n].from == currentGeneration[i].ToString())
                {
                    nextGeneration += currentRules[n].too;
                    foundRule = true;
                    break;
                }
            }
            if(foundRule == false)
            {
                nextGeneration += currentGeneration[i].ToString();
            }
        }
        currentGeneration = nextGeneration;
        nextGeneration = "";
        return currentGeneration;
    }

Now we have the boolean, we can now add a check after our loop through the rules. All this check needs to do, is see if the boolean we made still equals false, and if it does, add the current character we are checking to the next generation.

Now we need a way to do this multiple times, before giving us our result. So we add a new variable to our method, called generations. This will represent the number of times we go over the string before returning it. To make this work all we do is enclose everything in a loop that runs a number of times equal to the generations, reusing our last generations string each time. 

    string axiom;
    LSystemRule[] rules;
    string generateString(string currentAxiom, LSystemRule[] currentRules, int generations)
    {
        string currentGeneration = currentAxiom, nextGeneration = "";
        for(int g = 0; g < generations; g++)
        {
            for (int i = 0; i < currentGeneration.Length; i++)
            {
                bool foundRule = false;
                for (int n = 0; n < currentRules.Length; n++)
                {
                    if (currentRules[n].from == currentGeneration[i].ToString())
                    {
                        nextGeneration += currentRules[n].too;
                        foundRule = true;
                        break;
                    }
                }
                if (foundRule == false)
                {
                    nextGeneration += currentGeneration[i].ToString();
                }
            }
            currentGeneration = nextGeneration;
            nextGeneration = "";
        }        
        return currentGeneration;
    }

Now we have a very basic systems for building each generations string. The final part will be to introduce some randomness into this system. We can do this by turning our rules from a just a from a string too another string, to an array of strings and then pick randomly from there.

First we set up our rules variable.

[System.Serializable]
public class LSystemRule
{
    public string from;
    public string[] too;
}

and then add our randomization to the returned value, by picking a random number between zero and the length of our too array.

    string axiom;
    LSystemRule[] rules;
    string generateString(string currentAxiom, LSystemRule[] currentRules, int generations)
    {
        string currentGeneration = currentAxiom, nextGeneration = "";
        for(int g = 0; g < generations; g++)
        {
            for (int i = 0; i < currentGeneration.Length; i++)
            {
                bool foundRule = false;
                for (int n = 0; n < currentRules.Length; n++)
                {
                    if (currentRules[n].from == currentGeneration[i].ToString())
                    {
                        nextGeneration += currentRules[n].too[Random.Range(0, currentRules[n].too.Length)];
                        foundRule = true;
                        break;
                    }
                }
                if (foundRule == false)
                {
                    nextGeneration += currentGeneration[i].ToString();
                }
            }
            currentGeneration = nextGeneration;
            nextGeneration = "";
        }        
        return currentGeneration;
    }

In doing this, we can now have multiple possible outputs for any given rule, meaning our trees can have more randomisation while still allowing us ultimate control over how they end up looking.

And with that Part 2: L-Systems is done; the boring part is over. This section is not the most visually interesting, but will serve as the backbone of the last part of this series. There we will bring the two topics covered in these tutorials together, and will probably as such be much longer. Again if you have any questions, feel free to drop me a line @ApparentRaisin

Otherwise, until next time

-Max