Neues aus der Serie "Dolles aus der Wissenschaft", Heute: L-Systeme

Den Thread wollte ich dann doch noch retten. Ich werde demnächst mal was neues schreiben, aber im Moment bin ich wieder tief in Hausarbeiten versunken, aber mal sehen da kommt bestimmt noch das ein oder andere Thema bei rum :D

L-Systeme oder auch Lindenmayer Systeme sind Ende der sechziger Jahre von Aristid Lindenmayer entwickelt worden um Wachstum von Pflanzen zu simulieren.

Was ist das Besondere an L-Systemen? Erstens, die zugrunde liegenden Prinzipien sind relativ einfach, dennoch können äußerst komplexe Strukturen und Wachstumsfaktoren simuliert werden; wie komplex und schick das ganze aussehen kann, dazu später mehr. Diese Eigenschaft trotz einfacher Mechanismen komplexe Ergebnisse und Dynamik zu erzeugen wird auch als Emergenz bezeichnet, um den alten Aristoteles mal zu entstauben: Das Ganze ist mehr als die Summe seiner Teile. Zweitens, auch wenn Mathematiker oft von einfachen Systemen sprechen die zugrunde liegende Formalisierung ist es oft nicht (Es soll ja Leute geben, die bei gekoppelten Differentialgleichungen schreiend das Weite suchen). Im Gegensatz dazu sind L-Systeme aber wirklich relativ leicht zu verstehen.

Im Prinzip sind L-Systeme Generative Grammatiken, also eine Sammlung verschiedener Ersetzungsregeln für Zeichen und Strings.
Ich verzichte auf die mathematische Definitionen und erläutere dies anhand von Beispielen, solche Ersetzungsregeln sehen in etwa so aus:

A -> ABA
B -> A

Ein Pfeil bedeutet 'wird ersetzt durch', sprich A wird ersetzt durch den String ABA und B durch A. Wenn wir nun zum Beispiel mit A anfangen, dann erhalten wir nach der ersten Iteration des Algorithmus ABA. Nun werden wieder alle Buchstaben - gleichzeitig wohlgemerkt - ersetzt, das führt dann zu ABAAABA, und so weiter. Die gleichzeitige Ersetzung ergibt auch aus biologischer Sicht Sinn, Pflanzen wachsen ja auch im Ganzen und nicht nur an einer einzigen Stelle wird ein Blatt ausgebildet.

Nun können wir zumindest nette, exponentiell wachsende Strings generieren, aber mit Pflanzenwachstum hat das noch nicht wirklich viel zu tun. Der erste Schritt in diese Richtung wird erreicht durch das Konzept des Turtle Drawings. Man kann sich eine arme Schildkröte vorstellen, durch dessen Panzer ein dicker Bleistift gesteckt wurde. Diese Schildkröte sitzt nun auf einem Blatt Papier und kann dort munter (trotz Bleistifts durch die Eingeweide!) herum wandern und malen. Genauer gesagt, kann man der Schildkröte befehlen eine gewisse Schrittweite nach vorne zu gehen oder sich um einen gewissen Winkel nach links oder rechts zu drehen. Der ein oder andere wird sich hier an die Programmiersprache LOGO erinnern, die gerne genutzt wird um Kinder an das Programmieren heranzuführen. Um der Schildkröte Befehle zu geben gibt es bestimmte Symbole: F für vorwärts gehen und dabei zeichnen, f für vorwärts ohne zu zeichnen und + und - für eine Drehung um einen festen Winkel nach rechts oder links.

Diese Symbole werden in ein Grammatik eingebunden und der String, der nach einer festen Anzahl an Iterationen erzeugt wird, kann von der Schildkröte als Befehlskette zum Zeichnen interpretiert werden. Zeichen, die der Schildkröte unbekannt sind, werden einfach ignoriert und überlesen.
Man nehme beispielsweise die folgende Grammatik:

F->F+F--F+F

Somit lassen sich die folgenden Strings erzeugen:
F (Start), F+F--F+F (1. Generation), F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F (2. Generation), usw.
Wenn wir diese von der Schildkröte zeichnen lassen, einen festen Drehwinkel von 60° wählen und die feste Schrittweite für jede Iteration dritteln, dann lassen sich schöne Kochkurven erstellen:
Anhang 334

Dennoch die Ähnlichkeit zu natürlichen Pflanzen ist eher vage bis nicht vorhanden, das System muss dafür noch um einige Konzepte ergänzt werden. Die Klammer Operatoren [ und ] erweitern die Schildkröte um einen so genannten Stack Memory. Auf diesen Speicher können die aktuelle Position und die aktuelle Orientierung abgelegt werden. Dies geschieht sobald die Schildkröte [ liest. Wird jedoch ] eingelesen so nimmt die Schildkröte den obersten Eintrag vom Speicher und wird dorthin zurück teleportiert. Dadurch ist es beispielsweise möglich nach dem Zeichnen eines Astes wieder zum Stamm zurückzukehren.
So lassen sich schon sehr natürlich wirkende Pflanzen erzeugen:
Anhang 331
n ist die Anzahl der Iterationen und der Winkel ist mit klein Sigma bezeichnet, das Symbol X wird von der Schildkröte ignoriert und dient nur der Grammatik. Das Bild stammt aus [1].


Natürlich kann man die Schildkröte etwas modifizieren und dreidimensionale Rotationen und farbige Zeichnungen erlauben. Das Hinzufügen von Makrostrukturen wie beispielsweise die Möglichkeit ganze Blätter zu zeichnen kann die Schildkrötenbefehle noch ergänzen:
Anhang 335
Bild entnommen aus [1].

Und tatsächlich, dies sieht schon sehr nach einer natürlichen Pflanze aus.

Das L-System lässt sich aber noch erweitern, man kann beispielsweise Stochastizität einführen. Demnach gibt es mehrere Regeln um ein Zeichen zu ersetzen und eine Regel wird zufällig mit einer bestimmten Wahrscheinlichkeit ausgewählt:

A -> AB : 0.2
A -> BA : 0.8

Hier wird A mit 20% Wahrscheinlichkeit durch AB und mit 80% Wahrscheinlichkeit durch BA ersetzt. So lassen sich Pflanzen des selben Typs gut variieren:
Anhang 333
Alle Pflanzen sind mit den gleichen stochastischen Regeln erstellt. Das Bild stammt auch aus [1].

Obwohl die Pflanzen unterschiedlich sind, könnte man sie gut der gleichen Art zuordnen.

Darüber hinaus lässt sich noch Kontextsensitivität definieren:

B<A>C -> ACA

Hier wird A nur durch ACA ersetzt falls sich zur Linken von A ein B und zur Rechten ein C befindet. Zuvor war es unmöglich zu simulieren, dass ein Baum in der Krone anders wächst als unten am Stamm, durch Kontextsensitivität lässt sich dies jedoch erreichen. Kontextsensitive Pflanzen sehen zum Beispiel so aus:
Anhang 330
Wiederum stammt das Bild aus [1].

Dennoch wird Kontextsensitivität etwas komplizierter wenn man die Klammeroperatoren [ und ] hinzunimmt mit denen sich Verästelung simulieren lassen. Der Kontext eines Zeichens ist dann definiert als der obere und untere Teil in der Zeichnung und nicht notwendigerweise als der Kontext direkt im String.
Zum Beispiel würde die obere Regel auch in diesem Fall greifen B[ACA]AC, A befindet sich zwischen B und C und der Nebenast [ACA] wird ignoriert. In der resultierenden Pflanzenzeichnung lägen B und A nämlich neben bzw. untereinander.
Kontextsensitivität kann auch genutzt werden um Informationsfluss in Pflanzen zu simulieren, beispielsweise Chemikalien die durch den Stängel transportiert werden oder ähnliches.

Die letzte Erweiterung parametrisiert L-Systeme und die Simulation kann durch logische Ausdrücke und mathematische Operatoren und Funktionen ergänzt werden:

A(t): t > 3 -> B(4t) C(t^2+sin(t),ln(t))

A wird nur durch BC ersetzt wenn der Parameter t größer als 3 ist, darüber hinaus wird t weiter an B und C übergeben. Sehr komplexe Modelle sind möglich wenn nun zusätzlich noch ein mathematisches Modell der Umgebung der Pflanze gegeben ist, das beispielsweise Parameter bestimmen kann, welche das einfallende Licht, Nährstoffe im Boden oder Hindernisse wie Felsen oder Steine beschreiben. Solche mit der Umgebung kommunizierenden L-Systeme werden auch Open L-Systems genannt. Die Schildkrötenbefehle lassen sich ebenso gut parametrisieren: F(t) oder +(t) könnten beispielsweise einen Schritt oder Drehung um den Faktor t bedeuten.

Zum Beispiel lässt sich damit eine Pflanze in einer Box simulieren, die Umgebung definiert die Grenzen der Box,
Anhang 332
Bild entnommen aus [2].

oder auch Bäume die um Sonnenlicht konkurrieren und deshalb voneinander weg wachsen:
Anhang 336
Bild entnommen aus [3].

Wie gezeigt sind L-System ein sehr mächtiges Werkzeug um Pflanzen naturgetreu zu modellieren. L-Systeme werden auch vielfach in der Wissenschaft verwendet, beispielsweise um den Metabolismus von Bäumen zu untersuchen [4] oder die Entwicklung von Wurzelwerk in verschiedenen Bodenarten [5]. Aber nicht nur künstliche Pflanzen werden erstellt, auch andere wachsende biologische Strukturen wie das Wachstum von neuronalem Gewebe [6]. MWn werden L-System auch in 3D-Spielen häufig verwendet um Wälder und andere Landschaften zu kreieren, leider konnte ich dazu aber keine Quellen finden.

Wer interessiert ist, HIER gibt es sehr viele kostenlose Literatur zu dem Thema.

[1] P. Prusinkiewicz and A. Lindenmayer, The Algorithmic Beauty of Plants. Springer, 1990.

[2] P. Prusinkiewicz, M. James and R. Mech, Synthetic Topiary, Computer Graphics Proceedings, 1994.

[3] R. Mech and P. Prusinkiewicz, “Visual models of plants interacting with their environment,” in Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, ser. SIGGRAPH ’96. New York, NY, USA: ACM, 1996, pp. 397–410.

[4] M. T. Allen, P. Prusinkiewicz, and T. M. DeJong, “Using l-systems for modeling source-sink interactions, architecture and physiology of growing trees: The l-peach model,” New Phytologist, vol. 166, no. 3, pp. pp. 869–880, 2005.

[5] D. Leitner, S. Klepsch, G. Bodner, and A. Schnepf, “A dynamic root system growth model based on l-systems,” Plant and Soil, vol. 332, pp. 177–192, 2010, 10.1007/s11104-010-0284-7.

[6] H. Jelinek, A. Karperien, D. Cornforth, R. M. C. Junior, J. de Jesus Gomes, R. Marcondes, C. Junior, J. Jesus, and G. Le, “Micromod - an l-systems approach to neuron modelling,” in National University, 2002, pp. 156–163.