Wir haben den «Linke-Hand»-Algorithmus kennengelernt und bewiesen, dass man damit aus jedem Labyrinth herausfindet:
Irrgarten
Leider funktioniert dieser Algorithmus im «Irrgarten» nicht! Als Irrgarten bezeichnet man ein erweitertes Labyrinth mit mehr als einem möglichen Weg zum Ausgang.
So führt er im folgenden Beispiel zu einer Endlosschleife um eine Insel herum.
Versuch
So kommen wir nicht weiter! Man muss sich irgendwann wieder von solchen Inseln lösen. Also neuer Versuch: geradeaus der Nase nach bis zur Wand, der Wand so lange folgen, bis man wieder in die alte Richtung schaut, und dann wieder der Nase nach. Jetzt macht die Insel keine Probleme mehr:
Allerdings stecken wir wieder in einer Endlosschleife. Dieses Mal, weil wir immer, wenn wir nach oben gucken, geradeaus gehen. Sich die Startrichtung zu merken reicht also nicht – wir müssen uns merken wie oft wir uns gedreht haben:
Pledge-Algorithmus
Da unser Irrgarten rechteckig ist, zählen wir die gemachten Vierteldrehungen[1]: nach Links +1, nach Rechts -1
Im Beispiel guckt der Roboter zu Beginn nach oben. Die Anzahl Drehungen ist natürlich 0.
Nun fahren wir mit der linken Hand der Wand entlang, ausser wir erreichen bei der Drehung eine 0. Dann gehen wir geradeaus. So verlassen wir die Insel, bleiben aber oben rechts nicht hängen:
Entdeckt haben soll diesen Algorithmus ein zwölfjähriger Junge namens John Pledge; deshalb nennt man ihn den Pledge-Algorithmus.
in Scratch
Scratch ist eine graphische Programmiersprache, in der man kleine Programme per drag & drop zusammenzustellen kann.
Einen allgemeinen, kostenlosen Scratch-Editor finden Sie online unter
Mit Datei –> Hochladen von deinem Computer… öffnen Sie die bereitgestellte Vorlage LeftHandPledge.sb3.
Das Ganze sollte dann etwa so aussehen:
Aufgabe
Testen Sie zunächst die bereits vorhandene Funktionalität mit verschiedenen Bühnenbildern. Ändern Sie dann das Skript so ab, dass die kleine Figur auch aus den Irrgärten bis nach draussen findet.
- Die kleine Figur namens Robot soll durch das Labyrinth navigieren. Zum Starten des Programms drücken Sie auf die grüne Flagge, zum Stoppen auf das rote Stoppzeichen. Vor dem Start kann die Figur mit der Maus zu einem beliebigen Startpunkt gezogen werden. Unter Bearbeiten –> Turbo-Modus kann man die Ausführung des Programms stark beschleunigen.
- Insgesamt sind zehn Labyrinthe und Irrgärten verschiedener Schwierigkeitsstufen im Projekt vorhanden (Bühnenbilder). Wenn Sie auf das Icon «Bühne» unten rechts klicken, erscheint ein neuer Tab (oben Mitte) namens «Bühnenbilder». Dort können Sie die Labyrinthe und Irrgärten austauschen oder sogar editieren.
- Das bereits angelegte Skript (rechts) setzt die Linke-Hand-Regel um, es sollte also in allen Labyrinthen zum Ausgang (blau markiert) finden, in Irrgärten nicht unbedingt (je nach Startpunkt).
- Um den Pledge-Algorithmus umzusetzen, müssen Sie lediglich den zentralen Teil des Programms verändern. Dazu sollten Sie zunächst verstehen, wie die Linke-Hand-Regel umgesetzt ist. Grob gesagt wird der gelbe Streifen vor dem Robot als Farbdetektor verwendet, ähnlich wie bei einem richtigen Roboter. Durch Drehungen kann man herausfinden, in welcher Richtung keine Wand vor dem Roboter ist – und dann einen kleinen Schritt nach vorne gehen.
Lösung
Zusatzaufgabe
Roboter mit mehreren Detektoren sind schwieriger zu programmieren, sie können aber ggf. effizienter sein. Im Projekt findet sich noch ein weiteres Kostüm mit mehreren als Detektoren verwendbaren Farbfeldern. Schaffen Sie es, damit einer Wand effizienter zu folgen (weniger Drehungen, ggf. grössere Schritte)?
wir könnten auch in Grad zählen, aber bei uns gibt es nur 90°-Drehungen ↩︎