Lexa

WPF, C#, Objective C and a little Math

Context sensitive parametric L-systems framework in C#

Subject of this post is a small C# library, which can be used to:
– define L-System and Modules as C# classes,
– create and use L-System using these definitions.

I was inspired by “L+C” language (see official page of L+C for details), but in contrast to “L+C” I wanted to use only native language features, without any source code parsers or translators from L-System definition source code to C# source code. Consequently, I wanted to debug L-System source code as any other source code of .Net application, and use the library in any application.

Modules are defined using just C# types. In case of parametric L-Systems module uses properties as parameters. For example:

public class A
{
    public int X { get; protected set; }
    public int Y { get; protected set; }
    public A(int x, int y)
    {
        this.X = x;
        this.Y = y;
    }
}

Any C# type can be used as parameters, including enums, user defined types, etc.

Next question was – how to define production rules. After some experiments I found that the best way to define production rule is a function with parameters representing different predecessor parts – strict predecessor, left context, right context, etc. To specify “role” of each parameter in predecessor I used ProductionAttribute – C# Attribute class containing string describing predecessor composition.

As example, the following source code presents production rule function transforming module B surrounded with modules A and C in module D if some condition is met:

...
[Production("a < b > c")]
object SomeProductionMethod(A a, B b, C c)
{
    if (b.X > a.X + c.Y)
        return new D(b.X + b.Y);
    else if (b.x > 1)
        return new EmptyModule();
    else
        return null;
}
...

Here EmptyModule is a special type of module – it can be returned by production rule to replace strict predecessor with nothing. Returned null means that rule is not applicable.

Description uses “L+C” form for predecessor definition:

new-left-context << left-context < strict-predecessor > right-context
left-context < strict-predecessor > right-context >> new-right-context

Any part of predecessor definition can consist of zero or more modules, the only part which must have at least one module is strict predecessor. New-left-context is used when rewriting from left to right, new-right-context is used when rewriting from right to left.

Now the system can be defined as a class with functions tagged with ProductionAttribute – SystemDefinition class. Final task is to analyze this class, extract tagged methods and generate information which will be used by string rewriting algorithm. This task is solved with help of reflection and regular expressions in special class SystemBuilder. The user of the library shall just call SystemBuilder.Build method with SystemDefinition instance and use returned System object (if any ProductionAttribute data is wrong, an exception will be thrown!). For example:

var definition = new MySystemDefinition();
System system = SystemBuilder.BuildSystem(definition);
system.String = new [] { new F(), new F() };
for (int i = 0; i < 10; ++i)
{
    system.RewriteLeftToRight();
}
...

Thats basically it. At the moment solution contains the library itself and small console application implementing context-sensitive variant of Anabaena (example is taken from “Introduction to Modeling with L-Systems” after Przemyslaw Prusinkiewicz). This is the full text of the console application:

public class W
{
    public double T { get; private set; }
    public W(double t) { this.T = t; }
    public override string ToString()
    {
        return string.Format("W({0:0.00})", this.T);
    }
}

public class M
{
    public double T { get; private set; }
    public M(double t) { this.T = t; }
    public override string ToString()
    {
        return string.Format("M({0:0.00})", this.T);
    }
}

public class AnabaenaDefinition
{
    public const double Div = 1;
    public const double ShortCell = 0;
    public const double LongCell = 0.2;
    public const double TimeStep = 0.7;
    public const double Epsilon = 0.000001;

    [LSystems.Production("w")]
    public object WallGrow(W w)
    {
        return new W(w.T + TimeStep);
    }

    [LSystems.Production("m")]
    public object CellGrow(M m)
    {
        if (m.T < Div - Epsilon)
            return new M(m.T + TimeStep);
        else
            return null;
    }

    [LSystems.Production("leftWall < m > rightWall")]
    public object Divide(W leftWall, M m, W rightWall)
    {
        if (m.T > Div - Epsilon)
        {
            if (leftWall.T < rightWall.T)
            {
                return new object[]
                {
                    new M(m.T - Div + LongCell),
                    new W(m.T - Div),
                    new M(m.T - Div + ShortCell),
                };
            }
            else
            {
                return new object[]
                {
                    new M(m.T - Div + ShortCell),
                    new W(m.T - Div),
                    new M(m.T - Div + LongCell),
                };
            }
        }
        return null;
    }
}

class Program
{
    static void Main(string[] args)
    {
        // Create L-System.
        var definition = new AnabaenaDefinition();
        LSystems.System system =
        LSystems.SystemBuilder.BuildSystem(definition);
        system.String = new object[]
{
new W(0), new M(0), new W(AnabaenaDefinition.TimeStep)
};

        // Rewrite and printout the result.
        Print(system.String as IEnumerable);

        for (int i = 0; i < 7; ++i)
        {
            system.RewriteLeftToRight();
            Print(system.String as IEnumerable);
        }

        Console.WriteLine("Press any key to exit...");
        Console.ReadKey();
    }

    private static void Print(IEnumerable modules)
    {
        foreach (object module in modules)
        {
            Console.Write("{0} ", module);
        }
        Console.WriteLine();
    }
}

And this is the output:

W(0,00) M(0,00) W(0,70)
W(0,70) M(0,70) W(1,40)
W(1,40) M(1,40) W(2,10)
W(2,10) M(0,60) W(0,40) M(0,40) W(2,80)
W(2,80) M(1,30) W(1,10) M(1,10) W(3,50)
W(3,50) M(0,30) W(0,30) M(0,50) W(1,80) M(0,30) W(0,10) M(0,10) W(4,20)
W(4,20) M(1,00) W(1,00) M(1,20) W(2,50) M(1,00) W(0,80) M(0,80) W(4,90)
W(4,90) M(0,00) W(0,00) M(0,20) W(1,70) M(0,40) W(0,20) M(0,20) W(3,20) M(0,00) W(0,00) M(0,20) W(1,50) M(1,50) W(5,60)
Press any key to exit...

Complete solution can be found here.

edit 23.07.2011: check out last version of the source code, including 2d and 3d viewer on this google project page.


Categorised as: L-Systems


Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>