Einheit 4: Komplette Wegfindungsalgorithmen

This is an old revision of the document!

Die Grundideen sind folgende:

Wir haben eine Todo-Liste mit Zellen, die noch zu bearbeiten sind.
Die Zellen sind markiert, um zu wissen, ob diese schon bearbeitet sind oder nicht (damit werden diese auch nicht mehrfach zur Todo-Liste hinzugefügt).

Wir werden folgende Listen-Operationen verwenden:

l=[7,23,42] # Liste mit Elementen initialisieren
print(len(l)) # Anzahl Element (hier 3)
print(l[2]) # Drittes Element (also 42) (Erstes Element ist l[0])
l.append(107) # Element hinten anfügen, danach ist die Liste [7,23,42,107]
a = l.pop() # Letztes Element entfernen (a ist 107, die Liste wieder [7,23,42]
shuffle(l) # Liste verwürfeln

Speichern Sie das Programm aufgabe7.py im Verzeichnis Labyrinth.
Führen Sie das Programm aus.
Studieren Sie das Programm und versuchen Sie, seine Funktionsweise zu verstehen.
- Führen Sie das Programm in einem 2×2-Labyrinth von Hand aus. Führen Sie die todo-Liste nach.

In dieser Aufgabe soll ein Weg nur innerhalb jener Zellen gefunden werden, die im Bild einem schwarzen Pixel entsprechen.

Immer noch in der Datei aufgabe7.py fügen Sie am Anfang folgende Zeile hinzu:

from pnmbild import PNMBild

Bevor das Labyrinth initialisiert wird, laden Sie ein pnm-Bild (z.B. herz.pnm oder Ihr eigenes) wie folgt:

bild = PNMBild("herz.pnm")
l = Laby(bild.breite, bild.hoehe)
l.importBild(bild)
print(l)
l.clearMarks()

Damit kann die Bildinformation von jeder Zelle angefragt werden.
Fügen Sie folgende Funktion (nach den import-Zeilen) ein, um eine Startzelle mit Bildwert 1 (schwarz) zu finden:

def findStart(l:Laby)->Zelle:
    for y in range(l.hoehe):
        for x in range(l.breite):
            if l[x,y].bild==0:   # Schwarzer Pixel?
                return l[x,y]

Ersetzen die Zeile, wo die Variable start erstmals definiert wird durch

start = findStart(l)

Kommentieren Sie die sleep Anweisungen (und evtl. die print-Anweisungen) in der while-Schlaufe aus.
In der while-Schleife, im for-loop, wo überprüft wird, ob der Nachbar existiert und noch frei ist, fügen Sie die zusätzliche Bedingung hinzu, dass der entsprechende Pixel schwarz ist, mit nb.bild==0.
Testen Sie das Programm.

Es geht darum, zwei möglichst weit voneinander entfernte Startzellen am Rand vom Bild zu bestimmen.

Die Grundidee ist folgende:

Man erstellt eine Liste von allen Zellen, die am Rand sind und schwarzen Pixeln entsprechen.
Für jedes mögliche Paar dieser Zellen wird die Entfernung mit der «Manhattan Distance» bestimmt.
Das Paar mit der grössten Distanz wird als Start- und Endpunkt des Labyrinths verwendet.

Immer noch im Verzeichnis labyrinth, speichern Sie die Datei startzielpaar.py
Studieren Sie die Funktion in der Datei startzielpaar.py und vervollständigen Sie sie.
Zurück in der Datei aufgabe7.py, fügen Sie folgenden import hinzu:

from startzielpaar import startzielpaar

Ganz am Schluss, unmittelbar vor der Ausgabe, markieren Sie das Start/Ziel-Paar wie folgt:

p = startzielpaar(l)
p[0].mark = "S"
p[1].mark = "Z"

Bis jetzt haben wir Labyrinthe erzeugt, aber den Weg zwischen zwei Punkten nicht gespeichert, bzw. nicht bestimmt.

Eine einfache Möglichkeit dafür ist folgende:

immer, wenn ein neuer Nachbar besucht wird, wird der Nachbar mit der Richtung markiert, in der man zurück kommt.
Dann kann man mit diesen Markierungen von der Zielzelle (von jeder Zelle!) zurück zur Startzelle finden.

Damit ist es Zeit, das Hauptprogramm main.py zu beginnen. Von dort werden alle Funktionen aufgerufen.

Speichern Sie die Datei main.py im Verzeichnis labyrinth.
Studieren und kommentieren Sie den Code in der Datei main.py. Ausführbar ist der Code aber noch nicht:
Speichern Sie die Datei wegaufbild.py ebenfalls im Verzeichnis labyrinth.
Studieren Sie den Code der Datei wegaufbild.py.
- Der erste Teil der Funktion wegaufbild findet alle Wege.
- Der zweite Teil bestimmt den Weg vom Ziel zum Start und macht eine Liste aus allen Zellen (in der korrekten Reihenfolge).
Führen Sie jetzt main.py aus. Eventuell müssen/können Sie den Namen der .pnm-Datei anpassen.
Der Weg soll jetzt noch markiert werden und alle Wände, ausser jenen für den Weg, geschlossen werden.
Fügen Sie dazu folgende Funktion nach den imports in der Datei wegaufbild.py hinzu:

def labyrinthNurMitWeg(laby:Laby, weg:list[Zelle]) -> None:
    # Alle Markierungen löschen
    laby.clearMarks()
    # Alle Wände schliessen
    laby.closeAll()
    # Weg-Zellen mit # markieren
    for zelle in weg:
        zelle.mark = "#"
    # Wände auf dem weg öffnen
    for i in range(len(weg)-1):      # Vom ersten bis vorletztem Weg-Element
        d = weg[i].dirTo(weg[i+1])   # Richtung des Wegs an Stelle i
        weg[i].zustand(d, True)      # Wand in diese Richtung öffnen

In der Datei wegaufbild.py, zu unterst, untermittelbar vor dem return, rufen Sie die Funktion wie folgt auf:

    labyrinthNurMitWeg(laby, weg)

In der Datei main.py, fügen Sie als letzte Zeile print(laby) hinzu, um das Labyrinth auszugeben.
Testen Sie das Programm main.py.
Als letztes sollen noch die Wände von Start- und Zielzelle nach aussen geöffnet werden. Fügen Sie die beiden folgenden Funktionen in der Datei wegaufbild.py nach den imports hinzu:

def randWandAuf(zelle:Zelle) -> None:
    if zelle.y==0:
        zelle.zustand(3, True)
    elif zelle.y==zelle.laby.hoehe-1:
        zelle.zustand(1, True)
    elif zelle.x==0:
        zelle.zustand(2, True)
    elif zelle.x==zelle.lab.breite-1:
        zelle.zustand(0, True)
 
def raenderOeffnen(paar: list[Zelle]) -> None:
    randWandAuf(paar[0])
    randWandAuf(paar[1])
    paar[0].mark="S"
    paar[1].mark="Z"