Zufall und Prozedurale Generierung - Bäume

News118.07.2016

News118.07.2016

ure> Vorab müssen wir aber wieder etwas klären: Wollen wir etwas erzeugen das wie ein Baum aussieht, aber keine echte Funktion hat? Oder wollen wir einen Baum so perfekt wie möglich simulieren, auf die Optik aber weniger Wert legen? Beides gleichzeitig ist nicht ganz einfach zu erreichen, wir konzentrieren uns in diesem Beitrag auf die Optik. Wenn man visuell ansprechende Bäume erzeugen möchte braucht man diese in der Regel für Computerspiele oder Kinofilme. Auch diese Bereiche stellen allerdings nicht immer die gleichen Anforderungen. So müssen die Bäume für ein Spiel wie The Witcher 3 auch noch aus nächster Nähe, und vor allem auch von unten, hervorragend aussehen, dürfen den Renderprozess aber nicht zu sehr ausbremsen. Für einen Kinofilm wie Starwars VII ist hingegen (fast) egal wie lange es dauert den Baum zu rendern: Das tut man eh nur einmal und liefert das Ergebnis dann als Video aus. Und in Strategiespielen wie Anno 2070 oder Tropico müssen Bäume zwar nicht von unten, dafür aber in großen Mengen gerendert werden. Ein typischer Ansatz um Bäume dieser Art zu erzeugen ist eine so genannte Grammatik mit Wahrscheinlichkeiten zu versehen. Den Begriff "Grammatik" kennst du sicherlich schon aus der Schule und erfreulicherweise ist für diesen Begriff Bedeutung in der Informatik recht nahe an dem, was man vermuten würde: Es geht darum ein Regelwerk für Texte zu formulieren, bei deren Anwendung quasi nebenbei ein Baum erzeugt wird. Die für Bäume im Regelfall genutzten Grammatiken nennt man Lindenmayer-System (oder abgekürzt auch L-System) und sie funktionieren ungefähr so: Man definiert sich ein System aus unterscheidbaren Anweisungen (Variablen genannt), Operationen sowie Produktionsregeln, um diese ineinander zu überführen:

Variablen : A B

Operationen : + 60°, − 60°

Start  : A

Produktionsregeln  : (A → +B−A−B+), (B → −A+B+A−)

In diesem Beispiel stehen die Anweisungen A und B für "zeichne eine Linie fester Länge mit einem variablen Winkel". Mit den Operationen + und - wird der Winkel von A und B verändert, der Startwert beträgt üblicherweise 0°. Man beginnt dann den Startwert mit den Produktionsregeln zu verändern. In diesem Beispiel können wir also das A durch die erste Produktionsregel ersetzen: Man erhält dann +B−A−B+. Und in diesem Ergebnis kann man dann sowohl A als auch B gemäß der Produktionsregeln ersetzen: +(−A+B+A−)-(+B−A−B+)-(−A+B+A−)+. Und auf dieses Ergebnis könnte man die Regeln nochmal anwenden, aber weil sich kein Mensch vorstellen kann was dabei gezeichnet werden würde lässt man das lieber einen Computer machen. Das Ergebnis für diese speziellen Regel sind die so genannten Sierpinsky Dreiecke. Und mit genau dieser Art von Regel kann man auch Bäume und Sträucher erzeugen. In diesem Fall stehen die Operationen dann für Dinge wie "Male ein Blatt", "Drehe den Stamm", "Erzeuge eine Astgabelung", ... und die entstehenden Texte lassen sich noch deutlich schlechter ohne einen Computer interpretieren. Wer sich das Titelbild ein wenig genauer anschaut kann vermutlich ein paar dieser Regeln da wieder rauslesen. Es ist dann die Aufgabe des Designers sinnvolle Regeln zu schreiben: Aus einem Blatt darf niemals ein Stamm wachsen, aus einer Astgabelung sollten zwei (oder mehr?) Äste wachsen, der Stamm sollte sich um nicht mehr als zum Beispiel 90° winden, ... Wenn man das System einmal verstanden hat kann man plötzlich eine ganze Menge von Bäumen mit zum Beispiel ngPlant oder Arbaro selber erzeugen. Diese Programme arbeiten dann im Hintergrund zwar noch mit Texten, verpacken diese aber in ein schöneres Benutzerinterface.