lehrkraefte:blc:informatik:glf24:laby:wegfindentodo

This is an old revision of the document!

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).

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

Aufgabe 7

  • 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.

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:
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.

Aufgabe 9

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, legen Sie eine neue Datei startzielpaar.py an.
  • lehrkraefte/blc/informatik/glf24/laby/wegfindentodo.1747207548.txt.gz
  • Last modified: 2025/05/14 07:25
  • by Ivo Blöchliger