Advertisement
  1. Game Development
  2. Programming
Gamedevelopment

So beschleunigen Sie A * Pathfinding mit dem Jump Point Suchalgorithmus

by
Difficulty:IntermediateLength:LongLanguages:

German (Deutsch) translation by Jeane Jade (you can also view the original English article)

Wegfindung ist allgegenwärtig in spielen.  Es ist also wichtig, die Zusammenhänge zu verstehen, die vorhanden sind, wenn die Verwendung von algorithmen wie A*.  In diesem tutorial gehen wir decken eine relativ neue Methode für die Suche grid-basierte Welten: Jump Point Search, welche Beschleunigung Ein* um Größenordnungen. 

 Hinweis: Obwohl dieses tutorial ist geschrieben mit AS3 und Flash, sollten Sie in der Lage, verwenden Sie die gleichen Techniken und Konzepte, die in fast jedem Spiel-Entwicklungsumgebung.

 Diese Umsetzung basiert auf dem original-Papier und-Artikel auf JPS finden Sie hier: Jump Point Search. Die 
 Lua-basierte Implementierung, Jumper, wurde verwendet für die Hilfe mit einigen teilen der Umsetzung.


Jump Point Search-Demo 

 Klicken Sie auf die SWF-um es zu fokussieren, dann bewegen Sie Ihre Maus über non-blocking Gebiete auf der Karte zu haben, die NPCs versuchen, um es zu bekommen. Leertaste zum wechseln zwischen Einer*, Jump Point Search, und beide. 

Kein Flash?  Schauen Sie sich das YouTube-video anstatt: 


Setup 

Die demo-Implementierung, die oben verwendet AS3 und Flash mit dem Starling-Framework für GPU-beschleunigte rendering-und der Polygon-ds-Bibliothek für die Datenstrukturen. 


Wegfindung 

 Wegfindung ist oft in video-Spiele und Sie sind sicher zu stoßen, das es an irgendeinem Punkt während Ihrer Spiele-Entwicklung-Karriere. Seine primäre Verwendung ist, um zu geben, intelligente Suche-Bewegung-Verhalten zu künstlichen Personen (NPCs), um Sie zu vermeiden, stoßen Dinge (oft). 

 In einige der Spiele, die der Spieler-avatar ist auch das Thema Wegfindung (Strategie Spiele, viele Dritte-person-RPGs und adventure Spiele).  So könnte man annehmen, dass das problem der Wegfindung gelöst ist, aber leider ist das nicht der Fall; es gibt keine silberne Kugel, die Sie verwenden können, und nur mit ihm getan werden.

 Und auch in den großen AAA-Spiele, finden Sie noch komische Dinge wie diese:

 Es kann nicht ein Königsweg, sondern es ist eine Kugel: A* (A-star) Algorithmus.  In diesem tutorial werden wir sehen, eine kurze übersicht von A* - und wie es zu beschleunigen mit einem anderen Algorithmus, Jump Point Search.

 Als erstes benötigen wir eine Möglichkeit zur Darstellung unserer Spiel-Welt in einer Weise, dass ein pathfinding-Algorithmus verwenden können.


Welt-Darstellungen 

 Eines der wichtigsten Dinge zu beachten, wenn Sie sich Gedanken über die Wegfindung für Ihr Spiel ist die Welt der Repräsentation.  Wie werden die Daten von der begehbaren Bereiche und Hindernisse organisiert, die mit der Programmierung Strukturen im Speicher?

 Die einfachste Darstellung, die Sie verwenden können, ist eine grid-basierte Struktur, wobei Pfad-Knoten sind organisiert in einem raster und kann dargestellt werden durch ein 2D-array.  Wir verwenden diese Darstellung in diesem tutorial.  Genauer gesagt, es wird ein acht-Wege-raster-Darstellung: eine Bewegung in gerader und diagonaler Richtung.


 Die schwarzen Pixel im Bild repräsentieren die blockierende Zellen.

Ihre Anforderungen können unterschiedlich sein, so dass diese Struktur möglicherweise nicht für Sie.  Gute Sache ist, dass man mit etwas Bearbeitung (in der Regel getan, offline) können Sie ändern Wegfindung Darstellungen in andere Formate.   Alternativen zu grid-basierten Ansatz würde gehören Dinge wie polygon (Hindernisse, vertreten durch Polygone) oder navigation meshes (navigation Flächen mit Polygonen dargestellt); diese vertreten die gleichen Daten mit weniger Knoten.

 Andere Daten, die gespeichert werden können in der map-Darstellung sind die Kosten: wie viel kostet das Reisen von einem Knoten zu einem anderen.  Dies kann verwendet werden, für die AI zu bestimmen, der Pfad, der zum Beispiel bevorzugt Straßen über regelmäßige terrain (was die Kosten von der Straße weniger als das terrain).

 Jump Point Search ist speziell für acht-Wege-grid-basierten map-Darstellung, also werden wir das nutzen. Auch in seiner vanilla form nicht unterstützt gewichtet Karten.   Im letzten Abschnitt werde ich diskutieren einen möglichen Weg, dies zu beheben.)


A* Pathfinding Refresher 

Jetzt haben wir eine Welt, die Darstellung werfen wir einen kurzen Blick auf die Implementierung Eines*.   Es ist ein gewichteter graph search-Algorithmus verwendet Heuristiken (kleine "Hinweise"), wie am besten Suche in der Umgebung von dem Startknoten zu dem Endknoten.

Ich empfehle, dass Sie überprüfen diese Visualisierung von pathfinding-algorithmen: 
PathFinding.js - visual.   Mit ihm spielen kann steigern Sie Ihre intuition, was der Algorithmus eigentlich tut - und es macht Spaß!

Für pathfinding mit A* in rechteckige Gitter, die wir tun, die folgenden: 

 Heuristik ist im wesentlichen so dass eine Vermutung auf die chance, dass der Knoten evaluiert wird zum Ziel führen.  Heuristiken können einen großen Unterschied in der Effizienz der pathfinding-algorithmen, die in der Regel begrenzen die Anzahl der Knoten, die müssen besucht werden.  Gehen wir der Manhattan-Distanz für unsere Zwecke (was bedeutet, dass Knoten, die näher zum Ziel haben wird, eine kleinere Zahl):

Dies ist mehr oder weniger es.   Beenden wir den Algorithmus, wenn wir die Ziel-Knoten, und dann track back mit übergeordneten Variablen von Knoten zu konstruieren, die den Pfad.

 Such-algorithmen können verwendet werden, für andere Dinge auch.  A* ist eine Allgemeine gewichtete graph-search-Algorithmus, die verwendet werden können, die auf diesen Graphen.  Dies kann auf andere Felder im AI -, wie die Suche nach der optimalen Schritte zur Erreichung bestimmter Ziel: eine Bombe werfen, oder führen Sie in Deckung und versuchen, schleichen sich von hinten an einen Feind?

 Im Spiel Entwicklung, die wir brauchen, um Dinge schnell, als die Aktualisierung unserer Spiele bei 60 Bildern pro Sekunde jede Millisekunde zählt.  Obwohl Ein* führt relativ gut für einige Verwendungsmöglichkeiten, es besteht die Notwendigkeit, um es schneller oder weniger Speicher verwenden.


Optimierungen 

 Die Wahl der Darstellung ist die erste Sache, die haben einen Einfluss auf die Wegfindung Leistung und die Wahl des pathfinding-Algorithmus.  Die Größe der Grafik, die gesucht wird, wird eine große Korrelation auf, wie Sie Ihre Wegfindung führt (was Sinn macht; es ist einfacher, Ihren Weg zu finden in Ihrem Zimmer als in einer großen Stadt).

 Dann würden Sie überlegen, höhere level-Optimierungen, die in der Regel mit clustering Daten in kleinere Regionen und dann Suche diese, während Sie später verfeinern Pfade reiste in kleineren Regionen.  Zum Beispiel, wenn Sie wollen, gehen Sie zu einem restaurant in einer benachbarten Stadt, die Sie zuerst berücksichtigen, wie Sie von Ihrer Stadt, und sobald Sie in dieser Stadt Grenzen Sie Ihre "Suche" in den Bereich, wo das restaurant liegt, ignorieren den rest. Dies würde gehören Dinge wie Sümpfe, dead-end-elimination und HPA*. 

Auf der niedrigsten Ebene, die Sie zu tun haben, die suchen.   Sie wählten Ihre Darstellung der Daten und die möglichen Abstraktionen und stecken Sie Sie in einen Algorithmus, werden pick-out-Knoten, Reisen hier und dort die Suche nach dem Ziel.  Diese algorithmen basieren in der Regel auf den A* - Suchalgorithmus mit den möglichen änderungen.  In einfacheren Fällen können Sie Weg mit mit den geraden A*, das bietet Ihnen die Einfachheit.  Ich habe eine grid-basierte Implementierung in die source-download.


Jump Point Search 

 Da dieses tutorial über die Implementierung von Jump Point Search, die Wegfindung graph dargestellt werden, mit einem raster.  Und es konkret werden muss, um ein acht-Wege-Netz, da der Algorithmus direkt verwendet.

 Was Jump Point Search wirklich tut, ist zu beseitigen eine Menge von Zwischenknoten in bestimmter Art raster-Kombinationen.  Er springt ein paar von diesen würden Sie hinzufügen, um die Liste zu öffnen und die geschlossene Liste, wie auch andere Berechnungen, die zu Gunsten der dabei einige weitere Verarbeitung bei der Auswahl der nächsten Knoten.

Wie mit Einer* Holen wir von der offenen Szene der Knoten mit dem niedrigsten F-score.  Aber dies ist, wo die Dinge anfangen, interessant zu werden.   Statt der Kommissionierung die benachbarten Knoten nennen wir diese Funktion für uns tun:

Was dies bedeutet ist beseitigt Knoten, die nicht interessant sind, unseren Weg.   Für diese verwenden wir die Richtung von Eltern-als wichtigste Leitlinie. Hier sind Beispiele der Beschneidung der Knoten, die ignorieren wir für den horizontalen und vertikalen Richtungen: 

Beispiel für eine horizontale beschneiden Situationen. 

Im code wird dies am Ende als eine Serie von if-Anweisungen, die überprüfung für diese Situationen.  Sehen Sie hier das Beispiel, beschreibt den richtigen Fall aus der Bild: 


Beispiel Diagonale beschneiden Situationen. 

 Nachdem wir Holen die Nachbarn versuchen wir finden einen Sprungpunkt, der einen Knoten, die erreicht werden können von der aktuellen, aber nicht unbedingt nur in einer einzigen Weise.  Um es deutlicher zu sagen formal, was die JPS macht, ist zu beseitigen Symmetrie zwischen Pfade - jeder hat eine andere permutation des gleichen moves:


Pfad Symmetrie Beispiel. 

Also für große, offene Räume, die wir haben können, riesige Gewinne zu.  Hier ist, wie der Sprung-Methode funktioniert: 

 Ich habe entfernt die erzwungene Nachbar-checks aus dem if-Anweisungen, da Sie Recht groß ist.  Sie bestehen im wesentlichen aus Schecks, die ähnlich sind zu denen, wenn wir zuerst abgeholt Nachbarn für einen neuen Knoten (die Menge von Tests, um zu sehen, wenn die Zellen gesperrt sind).  Sie dienen dem Zweck der Erkennung, wenn wir berechtigt sind, unsere Annahmen über die Symmetrie.


Beispiel der Sprung-Funktion Verhalten. 

 Die Diagonale ist ein besonderer Fall, und wir müssen schauen Sie nicht nur gezwungen Nachbarn in den diagonalen Richtungen, aber in der horizontalen und vertikalen Richtungen, und wenn diese fehlschlagen, haben wir uns zu stellen gezwungen Knoten als ein Punkt springen.  Wir müssen auch überlegen, ein spezieller Fall von Ziel-Knoten, wo Sie den Sprung-Methode beendet.

 Jedes mal, wenn wir nicht finden, eine Suche nach Knoten nennen wir die jump-Funktion rekursiv in der angegebenen Richtung. In der demo habe ich tatsächlich ausgerollt, dieses rekursiven Aufrufs, da diese aufgerufen wird, eine Menge.   (In meinen Tests, diese verbesserte Leistung durch einen Faktor von zwei.)

 Dies ist, was die JPS hat; das Ergebnis ist der neue Knoten für den A* zu prüfen, und wir gehen mit dem Algorithmus. Wenn der Ziel-Knoten gefunden wird, rekonstruieren wir den Pfad und gibt ihn zurück. 


Eigenschaften 

 JPS kann überspringen eine Menge von Knoten, bei der Suche, die kann schöne Verbesserungen in der Geschwindigkeit (in meinem Projekt ist es etwa 30x mehr Ein*), aber es kommt mit einem Preis. 

Es funktioniert am besten auf einem einheitlichen raster, sondern können arbeiten gemacht werden, die mit nicht-Uniformen mit zusätzlichen Optimierungen, Kennzeichnung Nachbarn gezwungen, wo es einen übergang zu einem Knoten verschiedene Kosten (am besten verwenden Sie diskrete Kosten). 

In einem Spiel, In dem ich arbeite, wird das raster gleichmäßig ist außer für Straßen, die Kosten viel weniger als zu Fuß auf regelmäßige terrain.  (Es sieht viel besser aus, wenn der Charakter, der respektiert, dass.)  Am Ende habe ich dies Problem gelöst, indem precomputing einige Werte der Straße Positionen.   Bei der Wegfindung ist eingeleitet, der Algorithmus sucht möglich die nächsten Punkte auf dem Weg von der start-und Ziel-Knoten, und sucht dann in einem speziellen high-level-Diagramm der Straßen (die vorausberechnete), und verwendet dann JPS zu suchen, Gelände, Gebiete.


Debugging 

Eine kurze Notiz über das Debuggen.   Das Debuggen dieser Art von algorithmen kann sehr schwierig sein, und es ist fast sicher, dass die erste Implementierung wird einige schwer zu finden Fehler.  Sie können tun Sie sich selbst einen gefallen und bauen eine Art der Visualisierung funktionell und zeichnen, was passiert, wenn der Algorithmus ausgeführt wird.

 Wenn Sie einen Fehler, sollten Sie reduzieren Sie die domain (grid size), um die minimale, mit der Sie Ihr problem reproduzieren und von dort zu testen. Wie Sie sich wahrscheinlich denken können, ist meine erste Umsetzung von JPS hat nicht funktioniert sofort! 

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.