Wäre es akzeptabel, Grenzen um meine Pfadfinderzone zu legen?

Question

Ich verwende derzeit den A * Pathfinding-Algorithmus, um einen Pfad auf einem unendlichen Gitter zu berechnen (mit einem UnboundedGrid in Gridworld, der AP CS Fallstudie, wenn das irgendjemand hilft). Alles funktioniert wunderbar, außer in Fällen, in denen kein gültiger Pfad existiert, weil der Endknoten vollständig von Wänden umgeben ist. Wie erwartet, sucht der Algorithmus unendlich weiter und findet niemals den Endknoten.

Eine mögliche Lösung wäre, die Wände um den gesamten Pfadsuchbereich unsichtbar zu platzieren (wie der Benutzer sie nicht sieht, aber der Algorithmus tut dies) und stellt den Startknoten, den Endknoten und die gesamte Wand sicher Knoten befinden sich innerhalb dieser Wände, mit 2-3 Zwischenräumen. Etwas wie:

_________________________________ 
|        | 
|    S |    | 
|   _____| _____  | 
|      | E |  | 
|      |___|  | 
|_______________________________| 

... die Idee ist, dass schließlich alle Knoten werden dem closedlist hinzugefügt werden, wird die Openlist leer geworden, und an diesem Punkt werde ich wissen, dass kein gültiger Pfad vorhanden ist.

Scheint dies eine vernünftige Lösung für das Problem? Gibt es irgendwelche Möglichkeiten, wie dies möglicherweise schiefgehen könnte? Ich verstehe, dass eine andere Lösung darin besteht, vom Ende her gleichzeitig rückwärts zu suchen, aber dies scheint möglicherweise teuer zu sein, insbesondere in Fällen, in denen der Endknoten nicht so eng umschlossen ist.

Answer 1

Wissen Sie nicht genau wo ist der Endknoten? Wenn Sie dies tun, überprüfen Sie einfach, ob es umschlossen ist, bevor Sie Ihren Algorithmus ausführen.

Answer 2

Siehe auch meinen Kommentar zu Ihrer Frage. Nach dem Tippen kam ich auf, was eine nette Lösung sein könnte. Dies ist für einen Fall, in dem Sie Ihren Endknoten nicht kennen und nichts mit der Position Ihres Endknotens tun können, wie oben vorgeschlagen.

Sie könnten auch etwas entlang der Linien von: „Ich habe einen geschlossenen Kasten in meinem Bereich und keinen Weg nach x Zeit gefunden haben, so mit y% propability kann ich sagen, es gibt keinen Weg, und aktualisieren die y% im Laufe der Zeit zu erhöhen, aber nie zu 100% zu erreichen.

Könnte eine schöne Lösung sein, die in der Mitte ist das Suchgebiet begrenzt und nichts zu tun.

Answer 3

ich hatte ein ähnliches Problem und hier ist was ich tat:

1. Run-Algorithmus für n Iterationen bei einem Start für B.
Benutzer
2. Run-Algorithmus für n Iterationen, bei B ausgehend von A. Benutzer

Wenn entweder Lauf feststellt, dass ein oder der andere befindet sich in einem vollständig isolierten Bereich (keine offenen Knoten mehr), die Suche schlägt fehl. Ansonsten wird die Suche als normal durchgeführt.

Der Trick hier ist natürlich, mit einem guten Wert für n zu kommen. Ich machte mehrere Durchgänge mit steigenden n und zwischengespeichert die Ergebnisse (mein Diagramm nicht viel geändert).

Answer 4

Sie verwenden A *, also sollten Sie in der Lage sein, die Terrain-Nodes mit Kosten zu gewichten. Setzen Sie einen wahnsinnig hohen Preis auf die Wandknoten. Es muss größer als die Gesamtkosten eines möglichen Pfades sein. Wenn die Endkosten des Pfads größer als diese Grenzkosten sind, mussten Sie eine Wand passieren, um einen Pfad zu finden, der ungültig ist.Der A * -Algorithmus routet um Knoten mit hohen Kosten, so dass er nicht durch eine Wand routet, es sei denn, es muss.