Map L-systems

Map L-systems are version of the more familiar L-systems. Formally, they can be treated as a method for rewriting strings. L-systems are equivalent to formal grammars.

L-systems have been used in computer graphics to generate realistic images of trees and flowers. With the aid of turtle-graphics, the string is graphically interpreted. The turtle interprets the symbols in the string as "move forward and draw a line", "turn X degrees to the right", etc. Two important symbols are the "push state onto stack" (usually represented by "[") and "pop state from stack" (represented by "]"). These instructions allows the turtle to create a branch from the structure. When the turtle encounters a "[", the current state (position) is saved (on a stack) and when it encounters the corresponding "]" the old state is popped from the stack. Thus, the turtle is moved back to the position where it was before the "[".

A flower created using L-systems.

Map L-systems are very similar to ordinary L-systems. The grammar used by Map L-systems has one major difference from ordinary L-system grammars, the seed must form a a closed loop. That ensures that the system starts with a valid surface. The Map L-systems grammar is interpreted in the same way as ordinary L-systems, the only difference is when handling the branches. With Map L-systems, branches facing each other are connected and branches that do not have "an opposite" are simply removed. This will lead to an increasing subdivision of the original surface. Map L-systems were originally used to model cellular development in morphogenesis.

An example of a map L-system

Map L-systems are planar graphs and connecting the branches is comparatively easy and straightforward. GENR8 creates surfaces in 3D space and thus the graphs can not be restricted to a plane. Allowing for the turtle to move in threee dimensions is an easy task. The difficult part is making sure that the branches connect properly. This is solved by introducing a new parameter, branch angle. When a branch tries to connect to other branches, it searches a cone where the arc is limited by this parameter. Thus, a high branch angle usually results in a surface with more subdivisions. More about the growth model and map L-systems can be found in the thesis.

Both L-systems and Map L-systems are very good at mimicing organic growth and that is one of the reasons they are used in GENR8. When a structure described by an L-system grows, all parts grow concurrently. Also, environmental interaction is easy to model with L-systems. Furthermore, L-systems are easy to use in combination with evolutionary algorithms. Finally, it is a very elegant way to represent such a complex entity as a surface.