Share
Pathfinding ist in Spielen allgegenwärtig. Daher ist es wichtig, die Auswirkungen zu verstehen, die bei der Verwendung von Algorithmen wie A * auftreten. In diesem Tutorial behandeln wir eine relativ neue Methode zum Durchsuchen von gitterbasierten Welten: Sprungpunktsuche, was A * um Größenordnungen beschleunigen kann.
Hinweis: Obwohl dieses Tutorial mit AS3 und Flash geschrieben wurde, sollten Sie in der Lage sein, in fast jeder Spieleentwicklungsumgebung dieselben Techniken und Konzepte anzuwenden.
Diese Implementierung basiert auf der Originalarbeit und dem Artikel zu JPS, die Sie hier finden: Jump Point Search. Das
Die lua-basierte Implementierung, Jumper, wurde zur Unterstützung bei einigen Teilen der Implementierung verwendet.
Klicken Sie auf die SWF-Datei, um den Fokus zu erhalten. Bewegen Sie dann die Maus über nicht blockierende Bereiche der Karte, damit die NPCs versuchen, darauf zuzugreifen. Drücken Sie die Leertaste, um zwischen A *, Jump Point-Suche und beiden zu wechseln.
Kein Blitz? Schauen Sie sich stattdessen das YouTube-Video an:
Die obige Demo-Implementierung verwendet AS3 und Flash mit Starling Framework für GPU-beschleunigtes Rendering und die polygonal-ds-Bibliothek für Datenstrukturen.
Pathfinding wird häufig in Videospielen verwendet, und Sie werden mit Sicherheit irgendwann während Ihrer Karriere in der Spieleentwicklung darauf stoßen. Seine hauptsächliche Verwendung besteht darin, künstlichen Entitäten (NPCs) ein intelligent aussehendes Bewegungsverhalten zu geben, um zu vermeiden, dass sie auf Dinge stoßen (oft)..
In einigen Spielen ist auch der Spieleravatar Pfadfindern ausgesetzt (Strategiespiele, viele Third-Person-RPGs und Abenteuerspiele). Man könnte also annehmen, dass das Problem der Pfadfindung gelöst ist, aber das ist leider nicht der Fall. Es gibt keine silberne Kugel, die Sie verwenden können und einfach damit fertig werden.
Und selbst in großen AAA-Spielen finden Sie immer noch lustige Dinge wie diese:
Es kann keine Silberkugel geben, aber es gibt eine Kugel: den A * (A-Stern) -Algorithmus. In diesem Tutorial wird ein kurzer Überblick über A * und die Beschleunigung mit einem anderen Algorithmus, der Sprungpunktsuche, gegeben.
Zuerst brauchen wir einen Weg, um unsere Spielwelt so darzustellen, dass ein Wegfindungsalgorithmus sie verwenden kann.
Eines der wichtigsten Dinge, die zu berücksichtigen sind, wenn Sie über die Pfadfindung für Ihr Spiel nachdenken Weltdarstellung. Wie sind die Daten der passierbaren Bereiche und Hindernisse mit Programmierstrukturen im Speicher organisiert??
Die einfachste Darstellung, die Sie verwenden können, ist eine gitterbasierte Struktur, in der Pfadknoten in einem Gitter angeordnet sind und durch ein 2D-Array dargestellt werden können. Wir werden diese Darstellung in diesem Tutorial verwenden. Im Einzelnen handelt es sich dabei um eine Darstellung mit acht Wegen: Erlaubt die Bewegung in geraden und diagonalen Richtungen.
Ihre Anforderungen können unterschiedlich sein, daher passt diese Struktur möglicherweise nicht zu Ihnen. Die gute Sache ist, dass Sie bei der Verarbeitung (normalerweise offline) die Darstellung der Pfadfindung in andere Formate ändern können. Alternativen zum gitterbasierten Ansatz umfassen Dinge wie Polygone (Hindernisse, die durch Polygone dargestellt werden) oder Navigationsnetze (Navigationsbereiche, die durch Polygone dargestellt werden); diese können dieselben Daten mit weniger Knoten darstellen.
Weitere Daten, die in der Kartendarstellung gespeichert werden können, sind Kosten: Wie viel kostet es, von einem Knoten zum anderen zu reisen. Dies kann für die KI verwendet werden, um den Pfad zu bestimmen, der zum Beispiel Straßen gegenüber normalem Gelände bevorzugt (wodurch die Kosten der Straße niedriger sind als das Gelände)..
Die Jump Point-Suche ist speziell für die Darstellung von Karten mit acht Wegen ausgelegt, daher werden wir diese verwenden. In seiner Vanilleform unterstützt es auch keine gewichteten Karten. (Im letzten Abschnitt werde ich einen möglichen Weg beschreiben, um Abhilfe zu schaffen.)
Jetzt haben wir eine Weltrepräsentation. Schauen wir uns kurz die Implementierung von A * an. Hierbei handelt es sich um einen gewichteten Graph-Suchalgorithmus, der Heuristiken (kleine "Hinweise") verwendet, um den Bereich vom Startknoten bis zum Endknoten am besten zu durchsuchen.
Ich empfehle Ihnen dringend, sich diese Visualisierung von Wegfindungsalgorithmen anzusehen:
PathFinding.js - visuell. Mit ihm zu spielen kann Ihre Intuition dessen, was der Algorithmus tatsächlich tut, steigern - und es macht Spaß!
Für die Pfadfindung mit A * in rechteckigen Gittern gehen wir folgendermaßen vor:
1. Suchen Sie den Knoten, der Ihrer Position am nächsten ist, und geben Sie ihn als Startknoten an, und setzen Sie ihn in die offene Liste. 2. Während sich Knoten in der offenen Liste befinden: 3. Wählen Sie den Knoten aus der offenen Liste mit der kleinsten F-Bewertung aus. Setzen Sie es in die geschlossene Liste (Sie möchten es nicht noch einmal in Betracht ziehen). 4. Für jeden Nachbarn (benachbarte Zelle), der nicht in der geschlossenen Liste enthalten ist: 5. Setzen Sie den übergeordneten Knoten auf den aktuellen Knoten. 6. Berechnen Sie den G-Score (Entfernung vom Startknoten zu diesem Nachbarn) und fügen Sie ihn der offenen Liste hinzu. 7. Berechnen Sie den F-Score, indem Sie dem G-Wert Heuristiken hinzufügen.zusammenhängende Posts
Die Heuristik geht im Wesentlichen davon aus, dass der zu bewertende Knoten zum Ziel führt. Heuristiken können einen großen Unterschied in der Effizienz von Pfadfindungsalgorithmen ausmachen, da sie dazu neigen, die Anzahl der Knoten, die besucht werden müssen, zu begrenzen. Wir werden die Manhattan-Distanz für unsere Zwecke verwenden (dh Knoten, die näher am Ziel sind, haben eine geringere Anzahl):
private Funktion manhattanDistance (start: Node, end: Node): int return Math.abs (end.x - start.x) + Math.abs (end.y - start.y);
Das ist mehr oder weniger es. Wir stoppen den Algorithmus, wenn wir den Zielknoten gefunden haben, und verfolgen dann den Pfad mithilfe der Elternvariablen des Knotens.
Suchalgorithmen können auch für andere Zwecke verwendet werden. Ein * ist ein allgemein gewichteter Graph-Suchalgorithmus und kann für jeden solchen Graphen verwendet werden. Dies kann andere Felder in der KI abdecken, z. B. die Suche nach den optimalen Schritten, um ein bestimmtes Ziel zu erreichen: Werfen Sie eine Bombe oder suchen Sie nach Schutz und versuchen Sie, sich hinter einen Feind zu schleichen?
Bei der Spieleentwicklung müssen wir schnell vorgehen, wenn wir unsere Spiele mit 60 Frames pro Sekunde pro Millisekunde aktualisieren. Obwohl A * für einige Anwendungen einigermaßen gut funktioniert, besteht die Notwendigkeit, es schneller zu machen oder weniger Speicher zu verwenden.
Die Wahl der Repräsentation ist das Erste, was sich auf die Pfadfindungsleistung und die Wahl des Pfadfindungsalgorithmus auswirkt. Die Größe des gesuchten Graphen hat einen großen Zusammenhang in Bezug auf die Leistung Ihrer Pfadfindung (was sinnvoll ist; es ist einfacher, sich in Ihrem Zimmer zurechtzufinden als in einer Großstadt)..
Dann würden Sie Optimierungen auf höherer Ebene in Betracht ziehen, die normalerweise das Clustering von Daten in kleinere Regionen und das anschließende Durchsuchen dieser umfassen, während Sie später die Pfade in bereisten kleineren Regionen verfeinern. Wenn Sie beispielsweise zu einem Restaurant in einer benachbarten Stadt gehen möchten, müssen Sie zunächst überlegen, wie Sie von Ihrer Stadt zu dieser gelangen. Sobald Sie sich in dieser Stadt befinden, beschränken Sie Ihre Suche auf den Bereich, in dem sich das Restaurant befindet den Rest ignorierend. Dazu gehören beispielsweise Sümpfe, Sackgassenbeseitigung und HPA *..
Auf der untersten Ebene müssen Sie die Suche durchführen. Sie wählen Ihre Datenrepräsentation und mögliche Abstraktionen aus und fügen sie in einen Algorithmus ein, der Knoten auswählt, hin und her geht und nach dem Ziel sucht. Diese Algorithmen basieren normalerweise auf dem A * -Suchalgorithmus mit möglichen Modifikationen. In einfacheren Fällen können Sie mit Straight A * davonkommen, was Ihnen die Einfachheit bietet. Ich habe eine gridbasierte Implementierung im Quellendownload bereitgestellt.
Da es sich bei diesem Lernprogramm um die Implementierung der Jump Point-Suche handelt, wird der Pfadfindungsgraph mit einem Raster dargestellt. Es muss insbesondere ein Acht-Wege-Gitter sein, da der Algorithmus es direkt verwendet.
Bei der Jump Point-Suche werden in einer bestimmten Art von Gitterkombinationen viele Zwischenknoten eliminiert. Es werden einige davon übersprungen, die Sie der offenen Liste und der geschlossenen Liste hinzufügen würden, sowie andere Berechnungen, um bei der Auswahl des nächsten Knotens eine weitere Verarbeitung vorzunehmen.
Wie bei A * wählen wir aus der offenen Szene den Knoten mit dem niedrigsten F-Score aus. Aber hier beginnt es interessant zu werden. Anstatt benachbarte Knoten auszuwählen, rufen wir diese Funktion auf, um dies für uns zu tun:
Funktion defineSuccessors (aktuell: Knoten, Start: Knoten, Ende: Knoten): Vektor.var Nachfolgern: Vektor. = neuer Vektor. (); var Nachbarn: Vektor. = nodeNeighbours (aktuell); für jeden (var-Nachbarn: Knoten in Nachbarn) // Richtung vom aktuellen Knoten zum Nachbarn: var dX: int = clamp (neighbour.x - current.x, -1, 1); var dY: int = Klemme (Nachbar.y - Strom.y, -1, 1); // Versuchen Sie, einen Knoten zu finden, zu dem Sie springen möchten: var jumpPoint: Node = jump (current.x, current.y, dX, dY, start, end); // Wenn gefunden, füge es der Liste hinzu: if (jumpPoint) successors.push (jumpPoint); Nachfolger zurückgeben;
Dadurch werden Knoten eliminiert, die für unseren Pfad nicht interessant sind. Hierfür verwenden wir die Richtung vom Elternteil als Hauptrichtlinie. Hier sind Beispiele für das Beschneiden der Knoten, die für horizontale und vertikale Richtungen ignoriert werden:
Beispiel für eine horizontale Beschneidung.
Im Code endet dies als eine Reihe von ob Anweisungen, die auf diese Situationen prüfen. Sie können das Beispiel hier sehen und den richtigen Fall aus dem Bild beschreiben:
if (directionY == 0) if (! _world.isBlocked (current.x + directionX, current.y)) if (_world.isBlocked (current.x, current.y + 1)) // Einen Knoten erstellen mit der neuen Position neighbours.push (Node.pooledNode (current.x + directionX, current.y + 1));
Nachdem wir den Nachbarn ausgewählt haben, versuchen wir einen Sprungpunkt zu finden, einen Knoten, der vom aktuellen Punkt aus erreichbar ist, jedoch nicht notwendigerweise nur auf eine einzige Weise. Um es formal zu sagen: JPS beseitigt die Symmetrie zwischen Pfaden - jeder hat eine unterschiedliche Permutation der gleichen Bewegungen:
Für große Freiflächen können wir also große Gewinne erzielen. So funktioniert die Sprungmethode:
Funktionssprung (cX: int, cY: int, dX: int, dY: int, Start: Knoten, Ende: Knoten): Knoten // cX, cY - Aktuelle Knotenposition, dX, dY - Richtung // Position von new Knoten, den wir betrachten werden: var nextX: int = cX + dX; var nextY: int = cY + dY; // Wenn es blockiert ist, können wir hier nicht springen, wenn (_world.isBlocked (nextX, nextY)) null zurückgibt; // Wenn der Knoten das Ziel ist, gib es zurück falls (nextX == end.x && nextY == end.y) return new Node (nextX, nextY); // Diagonalfall if (dX! = 0 && dY! = 0) if (/ *… Diagonal Forced Neighbor Check… * /) return Node.pooledNode (nextX, nextY); // In horizontaler und vertikaler Richtung auf erzwungene Nachbarn prüfen // Dies ist ein Sonderfall für diagonale Richtung, wenn (Sprung (nextX, nextY, dX, 0, Anfang, Ende)! = Null || jump (nextX, nextY, 0 , dY, start, end)! = null) return Node.pooledNode (nextX, nextY); else // Horizontaler Fall if (dX! = 0) if (/ *… Horizontal Forced Neighbor Check… * /) return Node.pooledNode (nextX, nextY); /// Vertikaler Fall else if (/ *… Vertical Forced Neighbour Check… * /) return Node.pooledNode (nextX, nextY); /// Wenn kein erzwungener Nachbar gefunden wurde, versuchen Sie den nächsten Sprungpunkt-Sprung (nextX, nextY, dX, dY, start, end);
Ich habe die erzwungenen Nachbarschaftsprüfungen aus den if-Anweisungen entfernt, da sie ziemlich groß sind. Sie bestehen im Wesentlichen aus Prüfungen, die denen ähneln, als wir zum ersten Mal Nachbarn für einen neuen Knoten ausgewählt haben (viele Prüfungen, um zu sehen, ob Zellen blockiert sind). Sie dienen dazu, herauszufinden, wann wir unsere Annahmen zur Symmetrie haben dürfen.
Der diagonale Fall ist etwas Besonderes, und wir müssen nicht nur nach erzwungenen Nachbarn in diagonaler Richtung suchen, sondern auch in horizontaler und vertikaler Richtung. Wenn einer dieser Bereiche fehlschlägt, müssen wir einen erzwungenen Knoten als Sprungpunkt setzen. Wir müssen auch einen Sonderfall des Zielknotens berücksichtigen, bei dem die Sprungmethode endet.
Jedes Mal, wenn wir keinen Suchknoten finden, rufen wir die Sprungfunktion rekursiv in die angegebene Richtung auf. In der Demo habe ich diesen rekursiven Aufruf tatsächlich abgewickelt, da dieser häufig aufgerufen wird. (In meinen Tests verbesserte sich die Leistung um den Faktor zwei.)
Das macht JPS. Das Endergebnis sind neue Knoten, die A * prüfen soll, und wir fahren mit dem Algorithmus fort. Wenn der Zielknoten gefunden wird, rekonstruieren wir den Pfad und geben ihn zurück.
JPS kann bei der Suche eine Vielzahl von Knoten überspringen, was zu guten Geschwindigkeitsverbesserungen führen kann (in meinem Projekt sind es etwa 30x über A *), was jedoch mit Kosten verbunden ist.
Es funktioniert am besten mit einem einheitlichen Raster, kann aber durch zusätzliche Anpassungen mit Uniformen arbeiten, wobei Nachbarn als erzwungen bezeichnet werden, wenn ein Übergang zu einem Knoten mit unterschiedlichen Kosten erfolgt (am besten, diskrete Kosten zu verwenden)..
In einem Spiel, an dem ich gerade arbeite, ist das Raster einheitlich, mit Ausnahme von Straßen, die viel weniger kosten als das Gehen auf normalem Gelände. (Es sieht viel besser aus, wenn der Charakter das respektiert.) Am Ende habe ich dies gelöst, indem ich einige Werte der Straßenpositionen vorberechnet habe. Wenn die Pfadfindung initiiert wird, sucht der Algorithmus nach möglichen Anfangspunkten vom Pfad aus den Start- und Zielknoten. Anschließend durchsucht er einen speziellen übergeordneten Graphen von Straßen (der vorberechnet ist), und verwendet dann JPS zum Durchsuchen von Geländebereichen.
Eine kurze Anmerkung zum Debuggen. Das Debuggen dieser Art von Algorithmen kann sehr schwierig sein, und es ist fast sicher, dass die erste Implementierung einen schwer zu findenden Fehler haben wird. Sie können sich selbst einen Gefallen tun und eine Art Visualisierung funktional erstellen und zeichnen, was bei der Ausführung des Algorithmus passiert.
Wenn Sie einen Fehler erhalten, sollten Sie die Domäne (Rastergröße) auf das Minimum reduzieren, mit dem Sie Ihr Problem reproduzieren und von dort aus testen können. Wie Sie sich vermutlich denken können, funktionierte meine erste Implementierung von JPS nicht sofort!
Accentsconagua