Lindenmayer System in MSWLogo

Lindenmayer-System in MSWLogo

Aristid Lindenmayer (* 17. November 1925 in Budapest; † 30. Oktober 1989) war ein ungarischer theoretischer Biologe. 1968 entwickelte er eine formale Sprache als Grundlage einer axiomatischen Theorie biologischer Entwicklung. In jüngerer Zeit fanden die Lindenmayer-System oder L-System genannten Systeme Anwendung in der Computergrafik bei der Erzeugung von Fraktalen und in der realitätsnahen Modellierung von Pflanzen.

Das L-System ist ein Ersetzungssystem. Ausgehend vom Startsymbol, dem Axiom, wird jedes Zeichen schrittweise nach festgelegten Regeln durch eine bestimmte Zeichenfolge ersetzt, die auch aus demselben Zeichen bestehen kann. In jedem Iterationsschritt werden alle vorhandenen Regeln gleichzeitig auf die schon vorhandene Zeichenkette angewendet.

Lindenmayer-Systeme stellen eine ausgesprochen effiziente Komprimierung von Pflanzen-Modellen dar. Durch den inhärenten Nichtdeterminismus limitierter Lindenmayer-Systeme lassen sich fast beliebig viele verschiedene – jedoch einander ähnelnde – Pflanzen-Modelle aus einem System ableiten. Zudem erfordert die Berechnung eines statisch implementierten Systems vergleichsweise wenig Aufwand. Es liegt also eine Anwendung nahe, in der große Pflanzenbestände generiert werden müssen. Zum Beispiel bei der Simulation eines Waldes in Computerspielen oder in Applikationen zur Landschaftsplanung limitierte Lindenmayer-System zum Einsatz kommen, bei denen die Bäume in Echtzeit nur für den gerade sichtbaren Ausschnitt berechnet werden.

Aus einer Studienarbeit von Frank Böhmer (TU Braunschweig, 2002 Seite 10)

Aristid Lindenmayer

1. Es sei V ein Alphabet (a₁, a₂, a₃, ... a_n), V* die Menge aller möglichen Wörter aus V und V⁺ die Menge aller möglichen Wörter aus V ohne {∅}.
2. Ein 0L-System ist das geordnete Tripel [V,ω,P],in dem V das Alphabet ω ∈ V⁺ ein nichtleeres Wort genannt Axiom und P ⊂ VxV⁺ eine endliche Menge an Produktionsregeln ist. Eine Produktionsregel (a,ϰ) ∈ P wird als a → ϰ geschrieben. Der Buchstabe a und das Wort ϰ werden Vorgänger und Nachfolger genannt (amerikan. predecessor und successor).
3. Für jeden Buchstaben a existiert mindestens ein Wort ϰ ∈ V*, so dass a → ϰ. Ist kein spezielles Wort ϰ für einen bestimmten Vorgänger a ∈ V gegeben, so wird a → ϰ der Menge aller P hinzugefügt.

Ein Lindenmayer-System besteht demnach aus drei Arten von Regeln:
1. einer Startregel,
2. einer endlichen Menge von Hauptersetzungsregeln und
3. einer Abbruchregel.
Zur Erzeugung einer Zeichenfolge wird mit der Startregel begonnen, dann werden n-mal die Hauptersetzungsregeln angewendet. Zum Schluss tritt die Abbruchregel in Aktion. Die Zahl n heißt Ordnung der erzeugten Zeichenfolge.

Beispiel - die Bakterie Anabaena Catenula

Lindenmayer betrachtet in seiner Veröffentlichung als Beispiel zum L-System des Wachstum der Bakterie Anabaena Catenula
Für das Wachstum sind Elemente aus zwei verschiedenen Bakterientypen verantwortlich, die sich durch ihre Größe sowie durch ihr Teilungsverhalten unterscheiden. Wir nennen sie A und B. Da beide Typen asymmetrisch aufgebaut sind, können sie in der Kette entweder nach links oder nach rechts orientiert sein. Es gibt daher vier unterschiedliche Elemente.

Das Alphabet V des L-Systems beschränkt sich auf vier Zeichen:
V = {A_links, A_rechts, B_links, B_rechts}

Die Produktionsregeln:
Eine nach rechts orientierte A-Bakterie teilt sich nach einer gewissen Zeit in eine nach rechts orientierte B-Bakterie und in eine nach links orientierte A-Bakterie und sowie auch spiegelverkehrt. Es ergibt sich folgende Produktionsregel:
p₁: A_rechts -> A_linksB_rechts
p₂: A_links -> B_linksA_rechts
p₃: B_rechts -> A_rechts
p₄: B_links -> A_links

Vom Axiom ausgehend und die Produktionsregeln anwendend erhält man eine Sequenz von Zeichenketten, die die verschiedenen Wachstumsstadien von Anabanea Catenula entsprechen.

Vergleich: L-System mit der Fibonacci-Folge

Das Wachstum dieser Bakterie hat eine Entsprechung mit der sog. Fibonacci-Folge. Zählt man nämlich die pro Generation entstehenden Bakterien zusammen, so sieht man, dass diese Zahlen die Folgeglieder der Fibonacci-Folge darstellen.

Leonardo da Pisa,
auch Fibonacci genannt (* um 1170 in Pisa; † nach 1240 ebenda), war Rechenmeister in Pisa und gilt als einer der bedeutendsten Mathematiker des Mittelalters.
Auf seinen Reisen nach Afrika, Byzanz und Syrien machte er sich mit der arabischen Mathematik vertraut und verfasste mit den dabei gewonnenen Erkenntnissen das Rechenbuch Liber ab(b)aci im Jahre 1202 (Überarbeitung 1228). Bekannt ist daraus heute vor allem die nach ihm benannte Fibonacci-Folge, die im Zusammenhang mit dem Goldenen Schnitt steht.

Quelle: Wikipedia

Die Fibonacci-Folge
1. Jedes Paar Kaninchen wirft pro Monat ein weiteres Paar Kaninchen.
2. Ein neugeborenes Paar bekommt erst im zweiten Lebensmonat Nachwuchs (die Austragungszeit reicht von einem Monat in den nächsten).
3. Die Tiere befinden sich in einem abgeschlossenen Raum („in quodam loco, qui erat undique pariete circundatus“), so dass kein Tier die Population verlassen und keines von außen hinzukommen kann.

Mathematische Beschreibung
Die beiden ersten Glieder der Zahlenfolge sind jeweils 1. Das folgende Glied berechnet sich aus der Summe der beiden vorhergehenden.
Also: f_n = f_n-1 + f_n-2
1 – 1 – 2 – 3 – 5 – 8 – 13 – 21 – 34 – 55 - 89 usw.

Programm-Code 1

to fibonacci :tiefe
cs
make "initiator "A
make "generatorA "B
make "generatorB "AB
make "fibonaccisequenz :initiator
repeat :tiefe[make "beginnsequenz " sequenz :fibonaccisequenz
print :fibonaccisequenz print :tiefe
print count :fibonaccisequenz wait 40]
end

Programm-Code 2

to sequenz :zeichenkette
ifelse :zeichenkette=" [make "fibonaccisequenz :beginnsequenz stop][make "befehl (first :zeichenkette)
ifelse (:befehl="A) [make "beginnsequenz word :beginnsequenz :generatorA][]
ifelse (:befehl="B) [make "beginnsequenz word :beginnsequenz :generatorB][]
sequenz butfirst :zeichenkette]
end

Programm-Code 3

to main
cs
setpencolor [255 53 40]
setpensize[5 5]
fibonacci 6
end

Der Aufruf erfolgt durch main.
Mit diesem Programm werden die Ergebnisse mit Hilfe von print im Command-Feld ausgegeben.

Bildschirmausgabe
Soll die Ausgabe auf dem Grafikbildschirm mit Hilfe von label erfolgen, so muss mit setpos ein wenig mehr Aufwand betrieben werden.
Geändert werden muss dann die Prozedur tiefe, die beiden anderen Programme bleiben erhalten.
Der Aufruf im main-Programm muss jetzt fibonaccilabel 6 lauten.

Programm-Code 1A

to fibonaccilabel :tiefe
cs
make "initiator "A
make "generatorA "B
make "generatorB “BA
make "xkoord -300
make "ykoord 300
setlabelfont[[Arial]35 0 0 600 0 0 0 0 3 2 1 18]
rt 90 penup
setpos (list :xkoord :ykoord) pendown
label "Anzahl make "fibonaccisequenz :initiator
penup make "xkoord :xkoord+120
setpos (list :xkoord :ykoord) pendown
label "Fibonaccisequenz
make "fibonaccisequenz :initiator

Programm-Code 1B

... penup
make "xkoord -300
make "ykoord 250
setpencolor[30 30 200]
repeat :tiefe[make "beginnsequenz " sequenz :fibonaccisequenz
penup setpos (list :xkoord :ykoord) pendown
label count :fibonaccisequenz
make "xkoord :xkoord+120 penup
setpos (list :xkoord :ykoord) pendown
label :fibonaccisequenz print :tiefe
make "xkoord -300
make "ykoord :ykoord-50]
end

L-System zur Darstellung von Fraktalen
Die grafischen L-Systeme werden dadurch gewonnen, dass den Buchstaben Schildkröteninterpretationen gegeben werden.
V – Vorwärts, gehe einen Schritt nach vorn und zeichne dabei eine Linie
P – Drehe dich um einen gegebenen Winkel nach links (lt → - )
M – Drehe dich um einen gegebenen Winkel nach rechts (rt → +)

Die 5 Programme in den rot unterlegten Feldern stellen die Implementierung des Lindenmayer-Systems dar. Die entsprechenden Programme wie z.B. kochkurve rufen polygon1 mit den entsprechenden Werten für die Variablen initiator, generator, winkel, seite, tiefe und restinitiator auf.

to polygon1
ifelse (:restinitiator = ") [stop][ make "befehl (first :restinitiator)
make "restinitiator butfirst :restinitiator
ifelse (:befehl = "M) [M][]
ifelse (:befehl = "P) [P][]
ifelse (:befehl = "V) [umweg :generator :tiefe][]
polygon1]
end

to umweg :nochgenerator :tiefe
ifelse (:nochgenerator=")[stop][make "befehl first :nochgenerator
make "nochgenerator butfirst :nochgenerator
ifelse(:befehl = "M) [M][]
ifelse(:befehl = "P) [P][]
ifelse(and :befehl = "V :tiefe=0) [V stop][]
ifelse(and :befehl = "V :tiefe>0) [umweg :generator (:tiefe-1)][]
umweg :nochgenerator :tiefe]
end

to V
fd :seite
end

to P
lt :winkel
end

to M
rt :winkel
end

Die Koch-Kurve mit Hilfe des Lindenmayer-Systems
Die Koch-Kurve erhält man, indem man, ausgehend von einer Strecke, das mittlere Drittel dieser Strecke entfernt und es durch zwei Schenkel eines gleichseitigen Dreiecks ersetzt. Mit den entstehenden Teilstrecken wird dieser Vorgang beliebig oft wiederholt.

to kochkurve
cs
make "initiator "V
make "generator "VPVMMVPV
make "winkel 60
make "seite 30
make "tiefe 3
make "restinitiator :initiator
penup setpos[-400 0]
rt 90 pendown
setpensize[5 5] setpencolor[50 50 220]
polygon1
end

Der Aufruf geschieht mit kochkurve. Die Rekursionstiefe kann durch die Zuweisung make "tiefe 3 verändert werden.

to kochinsel
cs
make "initiator "VMVMVMV
make "generator "VMVPVPVVMVMVPV
make "winkel 90
make "seite 20
make "tiefe 2
make "restinitiator :initiator
penup setpos[-50 200]
rt 90 pendown
setpensize[5 5] setpencolor[255 204 0]
polygon1
end

Der Aufruf geschieht mit kochinsel. Die Rekursionstiefe kann durch die Zuweisung make "tiefe 2 verändert werden.

Die Kochinsel

Die Levy- oder Muschelkurve ist ein Fraktal, dessen Bedingungen als Erstes von Ernesto Cesaro im Jahr 1906 und Georg Faber 1910 beschrieben wurde, aber jetzt den Namen des französischen Mathematikers Paul Levy trägt. Dieser konnte neben den mathematischen Bedingungen auch die geometrische Konstruktion angegeben.

Konstruktion
1. Zeichne eine Linie a zwischen 2 gegebenen Punkten A und B.
2.a sei die Hypotenuse eines gleichschenkligen rechtwinkligen Dreiecks und bilde die Katheten a_L und a_R.
3.Fahre rekursiv mit a_L und a_R fort.

to Levy_Kurve
cs
make "initiator "PVPV
make "generator "VPVM
make "winkel 90
make "seite 12
make "tiefe 10
make "restinitiator :initiator
penup setpos[100 150]
pendown setpensize[3 3]
setpencolor[250 100 100]
polygon1
end

Die Levy-Kurve

Waclaw Sierpinski
Waclaw Sierpinski (* 14. März 1882 in Warschau; † 21. Oktober 1969 in Warschau) war ein polnischer Mathematiker. Er ist bekannt für seine herausragenden Beiträge zur Mengenlehre (Untersuchungen zum Auswahlaxiom und zur (verallgemeinerten) Kontinuumshypothese), Zahlentheorie, Funktionentheorie und Topologie.
Drei wohlbekannte Fraktale, das Sierpinski-Dreieck, der Sierpinski-Teppich und die Sierpinski-Kurve, sind nach ihm benannt, genauso das Sierpinski-Problem, die Sierpinski-Zahl und die Sierpinski-Konstante in der Zahlentheorie

W. Sierpinski

Der Algorithmus 1 für das Sierpinski-Dreieck
1.Zeichne ein Dreieck (Initiator)
2.Verbinde die Mittelpunkte der Seiten, dadurch wird das ursprüngliche Dreieck in 4 deckungsgleiche Teildreiecke zerlegt.
3.Entferne das mittlere der 4 Teildreiecke – die anderen 3 Teildreiecke bleiben übrig.
4.Wende die Schritte 2 und 3 auf die 3 übrig gebliebenen Teildreiecke an.

Interessant ist beim Sierpinski-Dreieck, dass es dafür verschiedene, sehr unterschiedliche Algorithmen gibt. Die Teilung des Ursprungsdreieck ist oben angegeben.
Das Sierpinski-Dreieck entsteht auch beim sog. Fluch des Pharaos.
Im Königsdreieck (alle Seiten sind gleich lang), das sich zwischen drei Pyramiden erstreckt, befinden sich irgendwo unter dem Staub der Jahrtausende der Eingang zur Grabkammer des Pharaos Tutramses. Schon viele Schatzsucher haben sich aufgemacht, das Grab zu finden und nach den kostbaren Grabbeigaben zu schürfen. Vergeblich!
Der Fluch des Pharaos bewirkt, dass sich der Schatzsucher, sobald er sich im Königsdreieck befindet, nur geradlinig auf eine der Pyramidenspitze zu bewegen kann. Dabei schafft er jeweils genau die Hälft der Strecke bis zur nächsten Pyramide und muss eine Weile rasten, um dann von neuem irgendeine Pyramide anzusteuern. Gibt es Stellen im Königsdreieck, die ein Schatzsucher niemals erreichen kann, so dass der Eingang zur Grabkammer verborgen bleibt und der Pharao seine ewige Ruhe behalten wird? Auch hier entsteht das Sierpinski-Dreieck.
Die Regel 90 für zellulare Automaten erzeugt ebenfalls das Sierpinski-Dreieck.

Das Sierpinski-Dreieck

Der Programm-Code
to sierpinski
cs
make "initiator "VPVPVP
make "generator "VPVMVMVPV
make "winkel 120
make "seite 40
make "tiefe 4
make "restinitiator :initiator
penup
setpos[-200 -250]
rt 90
pendown
setpensize[4 4]
setpencolor[125 120 100]
polygon1
end
Der Aufruf geschieht mit sierpinski. Die Rekursionstiefe kann durch die Zuweisung make "tiefe 4 verändert werden.

Das Sierpinski-Dreieck