- Um in einem 8-Bit-Top-down-Spiel im Stil von Zelda Monsterverfolgung umzusetzen, reicht einfache Bewegung in gerader Linie nicht aus; der Beitrag vergleicht Dijkstra und A* und sucht nach den passenden Kompromissen fürs Pathfinding in Spielen
- Bewegung in gerader Linie bleibt an Wänden hängen, aber mit Wall-Sliding kann sich die Figur an Wänden entlangbewegen; das verbessert das Spielgefühl und ermöglicht zugleich strategische Elemente, bei denen Monster im Gelände festgesetzt werden
- Der Dijkstra-Algorithmus garantiert den kürzesten Pfad, durchsucht aber breit die Umgebung des Startknotens und berechnet in Spielen, in denen sich das Ziel in jedem Frame ändert, deutlich mehr als nur die benötigte nächste Richtung
- A* priorisiert die Suche anhand der Entfernung zum Ziel, betrachtet zuerst die Zielrichtung und kann bei einer Wand durch Untersuchung benachbarter Knoten einen Umweg finden, ohne bereits besuchte Knoten erneut zu besuchen
- Auf Spielkarten lassen sich Geschwindigkeit und Implementierungsaufwand mit einem impliziten Graphen, der keine Nachbarschaftslisten vorab erstellt, tilebasierter Suche und geometriebasierten Heuristiken wie einer Begrenzung der Iterationstiefe steuern
Spielkontext und Grundanforderungen
- In einem 8-Bit-Top-down-Spiel im Zelda-Stil auf Basis von PPU466 sollten Monster den Spieler verfolgen
- PPU466 hat ähnlich wie Fantasy-Konsolen à la PICO-8 Einschränkungen wie 8-Bit-Grafik, 4 Farben pro Tile, feste Hintergründe und eine geringe Anzahl von Sprites
- Ziel war, dass Monster dem Spieler folgen, ohne einfach an Wänden stehenzubleiben oder auf unerwünschte Weise festzusitzen
Bewegung in gerader Linie und Wall-Sliding
- Der einfachste Ansatz ist, eine Gerade zwischen Monster und Spieler zu ziehen und das Monster in diese Richtung zu bewegen
- Nutzt man nur diese Methode, bleibt das Monster stehen, sobald es eine Wand berührt
- Mit Wall-Sliding bleibt es beim Zusammenstoß mit einer Wand nicht stehen, sondern bewegt sich an der Wand entlang
- Bei der Spielerbewegung ist das eine Technik, die die Steuerung in der Nähe von Wänden und Ecken reaktionsschneller macht und in fast allen Spielen verwendet wird
- Sie wird seit Pac-Man eingesetzt; Pac-Man Championship Edition DX+ fügt einen Funkeneffekt hinzu, wenn der Spieler an einer Wand entlanggleitet
- Kombiniert man Bewegung in gerader Linie mit Wall-Sliding, kann man Monster in bestimmten Geländeformen festsetzen
- Manche Spiele nutzen das als strategisches Element; Runescapes Safespotting ist ein Beispiel
- In diesem Spiel war das nicht das gewünschte Verhalten, daher wurden echte Pathfinding-Algorithmen betrachtet
Grenzen des Dijkstra-Algorithmus
- Der Dijkstra-Algorithmus ist intuitiv zu implementieren und garantiert den kürzesten Pfad
- Das Problem ist, dass er viel mehr Arbeit verrichtet als nötig
- Er findet die kürzesten Pfade vom Startknoten zu allen anderen Knoten im Graphen
- Zwar kann man stoppen, sobald der Zielknoten gefunden ist, aber es gibt keine Möglichkeit, die Suche in Richtung eines bestimmten Ziels zu lenken
- In Videospielen bewegt sich der Spieler ständig, daher ändert sich das Ziel des Monsters in jedem Frame
- Was das Monster braucht, ist weniger der gesamte Pfad als vielmehr die Information, in welche Richtung es sich jetzt bewegen soll
- Man könnte die kürzesten Pfade für jedes Pixel oder Tile der Karte vorab berechnen, würde dafür aber viel Speicher benötigen
- Auf Legacy-Plattformen oder ressourcenbeschränkten Plattformen ist Dijkstra daher ungeeignet
Warum A* gut zum Pathfinding in Spielen passt
- Der A*-Suchalgorithmus verwendet die Distanzinformation vom Startknoten zum Ziel, um die Suchpriorität festzulegen
- Im ersten Schritt versucht er bevorzugt die Richtung, die direkt zum Ziel führt
- Anders als Dijkstra verbringt er nicht viel Zeit mit der Suche in die entgegengesetzte Richtung, wenn das nicht nötig ist
- Wenn eine Wand den Weg blockiert, untersucht er umliegende Knoten, um die Wand zu umgehen
- Da er wie Dijkstra bereits gesehene Knoten nicht erneut besucht, kann er auch dann letztlich einen Umweg finden, wenn viel Zurückgehen nötig ist
- Im Beispiel bleibt ein Monster, das A* verwendet, nicht hinter einer Wand gefangen
Implizite Graph-Datenstruktur
- Lehrbuchartige Graphen werden als Knotenliste plus Adjazenzmatrix oder Adjazenzliste dargestellt, in Spielen lassen sich benachbarte Knoten jedoch flexibler erzeugen
- Beispielsweise kann man auf einem Bildschirm mit 256×240 Pixeln jede Pixelkoordinate als einen Knoten betrachten
- Benachbarte Pixel liegen in 8 Richtungen: oben, unten, links, rechts sowie den vier Diagonalen
- Die Kosten für horizontale und vertikale Bewegung betragen 1, die Kosten für diagonale Bewegung √2, also etwa 1,4
- Statt eine riesige Adjazenzliste vorab zu erstellen, kann man sie nur für tatsächlich besuchte Knoten ad hoc erzeugen
- Pixel, die auf einer Wand liegen oder von einem anderen Sprite belegt sind, sind keine gültigen Monsterpositionen und werden daher dynamisch aus der Adjazenzliste ausgeschlossen
- Mit diesem Ansatz muss man im Map-Editor nicht manuell nicht erreichbare Knoten ausschließen
Heuristiken, die die Geometrie der Karte berücksichtigen
- Einige Elemente von A* lassen sich direkt an die geometrische Struktur der Karte anpassen
-
Schrittgröße
- Statt Pixel als Knoten zu verwenden, kann man in 2D-tilebasierten Spielen Tiles als Knoten verwenden
- Die Suche auf Tile-Ebene reduziert die Zahl der Iterationen bis zum Pfad zum Spieler deutlich und macht die Suche schneller
- In diesem Fall ist der Pfad weniger eine exakte Liste von Bewegungen pro Frame als vielmehr eine Sequenz von Richtungen, in die das Monster gehen soll
- Monster bewegen sich normalerweise nicht mit einer Geschwindigkeit von 1 Tile pro Frame, daher ist auch bei einem tilebasierten Pfad die tatsächlich benötigte Information die Richtung, in der der Spieler erreichbar ist
- Pixelbasierte Pfade haben denselben Charakter, und das Monster bewegt sich möglicherweise nicht mit 1 Pixel pro Frame oder in ganzzahligen Pixelschritten
-
Iterationstiefe
- Wenn bei A* ein Knoten aus der Priority Queue entnommen wird, ist dieser Knoten der letzte Schritt des besten bisher gefundenen Pfads
- Stoppt man den Algorithmus nach einer festen Anzahl von Iterationen, erhält man den derzeit besten geschätzten Pfad zum kürzesten Pfad bis zum Ziel
- Auch ohne den Algorithmus vollständig auszuführen, kann man eine sinnvolle Bewegungsrichtung erhalten
- Die maximale Iterationstiefe muss an die Geometrie des Levels angepasst werden
- Ist die Tiefe zu gering, kann das Monster weiterhin hinter einer Wand festhängen
- Im Beispiel bleibt das Monster bei einer festen Tiefe von 30 Tiles je nach Spielerposition stecken und kommt nicht voran
- Da A* in jedem Frame neu berechnet wird, können Schleifen entstehen
- Im ersten Frame, in dem es die Wand erreicht, berechnet es, dass es nach unten gehen soll
- Im nächsten Frame berechnet es, dass es nach oben gehen soll
- Durch diese Wiederholung bleibt das Monster in einer Schleife gefangen
- Wenn der Spieler in den Suchbereich des Monsters gerät, kann es den richtigen Pfad finden
- Bei einer festen Tiefe von
1tritt dieses Phänomen noch extremer auf: Das Monster kehrt ständig zu dem Pixel zurück, das die kürzeste euklidische Distanz zum Spieler hat
Kompromiss durch Vorberechnung
- Für eine ausgefeiltere Lösung kann man für jede Position auf der Karte vorab die maximale Tiefe berechnen, die A* benötigt, um einen Pfad zu finden
- Anders als bei einer Dijkstra-artigen Vorberechnung aller Pfade muss nur dieser eine Maximalwert gespeichert werden
- Ist diese maximale Tiefe gegeben, kann A* in Echtzeit einen gültigen Pfad finden
1 Kommentare
Hacker-News-Kommentare
Tricks, die ich in einem Produktions-MMO für A* verwendet habe: 1) Mit einem hierarchischen Graphen wie Stadt-Ebene, zwischen Räumen in Gebäuden und innerhalb von Räumen kann man selbst zwischen Punkten in irgendeinem Raum irgendeines Gebäudes irgendeiner Stadt in einem Bruchteil einer Millisekunde suchen
2) Wenn man die Metadaten der aktuellen A*-Suche direkt im Graphknoten selbst speichert, muss man kein separates assoziatives Array pflegen
3) Statt dem resultierenden Pfad stumpf zu folgen, ist es besser, ihn als Eingabe für ein Steering-Verhalten zu nutzen, das versucht, wann immer möglich die Ecke zum nächsten Pfadknoten abzuschneiden. Wenn es ein Pfad zu einem anderen Charakter ist, lässt man den Zielcharakter „Brotkrumen“ fallen und fügt sie dem Pfad hinzu, wenn seine neue Position nicht mehr in gerader Linie vom letzten Knoten des Pfads erreichbar ist
2b) Das wird in eine 16-Bit-Bitmaske komprimiert. 8 Stücke à 2 Bit, also 8 Richtungen, und in einer Hash-Tabelle gespeichert
2c) Jedes Bit-Stück hat vier Zustände: FULL_BLOCK (Wand), HARD_BLOCK (großes Objekt, das das Passieren der Kachel aus keiner Richtung erlaubt), SOFT_BLOCK (kleines Objekt, das das Passieren an einer Ecke verhindert), NO_BLOCK (leere Kachel oder Kachel mit sehr kleinem Objekt)
Dadurch müssen Einheiten im Gebäude bei der Pfadsuche nicht für jede Kachel auf Hindernisse prüfen. Wenn ein Objekt nicht riesig ist und durch seine Rotation weder die Eingangs- noch die Ausgangsecke blockiert, kann man auch eine Kachel mit Objekt durchqueren. Und schließlich können Agenten sogar durch Wände gehen, damit die Simulation nicht kaputtgeht, etwa wenn der Spieler vergisst, Türen zu platzieren
https://store.steampowered.com/app/2287430/Metropolis_1998/
Solange sich ein Charakter innerhalb dieser „Blase“ befindet, kann man Kollisionsprüfungen mit der Welt komplett überspringen
Im Studium habe ich nicht verstanden, warum A* in RTS so schwierig ist, aber nachdem ich die Erklärung gelesen hatte, dass sich alles Bewegliche ständig neu einen Pfad suchen muss, um nicht durch andere Einheiten hindurchzugehen, habe ich plötzlich wieder mehr Respekt vor Command & Conquer bekommen
Ich persönlich würde das vermeiden, wenn es keinen sehr guten Grund dafür gibt
Um eine in Scala geschriebene Quoridor-AI zu beschleunigen, habe ich viel über schnelles Pathfinding nachgedacht, und das sind die Tricks, die ich gelernt habe
MPAA (Multi-Path Adaptive A*) ist gut in Situationen, in denen Hindernisse hinzukommen und man denselben Bereich mehrfach neu durchsuchen muss. Man kann Ergebnisse früherer Suchen einspeisen, um die Pfadsuche zu beschleunigen
JPS (Jump Point Search) ist theoretisch attraktiv, weil sich die Zahl der zu betrachtenden „Knoten“ stark reduzieren lässt, aber der Overhead für das Finden der Jump Points war so hoch, dass es in der Praxis keinen Geschwindigkeitsgewinn gab. Vielleicht gibt es einen Weg, die Ideen von MPAA und JPS zu kombinieren, aber wenn man kreativ an Algorithmen herumschraubt, schießt man sich wegen kleiner konzeptioneller Details leicht selbst ins Bein. Zum Beispiel kann die Verwendung von
>statt>=in manchen Fällen dazu führen, dass der echte kürzeste Pfad nicht garantiert wirdBeim Speichern offener Knoten lohnt sich statt eines richtigen Heaps auch eine Bucket Priority Queue, wenn der maximale Prioritätswert eine relativ kleine Ganzzahl ist. Da das interne Array per Priorität indiziert wird, sind Einfügen und Entnehmen ziemlich schnell
Quoridor wird auf einem 9x9-Gitter gespielt, und wiederholtes Pathfinding ist unverzichtbar, um zu beurteilen, wie nah Spieler ihrem Ziel sind und ob das Ziel überhaupt erreichbar ist. Um mögliche Züge aus einer bestimmten Position zu bestimmen, muss man prüfen, dass nicht jeder Zug das Erreichen des Ziels unmöglich macht. Ich plane eine Veröffentlichung in einigen Monaten, mit mindestens drei Entscheidungs-„Engines“: mtdf (eine Minimax-Variante), MCTS (eine parallele Version mit ein paar Tricks) und ein Hybrid mit catboost
Das Schöne daran ist, dass man das als Lookup-Tabelle für die Heuristikfunktion verwenden kann statt der normalen Luftliniendistanz. Zum Beispiel könnte man diese Tabelle zu Beginn jedes Zugs mit dem Floyd-Warshall-Algorithmus initialisieren, sodass bereits gesetzte Wände berücksichtigt werden. Ich habe diese Technik bei einem ähnlichen Problem eingesetzt und A* damit ziemlich deutlich beschleunigt, und sie war sehr simpel. Allerdings war es reines A* ohne MPAA oder JPS
Vor einigen Jahren habe ich der JPS-Implementierung von PathFinding.js eine Funktion hinzugefügt, die die rekursive Suche nach Jump Nodes visualisiert. Die Online-Demo ist hier: https://qiao.github.io/PathFinding.js/visual/
Wenn es mehr als einen Gegner gibt, kann es aus Sicht des Spielers günstiger sein, einfach einmal Dijkstra laufen zu lassen und dann jeden Monster den optimalen Pfad zum Spieler nachschlagen zu lassen
Die Rechenkosten werden dadurch besser vorhersagbar, wenn sich die Zahl der Monster ändert
Das Problem mit der zu geringen Tiefe in der letzten Animation wirkt wie ein interessantes Verhalten. Es sieht so aus, als ob das Monster „wartet, um zu sehen, in welche Richtung du gehst“.
Könnte man es nicht sogar täuschen, indem man so tut, als würde man in eine Richtung gehen, und dann die Richtung wechselt? Zum Glück sind Menschen bei so etwas ziemlich nachsichtig und neigen offenbar dazu, allem mögliche Intelligenz zuzuschreiben
Im Grunde müsste der Gegner seinen Pfad nicht in jedem Frame, sondern erst nach einer kurzen Verzögerung aktualisieren. Dann würde er aufgrund seiner „Trägheit“ dem bisherigen Pfad folgen, und der Spieler könnte ihn täuschen
Eine interessante Anwendung von A* im Spielekontext: Es gab einen Programmierer, der Anfang der 2000er einen Computergegner für ein Spiel bauen musste.
Er abstrahierte die Wahlmöglichkeiten der AI im Spiel und ließ A* in diesem Graphen die kürzeste Distanz finden. Das Spannende daran war, dass A* nicht für klassisches Pathfinding in der Welt genutzt wurde, sondern für die Darstellung der Entscheidungen, die der Computer treffen konnte, wobei der kürzeste Pfad die bestmögliche Strategie repräsentierte
0 - https://www.gamedeveloper.com/design/building-the-ai-of-f-e-...
1 - https://web.archive.org/web/20230804100329/https://alumni.me...
Es gibt dazu auch eine Materialsammlung (nicht von mir): https://github.com/agoose77/goap-resources
Menschen scheinen anzunehmen, dass sie selbst und andere Menschen bei völlig verschiedenen Tätigkeiten wie Routenplanung, Risiko-Nutzen-Abwägung oder dem Planen einer Veranstaltung in sechs Monaten ähnliche Denkmuster und ähnlich tiefe Überlegungen nutzen. Wenn sich unterschiedliche „Suchräume“ als Graphen kodieren lassen, die zu einem gemeinsamen Algorithmus passen, entsteht beim Spielen in einem Zustand der Immersion leicht der Eindruck, die AI sei überlegt und fast schon personenhaft
Als ich an der Uni A* lernte, hatte ich gleichzeitig dieses merkwürdige Problem auf einem öffentlichen Minecraft-Server.
Der Server ruckelte extrem, und beim Profiling stellte sich heraus, dass Zombies in einer Schleife festhingen, in der sie versuchten, den Weg in ein Dorf zu finden, das durch einen großen Zaun vollständig abgesperrt war. Das bedeutet, die damalige Implementierung war naiv genug, niemals aufzugeben.
Ich meine, es gab dazu einen ziemlich ausführlichen Bugreport, der erklärte, wie man das beheben könnte
Besonders wenn mehrere Tiere gleichzeitig durch einen unpassierbaren Zugang wollten, konnte das die fps sehr deutlich beeinträchtigen. Andererseits könnte man sagen, dass das als Katzenverhalten, die äußerst hartnäckig verlangen, durch geschlossene Türen zu gehen, unglaublich realistisch ist. Noch realistischer wäre es allerdings, wenn die Katze in dem Moment, in dem man die Tür öffnet, sofort ihre Meinung ändert und jedes Interesse daran verliert, hindurchzugehen!
Vielleicht sind auch Arbeiten zu Multi-Agenten-Systemen mit A* in unbekanntem Gelände interessant: https://www.researchgate.net/publication/333917261_Implement...
In diesem Artikel und im HN-Thread stehen gute Tipps. Ich hatte bisher noch nicht oft Anlass, A* zu verwenden, aber ich weiß, dass es eine brauchbare Haskell-Bibliothek gibt: https://hackage.haskell.org/package/astar-monad-0.3.0.0#read...