Wegfindungsalgorithmen

Ziel ist es, dass Sie ihren Wegfindungsalgorithmus in Python übersetzen und auf verschiedenen Labyrinthen testen.

# aktuelle Position = Startposition
# Wiederhole:
#   Alle Nachbarfelder der aktuellen Position betrachten
#   wenn ein Nachbar mit 'Z' markiert ist:
#     Beende mit "Fertig, Weg gefunden!"
#   wenn es einen unmarkierten Nachbar nb gibt:
#     markiere aktuelle Position mit 'o'
#     aktuelle Position ist neu nb
#   sonst:
#     aktuelles Feld mit 'X' markieren
#     wenn es einen Nachbar nb mit 'o' markiert gibt:
#       aktuelles Feld ist neu nb
#     sonst:
#        Beende mit "Fertig, es gibt keinen Weg"

Beispiellabyrinthe gibt es hier: labs.zip. Entpacken Sie die Dateien ins gleiche Verzeichnis, wo sich ihre Programme und die Klassen befinden.

Von Datei laden

from laby import Laby
from zelle import Zelle
 
l = Laby.load("10x07-06.txt")
print(l)

In Datei speichern

# l enthält eine Instanz der Klasse Laby
l.save("meineloesung.txt")

l[0,0].mark = "S"
l[l.breite-1, l.hoehe-1].mark = "Z"

aktuell = l[2,4]                    # eine Zelle des Labyrinths
for dir in range(4):                # Alle Richtungen durchgehen
    if aktuell.offen[dir]:          # Wand in die Richtung ist offen
        nb = aktuell.nachbar(dir)   # Nachbarszelle (oder None, wenn es diese nicht gibt)
        if nb!=None:                # Nur wenn es diese Zelle auch gibt (Mauern am Rand könnten auch offen sein)
            # Tu wat mit nb
            nb.mark = "X"
            aktuell = nb
            break                   # for-Schleife sofort beenden (evtl. weitere Nachbarn ignorieren)

Idee: Für jede vorhandene Markierung um eine aktuelle Zelle generiert man eine Liste mit Zellen mit dieser Markierung, z.B. {'X':[a,b], '.':[c], 'S':[d]}, .d.h. es gibt zwei Nachbarszellen a,b, die mit 'X' markiert sind, eine mit '.' und eine mit 'S'.

nachbarn = {}   # Leerer dictionary
aktuell = l[2,4]                    # eine Zelle des Labyrinths
for dir in range(4):                # Alle Richtungen durchgehen
    if aktuell.offen[dir]:          # Wand in die Richtung ist offen
        nb = aktuell.nachbar(dir)   # Nachbarszelle (oder None, wenn es diese nicht gibt)
        if nb!=None:                # Nur wenn es diese Zelle auch gibt (Mauern am Rand könnten auch offen sein)
            if nb.mark in nachbarn: # Markierung gibt es schon
                nachbarn[nb.mark].append(nb)        # Zur List hinzufügen
            else:
                nachbarn[nb.mark] = [nb]            # Sonst neue Liste mit einem Eintrag