Möglichen Pfad überprüfen

[Plauzi92]

Hi zusammen,

ich sitze gerade an einem kleineren Projekt und hätte dazu eine Frage.
Ein Labyrinth hat einen Start- und einen Zielpunkt und natürlich Wände. Die Wände können vom Spieler gesetzt werden. Vor dem Platzieren muss allerdings geprüft werden, ob danach noch ein Pfad zum Ziel vorhanden ist. Zuerst dachte ich an A* oder Djikstra, aber da mir der kürzeste Weg egal ist, wollte ich es etwas simpler halten.
Ich hab das ganze mal auf einem Blatt Papier versucht und bin auf eine Lösung gekommen. Ich denke die entspricht der Breitensuche wenn mich nicht alles täuscht
Die Frage ist, ob das ganze noch einfacher geht bzw. würde mich mal interessieren wie ihr das lösen würdet.

Setze den Startpunkt in die geschlossene Liste
Setze alle Nachbarn in die offene Liste
Solange der Endpunkt nicht in der geschlossenen Liste ist: (Hier könnte man eigentlich auch die offene Liste prüfen denke ich)
Solange die offene Liste nicht leer ist:
Entferne das erste Element der offenen Liste und setze es in die geschlossene Liste
Für alle Nachbarn
Nachbar frei und nicht in geschlossener Liste? -> offene Liste

Danke im Voraus

 

[Oneixee5]

Wenn der kürzeste Weg sowieso egal ist: Es gibt eine alte Labyrinth-Regel, einfach immer rechts abbiegen und du kommst ganz sicher ans Ziel.

 

[LimDul]

Hi zusammen,

ich sitze gerade an einem kleineren Projekt und hätte dazu eine Frage.
Ein Labyrinth hat einen Start- und einen Zielpunkt und natürlich Wände. Die Wände können vom Spieler gesetzt werden. Vor dem Platzieren muss allerdings geprüft werden, ob danach noch ein Pfad zum Ziel vorhanden ist. Zuerst dachte ich an A* oder Djikstra, aber da mir der kürzeste Weg egal ist, wollte ich es etwas simpler halten.
Ich hab das ganze mal auf einem Blatt Papier versucht und bin auf eine Lösung gekommen. Ich denke die entspricht der Breitensuche wenn mich nicht alles täuscht
Die Frage ist, ob das ganze noch einfacher geht bzw. würde mich mal interessieren wie ihr das lösen würdet.




Danke im Voraus

Jepp das entspricht Breiten bzw. Tiefensuche und sollte für das passend sein.

Wenn der kürzeste Weg sowieso egal ist: Es gibt eine alte Labyrinth-Regel, einfach immer rechts abbiegen und du kommst ganz sicher ans Ziel.

Die ist aber deutlich schwieriger umzusetzen, den dieses Verfahren hat ein Problem in der Programmierung:

* Das Ziel muss eine Lücke in der Wand sein Beispiel wo es nicht klappt:

XXXXX
X...X
X.o.X
X...X
XXXXX

An den Mittelpunkt, das Ziel (=o) komme ich nie, wenn ich mich nur an der Wand entlagebwege

* Ich darf an einer inneren Wand starten, so dass ich innen im Kreis laufen.

Beispiel:

XXoXX
X...X
X.X.X
X...X
XXXXX

Wenn ich nicht aufpasse laufe ich nur um die Säule in der Mitte rum.

 

[mihe7]

Wenn der kürzeste Weg sowieso egal ist: Es gibt eine alte Labyrinth-Regel, einfach immer rechts abbiegen und du kommst ganz sicher ans Ziel.

Nein, s. http://www.mathematische-basteleien.de/irrgarten.htm#Irrgarten von Chevening in Kent

Wenn der Weg egal ist, könnte einfach ein Flood-Fill funktionieren.

 

[Plauzi92]

Ich habe das ganze mal wie im Eingangspost beschrieben implementiert und es funktioniert.

Nein, s. http://www.mathematische-basteleien.de/irrgarten.htm#Irrgarten von Chevening in Kent

Wenn der Weg egal ist, könnte einfach ein Flood-Fill funktionieren.

Ist Flood-Fill nicht das gleiche wie eine Breitensuche? Beide prüfen doch so lange die nächsten Nachbarn bis das Ziel erreicht wurde, bzw alle überprüft wurden oder nicht?

 

[mihe7]

Ja, so ähnlich, nur dass beim Flood-Fill einfach mit Markierung ("Farbe") gearbeitet wird. Das spart die Listen.