lehrkraefte:blc:informatik:glf24:laby:wegfindentodo [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Einheit 4: Komplette Wegfindungsalgorithmen ======
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).

<WRAP info>
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
</WRAP>

===== Aufgabe 7 =====
  * Speichern Sie das Programm {{lehrkraefte:blc:informatik:glf24:laby: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 2x2-Labyrinth von Hand aus. Führen Sie die todo-Liste nach.

===== Aufgabe 8 =====
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:
<code python>
from pnmbild import PNMBild
</code>
  * Bevor das Labyrinth initialisiert wird, laden Sie ein pnm-Bild (z.B. ''herz.pnm'' oder Ihr eigenes) wie folgt:
<code python>
bild = PNMBild("herz.pnm")
l = Laby(bild.breite, bild.hoehe)
l.importBild(bild)
print(l)
l.clearMarks()
</code>
  * Damit kann die Bildinformation von jeder Zelle angefragt werden.
  * Importieren Sie zusätzliche die Klasse ''Zelle'' indem Sie folgende Zeile am Anfang vom Programm hinzufügen:
<code python>
from zelle import Zelle
</code>
  * Fügen Sie folgende Funktion (nach den «''from ... import ...''»-Zeilen) ein, um eine Startzelle mit Bildwert 1 (schwarz) zu finden:
<code python>
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]
</code>
  * Ersetzen die Zeile, wo die Variable start erstmals definiert wird durch
<code python>
start = findStart(l)
</code>
  * 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.


===== Aufgabe 9 =====
<WRAP info>
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.
</WRAP>
 
  * Immer noch im Verzeichnis ''labyrinth'', speichern Sie die Datei {{lehrkraefte:blc:informatik:glf24:laby: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:
<code python>
from startzielpaar import startzielpaar
</code>
  * Ganz am Schluss, unmittelbar vor der Ausgabe, markieren Sie das Start/Ziel-Paar wie folgt:
<code python>
p = startzielpaar(l)
p[0].mark = "S"
p[1].mark = "Z"
</code>

===== Aufgabe 10 =====
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 {{lehrkraefte:blc:informatik:glf24:laby: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 {{lehrkraefte:blc:informatik:glf24:laby: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:
<code python>
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
</code>
  * In der Datei ''wegaufbild.py'', zu unterst, untermittelbar vor dem ''return'', rufen Sie die Funktion wie folgt auf:
<code python>
    labyrinthNurMitWeg(laby, weg)
</code>
  * 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:
<code python>
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"
</code>
  * Rufen Sie die Funktion in der Datei ''wegaufbild.py'' zuunterst, unmittelbar vor dem ''return'' auf:
<code python>
    raenderOeffnen(paar)
</code>
  * Testen Sie das Programm ''main.py''.