Die Turtle-Grafik (engl. turtle, zu Deutsch Schildkröte) ist eine Idee von Seynour Papert, der damit ein Lehrmodell für den Unterricht schaffen wollte. Populär wurde der Turtle sicherlich durch die „Kindersprache“ LOGO. Aber auch anderswo wurde mit dem Turtle viel gearbeitet. Und so erhielt er viele Namen. Eingeführt in der Oberstufe durch einen Roboter (Robi oder so) bzw. den Hamster Nikki.
Das Turtle-Grundprogramm
Um den (das?) Turtle zu steuern, brauchen wir lediglich ein paar Unterprogramme:
- void turnright(int winkel)
- void turnleft(int winkel)
- void forwd(float step)
- void back(float step)
Die Implementierung dieser grundlegenden Befehle ist sehr einfach. Wir werden dazu den Winkel und die Position als lokale Variablen einführen und darauf zurückgreifen. Die Unterprogramme werden die Variablen angle, x, y‚ oldx, oldY nutzen:
import java.awt.AWTEvent;
import java.awt.Frame;
import java.awt.Graphics;
import java.awt.event.WindowEvent;
@SuppressWarnings( "serial" )
public class Turtle extends Frame
{
private double angle = 0, x = 300, y = 300, oldX = 300, oldY = 300;
private Graphics graphics;
// Initialisiert Turtle-Grafik und bringt Frame auf den Schirm
public Turtle()
{
setTitle( "Turtle-Grafi" );
setSize( 600, 600 );
enableEvents( AWTEvent.WINDOW_EVENT_MASK );
setVisible( true );
}
public void setGraphics( Graphics graphics )
{
this.graphics = graphics;
}
// Methoden, die den Stift bewegen
public void turnright( double degree )
{
if ( (angle += degree) > 360 )
angle %= 360;
}
public void turnleft( double degree )
{
if ( (angle -= degree) < 0 )
angle %= 360;
}
public void forwd( double step )
{
back( -step );
}
public void back( double step )
{
oldX = x;
oldY = y;
x -= step * Math.sin( Math.toRadians( angle ) );
y += step * Math.cos( Math.toRadians( angle ) );
graphics.drawLine( (int) x, (int) y, (int) oldX, (int) oldY );
}
// Events vom Schließen des Fensters abfangen
@Override
protected void processWindowEvent( WindowEvent e )
{
if ( e.getID() == WindowEvent.WINDOW_CLOSING )
System.exit( 0 );
super.processWindowEvent( e );
}
}
Mit dieser kleinen Basisklasse ist schon eine Menge machbar, wie es uns der folgende Abschnitt uns zeigen wird.
Dreiecke und Kurven
Zum Einstieg in die Turtle-Grafik eignen sich rekursive Grundstrukturen. Dazu bieten sich Dreiecke und Kurven besonders an.
Dreiecke
Das erste darzustellende Objekt wird ein Dreieck sein. Im Dreieck werden weitere Dreiecke erscheinen, was durch Rekursion ein leicht lösbares Problem ist. Die Dreiecke bestehen dabei aus wiederum drei Dreiecken mit der halben Seitenlänge, die in den Spitzen sitzen. Schauen wir uns einmal das Listing an:
import java.awt.Graphics;
final class Dreiecke extends Turtle
{
public static void main( String args[] )
{
new Dreiecke();
}
void tri( float len, int deep )
{
if ( deep != 0 ) {
for ( int i = 1; i < 4; i++ ) {
forwd( len );
turnright( 120 ); // (a)
tri( len / 2, deep - 1 ); // (b)
}
}
}
public void paint( Graphics g )
{
setGraphics( g );
tri( 100, 2 );
}
}
Werden die die Zeilen (a) und (b) vertauscht, so erscheinen die kleineren Dreiecke in die größeren geklappt.
Mit
tri(len/2, deep-1); back(len); turnright(120);
in der for-Schleife erhalten wir einen weiteren Effekt, nach dem Zeichnen einer Seite wird der Turtle rückwärts gesetzt. Somit ist nicht das innere des Dreieckes gefüllt, sondern die Seiten wandern nach außen.
Peano-Kurve
Bisher wurden von uns nur gleichseitige Dreiecke untersucht. Die Peano-Kurve ist ebenfalls aus einem Dreieck zusammengesetzt, jedoch ist hier die Grundfigur gleichseitig und rechtwinklig. In einem Dreieck passen zwei weitere. Auffallend ist, dass sich Peano-Kurven immer schneiden, andere Kurven machen dies — wie wir sehen werden — nicht immer. Die Peano-Kurve ist das beste Beispiel einer flächendeckenden Kurve.
import java.awt.*;
final class PeanoKurve extends Turtle
{
final static double SQRT2 = Math.sqrt( 2 );
public static void main( String args[] )
{
new PeanoKurve();
}
void peano( double len, int deep )
{
if ( deep != 0 ) {
forwd( len );
turnleft( 135 );
peano( len / SQRT2, deep - 1 );
forwd( len / SQRT2 );
turnleft( 90 );
peano( len / SQRT2, deep - 1 );
forwd( len / SQRT2 );
turnleft( 135 );
}
}
public void paint( Graphics g )
{
setGraphics( g );
peano( 200, 5 );
}
}
Koch-Kurve
Das Idee einer Koch-Kurve ist einfach: Ersetzte jede gezeichnete Strecke durch eine Grundfigur. Diese Grundfigur setzt sich aus einer kleineren Grundfigur zusammen, usw. Im Gegensatz zu den anderen Programmen, wird nicht auf jeder Schachtlungstiefe gezeichnet, sondern nur auf der Untersten. Das bedeutet, nur die kleinen Strukturen kommen auf den Schirm. Zur Verdeutlichung das folgende Programm:
import java.awt.*;
final class KochKurve extends Turtle
{
public static void main( String args[] )
{
new KochKurve();
}
void koch( double len, int deep )
{
if ( deep != 0 ) {
koch( len / 3, deep - 1 );
turnleft( 60 );
koch( len / 3, deep - 1 );
turnright( 120 );
koch( len / 3, deep - 1 );
turnleft( 60 );
koch( len / 3, deep - 1 );
}
else // deep == 0
forwd( len );
}
public void paint( Graphics g )
{
setGraphics( g );
koch( 200, 3 );
}
}
Die immer gern gesehene Schneeflocke erhalten wir durch zusammenfügen der drei Seiten, die durch die Funktion koch() einzeln gezeichnet wurden. Die paint(…)–Methode erweitern wir durch eine kleine Schleife.
public void paint( Graphics g )
{
setGraphics(g);
for (int i=0; i < 3; i++) {
koch(100, 2);
turnright(120);
}
}
Hilbert-Kurven
Mit der Hilbert-Kurve wollen wir das Kapitel der Kurven beenden. Das Grundprinzip wurde deutlich und die wichtigsten Namen genannt — Koch, Peano und Hilbert. In der Hilbert—Kurve wird nun in den Ecken die Funktion wieder rekursiv aufgerufen, gezeichnet wird in jeder Schachtelungstiefe. Hier gilt es sich zu merken: Die Kurve hat weder Berührungspunkte noch Schnittpunkte.
import java.awt.*;
final class HilbertKurve extends Turtle
{
public static void main( String args[] )
{
new HilbertKurve();
}
void hilbert( double len, int deep, int direction )
{
if ( deep > 0 ) {
turnleft( direction * 90 );
hilbert( len, deep - 1, -direction );
forwd( len );
turnright( direction * 90 );
hilbert( len, deep - 1, direction );
forwd( len );
hilbert( len, deep - 1, direction );
turnright( direction * 90 );
forwd( len );
hilbert( len, deep - 1, -direction );
turnleft( direction * 90 );
}
}
public void paint( Graphics g )
{
setGraphics( g );
hilbert( 50, 4, 1 );
}
}
Ist die Variable direction gerade, so beginnt die Hilbert-Kurve mit einer Links-‚ andernfalls mit einer Rechtsdrehung. Das Programm enthält noch einen Fehler, welchen?
Die ersten Bäume
In diesem Abschnitt wollen wir uns mit Bäumen beschäftigen. Sie sind ein ebenso wie die Kurven ein gutes Beispiel der Turtle-Grafik.
Ein simpler Baum
Beginnen wir mit einem einfachen Baum, wo noch nicht Viel nötig ist. Hier sind einfach ein paar Turtle-Befehle hintereinander gereiht worden.
public void tree( float len )
{
turnleft( 45 );
forwd( len );
back( len );
turnright( 90 );
forwd( len );
back( len );
turnleft( 45 );
}
Rekursion bringt’s
Nun kann es mit der Baumgenerierung so richtig losgehen. Ein Baum ist ein einfaches Geflecht aus Ästen. Das Gute daran: jeder Ast hat weitere Äste. Das hört sich natürlich schon nach Rekursion an. Wir deklarieren ein Unterprogramm tree()‚ dass eine V-förmige Grundstruktur zeichnet. Beim Zeichnen jedes weiteren Astes wird wieder tree() aufgerufen, bis die Länge eines Astes auf unter 10 schrumpft.
import java.awt.*;
final class Tree extends Turtle
{
public static void main( String args[] )
{
new Tree();
}
void tree( double len )
{
if ( len > 10 ) {
turnleft( 45 );
forwd( len );
tree( len / 2 );
back( len );
turnright( 90 );
forwd( len );
tree( len / 2 );
back( len );
turnleft( 45 );
}
}
public void paint( Graphics g )
{
setGraphics( g );
tree( 150 );
}
}
Anstatt mit einer Zweiglänge abzubrechen, kann auch nach Erreichen einer bestimmten Schachtelungstiefe — also die Anzahl rekursiver Aufrufe — abgebrochen werden. Dies wollen wir jetzt einmal versuchen. Zu der Länge eines Astes soll die Schachtelungstiefe und der Zeichenwinkel hinzukommen.
Um etwas Spannung in den Algorithmus zu bekommen, lassen wir den Winkel immer etwas größer werden. Das Ganze sieht dann so aus:
void tree2( float len, int deep, int angle )
{
if ( deep != 0 ) {
turnleft( angle );
forwd( len );
tree2( len / 2, deep - 1, angle + 3 );
back( len );
turnright( 2 * angle );
forwd( len );
tree2( len / 2, deep - 1, angle + 3 );
back( len );
turnleft( angle );
}
}
Und wir erhalten mit dem Unterprogramm und der Zeile tree2( 100, 6, 20 ) einen kleinen Baum — doch irgendetwas fehlt! Es ist der Stamm. Um ihn anzufügen bedarf es lediglich kleiner Änderungen.
void tree3( double len, int deep )
{
if ( deep != 0 ) {
forwd( len );
turnleft( 45 );
tree3( len / 1.5, deep - 1 );
turnright( 90 );
tree3( len / 1.5, deep - 1 );
turnleft( 45 );
back( len );
}
}
Doch auch mit Stamm wirkt der Baum zu künstlich. Um dem etwas entgegenzuwirken, wollen wir den Abknickwinkel und ein Verkürzungsverhältnis mit einbauen. Zudem soll der rechte und linke Winkel ein anderer sein. Sie sollen dem Unterprogramm übergeben werden. Hier das Ergebnis:
void tree4( double len, int deep, int angleL, int angleR, double lenL, double lenR )
{
if ( deep != 0 ) {
forwd( len );
turnleft( angleL );
tree4( len * lenL, deep - 1, angleL, angleR, lenL, lenR );
turnright( angleL + angleR );
tree4( len * lenR, deep - 1, angleL, angleR, lenL, lenR );
turnleft( angleR );
back( len );
}
}
Hier können wir viele Parameter variieren und bekommen eine Vielzahl von Bäumen. Mit tree(100, 6, 30, -5, 0.5, 0.75) generieren wir einen Baum im Wind.
Mehr Formenvielfalt
Leider lässt auch dieser Baum seine Herkunft nicht verleugnen. Die Äste sind noch zu gleichmäßig. Um dem ein Ende zu setzen, werden Zufallswerte eingesetzt, damit ein Baum öfters einmal anders aussieht. Um Zufallszahlen mit Hilfe von Funktionen der Java-Bibliothek nutzen zu können, ist das Mathe-Paket einzubinden. Die Funktion rand() wird dann Zufallszahlen zwischen Null und Eins liefern. Sie können als Multiplikatoren zu der Länge oder dem Winkel genommen werden. Die Bilder bekommen dadurch eine ganz andere Wirkung.
Eine ganz andere Möglichkeit ist das Abweichen vom V-förmigen Grundmuster. Es ist aus verschiedenen Gründen sinnvoll, von dieser Form abzuweichen, und eine asymmetrische Figur zu wählen. Die Symmetrie wird insofern gebrochen, dass nicht auf jedes V ein weites folgt, die linke Seite bleibt etwas „unterentwickelt“. Ziel ist ein harmonischeres Bild, und eine natürlichere Form.
void tree5( double len, int deep, int angle, double factor )
{
if ( deep != 0 ) {
turnleft( angle );
forwd( len );
tree5( len * factor, deep - 1, angle, factor );
back( len );
turnright( angle * 2 );
forwd( len );
turnright( angle );
forwd( len );
tree5( len * factor, deep - 1, angle, factor );
back( len );
turnleft( angle * 2 );
forwd( len );
turnleft( angle );
forwd( len );
tree5( len * factor, deep - 1, angle, factor );
back( len );
turnright( angle * 2 );
forwd( len );
tree5( len * factor, deep - 1, angle, factor );
back( len );
turnleft( angle );
back( len );
turnright( angle );
back( len );
turnleft( angle );
}
}
Ein Beispielaufruf: tree5( 50, 4, 30, 0.6 ),
L-Systeme
Bisher war die Umsetzung von Wachstumsprozessen ein aufwändiges Unterfangen. Anstatt Zwei rechts, zwei links zu diktieren, ist es wünschenswert eine Sprache zur Formulierung von Wachstumprozessen einzuführen. Immer ein Programm vor Augen zu haben welches mit Schlüsselwörtern wie forwd(), left()ist auch vom mathematischen Gesichtspunkt her nicht sinnvoll. Im Jahre 1968 führte der Biologe Aristid Lindenmayer die sogenannten L-Svsteme (Lindenmayer-Systeme) zur Beschreibung von Wachstumsprozessen ein. Dieses System entpuppt sich bei näherem Hinschauen als eine kontextfreie Grammatik (CFG). Wie bei der Grammatik so üblich besteht das L-System aus einem Tupel, bestehend aus einem Alphabet V = {a1, …, an}, Produktionsabbildungen P: V → V* wobei V* die Menge aller bildbaren Zeichenketten beschreibt. Mit einer Zeichenkette werden nun die Wachstumsprozesse beschrieben. Dazu werden Turtle-Kürzel eingeführt, die in folgender Tabelle aufgelistet sind.
Zeichen: Reaktion
F: um Schrittweite l nach vorne
f: hebe Schwanz und zeichne nicht
+: Winkel delta gegen den Uhrzeigersinn
-: Winkel delta im Uhrzeigersinn
Tabelle: Befehle des Automaten
Die Konstanten l und d sind Länge und Winkel.Die Zustände können als Tupel verwaltet werden. Die Einträge: x bzw. y ist die Koordinate, alpha der Winkel. Der Start ist mit (0,0,0) festgesetzt. Nach Rechts wird also losgelaufen. Die oben aufgelisteten Operationen angewandt, verändern das Tupel wie in der folgenden Tabelle angegeben.
Befehl: Zustand geht über in
F: (x + l * cos(alpha) , y + l * sin(alpha), alpha)
f: (x + l * cos(alpha), y + l * sin(alpha), alpha)
+: (x, y. alpha + delta)
-: (x, y. alpha – delta)
Tabelle: Änderung des Zustandes
Das L-System wird auch unter dem Namen Graftal geführt. Gelegentlich tauchen auch die Ziffern 0 und 1 auf, um keinen bzw. einen Schritt in die vorgegebene Richtung zu gehen. Eckige Klammern werden ebenso verwendet wie kennengelernt. Beispiel: 11[11]1. Gehe zwei Schritte nach vorne, zeichne dann einen Ast (die Verzweigung) von 2 Einheiten Länge, kehre zum Verzweigungspunkt zurück und ergänze den Stamm um eine Einheit. Einige bekannte Kurven sollen nun in L-System-Notation verdeutlicht werden.
Koch
Wir erinnern uns da sicherlich noch an die Koch-Kurve, bestehend aus 4 Strecken. Der Winkel der Strecken betrug immer 60 Grad, sodass wir in unserem System delta = 60° setzen können. Der Erzeugungs-String ist dann F+F–F+F. Die Abarbeitung folgt von links nach rechts, wie ein normaler mathematischer Ausdruck. Die Interpretation dieses Strings: Der Turtle geht einen Schritt der Länge l vor, dreht sich dann um 60 Grad nach links, geht wieder einen Schritt voraus, dreht sich zweimal um 60 Grad (also dann um 120 Grad) nach links, geht anschließend einen Schritt vor, um dann nach einer erneuten Drehung und Schritt voran zum Ende zu kommen. In der oben geschriebenen Schreibweise hätten wir also eine Produktionsregel, die in der Informatik die Schreibweise F → F+F–F+F bekäme.
Sierpinski-Pfeilspitze
Die gesamte Information über den Aufbau eines Objektes fasst man nun in einem Axiom zusammen. Somit wird die Beschreibung eines Objektes sehr kurz und kann in einer Tabelle leicht beschrieben werden.
Axiom: L
Produktionsregeln: L → +R-L-R+
R → -L+R+L
delta: 60°
Man sieht an diesem Beispiel, wie günstig es ist, mehrere Variablen einzuführen, um das Bild etwas übersichtlicher zu gestalten.
Achtung! Obwohl es nach einer Endlos-Verschachtelung aussieht — L ruft R auf und wieder umgekehrt — läuft das Programm trotzdem zu Ende. Es ist vielmehr dem Programmierer überlassen eine Abbruchbedingung zu implementieren. So beispielsweise das Abbrechen bei einer bestimmten Schachtlungstiefe oder Stammlänge.
Drachen-Kurve
Axiom: D
Produktionsregeln: D → -D++E
E → D–E+
delta: 60°
Bäume und Büsche
Nachdem wir das Grundsystem kennengelernt haben, dürfte es nicht schwerfallen, fraktale Gewächse zu entwickeln. Die Frage ist hier nur: Wie kann man eine Struktur, die sich verzweigt in einer Zeichenkette darstellen, die das L—System letztendlich verwendet? Notwendig dazu ist die Einführung zweier Symbole: [ und ]. Gelangt der Turtle bei der Interpretation der Zeichenkette an eine eckige Klammer, so muss er die Position und die Richtung des Turtles sichern und später wieder restaurieren. Nun hier ein Beispiel für eine krautartige Pflanze:
Axiom: F
Produktionsregeln: F —> F[+F]F[—F]F
delta: 25,7°
und noch ein Kraut:
Axiom: B
Produktionsregeln: F → FB
B → F[+B]F[—B]+B
delta: 25,7°
Bisher waren die vorgestellten Systeme immer deterministisch, das heißt es gab ein absehbares Ende und eine voraussehbare Form. Wenn der Zufall in ein L-System einzieht, so nennt man dies nicht-deterministisch Systeme stochastisch. Doch wenn der Zufall einfließt ist eine Aussage über das Wachstum schwierig. Dennoch ist es wichtig zu bestimmen wie groß die Wahrscheinlichkeit sein soll, dass ein Ereignis eintritt. Wenn der Baum z.B. nach rechts driften soll, so kann man Umgangssprachlich sagen: In 2 von drei Fällen gehe nach rechts. Um dies auszudrücken erweitern wir die Schreibweise ein wenig, und fügen die Wahrscheinlichkeit mit an. Hier das Beispiel von Kraut Nr. 3. (Wahrscheinlichkeit wurde
mit R abgekürzt.)
Axiom: F
Produktionsregeln: F → F[+F]F[—F]FR 1/3
F → F[+F]FR 1/3
F → F[—F]FR 1/3
delta: 25,7°
Die Anzahl der Produktionsregeln bestimmt also immer den Nenner des Bruches.
Etwas entfernt von der Pflanzen soll abschließend das L-System einer zufälligen Koch-Kurve aufgezeigt werden:
Axiom: F
Produktionsregeln: F → F-F++F—FR 0.5
F → F+F–F+FR 0.5
delta: 60°