[QUIZ#9] Zeichenbegabte Schildkröten

Quiz #9
Zeichenbegabte Schildkröten

Regeln
Die Regeln und der Ablauf der Quizrunde können in der entsprechenden Ankündigung eingesehen werden. Bitte lest sie euch aufmerksam durch, da sie alle wichtigen Informationen enthält. Lösungsansätze können und dürfen auch schon vorab untereinander ausgetauscht und diskutiert werden, allerdings nicht öffentlich im Forum. Verwendet stattdessen bitte private Nachrichten oder schaut im Chat vorbei.

Abgabe
Die Abgabe erfolgt wie immer im Abgabeforum. Abgabefrist ist voraussichtlich Sonntag, der 26. Juli 2009 um ca. 20 Uhr. Update: Verlängert bis Samstag, den 1. August 2009 um ca. 20 Uhr.

Das Problem
Ziel ist es diesmal, eine "zeichnende Schildkröte" zu implementieren. Die Aufgabe ist sehr umfangreich, deshalb habe ich sie auch in zwei Teilaufgaben aufgeteilt. Je nach Lust und Laune, Zeit und der individuellen Fähigkeiten könnt ihr entweder nur Teilaufgabe A oder beide bearbeiten (A ist Voraussetzung für B). Zu beiden Teilaufgaben gibt es auch Erweiterungen, die wie immer optional sind. Ihr habt vorbehaltlich wieder eine volle Woche Zeit zur Bearbeitung. Wenn es aber genügend Rückmeldungen gibt, dass mehr Zeit benötigt wird, wird die Abgabefrist entsprechend nach hinten verschoben.

Grafikausgabe
Dieses Problem beinhaltet die Ausgabe von einfachen Liniengrafiken. Wenn die verwendete Programmiersprache keine einfache Möglichkeit bietet, solche zu erzeugen, empfehle ich euch die Ausgabe von SVG. Ihr könnt dazu folgendes Template verwenden (Platzhalter in eckigen Klammern):
XML:
<?xml version="1.0" ?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
  "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg xmlns="http://www.w3.org/2000/svg" version="1.1"
  width="[Breite]" height="[Höhe]" stroke="black" fill="none">
  [Inhalt]
</svg>
Als [Inhalt] könnt ihr z.B. Strecken oder Streckenzüge verwenden:
XML:
<line x1="[Startpunkt x]" y1="[Startpunkt y]" x2="[Endpunkt x]" y2="[Endpunkt y]" />
XML:
<polyline points="[Punkt 1 x] [Punkt 1 y], [Punkt 2 x] [Punkt 2 y], [usw.], [Punkt n x] [Punkt n y]" />
Achtung: die Koordinatenangaben in SVG beziehen sich auf ein Koordinatensystem, in dem die y-Achse nach unten zeigt. In den Beispielen verwende ich allerdings das aus der Schule bekannte karthesische Koordinatensystem (y-Achse nach oben). Um zwischen den beiden Systemen umzuwandeln, könnt ihr die Anweisung y = Höhe - y verwenden.


Teilaufgabe A
Eine Schildkröte kennt ihre aktuelle Position in der Zeichenebene und ihre Blickrichtung (Winkel gegenüber der x-Achse). Sie kennt außerdem eine Liste von Aktionen, die sie einmalig nacheinander ausführt. In der einfachsten Form unterstützt die Schildkröte drei Aktionen:
  • +: Linksdrehung (gegen den Uhrzeigersinn)
  • -: Rechtsdrehung (im Uhrzeigersinn)
  • F: Vorwärtsbewegung in Blickrichtung (Forward)
Die Winkeländerung bei einer Drehaktion ist ein benutzerdefinierter Wert, ebenso die zurückgelegte Strecke bei einer Bewegung.

Das zu schreibende Programm soll den Weg, den die Schildkröte durchläuft, grafisch darstellen.

Eingabeformat A
Code:
Breite Höhe
x-Position y-Position
Schrittweite
Drehwinkel
Liste der Aktionen

Beispiel
Code:
130 110
15 10
100
120
F+F+F
Erklärung: Die Schildkröte startet an Position (15, 10) und blickt zunächst in Richtung der x-Achse. Sie läuft 100 Schritte vorwärts (F), dreht sich dann um 120 Grad nach links (+), läuft wieder 100 Schritte vorwärts, dreht sich weitere 120 Grad nach links und läuft abschließend nochmal 100 Schritte vorwärts. Der resultierende Weg ist ein Dreieck. Er wird in ein Bild mit Breite 130 und Höhe 110 eingezeichnet:
dreieck.png

Erweiterung
Die Schildkröte soll nun ein Gedächtnis erhalten. Sie kann sich ihre aktuelle Position merken und später wieder dorthin zurückkehren. Dazu kennt sie zusätzlich diese Aktionen:
  • [: Merken der aktuellen Position und Blickrichtung
  • ]: Zurücklaufen zur gemerkten Position und Drehung in gemerkte Blickrichtung
Der Pfad, den die Schildkröte beim Zurücklaufen zurücklegt, soll im Ausgabebild nicht eingezeichnet werden. Das Verhalten von verschachtelten [ und ] soll dem von push und pop bei einem LIFO-Stack (Stapel, Keller) entsprechen.


Teilaufgabe B
Jetzt soll die Schildkröte dazu gebracht werden, dass sie selbstähnliche Gebilde (Fraktale) zeichnet. Dazu erhält das Programm eine Startliste von Aktionen, zusätzlich eine Ersetzungsliste und eine Iterationsanzahl n. Die Ersetzungliste ist wieder eine Liste von Aktionen. Dadurch ergibt sich das...

Eingabeformat B
Code:
Breite Höhe
x-Position y-Position
Schrittweite
Drehwinkel
Startliste
Iterationsanzahl
Ersetzungsliste

Beispiel
Code:
260 300
10 80
1
60
F++F++F
5
F-F++F-F
Die Startliste ist F++F++F und die Ersetzungsliste lautet F-F++F-F. Für n = 0 soll die Schildkröte einfach nur die Startliste ablaufen. Ist n = 1, so wird zuerst jedes F in der Startliste durch die Ersetzungsliste ersetzt und dann die resultierende Liste abgelaufen:

Anders formuliert: die Schildkröte läuft die Startliste ab, führt aber bei jedem F die Ersetzungsliste aus, anstatt vorwärts zu laufen. Bei n = 2 werden zwei "Ersetzungsrunden" durchgeführt. Die sich ergebende Liste wäre also
Code:
F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F
Für höhere n lässt sich dieses Verfahren beliebig fortführen. Die Liste der Aktionen wächst dabei allerdings exponentiell, man sollte n also nicht zu groß wählen (einstelliger oder sehr kleiner zweistelliger Bereich).

Für n = 5 ergibt sich dieses Bild (die Kochsche Schneeflocke):
koch.png

Erweiterung I
Um noch komplexere Fraktale zeichnen zu können, soll anstatt der Ersetzungsliste eine Reihe von Ersetzungsregeln angegeben werden können. Eine Ersetzungsregel hat zwei Bestandteile: das zu ersetzende Symbol (beliebiger lateinischer Großbuchstabe) und die Ersetzungsliste (Liste von Aktionen + Symbolen).

Beispiel
Code:
X XF+F
F FF
sind zwei Ersetzungsregeln. Das zu ersetzende Symbol in der ersten Regel ist X, die Ersetzungsliste XF+F. Die zweite Regel beschreibt die Ersetzung von F durch FF.

Jedes Symbol darf in höchstens einer Ersetzungsregel als zu ersetzendes Symbol auftauchen. In jeder Iteration sollen jetzt sämtliche Ersetzungsregeln angewandt werden. Achtung: das soll für alle Regeln simultan (!) geschehen!

Beispiel

Es sollen die Ersetzungsregeln aus dem letzten Beispiel auf die Aktionsliste
Code:
XF
angewendet werden. Das Ergebnis nach einer Iteration ist
Code:
XF+FFF
und nicht
Code:
XFF+FFFF

Wenn die Schildkröte eine Aktionsliste abläuft, in der auch andere Symbole als F auftauchen, dann werden diese einfach ignoriert.

Eingabeformat B I
Code:
Breite Höhe
x-Position y-Position
Schrittweite
Drehwinkel
Startliste
Interationsanzahl
Ersetzungsregel 1
...
Ersetzungsregel k

Beispiel
Code:
340 340
10 10
5
90
X
6
X +YF-XFX-FY+
Y -XF+YFY+FX-
erzeugt die Hilbert-Kurve:
hilbert.png

Erweiterung II
Die Beschränkung, dass jedes Symbol nur in einer Ersetzungregel auftauchen darf, fällt weg. Stattdessen wird jeder Ersetzungsregel eine Wahrscheinlichkeit zugeordnet, dass diese gewählt wird. Für jedes Vorkommen eines zu ersetzenden Symbols wird also anhand der angegebenen Wahrscheinlichkeiten eine Regel ausgewählt, die für dieses Vorkommen angewandt wird. In der Eingabe könnte die Wahrscheinlichkeit einfach zwischen Symbol und Ersetzungsliste notiert werden.

Erweiterung III
Wer immer noch nicht genug hat, kann vielleicht mit den folgenden Stichworten was anfangen: kontextsensitive Ersetzungsregeln, anpassbare Farbgebung, GUI zur interaktiven Einstellung der Parameter, Erweiterung auf 3D, ...


Zusätzliche Beispiele/Tests
Im Eingabeformat A:
Code:
460 100
30 10
20
90
+FF+F--F+FF--FF+F--F+FF+FF+FF--FF+FF+FF--FF+FF+FF+F--F+FF--FF+F--F+FF+FFFF+FF+FF+FF+FFF+FF-F--F+FF+FF+FF--FF+FFF+FF-F++FFF+FF+FFFF+FFFF++FFFF+FFF+F+FF-F-FF
Ergebnis:
tutorials.png

Im Eingabeformat A, mit Erweiterung:
Code:
460 100
30 10
20
90
[+FF[FF][+F][-F]]FF[+FF]FF[+FF]FF[+FF[FF][+F][-F]]FFFF[+FF+FF+FF]F[+FF-F]FF[+FF]FFF[+FF[-F]+FF+FF]FF[+FFFF]FFF+F+FF-F-FF
Ergebnis:
tutorials2.png

Im Eingabeformat B:
Code:
400 600
130 10
5
22.5
++++F
5
FF-[-F+F+F]+[+F-F-F]
Ergebnis:
tree.jpg

Im Eingabeformat B I:
Code:
290 430
190 10
5
22.5
++++X
5
X F-[[X]+X]+F[+FX]-X
F FF
Ergebnis:
tree2.png

Im Eingabeformat B I:
Code:
490 340
380 120
5
90
FX
12
X X+YF+
Y -FX-Y
Ergebnis:
dragon.png

Im Eingabeformat B II (Je höher die Zahl desto wahrscheinlicher wird die Regel auswählt. Hier haben alle eine Wahrscheinlichkeit von 1:4, also 25%):
Code:
300 500
150 10
3
30
+++F
6
F 1 F[+F]F[-F]F
F 1 F[+F]F
F 1 F[-F]F
F 1 FF
Mögliche Ergebnisse:
nondet1.png nondet2.png nondet3.png nondet4.png nondet5.png

Wenn du weitere Beispiele hast, dann nur her damit.

Im Anhang nochmals sämtliche Beispiele in den jeweiligen Eingabeformaten, inkl. Logdateien und SVG-Ausgabe.
 

Anhänge

  • ersetzung.png
    ersetzung.png
    4,9 KB · Aufrufe: 1.775
  • ersetzung2.png
    ersetzung2.png
    2,2 KB · Aufrufe: 1.960
  • turtle.zip
    344,9 KB · Aufrufe: 59
Zuletzt bearbeitet von einem Moderator:

OnlyFoo

Erfahrenes Mitglied
Ich hab so viel zu tun... Für die Uni lernen, schreib ne Klausur morgen, etc... Und was macht ihr? Stellt ne neue Quiz-Aufgabe, damn!

Trotzdem, schöne Aufgabe, hab in den letzten 30min mal eine funktionsfähige Version in den Editor gehackt, werd das noch etwas ausschmücken und säubern, dann bin ich fertig und kann Lernen *gähn*
 

OnlyFoo

Erfahrenes Mitglied
Ich habe noch eine Version in bash geschrieben... Sie ist verflucht langsam, und da es Bash an Fließkommazahlen mangelt, auch relativ ungenau. Aber sie läuft! =)

Edit: Version in C fertig, nu hör ich auf.
 
Zuletzt bearbeitet:
Hallo zusammen,

vielleicht für's Debugging ganz interessant sind die angehängten Logdateien. Sie geben für die letzten beiden Beispiele/Tests (tree.log und tree2.log) die Zwischenlisten in den einzelnen Iterationen an.

Grüße, Matthias

edit: Jetzt sind auch die Logs für die Hilbert- und Kochkurven dabei.
 

Anhänge

  • logs.zip
    3,4 KB · Aufrufe: 45
Zuletzt bearbeitet:

Spyke

Premium-User
e hab nen Hänger, weiß nicht wie ich auf die 2te Linie kommen kann (Teil A).
Kann ev. jemand kurz Hilfestellung geben?
 

zeja

Erfahrenes Mitglied
Wie gut dass die Spoiler-Messages in diesem Forum nicht so gut funktionieren....

Drehe dein Bild im angegebenen Winkel um den aktuellen Punkt.