Gesamtes Labyrinth auskundschaften und Rückwege markieren

Die Idee ist, einen Todo-Liste mit Zellen (Positionen) zu haben, die noch nicht «fertig augekundschaftet» sind.

Von dieser Liste nimmt man jeweils eine Zelle weg und bearbeitet diese. Dabei werden unter Umständen neue Zellen zur Todo-Liste hinzugefügt.

wegfindung-mit-todo-liste.py

from laby import Laby
from zelle import Zelle
 
# Eingabe: Labyrinth mit unmarkierten Zellen, ausser die Startzelle ist markiert mit 'S'
 
# Datei aus entpackter zip-Datei, siehe https://fginfo.ksbg.ch/dokuwiki/lib/exe/fetch.php?media=lehrkraefte:blc:informatik:glf25:labyrinthe:labs.zip
lab = Laby.load("labs/05x05-04.txt")
#
# Todo-Liste enthält die Startzelle
#
# Solange die Todo-Liste nicht leer ist, wiederhole:
#     Entferne eine Zelle aus der Todo-Liste, nenne diese «aktuell»
#     Für alle Richtungen $d$ von 0 bis und mit 3:
#         Ist der Durchgang zur Nachbarszelle «nachbar» in Richtung $d$ offen?
#             Ist «nachbar» unmarkiert?
#                 markiere «nachbar» (z.B. mit einem Pfeil, der zu «aktuell» zeigt mit >,v,<,^).
#                 Füge «aktuell» der Todo-Liste hinzu.
#                 Füge «nachbar» der Todo-Liste hinzu.
#                 Beende das Überprüfen der Richtungen sofort.
 
# Ausgabe: Von Jeder Zelle ist der Weg zur Startzelle markiert.
print(lab)

Je nachdem, wie die Zelle aus der Todo-Liste entfernt werden, wird das Labyrinth in unterschiedlicher Art durchsucht.

Tiefensuche: Die zuletzt eingefügten Zellen werden zuerst entfernt (Last in, first out). Die Todo-Liste wird als Stapel verwendet. Die Suche geht erst so weit wie irgend möglich, bzw. erst in die Tiefe.

Breitensuche: Die Zellen werden in der Reihenfolge entfernt, wie sie hinzugefügt wurden. D.h. Zellen hinten der Liste hinzugefügt und vorne entfernt. Die Suche besucht die Zellen in Reihenfolge ihrer Distanz von Startpunkt, geht «zwiebelschalenförmig» vor. Man könnte die Distanz vom Startpunkt als Markierung verwenden, z.B. 0-9, dann A-Z, dann a-z.

Werden neue Zellen jeweils wie im Pseudo-Code oben hinten angefügt, enthält die Todo-Liste immer den Weg vom Startpunkt zur aktuellen Zelle. Landet man in einer Sackgasse, geht man den gespeicherten Weg zurück, bis zu einer Zelle, wo ein weiterer Weg möglich ist.

D.h. im Moment, wo das Ziel gefunden wurde, enthält die Todo-Liste alle Zellen auf dem Weg von der Start-Zelle zur Ziel-Zelle.

todo = []              # Leere Liste
todo.append(start)     # Element hinten anfügen
prin(len(todo))        # Anzahl Elemente ausgeben
aktuell = todo.pop()   # Element hinten von der Liste entfernen
todo.append(start)
aktuell = todo.pop(0)  # Element vorne (von Position 0) entfernen

Warten, damit in der Ausgabe verfolgt werden kann, was läuft.

import time
 
time.sleep(0.1)   # 0.1s Warten

Markierungen für die Distanz. Folgende Funktion liefert die nächste Markierung (z.B. naechsteMarkierung("C") lieftert "D".

# Liefert die nächste Markierung 0-9,A-Z,a-z
def naechsteMarkierung(markierung):
   if markierung=="9":
       return "A"
   if markierung=="Z":
       return "a"
   return chr(ord(markierung)+1)