Labyrinth - Komplett abfahren

Hallo,

hab als Aufgabe einen Roboter durch ein Labyrinth zu schicken (handelt sich um ein Java-Spiel deswegen in dieser Kategorie). Der Roboter soll alle Wege mindestens einmal abgehen und wieder zu der Ausgangssituation zurückkehren. Das Labyrinth ist in diesem Fall unbekannt. Das Ganze läuft über Regelsätze die umschrieben so aussehen "Wenn Mauer(links), Mauer(rechts), Gang(Mitte) dann gehe geradeaus" Es handelt sich dabei um ein Labyrinth mit Schleifen. Meine Frage ist jetzt welcher Algorithmus für sowas am besten zur Anwendung kommen sollte. Ich meine wenn ich das Programm dann mit so 20 Regelsätzen starte und er findet einen Fehler und dann einfach für diese Situation noch einen Regelsatz schreiben, dann wird das nichts. Irgendwie muss ich an das Problem systematisch rangehen können bzw. für alle Situationen Regelsätze entwerfen.
Was sehr hilfreich ist das der Roboter bei gewissen Situationen wie eine Kreuzung eine Zahl auf den Boden schreiben kann und auch seinen Status ändern kann. Also zB wechsle ich seinen Status von schwarz in grün sobald er zu einer Kreuzung kommt und er beginnt dann wieder von 0 weil noch keine Regelsätze für den Status grün vorhanden sind.

Naja mir gehts hauptsächlich jetzt darum wie ich das Problem lösen kann auf einem Blatt Papier oder sonst irgendwie, weil rein mit Regelsätze am PC selber verliert man leichter den Überblick.

Danke schonmal

lg

disc

Hallo!

Eine Strategie wäre es beispielsweise immer an einer Wand entlang zu fahren und bei einer Abzweigung immer rechts/bzw. links abzubiegen. Dies funktioniert aber nur, wenn das Labyrinth keine Isolierten Elemente enthält (Kasten der keine andere Wand berührt) und der Roboter nicht an genau so einem Isolierten Element vorbei kommt (bzw. abgesetzt wird)....

Gruß Tom

Danke erstmal für die schnelle Antwort, das Labyrinth findet manhier

Nur wenn er bei jeder T-Kreuzung und X-Kreuzung rechts abbiegt, würde er mit Sicherheit ein paar Felder auslassen und ich müsste sicher gehen das er alle Felder mindestens einmal besucht.

Hab mir auch schon überlegt das die Reihenfolge, wie man sich dann bei den Kreuzungen benimmt wichtig ist damit keine Schleife entsteht bzw. er dann wirklich zum Schluss zurückgeht, nur das allein reicht auch nicht aus irgendwo häng ich wirklich.

lg disc

das sollte doch eigentlich über eine rekursive funktion möglich sein. die funktion entscheidet sich immer der reihe nach für eine möglichkeit. z.b. wenn möglich erst links, dann gerade aus und dann rechts. bei der nächsten wahlmöglichkeit ruft sich diese funktion wieder selbst auf und entscheidet wieder in der gleichen reihenfolge. wenn ein weg zu ende ist endet auch die aktuelle funktion und übergibt wieder an die übergeordnete. die wiederrum geht dann denn nächsten weg bis er zu ende ist usw ... so geht man alle möglichkeiten ab und läßt auch nichts aus ... ganz zum schluß steht man dann wieder am ausgangspunkt - ende gelände

HI !

Dafür gibt es den sogenannten A* (a-stern) Algorithmus. Interessant ist vielleicht auch der Dijkstra-Algorithmus.

Krösi

Naja aber dieser A* Alorithmus sucht ja auf dem ersten Blick den kürzesten Weg hinaus aus dem Labyrinth und ich brauch ja einen der alles absucht und wieder zurück zur Ausgangsposition geht....

hilfe

hast du das post von normaler_spinner gelesen?
das einzige, was fehlt, ist eine zyklenerkennung, ohne die terminiert der "algorithmus" nicht.

Hi,

Ok, hast recht, weiss gerade auch keine Patentlösung. Ich hab nur eben so meine Gedanken spielen lassen und hab mir überlegt, wie man ALLE Wege finden könnte. Hab so weitergegrübelt und überlegt, was passieren würde, wenn man dieses Labyrinth mit Wasser fluten würde, würde es nicht alle Wege finden ? Über Fluten bin ich dann auf FloodFill gekommen, ein Algorithmus der genau das macht. Kennst du bestimmt aus Malprogrammen, wenn du eine Fläche füllen willst. Hab auch mal einen Link dazu :

http://www.iam.unibe.ch/~fcglib/spe...illing/lessons/floodfill/floodfill_theory.php

Vielleicht hilft dir meine Gedankenspielerei ja weiter, vielleicht ist es auch absoluter Schwachsinn ... aber so hättest du zumindest alle Punkte, die nicht mit etwas anderem als einem Weg(oder Hindernis etc) belegt sind. Wie man dann die Punkte zu Pfaden verbindet kann auch nicht so schwer sein. Naja, ein rein philosphischer Ansatz, oder so
->

Krösi