Lindenmayer-System – jetzt lassen wir Pflanzen wachsen

Mit einem Lindenmayer-System kann man künstliche Pflanzen erstellen. Passt ganz gut, denn im letzten Artikel Waldbrand haben wir den gesamten Wald abgefackelt. Das L-System ist ein netter Algorithmus um realistisch aussehende Pflanzen für eine Simulation zu erstellen.

Lindenmayer-System – jetzt lassen wir Pflanzen wachsen

Ein Lindenmayer-System ist im Grund nur ein String aus Zeichen der eine Ersetzungslogik angibt. Diese wird rekursiv auf einem Ausgangszustand angewendet. Je nach Logik ergeben sich die unterschiedlichsten Strukturen, bekannt sind die so genannten Fraktale. In der Simulation und Spieleprogrammierung werden solche Systeme gerne genutzt.

Praktische Anwendung

Man kann mit nur wenig Logik ein fast unendlich großes System aus unterschiedlichsten Formen erstellen. Beispiele für prozedural erstellte Spielwelten sind: Elite, Spore oder das vor einiger Zeit kontrovers diskutierte No Man’s Sky. Bei diesen Spiele wird durch eine Regel unter Einbeziehung von Zufall ein Universum von zufällig erstellten Welten erstellt die alle ähnlichen Regeln folgen.

Pflanzen selber erstellen

Die folgende Bildergalerie zeigt einige mit dem Algorithmus erstellte Pflanzen. Man erkennt sehr gut, dass diese teilweise ganz andere Formen annehmen, diese aber aus der Natur sehr vertraut wirken.

Wie funktioniert nun der Algorithmus und wie implementiert man ihn?

Source Code

Wie immer gibt es meinen Source Code auf meiner GitHub Seite zum Download. Für die Beispiele verwende ich die ClanLib Game Engine, der relevante Teil zum Zeichnen kann aber auch in jeder anderen Engine umgesetzt werden.

Für dieses Beispiel benötigen wir lediglich eine Konstante:

#define OFFSET 100

Der in der globals.h definierte OFFSET gibt die Länge eines Elements der gezeichneten Pflanze an. Über die Pfeiltasten hoch und runter kann man dies dynamisch ändern (*2 oder /2 in der on_keyboard Methode in app.cpp):

case clan::keycode_down: length = length / 2; break;
case clan::keycode_up: length = length * 2; break;

Darüber können wir steuern, dass die Pflanze Bildschirm füllend gezeichnet wird. Wie funktioniert nun das Programm? Nachdem das Fester erstellt ist wird das L-System mit einem Anfangszustand initialisiert. Zu sehen ist lediglich ein gerader Strich. Mit der Leertaste kann man nun Schrittweise das eingestellte L-System anwenden -> Schritt für Schritt. Über die Zifferntasten 1 – 8 legt man das aktuell aktive L-System fest (ich habe 8 unterschiedliche Formeln erstellt – ihr dürft da gerne weitere erfinden oder meine anpassen). Die aus den anderen Beispielen (Sanduhr und Waldbrand) bekannten Methoden init(), compute() und render() initialisieren wir die Simulation, wenden die Spiellogik an oder zeichnen das Ergebnis. Die compute() Methode wird diesmal aber nicht in einer Spielschleife, sondern per Tastendruck (Leertaste) ausgelöst.

L-System Code

Das L-System habe ich in den beiden Klassen lsystem und lrule implementiert. lrule repräsentiert dabei eine einzelne Regel und zwar in der Form:

char _in;             // input
std::list<char> _out; // possible pattern (output)
int _propability;     // propability for that pattern

• Input
• Output
• Wahrscheinlichkeit

lsystem enthält den aktuellen Zustand und eine reihe von Regeln (lrule) die angewendet werden können. Zusätzlich auch noch einen Winkel, damit die Pflanze nicht kerzengerade wächst.

std::list<char> _string;   // current string
std::vector<LRule> _rules; // current replacement rule
int _angel;

Diese Regeln werden in der init() Methode der app.cpp Datei angelegt. Je nach Typ (ich habe 8 unterschiedliche Pflanzentypen definiert) sehen diese Regeln anders aus. Ein Beispiel:

case 1: lsystem.init("F", 20);
        lsystem.addRule('F', "F[-F[-F]+F][+F]F", 50);
        lsystem.addRule('F', "F[+F[+F]-F][-F]F", 50);

Das Beispiel zeigt einen Initialzustand vom System, der String besteht lediglich aus dem Ersetzungszeichen F. Weiters hat das System 2 Regeln die je eine Chance auf 50% haben. Das bedeutet mit einem Klick auf die Leertaste und dem Anstoßen der compute() Methode wird das F mit dem in der Regel definierten String ersetzt, beispielsweise „F[+F[+F]-F][-F]F“. Mit jedem weiteren Durchgang wird dann wieder jedes F mit der ausgewählten Kette an Zeichen ersetzt. Ein System kann 1 – beliebig viele unterschiedliche Regeln haben.

Zeichnen

In der render() Methode wird der definierte String gezeichnet. Das System kennt dabei folgende Zeichen:

• F
  Linie zeichnen (mit canvas.draw_line)
• +
  verzweigt mit positivem Winkel _angel
• –
  verzweigt mit negativem Winkel _angel
• [
  neue Ebene einfügen
• ]
  eine Ebene zurück

das sieht im Code wie folgt aus:

switch (rule[i])
{
    case 'F': end._x = start._x + (int)v.x;
              end._y = start._y - (int)v.y;
              canvas.draw_line((float)start._x, (float)start._y, (float)end._x, (float)end._y, color);
              break;
    case '+': v = v.rotate(v0, clan::Angle::from_degrees((float)lsystem._angel));
              break;
    case '-': v = v.rotate(v0, clan::Angle::from_degrees(-(float)lsystem._angel));
              break;
    case '[': posSave.push(end);
              vecSave.push(v);
              break;
    case ']': end = posSave.top();
              posSave.pop();
              v = vecSave.top();
              vecSave.pop();
              break;
}

Herausforderungen

Wie bei jedem Fraktal steigt mit jedem Schritt die Anzahl der Elemente die verändert werden müssen. Dieser Anstieg ist exponentiell, das heißt nach 5-6 Schritten wird das Programm sehr langsam und je nach RAM Speicher ist da auch bald eine Grenze erreicht. Dieses Problem ist bei Algorithmen allgegenwärtig. Der findige Programmierer ist nun gefragt und muss tricksen. Beispielsweise könnte man nur jene Bereiche weiter unterteilen bei denen das Ergebnis auch sichtbar ist.

Fazit

Lindemayer-Systeme sind ein schönes Beispiel wie man Natur mit simplen Regeln in einem Algorithmus darstellen kann. Es ist überraschend zu sehen, dass scheinbar zufällig wirkende Strukturen den selben Regeln folgen. Pflanzen wachsen nach einer simplen Formel und würden theoretisch alle gleich aussehen. Durch zufällige äußere Faktoren wie Lichteinfall, Nährstoffe, Wind und Wetter, und vieles mehr passt sich das Wachstum individuell an. Genau das simulieren wir mit einem kleinen Zufallsfaktor. Mehr dazu aber in weiteren Artikeln…

Ihr dürft gerne mit dem Source Code experimentieren. Wenn ihr eigene interessante Pflanzen erstellt habt könnt ihr mir diese gerne schicken, ich würde diese dann hier vorstellen.