Labyrinth-Problem
Inhaltsverzeichnis
Aufgabenstellung
Erstellt werden soll ein Programm, das aus einem beliebigen Labyrinth einen Ausgang findet, wenn es ihn gibt. Dazu benötigt man zunächst ein Labyrinth, das auch graphisch ausgegeben werden kann. Desweiteren können zusätzliche Aufgaben und Hindernisse in den Suchalgorithmus hinzugefügt werden.
Wegsuchen
Der Algorithmus des Wegsuchens funktioniert nach der Vorgehensweise des Backtracking, nach dem Versuch-und-Irrtum-Prinzip (trial and error). Dabei wird jede mögliche Kombination von Teillösungen in Form einer Rekursion ausprobiert bis eine problemlösende Gesamtlösung gefunden ist oder feststeht, dass es keine Lösung gibt, da wirklich alles getestet worden ist. Für das Labyrinthproblem ist ein Pseudocodealgorithmus von Wirth vorgegeben:
PROZEDUR Suche_Weg
Initialisiere den Auswahlvorgang
erfolgreich:= false
WIEDERHOLE
Wähle ersten/nächsten Schritt aus (hier 4 Möglichkeiten)
FALLS Schritt möglich
DANN
FALLS Schritt führt zum Ausgang
DANN
beende die Rekursion (erfolgreich)
SONST
markiere den neu betretenen Platz
Suche_Weg(von neuem Platz aus)
FALLS nicht erfolgreich
DANN
Markierung zurücknehmen
BIS erfolgreich oder keine weitere Möglichkeit mehr
So wird zunächst eine Richtung ausgewählt, in die der Wegsucher zuerst gehen soll. Die Suche wird als nicht erfolgreich definiert. Anhand der initialisierten Richtung wird der erste Schritt gewählt. Wenn ein möglicher Schritt zum Ausgang führt, ist die Suche erfolgreich und wird abgebrochen. Andernfalls geht man einen Schritt weiter und führt von dort die selbe Prozedur wieder aus (rekursiv). Die letzten drei Schritte werden solange wiederholt, bis man den Ausgang gefunden hat (erfolgreich), oder alle Richtungen abgetestet wurden (keine weitere Möglichkeit mehr).
Richtungswahl
Bei der Initialisierung des Auswahlvorgangs, also der Wahl der Richtung, in die er zuerst gehen soll, gibt es zwei Varianten. Man kann zum einen systematisch vorgehen, also an jeder Kreuzung immer zuerst in die gleiche Richtung gehen und dann im Uhrzeigersinn die anderen Richtungen abtesten. Das würde dem Wegsuchen in einem Labyrinth mit Kompass entsprechen, wobei man z.B. immer erst nach Süden oder nach Norden geht. Daher gibt es bei dieser Variante auch vier Möglichkeiten (zuerst hoch, nach rechts, runter oder nach links). Je nachdem wo das Ziel liegt und wie das Labyrinth beschaffen ist, kann die eine Richtung günstiger sein als die andere, sowohl hinsichtilich der Lösungsweglänge, als auch der Suchzeit.
Hoch
nach rechts
runter
nach links
In dem Beispiel ist "nach links" die Richtung, die einen kurzen Lösungsweg bringt und nur wenig vom Labyrinth dafür absuchen muss. "Hoch" liefert den selben Weg, hat vorher jedoch das gesamte Labyrinth abgesucht. "Nach rechts" sucht zwar nicht alles ab, findet aber einen längeren Lösungsweg.
Die zweite Variante der Richtungswahl ist, dass an jeder Kreuzung die erste Richtung zufällig gewählt und dann nacheinander dem Uhrzeigersinn nach abgetestet wird. Dabei ist nicht vorauszusagen, ob ein günstiger oder ungünstiger Weg entsteht.
In der Pseudocodezeile "Wähle ersten/nächsten Schritt aus" wird von der vorherigen Richtung eine weitergegangen.
Möglicher Schritt
Um zu testen, ob ein Schritt von der aktuellen Position aus in eine bestimmte Richtung möglich ist, ist es sinnvoll eine GibSchritt-Abfrage zu schreiben, die zurückgibt, was sich an der nächsten Position im Falle eines Schrittes befinden würde. In einer zweiten GibMöglich-Abfrage wird festgestellt, ob der Schritt möglich ist, indem der Wert mit den zum Begehen freigegebenen Werten abgeglichen wird.
Ob ein Schritt erfolgreich zum Ziel führt kann mit der oben beschriebenen GibSchritt-Abfrage ermittelt werden.
Rekursiver Aufruf
Da der rekursive Aufruf von der neuen Position aus erfolgen soll, ist es am sinnvollsten ihn direkt nach der Durchführung des tatsächlichen Schrittes auszuführen, da dabei die neuen Koordinaten berechnet werden. Wenn das Schrittsetzen in einer externen Prozedur stattfindet, kann der Aufruf also auch von dort erfolgen.
Rekursionsende
Die Rekursion wird beendet, wenn alle möglichen Richtungen erfolglos gewesen sind oder das Ziel gefunden ist. Im ersten Fall ist man an einer Position, wo bereits alle Versuche (alle Richtungen) erfolglos waren, daher werden alle vorherigen Aufrufe, bei denen das gleiche gilt, automatisch beendet. Man muss bei diesem Zurückgehen daher nur noch an die graphische Ausgabe denken (Markierung zurücknehmen). Wenn das Ziel gefunden ist, muss dies an die vorherigen Aufrufe, die das nicht wissen können, zurückgegeben werden, damit auch sie beendet werden. Das Wegsuchen ist beendet, wenn alle Aufrufe beendet sind.
Erweiterungen
Generieren
Das Generieren eines Labyrinths ist im Prinzip nur eine Vereinfachung des Wegsuchens, da die Abbruchbedingung des Ziel gefunden wegfällt. Das Labyrinth wird zunächst komplett mit Wänden gefüllt. Dann wird auch hier ein rekursiver Algorithmus benutzt, der alle möglichen Schritte prüft und abgeht, bis er keinen mehr findet. Um brauchbare Labyrinthe zu erhalten, ist es sinnvoll mindestens zwei Schritte auf einmal in die gleiche Richtung zu gehen, da dies besser aussieht.
Wegmarkieren
Bei einem Labyrinth, in dem es keine "Schleifen"(die Möglichkeit im Kreis zu gehen) gibt, z.B. in einem, wie oben beschrieben, generierten Labyrinth, ist diese Erweiterung nicht von besonderem Nutzen. Wenn es jedoch so eine Schleife oder sogar mehrere gibt, dann kann einem diese Funktion viel Zeit und dem Rechner Arbeit ersparen.
Weg 1
Weg 2
Weg 3
Das Problem besteht, wie hier zu sehen ist, darin, dass zwar erkannt wird, wenn ein Weg nicht zum Erfolg geführt hat, aber nicht, dass man an dieser Position schon einmal gewesen ist und dass sich nur der Weg zu dieser Position verändert hat. Wenn man den bereits erfolglos begangenen Weg jedoch Markiert, wird sichergestellt, dass er jede Position nur einmal betritt.
Monster
Ein Monster, das den gefundenen Wegsucher frisst, bewegt sich im Gegensatz zu diesem iterativ durch das Labyrinth. Das Ziel des Monsters bewegt sich und somit könnte bei einer Rekurson ein eben noch als erfolglos abgearbeiteter Weg im nächsten Moment erfolgreich sein. Es muss daher dahin zurückgehen dürfen, wo es gerade herkam. Die Wahl, in welche Richtung das Monster seinen nächsten Schritt setzt, darf jedoch nicht ganz dem Zufall überlassen werden, da es ansonsten genauso wahrscheinlich wäre, dass das Monster zurückgeht, wie, dass es weitergeht. Es käme kaum vom Fleck. Man sollte es also nicht unmöglich, aber unwahrscheinlich machen, dass es sofort wieder zurückgeht. Dies kann z.B. auf diese Weise erreicht werden (konkretes Beispiel):
WENN du in die Richtung (hoch) gegangen bist
DANN
Gib die Möglichkeit zufällig die Richtung zu wählen, außer entgegengesetzte Richtung (runter)
WENN dabei kein erlaubter Schritt entsteht
DANN
Teste beide Richtungsänderungen nochmal ab (rechts und links)
WENN dabei kein erlaubter Schritt entsteht
DANN
Versuche weiter in die Richtung (hoch) zu gehen
WENN dabei kein erlaubter Schritt entsteht
DANN
Gehe zurück (runter)
Auch für ein Monster braucht man eine Abfrage, die angibt, ob ein Schritt möglich ist, da es zusätzlich die Wegspur und markierten Felder betreten darf. Daher muss es eine Zwischenspeicherung geben, die sich merkt, was an der Selle, wo sich das Monster befindet, gewesen ist, damit nichts verloren geht. Das Monster wird sowohl gesetzt, wenn der Wegsucher vorwärts geht, als auch beim zurücknehmen des Wegs. Desweiteren muss der Wegsuchenalgorithmus um eine Abbruchbedingung Vom Monster gefressen erweitert werden. Die Abfrage dafür muss immer vor und nach dem Setzten des Monsters erfolgen.
Schlüsselsuchen
Die Erweiterung, dass man erst einen oder mehrere Schlüssel finden muss, damit der Ausgang freigegeben wird, besteht im Grunde aus zwei getrennten Suchen. Zuerst werden alle Schlüssel gesucht und die Abbruchbedingung des Ziel gefunden wird verhindert. Wenn alle Schlüssel gefunden sind, dann wird die Schlüsselsuche beendet und die Suche nach dem Ziel wird vom Start aus neu begonnen.
Kürzesten Weg suchen
Im wahren Leben wird man meist froh sein aus einem Labyrinth herausgefunden zu haben und sich nicht dafür interessieren, wie optimal sein Weg denn nun ist. Manch ein Freak wird sich aber vielleicht daran machen den kürzesten Weg zu suchen: Man sucht wie immer nach dem Ausgang, wenn man ihn gefunden hat, merkt (speichert) man sich den Weg und versucht auf anderem Wege wieder dorthin zu gelangen (Abbruchbedingung des Ziel gefunden muss verhindert werden). Wenn beim erneuten Zielsuchen der Weg länger wird, als der bereits gefundene, dann braucht man dort nicht mehr weitergehen (verhindert Schrittmoeglichkeit) und kehrt soweit zurück, bis das Weitersuchen wieder einen Sinn macht, der Weg wieder kürzer ist, als der bereits gefundene Kürzeste.
Umsetzung in Delphi
Das Programm: Datei:Labyrinth.zip
