PPS: Vom Spiel zur Wissenschaft SS06: Labyrinth

Inhaltsverzeichnis

Spielregeln

Die schwarzen Felder sind Wände, die weissen sind Wege. Das rosa Feld zeigt die aktuelle Position an. Das Ziel ist, an den Ausgang (ein Loch in einer Wand) zu gelangen. Indem man rechts, links, oben oder unten von der aktuellen Position hinklickt, kann man einen Zug machen. Der begangene Weg wird gelb markiert. Falls man in eine Sackgasse gerät, kann man mit einem Rechtsklick ein Feld zurückspringen und das falsche Feld wird grau.

  • Jumper

  • Arrows

  • Kreuze

    Illustrationen

    Knöpfe

  • Levels
  • Solve
  • Expert
  • Simple
  • Generate
  • Höhe und Breite
  • Wkt
  • Inst Solve
  • Sleep
  • Clear

    Algorithmen

    Die Labyrinth-Erstellung

    Das ganze Labyrinth packten wir in ein autonomes Objekt, welches sich selbst zu vorgegebenen Parametern ein Labyrinth erstellt.

    Voraussetzungen für das Labyrinth waren, dass es genau einen Lösungsweg besitzen sollte (keine Schleifen möglich werden) und jeder Punkt sollte auf irgend einem Weg erreichbar sein. Dazu implementierte ich einen rekursiven Allgorithmus, welcher etwa so funktioniert:

    Als erstes wird das gesammte Labyrinth (korrekt wäre eigentlich Irrgarten) mit Wänden gefüllt. Danach frisst Sich der Allgorithmus einen Weg hinein, wobei nie eine Verbindung zu einem anderen Weg erstellt wird. Bei einer Kreuzung verzweigt sich der Allgorithmus und ruft eine zweite Instanz von sich selbst auf, welche sich autonom weiterfrisst. Wenn alle Instanzen beendet sind muss noch irgendwo ein Ausgang gemacht werden.

    Das generierte tatsächlich recht schöne, anspruchsvolle Irrgärten, jedoch gab es einige Probleme für >100x100 Felder. StackOverflow lässt grüssen. Des weiteren gab es einige kleine Löcher ohne Wege. Aus diesem Grund implementierte ich noch einen anderen itterativen Allgorithmus, speziell für grosse Labyrinthe oder zum Auffüllen eines bereits erstellten.

    (Je nachdem alles mit Wänden füllen) Nimm irgend einen zufälligen Punkt im Labyrinth. Schau ob es eine Wand ist. Schau ob irgendwo angrenzend ein Weg ist, wenn ja mach eine Verbindung.

    Das tönt vorerst blöd, besonders um beispielsweise nur noch das letzte Element eines 100x100 Felds zu finden werden nach Wahrscheinlichkeit 10'000 Versuche benötigt, bis man das Feld trifft. Der Vorteil ist, dass es keine Elemente gibt, die bei einem auch noch so grossen Labyrinth einen überlauf erfahren könnten und 10000 Operationen sind sowieso nix.^^ Desweiteren sind die charakteristischen Lösungswege langweiliger wie beim letzten, da sie linearer sind.

    Zusatzfeatures

    So weit so gut. Labyrinth-Applets gibts im Netz wie Sand am Meer, daher musste noch was Spezielles her. Dank minder interessanten Vorlesungsstunden (tja solls geben), kamen wir auf die Idee mit Jumpern und Arrows (siehe Spielanleitung). Um diese zu implementieren eigenete sich der rekursive Allgorithmus natürlich besonders gut. Die Funktionsweise blieb genau dieselbe, dafür gabs natürlich einige andere Probleme. Die Labyrinthe sollten möglichst komplex werden und sie müssen immer Lösbar bleiben. Auch wird es besonders lustig, wenn man Jumper wider zurück springt oder sie von mehreren Seiten begeht...

    Weiter wird zu jeder Position abgespeichert, wie viele Schritte mindestens nötig sind um bis zu dieser Position zu kommen (einfacher counter). Dies ermöglicht dann am Ende den kompliziertest möglichen Ausgang zu setzen.

    Die Verzweigungen, Jumper, Arrows,... werden nach vorgegebener Wahrscheinlichkeit versucht zu setzen. (Wahrscheinlichkeit 1 für Verzweigung generiert hässliche Labyrinthe und Wahrscheinlichkeit nahe bei 0 klemmt sich schnell selbst ab und ruft dann den itterativen Füllalgorithmus auf.)

    Der Lösungs-Algorithmus

    Der Lösungsalgorithmus ist rein itterativ programmiert, sodass es keine Komplikationen gibt wenn das Labyrinth gross wird. Das Prinzip ist einfach. Man startet am Startfeld und versucht immer zuerst den rechten Weg zu nehmen. Wenn es keinen rechten Weg gibt, versucht man den geradeaus und folglich wenn dieser blockiert ist den links. So läuft man bis man in eine Sackgasse gerät. Da geht man einfach zurück bis zu der STelle, an der es noch eine nicht begangene Abzweigung hat usw. Auf diese Weise kommt man auf alle Fälle ins Ziel, sofern das Labyrinth lösbar ist.

    Mit den Jumpern und Pfeilen wird es ein bisschen komplizierter, doch das Prinzip bleibt das gleiche.

    Ein normales Labyrinth (also ohne Jumper und Pfeile) könnte man noch einfacher lösen, indem man immer an der rechten Wand entlanggeht. Man macht also keinen Schritt zurück, sondern dreht sich um und läuft wieder vorwärts. Doch das funktioniert mit den Jumpern und Pfeilen nicht mehr, da diese nicht auf beide Seiten begehbar sind (Pfeile immer und Jumper unter Umständen). Daher muss man die letzten Schritte rückgängig machen und kann nicht einfach die Sackgassen doppelt begehen (also hinein- und wieder herausgehen).

    Im Programm wird das so gelöst, dass der Weg in einem Stack abgespeichert wird, wodurch es einfach wird mit dem Zurückgehen. Wenn man in einer Sackgasse ist kann man das oberste Stack-element herausnehmen, bis man wieder bei einer Verzweigung ist.

    Zudem werden der begangene Weg und die Sackgassen in einer Separaten Klasse abgespeichert, sodass man den Lösungsweg danach auch darstellen kann.

    Applet

    Das Applet befindet sich hier

    Source

    Hier ist die Source und das Java-doc (in einem .zip file)