Wäre es akzeptabel, Grenzen um meinen Pfadfindungsbereich zu legen?

Question

Ich verwende derzeit den A* Pathfinding -Algorithmus, um einen Pfad in einem unendlichen Gitter zu berechnen (mit einem unbegrenzten Grid in Gridworld, der AP CS -Fallstudie, falls dies jemandem hilft). Alles funktioniert wunderbar, außer für Fälle, in denen kein gültiger Weg existiert, da der Endknoten vollständig von Wänden umgeben ist. Wie erwartet sucht der Algorithmus weiterhin unendlich und findet den Endknoten niemals.

Eine mögliche Lösung dafür wäre, unsichtbar zu platzieren (wie in, der Benutzer sieht sie nicht, aber der Algorithmus) Wände um den gesamten Wegfindungsbereich und sorgen dafür, dass der Startknoten, der Endknoten und alle Wandknoten sich in diesen befinden Wände, mit 2-3 Feldern oder so. Etwas wie:

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

... die Idee ist, dass irgendwann alle Knoten zur Enderlist hinzugefügt werden, die Openliste leer wird und zu diesem Zeitpunkt wissen, dass kein gültiger Weg besteht.

Scheint dies eine vernünftige Lösung für das Problem? Gibt es eine Möglichkeit, wie dies möglicherweise schief gehen könnte? Ich verstehe, dass eine andere Lösung darin besteht, gleichzeitig von Ende nach rückwärts zu patieren, aber dies scheint potenziell teuer zu sein, insbesondere in Fällen, in denen der Endknoten nicht so eng eingeschlossen ist.

Answer 1

Weißt du nicht genau, wo der Endknoten ist? Wenn Sie dies tun, überprüfen Sie einfach, ob es umgeben ist, bevor Sie Ihren Algorithmus durchführen.

Answer 2

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

Sie könnten auch etwas in der Art von: "Ich habe eine geschlossene Schachtel in meinem Feld gefunden und keinen Weg danach x Zeit so mit y% Aktuelle Ich kann sagen, dass es keinen Pfad gibt, und die Aktualisierung der Aktualisierung y% im Laufe der Zeit zunehmen, aber nie 100%erreichen.

Könnte eine schöne Lösung sein, die sich in der Mitte des Suchbereichs befindet und nichts tut.

Answer 3

Ich hatte ein ähnliches Problem und hier ist, was ich getan habe:

1. Algorithmus für n Iterationen, beginnend auf der Suche nach B.
2. Algorithmus für n Iterationen, beginnend bei B auf der Suche nach A.

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

Der Trick hier ist natürlich, ein gutes Preis -Leistungs -Verhältnis zu finden n. Ich habe mehrere Pässe mit zunehmendem Erhöhen gemacht n und zwischen den Ergebnissen zwischengespeichert (mein Diagramm hat sich nicht viel geändert).

Answer 4

Sie verwenden ein*, damit Sie die Geländeknoten mit Kosten gewichten können. Legen Sie wahnsinnig hohe Kosten auf die Wandknoten. Es muss größer sein als die Gesamtkosten eines möglichen Weges. Wenn die Endkosten des Pfades größer als diese Grenzkosten sind, mussten Sie eine Wand übergeben, um einen Pfad zu finden, damit er ungültig ist. Der A* -Algorithmus wächst zu hohen Kostenknoten, sodass er nicht durch eine Wand startet, es sei denn, sie muss.