LABYRINTH verlassen
Das Labyrinth bzw. der IIrrgarten
ist ein archetypisches Traumsymbol, welches von seiner Natur her für Verwirrung oder Orientierungslosigkeit steht. Im Traum verirren wir uns oft in einem Labyrinth und suchen einen Ausweg.
Hier gehen wir der Frage nach, wie ein kleiner Roboter selbständig einen Weg aus dem Irrgarten findet.
Was wir bereits kennen:
Starte das nebenstehenden SCRATCH-Programm. Zuerst wird ein passendes Labyrinth erzeugt und die rote Maus auf eine zufällige Position gesetzt. Solche Labyrinth-Generatoren haben wir schon angeschaut und verglichen. (Beachte bitte, dass der Algorithmus etwas Zeit braucht, bis er das Labyrinth zeichnen kann).
Im zweiten Schritt erkundet das SCRATCH-Programm die Wege des Labyrinths (gelbe Linie), bis sie auf den roten Startpunkt trifft.
Jetzt hat sie alle Informationen, um den Weg aus dem Irrgarten (grüne Linie) festzulegen.
Der verwendete Algorythmus
Die Rechte-Hand-Methode ist die bekannteste Regel, einen Irrgarten zu durchqueren. Man legt einfach seine rechte (oder linke) Hand an eine Wand des Irrgartens und hält dann beim Durchlaufen ständigen Kontakt. Falls alle Mauern, die man berührt, zusammenhängen oder mit der Außenseite verbunden sind, erreicht man entweder einen anderen Ausgang, oder man kehrt wieder zum Eingang zurück.
In diesem Scratch-Projekt wird zuerst ein zufälliger Irrgarten (mit nur einem Weg zwischen zwei beliebigen Orten!) gezeichnet und dann mit der Linken-Hand-Methode ein Weg gesucht. Die Wände des Irrgartens sind weiß, der Zielpunkt ist rot, die Figur hinterlässt eine gelbe Spur und die suchende Figur hat am Scheitel einen blauen Punkt und am rechten Ohr einen roten. Dadurch sind Abfragen wie "Farbe blau berührt weiß?" möglich. Wenn der blaue Punkt der Figur weiß (also die Wand des Irrgartens) oder gelb (die eigene Spur) berührt, dann soll die Figur nach links abbiegen (also mit der linken Hand der Wand folgen). Wenn das rote Ohr weiß oder gelb berührt, dann soll die Figur vorwärts gehen, ansonsten rechts abbiegen.
Wenn du jetzt schon ein wenig experimentieren möchtest gelangst du hier zur Originalversion des Programms.
Der von Canthiar in seinem "Random Maze Generator" verwendete Lösungsalgorithmus läuft bei dem Irrgarten des oben verlinkten Youtube-Videos in eine Endlosschleife:
Auch versagt dieser Algorithmus, wenn der Startpunkt im Inneren des Irrgartens bei einer Insel liegt:
Der Pledge-Algorithmus wurde von dem 12-jährigen John Pledge erfunden. Er folgt auch Wänden, aber kann auch Hindernisse umrunden. Dabei werden bei jedem Abbiegen die Abbiegewinkel addiert. Trifft man auf ein Hindernis, legt man eine Hand (zum Beispiel immer die rechte) auf das Hindernis und hält auf dem weiteren Weg den Kontakt aufrecht. Ist die Summe der gemachten Drehungen gleich Null, dann ist man wieder in die ursprüngliche Richtung ausgerichtet. Man löst die Hand vom Hindernis und geht wieder geradeaus weiter. Mit dem Pledge-Algorithmus kann man aus einem Irrgarten herausfinden. Für das Finden des Zentrums ist er nicht geeignet. Damit ein Mensch diese Methode verwenden kann, benötigt er einen Kompass.
Weg aus dem Labyrinth
Wie kommt man von einer (komplexen) Problemstellung auf eine algorithmische Beschreibung einer (schlauen) Lösung?
Im nachfolgenden SCRATCH-Programm wird ein einfacher, nicht sehr effizienter aber dafür recht anschaulicher Algorithmus verwendet.
Wenn du mit der Programmierung von geschachtelten Schleifen vertraut bist, findest du bestimmt schnell heraus, welcher Algorithmus dem einfachen Programm zu Grunde liegt.
Hast du dagegen noch keine oder nur Wenig Erfahrung mit der Programmierung von Programmschleifen rate ich dir dringend, das hier vorbereitete Lernprogramm mit der BROCKLY-Sprache anzuschauen. Die Sprache ist mit kleinen Abweichungen vergleichbar mit SCRATCH und genau für Schülerinnen und Schüler gedacht, die sich mit den Grundlagen der Codierung erst vertraut machen müssen.
Hier gelangst du zur Entwicklungsumgebung von SCRATCH und kannst den Programm-Code in aller Ruhe anschauen.
