Python Labyrinth Maze kürzesten Weg finden?

2 Antworten

ralphdieter
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Computer, Mathematik, Informatik
13.12.2021, 09:56

Erst mal ein paar Anmerkungen zu Deinem Code:

  • Wenn schon deutsch, dann bitte alles: dir⇒richtung, peek⇒nachsehen, file⇒datei, map⇒eingabe.
  • In __str__() missbrauchst Du das Schlüsselwort int als Bezeichner. Das ist richtig hässlich. Nimm lieber zeichen oder wert.
  • feld_laden() ist schräg: Globale Variablen sind pfui und wx, wy werden sowieso nirgends benutzt. map ist zuerst ein File-Objekt, dann eine Liste von Zeilen. Das irritiert gewaltig. Und ein return in einem Generator ist absolut sinnfrei. Es sieht so aus, als wolltest Du zwei Werte wx, wy aus der ersten Zeile lesen. Wenn das die Startposition ist, sollte die Methode nicht static sein, und falls es die Größe des Labyrinths sein soll, kannst Du höchstens damit prüfen, ob auch wirklich wy Zeilen mit je wx Zeichen (plus Zeilenende) gelesen werden können. Dazu musst Du wx und wy aber in int umwandeln und darfst diese erste Zeile nicht mehr für das labyrinth verwenden:
    @staticmethod
    def feld_laden( datei ):
        with open(datei) as eingabe:
            zeile1 = eingabe.readline().split()
            wx = int(zeile1[0])
            wy = int(zeile1[1])
            print(wx)
            print(wy)
            # restliche Zeilen lesen:
            zeilen = eingabe.readlines()
            # Größe prüfen:
            assert wy==len(zeilen) # geht auch schöner :-/
            for zeile in zeilen:
                assert wx==len(zeile)-1 # wx Zeichen + '\n'
        return zeilen
  • Der Kommentar in gehen() ist irreführend: Du drehst Dich einmal nach links (falls (0,0) oben links liegt), und dann solange nach rechts, bis Du einen Weg findest. Also bleibt die Wand immer links von oder links hinter Dir.
  • gehen() funktioniert nicht, wenn das Labyrinth Kreise enthält. Dazu zählt auch ein 2×2-Raum, wenn Du in der falschen Richtung anfängst.
Wie bekomme ich es hin, dass das Programm am Ende ausspuckt, was der kürzeste Weg ist.

Wenn das Labyrinth Kreise enthält, ist Dein Algorithmus sowieso falsch, weil Du dann endlos im Kreis laufen kannst. Andernfalls gibt es genau einen überschneidungsfreien Weg zum Ziel, und der ist damit logischerweise der kürzeste. Du musst Dir also nur auf jedem Feld merken, wohin Du zuletzt gelaufen bist. Dein Labyrinth ist aber ein Tupel aus Strings, also nicht änderbar. So sehe ich diese Möglichkeiten:

  1. Speichere das Labyrinth als Liste von Listen. Dann kannst Du dort Notizen eintragen. Du musst aber darauf achten, dass es jetzt nicht mehr nur ' ' und 'X' begehbar sind, sondern auch '^', '>', 'v' und '<' (oder was auch immer Du bei gehen() in die Felder schreibst). Eigentlich ist es nicht schön, Eingabewerte im Algorithmus zu ändern. Aber der Vorteil ist, dass Du den aktuellen Weg bei jeder Ausgabe sofort im Labyrinth sehen kannst. Dafür ist es schwieriger, den effektiven Weg als Liste von Koordinaten auszugeben („(8,1)-(8,2)-(9,2)-...“).
  2. Verwende ein zweites 2D-Feld in der gleichen Größe wie das Labyrinth. Das ist sauberer, macht aber die Ausgabe des Labyrinths mit Weg etwas umständlicher.
  3. Speichere in gehen() den aktuellen Weg in einem Dictionary pos⇒richtung oder pos⇒nächste pos:
        # gewählte Richtung merken:
        self.weg[self.spieler] = richtung
        self.spieler = self.folgen()

oder:

        # nächstes Feld merken:
        self.weg[self.spieler] = self.spieler = self.folgen()

Wenn Du aus einer Sackgasse zurückkommst, wird der Weg in gehen() einfach neu gesetzt. Bei bekannter Startposition kannst Du daraus den effektiv gelaufenen Weg (ohne Sackgassen) rekonstruieren und auch leicht als Text „(8,1)-(8,2)-(9,2)-...“ ausgeben. Nur wird es etwas lästiger, diesen Weg direkt im Labyrinth auszugeben.

KarlRanseierIII
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Computer, programmieren, Informatik
13.12.2021, 01:02

Wie habt ihr denn das auffinden des Weges umgesetzt? DFS oder BFS?
catboy 
Beitragsersteller
 13.12.2021, 01:27 
import time

class Spiel:

    def __init__(self, file): # die methode läuft auf eigenem objekt

        self.spiel = tuple(self.feld_laden(file)) #lädt das Spielfeld
        self.spieler = 8, 1 #Startwert definieren
        self.dir = 0, 1 # Richtung des Roboters um wie viele Schritte in (x, y)


    def __str__(self):
        return ''.join( ('*' if (s,z)==self.spieler else int)
                        for s,zeile in enumerate(self.spiel)
                            for z,int in enumerate(zeile)
                        )


    @staticmethod

    def feld_laden( file ):
        with open(file) as map:
            map = map.readlines(0)
            xmap = map[0].split()
            global wx
            global wy
            wx = xmap[0]
            wy = xmap[1]
            print(wx)
            print(wy)
            for zeile in map:
                yield zeile
        return wx, wy

    def peek(self, position):


         if 0 <= position[0] <= len(self.spiel):
             zeile = self.spiel[position[0]]
             if 0 <= position[1] <= len(zeile):
                return zeile[position[1]]
         return '\n'



    def folgen( self ): # Steuert die Position und Richtung des Roboters
        return self.spieler[0]+self.dir[0], self.spieler[1]+self.dir[1]

    def gehen( self ):
        """"
        Roboter bewegt sich um einen Schritt, versucht auf rechter Seite eine Wand zu haben.
        Wenn das Ziel erreicht ist wird True zurück gegeben
        """

        self.dir = self.dir[1], -self.dir[0]
        while self.peek(self.folgen()) not in "X ":
            self.dir = -self.dir[1], self.dir[0]

        self.spieler = self.folgen()

        return self.peek(self.spieler)=='X'

if __name__ == '__main__':

    spiel = Spiel("maze.txt")


    while not spiel.gehen():
        print(spiel, sep='')
        time.sleep(0.5)
        print("----------------")

print("Glückwunsch")

Das ist der bisherige Code den wir haben :)

0
KarlRanseierIII  13.12.2021, 02:07
@catboy

Okay, also eine DFS, wobei ihr immer Greedy die erste Möglichkeit nehmt. Das Labyrinth ist also zyklenfrei.

Möglichkeit 1:

Du probierst alle Wegvarianten durch, dabei nimmst Du ein Garnknäuel und markierst Dir den Weg.

Technisch: Du legst in einer Liste die besuchten Koordinaten nacheinander ab, erreichst Du X, brichst Du ab und speicherst Dir den Pfad mit seiner Länge ab.

Nun gehst Du den Pfad rückwärts und probierst alle anderen Abzweigungen. Solltest Du X wieder erreichen und der Pfad kürzer sein, merkst Du Dir diesen.

--------

Fällt Dir auf, was das Problem ist? Das wächst expotentiell in der Größe des Labyrinths.

Wie macht man das also besser?

Stelle Dir mal vor, Du schreibst an den Starpunkt eien 0 ins Labyrinth. Dann schaust Du Dir ALLE Nachbarfelder an, die erreichbar sind, dort schreibst Du eine 1 hin. Das machst Du immer so weiter, bis Du bei X ankommst. Natürlich ignorierst Du dabei solche Felder, die schon eine Nummer tragen. denn die hast Du bereits vorher schonmal erreicht, also auf kürzerer Strecke.

Nehmen wir nun an, Du hast X gefunden und dort eien 25 eingetragen. Du erzeugst eine Liste und schrebst dort die Koordinaten von X rein. nun suchst Du das erreichbare Feld, das mit 24 markiert ist und fügst die Koordinaten an die Liste an. Das machst Du bis Du beim Start (0) angekommen bist. Nun enthält Deine Liste den kürzesten Weg in umgekehrter Reihenfolge, Du drehst sie um und gibst sie aus (oder markierst den Weg im Labyrinth).

0