Share
In diesem Tutorial werde ich erklären Vektorfeldfindung und seine Vorteile gegenüber traditionellen Pfadfindungsalgorithmen wie Dijkstra. Ein grundlegendes Verständnis des Dijkstra-Algorithmus und der möglichen Felder wird Ihnen helfen, diesen Artikel zu verstehen, ist jedoch nicht erforderlich.
Pathfinding ist bei vielen Lösungen ein Problem, und jede hat ihre Vor- und Nachteile. Viele Pfadfindungsalgorithmen arbeiten, indem sie für jeden Pfadfinder einen Pfad zum Ziel berechnen. Dies bedeutet, dass die Pfadfindung doppelt so lange dauert, wenn doppelt so viele Pfadfinder berechnet werden. Dies ist in vielen Situationen akzeptabel, aber bei der Arbeit mit Tausenden von Pfadfindern ist ein effizienterer Ansatz möglich.
Bekannt als Vektorfeldfindung, Dieser Ansatz berechnet den Pfad vom Ziel zu jedem Knoten in der Grafik. Um diese Erklärung der Vektorfeldpfadfindung zu verdeutlichen, werde ich den Algorithmus anhand meiner speziellen Implementierung als Beispiel erläutern.
Hinweis: Die Vektorfeldpfadfindung kann allgemein zu Knoten und Graphen abstrahiert werden. Nur weil ich es anhand meines Kachel- und Gitter-basierten Ansatzes erkläre, bedeutet das nicht, dass dieser Algorithmus auf Kacheln beschränkt ist!
Die Vektorfeldpfadfindung besteht aus drei Schritten.
Dieses Video zeigt Ihnen die endgültigen Ergebnisse und gibt Ihnen einen allgemeinen Überblick über die Konzepte, die im folgenden Tutorial dargestellt werden:
Die Heatmap speichert die Wegentfernung vom Ziel zu jedem Feld auf der Karte. Die Wegentfernung unterscheidet sich von der euklidischen Entfernung dadurch, dass sie die Entfernung zwischen zwei Punkten berechnet, die nur durch das befahrbare Gelände gehen. Ein GPS berechnet zum Beispiel immer die Wegentfernung, wobei Straßen das einzige befahrbare Gelände sind.
Unten sehen Sie den Unterschied zwischen der Wegentfernung und der linearen Entfernung vom Ziel (rot markiert) zu einer beliebigen Kachel (rosa markiert). Nicht durchquerbare Kacheln sind grün gezeichnet. Wie Sie sehen, ist die Wegentfernung (gelb dargestellt) 9, während der lineare Abstand (hellblau dargestellt) ungefähr ist 4.12.
Die Zahlen oben links auf jeder Kachel zeigen die Wegentfernung zum Ziel, die vom Heatmap-Generierungsalgorithmus berechnet wird. Beachten Sie, dass es mehr als eine mögliche Wegstrecke zwischen zwei Punkten gibt. In diesem Artikel interessieren wir uns nur für den kürzesten.
Der Heatmap-Generierungsalgorithmus ist a Wellenfrontalgorithmus. Es beginnt am Ziel mit einem Wert von 0, und fließt dann nach außen, um die gesamte durchquerbare Region zu füllen. Der Wellenfrontalgorithmus besteht aus zwei Schritten:
Accentsconagua
0.Der Pfadabstand der vorherigen Kachel + 1.Hinweis: Der Wellenfrontalgorithmus führt einfach eine Breitensuche im Gitter durch und speichert, wie viele Schritte es dauert, um zu jedem Feld auf dem Weg zu gelangen. Dieser Algorithmus wird manchmal auch als bezeichnet Brushfire-Algorithmus.
Nun, da die Wegentfernung von jedem Feld zum Ziel berechnet wurde, können wir leicht den Weg bestimmen, der genommen werden muss, um dem Ziel näher zu kommen. Es ist möglich, dies zur Laufzeit für jeden Pfadfinder für jedes Bild durchzuführen, es ist jedoch oft besser, ein Vektorfeld einmal zu berechnen und dann alle Pfadfinder zur Laufzeit auf das Vektorfeld zu beziehen.
Das Vektorfeld speichert einfach einen Vektor, der an jeder Kachel den Gradienten der Distanzfunktion (in Richtung des Ziels) nach unten zeigt. Hier ist eine Visualisierung des Vektorfelds, wobei die Vektoren vom Mittelpunkt der Kachel auf dem kürzesten Weg zum Ziel zeigen (wieder in rot dargestellt)..
Dieses Vektorfeld wird durch Betrachten der Heatmap einzeln erstellt. Die x- und y-Komponenten des Vektors werden separat berechnet, wie im nachstehenden Pseudocode dargestellt:
Vector.x = left_tile.distance - right_tile.distance Vector.y = up_tile.distance - down_tile.distance
Hinweis: Die Entfernungsvariable jeder Kachel speichert die Wegentfernung zum Ziel, wie durch den Wellenfrontalgorithmus oben berechnet.
Wenn eine der Kacheln (links / rechts / auf / ab), auf die verwiesen wird, nicht befahrbar ist und daher keine nutzbare Entfernung gespeichert ist, wird anstelle der fehlenden Werte die der aktuellen Kachel zugeordnete Entfernung verwendet. Sobald der Pfadvektor grob berechnet wurde, wird er normalisiert, um später Inkonsistenzen zu vermeiden.
Nun, da das Vektorfeld berechnet wurde, ist es sehr einfach, die Bewegung für einen Pfadfinder zu berechnen. Angenommen, vector_field (x, y) gibt den Vektor zurück, den wir zuvor an der Kachel berechnet haben (x, y), und die gewünschte Geschwindigkeit ist ein Skalar, der Pseudocode zum Berechnen der Geschwindigkeit eines Partikels bei einer Kachel (x, y) sieht aus wie das:
Geschwindigkeitsvektor = Vektorfeld (x, y) * gewünschte_Geschwindigkeit
Die Partikel müssen sich lediglich in die durch den Vektor angegebene Richtung bewegen. Dies ist die einfachste Art und Weise, aber kompliziertere Bewegungssysteme können mit Hilfe von Strömungsfeldern leicht implementiert werden.
Zum Beispiel können die unter Grundlegendes Lenkverhalten erläuterten Techniken auf die Bewegung des Suchers angewendet werden. In einer solchen Situation kann der Velocity_Vector Die oben berechneten Werte würden als die gewünschte Geschwindigkeit verwendet, und das Lenkverhalten würde zur Berechnung der tatsächlichen Bewegung in jedem Zeitschritt verwendet.
Bei der Berechnung der Bewegung gibt es manchmal ein Problem, das als bekannt ist lokale optima. Dies tritt auf, wenn es zwei optimale (kürzeste) Pfade gibt, um von einem bestimmten Feld zum Ziel zu gelangen.
Dieses Problem ist in der Abbildung unten zu sehen. Die Kachel (rosa dargestellt) unmittelbar links von der Wandmitte weist einen Pfadvektor auf, dessen Komponenten (x und y) gleich 0 sind.
Lokale Optima führen dazu, dass Pfadfinder stecken bleiben; Sie beziehen sich auf das Vektorfeld, das keine Richtung angeben kann. Wenn dies geschieht, bleiben die Pfadfinder an der gleichen Stelle, wenn keine Korrektur implementiert wird.
Der eleganteste Weg, den ich gefunden habe, um das Problem zu beheben, besteht darin, sowohl die Heatmap als auch das Vektorfeld einmal zu unterteilen. Jede einzelne Heatmap- und Vektorfeld-Kachel wurde jetzt in vier kleinere Kacheln aufgeteilt. Das Problem bleibt bei einem unterteilten Raster dasselbe. es wurde nur geringfügig minimiert.
Der eigentliche Trick, der das lokale Optima-Problem löst, besteht darin, zunächst vier Zielknoten hinzuzufügen, anstatt nur einen. Dazu müssen wir lediglich den ersten Schritt des Heatmap-Generierungsalgorithmus ändern. Wenn wir bisher nur ein Ziel mit einer Wegentfernung von 0 hinzugefügt haben, fügen wir nun die vier Kacheln hinzu, die dem Ziel am nächsten liegen.
Es gibt mehrere Möglichkeiten, die vier Kacheln auszuwählen, aber es ist weitgehend unerheblich, wie sie ausgewählt werden. Solange die vier Kacheln nebeneinander liegen (und durchlaufbar sind), sollte diese Technik funktionieren.
Hier ist der geänderte Pseudocode für die Heatmap-Generierung:
0.Der Pfadabstand der vorherigen Kachel + 1.Und jetzt sind hier die endgültigen Ergebnisse, die deutlich zeigen, dass das lokale Optima-Problem beseitigt wurde:
Obwohl diese Lösung elegant ist, ist sie alles andere als ideal. Die Verwendung von bedeutet, dass die Berechnung der Heatmap und des Vektorfeldes aufgrund der erhöhten Anzahl von Kacheln viermal länger dauert.
Andere Lösungen erfordern, dass von Fall zu Fall geprüft wird, welche Richtung er einschlagen muss, was die Berechnungen der Partikelbewegung erheblich verlangsamt. In meinem Fall war die Unterteilung der Karten die bessere Option.
Hoffentlich haben Sie in diesem Tutorial gelernt, wie Sie zielorientierte Pfadfindung in einer Kachel-basierten Welt implementieren können. Denken Sie daran, dass diese Art der Pfadfindung im Kern einfach ist: Partikel folgen dem Gradienten der Distanzfunktion in Richtung des Ziels.
Die Implementierung ist komplexer, kann jedoch in die folgenden drei verwaltbaren Schritte unterteilt werden:
Ich hoffe, dass die Leute die hier vorgestellten Ideen erweitern. Wenn Sie Fragen haben, können Sie sie gerne in den folgenden Kommentaren stellen!
