Wie kann ich A * schneller beenden, wenn das Ziel unpassierbar ist?

Ich mache ein einfaches kachelbasiertes 2D-Spiel, das den A * -Pfadfindungsalgorithmus ("A Star") verwendet. Ich habe alles richtig gemacht, aber ich habe ein Leistungsproblem mit der Suche. Einfach ausgedrückt, wenn ich auf ein unpassierbares Plättchen klicke, durchsucht der Algorithmus anscheinend die gesamte Karte, um eine Route zu dem unpassierbaren Plättchen zu finden - auch wenn ich daneben stehe.

Wie kann ich das umgehen? Ich denke, ich könnte die Pfadfindung zum Bildschirmbereich reduzieren, aber vielleicht fehlt hier etwas Offensichtliches?

Einige Ideen zum Vermeiden von Suchvorgängen, die zu fehlgeschlagenen Pfaden führen:

Insel ID

Eine der billigsten Möglichkeiten, A * -Suchen effektiv zu beenden, besteht darin, überhaupt keine Suchvorgänge durchzuführen. Wenn die Bereiche für alle Agenten wirklich unpassierbar sind, füllen Sie jeden Bereich unter Last (oder in der Pipeline) mit einer eindeutigen Insel-ID . Überprüfen Sie beim Ermitteln des Pfads , ob die Insel-ID des Ursprungs des Pfads mit der Insel-ID des Ziels übereinstimmt . Wenn sie nicht übereinstimmen, macht die Suche keinen Sinn - die beiden Punkte befinden sich auf unterschiedlichen, nicht verbundenen Inseln. Dies hilft nur, wenn es wirklich unpassierbare Knoten für alle Agenten gibt.

Obergrenze einschränken

Ich beschränke die Obergrenze der maximalen Anzahl von Knoten, die durchsucht werden können. Dies verhindert, dass unpassierbare Suchvorgänge für immer ausgeführt werden. Es bedeutet jedoch, dass einige sehr lange passierbare Suchvorgänge verloren gehen können. Diese Nummer muss angepasst werden und löst das Problem nicht wirklich , verringert jedoch die mit langen Suchvorgängen verbundenen Kosten.

Wenn Sie feststellen, dass es zu lange dauert , sind die folgenden Techniken hilfreich:

Machen Sie es asynchron und begrenzen Sie Iterationen

Lassen Sie die Suche in einem separaten Thread oder in einem Teil jedes Frames ablaufen, damit das Spiel nicht auf die Suche wartet. Zeigen Sie eine Animation des Charakters an, der den Kopf kratzt oder die Füße stampft, oder was auch immer angebracht ist, während Sie darauf warten, dass die Suche endet. Um dies effektiv zu tun, würde ich den Status der Suche als separates Objekt beibehalten und zulassen, dass mehrere Status existieren. Wenn ein Pfad angefordert wird, greifen Sie auf ein Objekt mit freiem Status zu und fügen Sie es der Warteschlange der aktiven Statusobjekte hinzu. Ziehen Sie in Ihrem Pfadfindungs-Update das aktive Element von der Vorderseite der Warteschlange und führen Sie A * aus, bis A. abgeschlossen ist oder B. eine bestimmte Anzahl von Iterationen ausgeführt wird. Wenn Sie fertig sind, fügen Sie das Statusobjekt wieder in die Liste der freien Statusobjekte ein. Wenn es noch nicht abgeschlossen ist, setzen Sie es an das Ende der aktiven Suche und fahren Sie mit der nächsten fort.

Wählen Sie die richtigen Datenstrukturen

Stellen Sie sicher, dass Sie die richtigen Datenstrukturen verwenden. So funktioniert mein StateObject. Alle meine Knoten sind aus Leistungsgründen einer endlichen Zahl (z. B. 1024 oder 2048) zugeordnet. Ich verwende einen Knotenpool, der die Zuweisung von Knoten beschleunigt und es mir auch ermöglicht, Indizes anstelle von Zeigern in meinen Datenstrukturen zu speichern, die u16s sind (oder u8, wenn ich 255 maximale Knoten habe, was ich bei einigen Spielen mache). Für die Pfadfindung verwende ich eine Prioritätswarteschlange für die offene Liste, in der Zeiger auf Knotenobjekte gespeichert sind. Es ist als binärer Heap implementiert und ich sortiere die Gleitkommawerte als Ganzzahlen, da sie immer positiv sind und meine Plattform langsame Gleitkommavergleiche hat. Ich verwende eine Hashtabelle für meine geschlossene Karte, um die Knoten zu verfolgen, die ich besucht habe. Es speichert NodeIDs, nicht Nodes, um Cache-Größen zu sparen.

Cache was du kannst

Wenn Sie einen Knoten zum ersten Mal besuchen und die Entfernung zum Ziel berechnen, speichern Sie die im Statusobjekt gespeicherten Werte im Cache. Wenn Sie den Knoten erneut besuchen, verwenden Sie das zwischengespeicherte Ergebnis, anstatt es erneut zu berechnen. In meinem Fall hilft es, keine Quadratwurzel auf neu besuchten Knoten zu machen. Möglicherweise gibt es andere Werte, die Sie vorberechnen und zwischenspeichern können.

Weitere Bereiche, die Sie untersuchen könnten: Verwenden Sie die bidirektionale Pfadfindung, um von beiden Seiten aus zu suchen. Ich habe dies nicht getan, aber wie andere bemerkt haben, könnte dies helfen, ist aber nicht ohne Einschränkungen. Die andere Sache auf meiner Liste, die ich versuchen möchte, ist die hierarchische Pfadfindung oder die Cluster-Pfadfindung. Es gibt eine interessante Beschreibung in der HavokAI Dokumentation Hier ihr Clustering - Konzept beschreibt, die als die HPA unterscheiden * Implementierungen beschrieben hier .

Viel Glück und lassen Sie uns wissen, was Sie finden.

AStar ist ein vollständiger Planungsalgorithmus. Wenn also ein Pfad zum Knoten vorhanden ist, wird er von AStar garantiert gefunden. Folglich muss er jeden Pfad aus dem Startknoten heraus überprüfen, bevor er entscheiden kann, dass der Zielknoten nicht erreichbar ist. Dies ist sehr unerwünscht, wenn Sie zu viele Knoten haben.

Möglichkeiten, dies zu mildern:

• Wenn Sie a priori wissen, dass ein Knoten nicht erreichbar ist (z. B. hat er keine Nachbarn oder ist markiert UnPassable), kehren Sie zurück, No Pathohne AStar aufzurufen.

• Begrenzen Sie die Anzahl der Knoten, die AStar vor dem Beenden erweitern soll. Überprüfen Sie den offenen Satz. Wenn es jemals zu groß wird, kündigen Sie und kehren Sie zurück No Path. Dies schränkt jedoch die Vollständigkeit von AStar ein. es können also nur Pfade mit maximaler Länge geplant werden.

• Begrenzen Sie die Zeit, die AStar benötigt, um einen Pfad zu finden. Wenn die Zeit knapp wird, beenden Sie das Programm und kehren Sie zurück No Path. Dies schränkt die Vollständigkeit wie bei der vorherigen Strategie ein, skaliert jedoch mit der Geschwindigkeit des Computers. Beachten Sie, dass dies für viele Spiele unerwünscht ist, da Spieler mit schnelleren oder langsameren Computern das Spiel anders erleben.

4. Führen Sie eine doppelte A * -Suche vom Zielknoten aus gleichzeitig in derselben Schleife in umgekehrter Reihenfolge durch und brechen Sie beide Suchvorgänge ab, sobald eine unlösbar ist

Wenn das Ziel nur 6 Kacheln hat, auf die zugegriffen werden kann, und der Ursprung 1002 Kacheln hat, stoppt die Suche bei 6 (doppelten) Iterationen.

Sobald eine Suche die besuchten Knoten der anderen findet, können Sie den Suchbereich auch auf die besuchten Knoten der anderen Suche beschränken und schneller beenden.

Angenommen, das Problem ist, dass das Ziel nicht erreichbar ist. Und dass das Navigationsnetz nicht dynamisch ist. Der einfachste Weg, dies zu tun, ist ein viel spärlicheres Navigationsdiagramm (spärlich genug, damit ein vollständiger Durchlauf relativ schnell vonstatten geht) und die Verwendung des detaillierten Diagramms nur, wenn das Verfolgen möglich ist.

Verwenden Sie mehrere Algorithmen mit unterschiedlichen Eigenschaften

A * hat einige feine Eigenschaften. Insbesondere findet es immer den kürzesten Weg, falls vorhanden. Leider haben Sie auch einige schlechte Eigenschaften festgestellt. In diesem Fall muss es vollständig nach allen möglichen Pfaden suchen, bevor zugegeben wird, dass keine Lösung vorhanden ist.

Der "Fehler", den Sie in A * entdecken, besteht darin, dass die Topologie nicht bekannt ist. Sie haben vielleicht eine 2-D-Welt, aber das weiß es nicht. Nach allem, was es weiß, befindet sich in der äußersten Ecke Ihrer Welt eine Treppe, die es unter der Welt ans Ziel bringt.

Erwägen Sie, einen zweiten Algorithmus zu erstellen, der die Topologie berücksichtigt. In einem ersten Durchgang können Sie die Welt alle 10 oder 100 Felder mit "Knoten" füllen und dann eine Konnektivitätsgrafik zwischen diesen Knoten erstellen. Dieser Algorithmus findet den Pfad, indem zugängliche Knoten in der Nähe von Anfang und Ende gefunden werden und anschließend versucht wird, einen Pfad zwischen ihnen im Diagramm zu finden, falls einer vorhanden ist.

Eine einfache Möglichkeit, dies zu tun, besteht darin, jede Kachel einem Knoten zuzuweisen. Es ist trivial zu zeigen, dass Sie jeder Kachel nur einen Knoten zuweisen müssen (Sie können niemals auf zwei Knoten zugreifen, die in der Grafik nicht verbunden sind). Dann werden die Graphenkanten so definiert, dass zwei Kacheln mit unterschiedlichen Knoten benachbart sind.

Diese Grafik hat einen Nachteil: Sie findet nicht den optimalen Pfad. Es findet nur einen Weg. Es hat sich jedoch gezeigt, dass A * einen optimalen Weg finden kann.

Es bietet auch eine Heuristik zur Verbesserung der für die Funktion von A * erforderlichen Unterschätzungen, da Sie jetzt mehr über Ihre Landschaft wissen. Es ist weniger wahrscheinlich, dass Sie eine Sackgasse vollständig erkunden müssen, bevor Sie feststellen, dass Sie einen Schritt zurücktreten müssen, um vorwärts zu gehen.

Einige weitere Ideen zusätzlich zu den Antworten oben:

6. Cache-Ergebnisse der A * -Suche. Speichern Sie die Pfaddaten von Zelle A zu Zelle B und verwenden Sie sie nach Möglichkeit erneut. Dies gilt vor allem für statische Karten, und Sie müssen mehr mit dynamischen Karten arbeiten.

7. Cache die Nachbarn jeder Zelle. Eine * -Implementierung muss jeden Knoten erweitern und dem zu durchsuchenden offenen Satz seine Nachbarn hinzufügen. Wenn diese Nachbarn jedes Mal berechnet und nicht zwischengespeichert werden, kann dies die Suche erheblich verlangsamen. Und wenn Sie dies noch nicht getan haben, verwenden Sie eine Prioritätswarteschlange für A *.

Wenn Ihre Karte statisch ist, können Sie jeden Abschnitt mit einem eigenen Code versehen und diesen zuerst überprüfen, bevor Sie A * ausführen. Dies kann bei der Erstellung der Karte oder sogar in der Karte codiert werden.

Unpassierbare Kacheln sollten eine Flagge haben und wenn Sie sich auf eine Kachel wie diese bewegen, können Sie sich dafür entscheiden, A * nicht auszuführen oder eine Kachel daneben auszuwählen, die erreichbar ist.

Wenn Sie dynamische Karten haben, die sich häufig ändern, haben Sie ziemlich viel Pech. Sie müssen entscheiden, ob Ihr Algorithmus vor dem Abschluss gestoppt werden soll oder ob Überprüfungen von Abschnitten häufig abgeschlossen werden.

Wie kann ich A * schneller zu dem Schluss bringen, dass ein Knoten unpassierbar ist?

Profilieren Sie Ihre Node.IsPassable()Funktion, finden Sie die langsamsten Teile heraus und beschleunigen Sie sie.

Stellen Sie bei der Entscheidung, ob ein Knoten passierbar ist, die wahrscheinlichsten Situationen in den Vordergrund, damit die Funktion die meiste Zeit sofort zurückkehrt, ohne sich die Mühe zu machen, die unklareren Möglichkeiten zu prüfen.

Dies dient jedoch dazu, die Überprüfung eines einzelnen Knotens zu beschleunigen. Sie können ein Profil erstellen, um zu sehen, wie viel Zeit für die Abfrage von Knoten aufgewendet wird. Es scheint jedoch, als ob Ihr Problem darin besteht, dass zu viele Knoten überprüft werden.

Wenn ich auf ein unpassierbares Plättchen klicke, durchsucht der Algorithmus anscheinend die gesamte Karte, um eine Route zu dem unpassierbaren Plättchen zu finden

Wenn das Zielplättchen selbst nicht passierbar ist, sollte der Algorithmus überhaupt keine Plättchen prüfen. Bevor überhaupt mit der Pfadfindung begonnen wird, sollte die Zielkachel abgefragt werden, um zu überprüfen, ob dies möglich ist. Andernfalls wird ein Ergebnis ohne Pfad zurückgegeben.

Wenn Sie meinen, dass das Ziel selbst passierbar ist, aber von unpassierbaren Kacheln umgeben ist, sodass es keinen Pfad gibt, ist es normal, dass A * die gesamte Karte überprüft. Woher sollte es sonst wissen, dass es keinen Weg gibt?

Wenn letzteres der Fall ist, können Sie es durch eine bidirektionale Suche beschleunigen. Auf diese Weise kann die Suche ab dem Zielort schnell feststellen, dass es keinen Pfad gibt, und die Suche stoppen. Sehen Sie sich dieses Beispiel an , umgeben Sie das Ziel mit Wänden und vergleichen Sie bidirektionale und einzelne Richtungen.

Machen Sie die Wegfindung rückwärts.

Wenn Ihre Karte nur keine großen zusammenhängenden Bereiche mit nicht erreichbaren Kacheln enthält, funktioniert dies. Anstatt die gesamte erreichbare Karte zu durchsuchen, durchsucht die Wegsuche nur den umschlossenen nicht erreichbaren Bereich.

Wenn die Bereiche, mit denen der Player verbunden ist (keine Teleports usw.) und die nicht erreichbaren Bereiche im Allgemeinen nicht sehr gut verbunden sind, können Sie das A * einfach ab dem Knoten ausführen, den Sie erreichen möchten. Auf diese Weise können Sie immer noch eine mögliche Route zum Ziel finden, und A * hört schnell auf, nach unerreichbaren Bereichen zu suchen.

Wenn ich auf ein unpassierbares Plättchen klicke, durchsucht der Algorithmus anscheinend die gesamte Karte, um eine Route zu dem unpassierbaren Plättchen zu finden - auch wenn ich daneben stehe.

Andere Antworten sind großartig, aber ich muss auf das Offensichtliche hinweisen - Sie sollten die Wegfindung zu einem unpassierbaren Plättchen überhaupt nicht ausführen.

Dies sollte ein früher Ausstieg aus dem Algo sein:

if not IsPassable(A) or not IsPasable(B) then
    return('NoWayExists');

So überprüfen Sie die größte Entfernung in einem Diagramm zwischen zwei Knoten:

(vorausgesetzt alle Kanten haben das gleiche Gewicht)

1. Führen Sie BFS von einem beliebigen Scheitelpunkt aus v.
2. Verwenden Sie die Ergebnisse, um einen Scheitelpunkt auszuwählen, der am weitesten entfernt ist v, wir nennen ihn d.
3. Führen Sie BFS von aus u.
4. Finden Sie den am weitesten entfernten Scheitelpunkt u, wir nennen ihn w.
5. Der Abstand zwischen uund wist der längste Abstand in der Grafik.

Beweis:

                D1                            D2
(v)---------------------------r_1-----------------------------(u)
                               |
                            R  | (note it might be that r1=r2)
                D3             |              D4
(x)---------------------------r_2-----------------------------(y)

• Sagen wir, der Abstand zwischen yund xist größer!
• Dann dementsprechend D2 + R < D3
• Dann D2 < R + D3
• Dann ist der Abstand zwischen vund xgrößer als der von vund u?
• Dann uwäre in der ersten Phase nicht gepflückt worden.

Gutschrift an prof. Shlomi Rubinstein

Wenn Sie gewichtete Kanten verwenden, können Sie dasselbe in Polynomialzeit erreichen, indem Sie Dijkstra anstelle von BFS ausführen, um den am weitesten entfernten Scheitelpunkt zu finden.

Bitte beachten Sie, dass ich davon ausgehe, dass es sich um ein zusammenhängendes Diagramm handelt. Ich gehe auch davon aus, dass es ungerichtet ist.

Ein * ist nicht wirklich nützlich für ein einfaches 2-D-Spiel, da, wenn ich richtig verstehe, vorausgesetzt, die Kreaturen bewegen sich in vier Richtungen, BFS die gleichen Ergebnisse erzielen wird. Selbst wenn sich Kreaturen in 8 Richtungen bewegen können, erzielen faule BFS, die Knoten bevorzugen, die näher am Ziel sind, dieselben Ergebnisse. A * ist eine Modifikation von Dijkstra, die viel rechenintensiver ist als die Verwendung von BFS.

BFS = O (| V |) angeblich O (| V | + | E |), aber nicht wirklich im Fall einer Top-Down-Karte. A * = O (| V | log | V |)

Wenn wir eine Karte mit nur 32 x 32 Kacheln haben, kostet BFS höchstens 1024 und ein echtes A * kann Sie satte 10.000 kosten. Dies ist die Differenz zwischen 0,5 Sekunden und 5 Sekunden, möglicherweise mehr, wenn Sie den Cache berücksichtigen. Stellen Sie also sicher, dass sich Ihr A * wie ein fauler BFS verhält, der Kacheln bevorzugt, die näher am gewünschten Ziel sind.

Ein * ist nützlich für Navigationskarten, wenn die Kosten für Kanten bei der Entscheidungsfindung wichtig sind. Bei einfachen Overhead-Spielen auf Kachelbasis spielen die Kosten für Kanten wahrscheinlich keine wichtige Rolle. Falls dies der Fall ist (verschiedene Kacheln kosten unterschiedlich), können Sie eine modifizierte Version von BFS ausführen, die Pfade, die durch Kacheln verlaufen, die den Charakter verlangsamen, verschiebt und benachteiligt.

Also ja BFS> A * in vielen Fällen, wenn es um Fliesen geht.