Procedural Buildings PART III: R0.3

R0.3 Design (draft)

L-systems 

According to wikipedia, "an L-system or Lindenmayer system is a parallel rewriting system and a type of formal grammar". I will skip the mathematical notations and I will try to simplify and exemplify.

My L-System implementation in Unity

An L-system is an iterative process and its application includes the following, for a chosen domain:

1. The translation or mapping process of elementary -building- blocks of the selected domain into symbols -usually we use characters (e.g. 'w' for windows, 'd' for doors, 'f' for floors). Thus a given vocabulary is built that is mapping this translation. Keep in mind that elementary blocks can also include operators on other blocks, e.g. '+' can be a symbol for addition and
2. The definition of a starting set of blocks in the form of a string to start with our iterations, called the axiom (e.g. "wdw" for 'window followed by door followed by window'). The axiom is modified in the next iteration by applying the production rules on it (see below).
3. A variable representing the L-system string at the i-th iteration, which holds the modification of the axiom string at the current (i-th) iteration (e.g. "wdwwfwwwdfwdf").
4. The definition of a set of rules that will be applied on the current set of blocks in each iteration. Now, this is essential for the result that we will get at the end of each iteration. An example of one such rule would be: (w -> ww), meaning that for any window symbol found in the L-system string in the i-th iteration, two windows will be created in its place in the (i+1)th iteration. Multiple such rules usually exist in the production rule set, and its construction is a meticulous job, often it is modified multiple times in a trial-and-error fashion.
5. The definition of the inverse mapping process from the i-th iteration L-system string variable into the assembly of the final procedural construction in the chosen domain. If we get this last piece, we can then assemble the building blocks and create the geometrical model that resulted from the L-System in Unity.

Steps 1 and 5 are not typically parts of an L-System but are essential if we would like to apply an L-System to a real-world problem, otherwise the L-System per se would be just a theoretical construct, a grammar and a produced string without practical meaning at the end of some iteration. Once we get all these 5 steps nailed, we are ready to start the procedural generation of our buildings using L-Systems.

the so-called Sierpinski triangle, a classic application of L-Systems

The example provided in the L-Systems description above is close to what I am trying to build, but it is incomplete. I will try to complete it, as an elementary example of what can be done. In this case, I will focus on a probable L-System for release R0.3:

Mapping process 

We have a building level to decorate with windows, empty tiles and pass columns (which segment the horizontal level into several sections). We will use the following vocabulary:

• w: window of a fixed width and hight (say 1 by 1 meters), positioned 0.5 meters above floor level
• t: empty tile of a fixed width (say 1 meter) and of the full level height
• c: column separating sections of fixed width (say 1 meter as well) and of the full level height

Axiom

Let us say that the width of the façade of the level is 10 meters. We are starting with the following axiom:

• "w"

Production Rules

Let us use the following 4 rules:

• t->twt
• w->wtw
• twt->c
• cc->tct

Iterations

Let us see how the L-System string is being developed through successive iterations:

1. wtw
2. wtwtwtwtw
3. wcwtwcwtw
4. wtwcwtwtwtwtwcwtwtwtwtw
5. wtwtwtwtwcwtwcwtwcwtwcwtwcwtw

etc.
We can see a pattern emerge. We may set when to interrupt the process, by bounding to a certain number of iterations.

Inverse mapping and texture creation

So the end result of iteration 3 is the string "wcwtwcwtw", which we will need to inverse map to a geometric shape or texture. I will add soon an image of this result rendered, and also provide the associated script.

Implementing a classical L-System

In order to warm up myself, and because I did not find any free L-System implementation in Unity, I wrote mine. As always, it is freely available for others to peek and check out. Apart from the fun of it, it will be handy when I will implement the building level outline randomisation, before extruding to the Y axis.

All the popular commands/operations are supported, namely:

• F (also A and B): move forward and draw a line of a fixed width
• f: move forward without drawing a line
• +: turn left on the XY plane to a "RotationAngle" degrees. RotationAngle is a parameter of the L-System, and is set in the beggining
• -: turn right on the XY plane to a "RotationAngle" degrees
• z: turn left on the ZY plane to a "RotationAngle" degrees
• a: turn right on the ZY plane to a "RotationAngle" degrees
• [: push state (store current position and direction)
• ]: pop state (restore position and direction)

The following options can be set:

• Production rules: Left hand part of the rule is separated from its right hand with the ':' character. The current version supports D-0 L-Systems, meaning that no rule can have more than one symbol on its left-hand part.
• Axiom: Here you may set the string of the starting set
• Iterations: this is where the number of iterations is set. I have limited this to 10 in order to protect you from wasting your pc resources and you from dying from boredom while waiting for the L-System rendering to end.
• Rotation Angle: capped as well, bound between 0 and 120 degrees

I have also provided a GUI where you may experiment with the L-System parameters. Check it out, select an existing L-System or design your own:

Next improvements planned:

• more L-Systems, 
• scene navigation to be able to pan/zoom properly over the L-System visualisation, 
• replacing line generation and visualisation with mesh generation and visualisation, 
• making the script enabled in the Unity editor, so that you may get the resulting mesh and experiment with it, use it in your scenes, play with it, animate it, dance with it, sing with it.

The code, please?

I feel that just the demo is of little use, if you cannot have the C# script in your hands and experiment with it. This blog sets for releasing every bit of code, no copyrights, no copylefts, just some attribution where it is due, as the Creative Commons license CC-BY 3.0 dictate. I will gradually release the code so that I will be able to properly explain its pieces. Everything resides in one script, named 'L_System_R03.cs'.

Public and private variables

   

// Public (visible through the Inspector) and private variables:
    
    /// <summary>
    /// The production rules. HashTable class, whose instance will store the L-System rules
    /// </summary>
    
    //public structure that holds production rules and their probabilities, to be used in the GUI
    public struct productionRuleDisplayType {
        public int id;
        public string rule;
        public float prob;
    }
    private productionRuleType productionRules = new productionRuleType();
    // the L-System string
    private string lSystem;
    // public in Inspector for the moment, until it moves to the game's GUI
    public productionRuleDisplayType [] prodRules = new productionRuleDisplayType[0];
    // these are used in the GUI
    private string newRulePrompt = "Insert a valid Rule";
    private bool dropDownBoxState = false;
    
    public string axiom;
    public int iterationsNumber = 5;
    public int rotationAngle = 45;
    public float branchLength = 1f;
    public Material lineMaterial;
    private int iterationsNumberBound = 20;
    private Vector3 lSystemStartpoint;
    private Vector3 lSystemDirection;
    // L-System symbols
    private char ruleDelimiter = ':';
    private const char forward1 = 'F';
    private const char forward2 = 'A';
    private const char forward3 = 'B';
    private const char skipForward = 'f';
    private const char turnLeftZ = '+';
    private const char turnRightZ = '-';
    private const char turnLeftX = 'x';
    private const char turnRightX = 'c';
    private const char push = '[';
    private const char pop = ']';
    private const char turnLeftY = 'a';
    private const char turnRightY = 'z';

    
    // The array of lines that will be drawn to represent the L-system is a GameObject with a LineRenderer
    private ArrayList lSystemGeometry = new ArrayList();
    
    // A class to hold the state of an L-System
    class lSystemState {
        public Vector3 position;
        public Vector3 rotation;
    }
    
    // a stack collection to store the states during visualisation of the L-System string (operations push and pop)
    private Stack currentState = new Stack();

Starting with the more important variables, lSystem string is holding the current series of our L-System symbols, as it is iteratively rewritten, iteration by iteration. productionRules is a variable that instantiates a special class that I wrote, named productionRuleType. The class is actually a collection of triples, all related to the L-System production rules: left-hand side of the production rule, right-hand side, and its probability which is one if no other rule can be applied on the L-String variable at any time, less than one if multiple rules apply and we have to select one of them (the sum of the probabilities of all those rules should be one though). An example of the latter case, is the set of rules: F->F+F+F and F->FF+FF+FF.

In order to facilitate the Unity GUI I needed some other expression of the production rules, as string data types (as the Unity manual instructs especially for the GUI.TextField case, one should use a string variable in the right-hand side to initialise the class instance and another string variable in the left-hand side to get the value input provided by the user). This need is met with the introduction of the prodRules variable and its associated simple struct productionRuleDisplayType. During the OnGUI method the prodRules array is populated, and when the user presses the START button to render the L-System, the production rules are read and ported on to productionRules.

The visualisation of the L-System is based on the iterative generation of line segments, properly positioned, that are rendered on the scene. lineMaterial defines the specific material that will be applied on the lines.
lSystemGeometry is a collection of the GameObjects of the generated lines. A set of typical symbols in L-Systems, also used in this implementation, are represented by constant characters that are referred in the code with their assigned names. Note that there are multiple symbols for the move forward command (that also draws a line). Even more symbols can be easily added if needed. Finally, the class lSystemState represents the state of the L-System visualisation at some iteration k, while the currentState variable is an instance of the Stack C# collection class, handy when one has to implement push and pop operations, as those for the '[' and ']' symbols in an L-System.

Grammar rewriting

Grammar rewriting is implemented by 2 methods that work in unison, one is wrapping the other.

The inline comments are adequately describing the relevant piece of the code.

   

// Rewrite grammar up to iterationsNumber iterations 
    /// <summary>
    /// Iterate until the specified iterationsNumber.
    /// </summary>
    /// <param name='iterationsNumber'>
    /// the Iterations number where the iteration will stop.
    /// </param>
    string iterate (int iterationsNumber) {
        for (int iteration=0; iteration<iterationsNumber; iteration++)
            for (int charIndex=0; charIndex<lSystem.Length; charIndex++) {
                // find all applicable rules' indices
                int [] applicableRules = new int [productionRules.Count];
                int applRulesIndex = 0;
                proceduralBuildings_R02.PPSSampling randomiser= new proceduralBuildings_R02.PPSSampling();
            
                for (int rIndex=0; rIndex < productionRules.Count; rIndex++)
                    if ( productionRules.getKey(rIndex) == lSystem.Substring(charIndex, productionRules.getKey(rIndex).Length) ) {
                        applicableRules[applRulesIndex++] = rIndex;
                        randomiser.setProbability( productionRules.getProbability(rIndex) );
                    }
                //determine length of applicableRules
                int applicableRulesNumber = randomiser.size();
//                for (int i=0; i<applicableRules.Length; i++)
//                    if (applicableRules[i] != null)
//                        applicableRulesNumber++;
                if (applicableRulesNumber > 0) {
                //select random applicable rule based on equal size sampling (all applicableRules candidates have equal probabilities)
                    int randomRuleIndex = randomiser.getRandomInt();
                    if (applicableRules[randomRuleIndex] >= productionRules.Count)
                        Debug.LogError("Error: the applicableRules selected index at " + randomRuleIndex + " is a string of zero length which is unacceptable.");
                    lSystem = rewriteGrammar(lSystem, charIndex, productionRules.getKey(applicableRules[randomRuleIndex]), productionRules.getRule(applicableRules[randomRuleIndex]));
                    charIndex += productionRules.getRule(applicableRules[randomRuleIndex]).Length -1;
                }
            }
        return lSystem;
    }
    
    /// <summary>
    /// Rewrites the grammar inside one iteration. This method is called by iterate.
    /// </summary>
    /// <returns>
    /// The grammar after having been rewritten. The grammar is the L-System string variable.
    /// </returns>
    /// <param name='grammar'>
    /// Grammar, which is the L-System string variable.
    /// </param>
    /// <param name='leftsideRule'>
    /// Leftside is the left-hand part of the production rule, to be searched for in the grammar and replaced.
    /// </param>
    /// <param name='rightsideRule'>
    /// Rightside rule, to replace the left-side part of the production rule.
    /// </param>
    /// <param name='characterIndex'>
    /// Character index that dictates where this method to look for possible rule applications (string substitutions) in the grammar string.
    /// </param>
    string rewriteGrammar(string grammar, int characterIndex, string leftsideRule, string rightsideRule) {
        string retVal = "";
        if (grammar.Length > characterIndex && grammar.Substring(characterIndex, leftsideRule.Length) == leftsideRule)
            for (int i=0; i<grammar.Length; i++) {
                if (i == characterIndex) {
                    retVal += rightsideRule;
                    // proceed i by the length of leftsiderule
                    i += leftsideRule.Length - 1;
                }
                else
                    retVal += grammar[i];
            }
        return retVal;
    }

The method iterate implements the grammar rewriting by applying the production rules on the L-System string variable iteratively, specifically an iterationsNumber times. Each time, the following are happening:

• In the current place of the 'cursor' (expressed by the charIndex variable) on the L-String variable, the production rules are checked, and for any ones that can be applied I store their productionRules indexes in the applicableRules array. This way both deterministic (where only one maximum rule can be applied at any time) and probabilistic L-Systems (where multiple rules can be applicable, and a selection process takes place each time) are accounted.
•  I instantiate a variable of the PPSSampling class (see R0.2), and then the getRandomInt method of this class is invoked. This is how one of the applicableRulesNumber number of rules will be selected to be applied to the L-System variable.
• rewriteGrammar is invoked with the selected rule as a parameter. It will search for the left-hand part of the rule starting from the insertion point (charIndex) and on, and will substitute with the right-hand part of the rule.
• charIndex will be increased by the length of the right-hand part of the rule that has just been applied, so that it will pass over the substituted part, and be ready for the remaining string.

L-System visualisation

 The visualise method constitutes the fifth step of an L-System, where the finally produced lSystem string variable is represented in a graphical form and is rendered on the screen. Each symbol in the string is parsed and interpreted. All 'move forward' symbols, i.e. F, A and B, are creating 3D lines. This simple task is carried out by the createLine method, which takes as its arguments the starting and ending point -a Vector3 variable- and the material to be applied on the created line:

   

/// <summary>
    /// Creates a line, implementing the F symbol in the l-System string.
    /// </summary>
    /// <returns>
    /// The line created, as a GameObject.
    /// </returns>
    /// <param name='start'>
    /// Starting point as Vector3
    /// </param>
    /// <param name='end'>
    /// Ending point as Vector3
    /// </param>
    /// <param name='aMaterial'>
    /// A material that the line will be drawn with
    /// </param>
    GameObject createLine(Vector3 start, Vector3 end, Material aMaterial) {    
        GameObject branchLine = new GameObject("L-System_Geometry");
        branchLine.AddComponent<LineRenderer>();
        LineRenderer renderer = branchLine.GetComponent<LineRenderer>();
        renderer.SetWidth(0.2f, 0.1f);
        renderer.SetVertexCount(2);
        renderer.SetPosition(0, start);
        renderer.SetPosition(1, end);
        renderer.material = aMaterial;
        return branchLine;
    }
}

createLine is invoked by visualise, let's see the code for the latter:

   

/// <summary>
    /// Visualise the L-System that lSystemString represents.
    /// </summary>
    /// <param name='lSystemString'>
    /// L-system string.
    /// </param>
    IEnumerator visualise(string lSystemString) {
        // browse through the lSystem string
        for (int i=0; i<lSystemString.Length; i++) {
            char choice = lSystemString.ToCharArray()[i];
            switch (choice) {
            case forward1: case forward2: case forward3: {
                lSystemGeometry.Add (createLine(lSystemStartpoint, lSystemStartpoint+lSystemDirection*branchLength, lineMaterial));
                lSystemStartpoint = lSystemStartpoint+lSystemDirection*branchLength; 
            }
                break;
            case skipForward: 
                lSystemStartpoint = lSystemStartpoint+lSystemDirection*branchLength;
                break;
            case turnRightZ:
                lSystemDirection = Quaternion.AngleAxis(rotationAngle, Vector3.forward)*lSystemDirection;
                lSystemDirection.Normalize();
                break;
            case turnLeftZ:
                lSystemDirection = Quaternion.AngleAxis(-rotationAngle, Vector3.forward)*lSystemDirection;
                lSystemDirection.Normalize();
                break;
            case turnRightX: {
                lSystemDirection = Quaternion.AngleAxis(rotationAngle, Vector3.right)*lSystemDirection;
                lSystemDirection.Normalize(); }
                break;
            case turnLeftX: {
                lSystemDirection = Quaternion.AngleAxis(-rotationAngle, Vector3.right)*lSystemDirection;
                lSystemDirection.Normalize(); }
                break;
            case turnRightY:
                lSystemDirection = Quaternion.AngleAxis(rotationAngle, Vector3.up)*lSystemDirection;
                lSystemDirection.Normalize();
                break;
            case turnLeftY:
                lSystemDirection = Quaternion.AngleAxis(-rotationAngle, Vector3.up)*lSystemDirection;
                lSystemDirection.Normalize();
                break;
            case push: {
                lSystemState newState = new lSystemState();
                newState.position = lSystemStartpoint;
                newState.rotation = lSystemDirection;
                currentState.Push (newState);
            }
                break;
            case pop: {
                lSystemState oldState = new lSystemState();
                oldState = (lSystemState)currentState.Pop();
                lSystemStartpoint = oldState.position;
                lSystemDirection = oldState.rotation;
            }
                break;
                
            }
        }
        yield return new WaitForFixedUpdate();

    }

Up to this point, things should have been clear more or less. What I omitted is describing and providing the code for the screen GUI. I feel that this discussion belongs to another thread where I should elaborate on some of the intricacies of Unity GUI. However, for your information, the GUI mode is GUILayout, which is a special GUI mode where the GUI elements do not need to be placed in space by absolute coordinates, but are making use of the screen space segmentation, just like the span or div commands are doing for HTML.

If you insist that the GUI part should be also provided and analysed here, then please drop a comment below saying so :)