Pathfinding

Softwaretechnologie II, 8.5.2008

1 Der Star unter den Pathfinding-Algorithmen: A*

- A* findet den kürzesten Weg zwischen zwei Punkten- A* sucht nicht „blind“ in jede Richtung, sondern schätzt die

beste Richtung ab- daher schnell & effizient- viele Weiterentwicklungen und Variationen des

Basisalgorithmus- kann nicht nur Pfade finden, für viele Problemstellungen

geeignet

Voraussetzungen:

- map / graph: das gesamte Gelände- nodes: repräsentieren jeweils einen Punkt oder ein Teilgebiet der Karte- distance / heuristic: Einschätzung des Wertes einer „node“ (z. B. Distanz vom Knoten bis zum Ziel)- cost: Kosten einer „node“ oder der Verbindung zwischen zwei „nodes“ (z. B. höhere Kosten wenn es bergauf geht oder durch Feindesland)

daraus Berechnung von drei Variablen für jede „node“:

- g (goal): Kosten vom Startpunkt bis zu diesem Knoten

- h (heuristic): geschätzte Kosten von diesem Knoten bis zum Zielpunkt- f (fitness): Summe aus „g“ und „h“ ->

Kostenschätzung des gesamten Pfades durch diesen Knoten

außerdem zwei Listen:

- open list: nicht erkundete Knoten, zu Beginn desAlgorithmus nur der Startpunkt

- closed list: vollständig erkundete Knoten

- ein Knoten ist vollständig erkundet, wenn „g“, „h“ und „f“ für ihn sowie alle seine Nachbarn berechnet sind und diese Nachbarn komplett auf die „open list“ aufgenommen wurden

Der Algorithmus

1. Let P = the starting point.2. Assign f, g and h values to P.3. Add P to the Open List. At this point, P is the only node on the Open list.

4. Let B = the best node from the Open list (best node has the lowest f-value)a. If B is the goal node, then quit - a path has been found.b. If the Open list is empty, then quit - a path cannot be found.

5. Let C = a valid node connected to B.a. Assign f, g, and h values to C.b. Check whether C is on the Open or Closed list.

i. If so, check whether the new path is more efficient (lower f-value)1. If so, update the path.

ii. Else, add C to the Open list.c. Repeat step 5 for all valid children of B.

6. Repeat from step 4.

- „g“ ist eindeutig zu berechnen: Kosten bis zum aktuellen Knoten

- Berechnung von „h“?- abhängig vom Anwendungszweck- hier: einfache Abschätzung der Distanz bis zum Zielknoten

z. B. h = | dx - sx | + | dy - sy |

(dx, dy) Zielknoten / (sx, sy) Startknoten

- nur Schätzung, tatsächliche Distanz kann abweichen!- Schätzmethode wichtig für Erfolg & Schnelligkeit des

Algorithmus

- Beispielentwurf einer Klasse für A*

class _asNode {public: _asNode(int, int);int f, g, h;

int x, y;int numchildren;int number;_asNode *parent;_asNode *next;

_asNode *children[8];void *dataptr;

};

- benötigt werden weiterhin zwei verknüpfte Listen, um die „open List“ und „closed List“ zu realisieren

- eine Methode zum Verknüpfen zweier Knoten parent <-> child, die die Schritte 5a und 5b des Algorithmus implementiert

- außerdem eine Methode, die die „g“-Werte aktualisiert

Beispiel: Ein Knoten hat bisher g = 5 für den kürzesten Pfad, der vom Startpunkt bis zu ihm führt. Nun wird über einen benachbarten Knoten ein kürzerer Pfad zu ihm gefunden und „g“ muss korrigiert werden.

- praktisch sind individuelle Kosten- und Validisierungsfunktionen, die die A*-Klasse flexibel einsetzbar machen

Fazit

- der Algorithmus A* an sich ist simpel- die Kunst liegt darin, seine Ergebnisse und seinen

Zeitverbrauch zu optimieren- Ansatzpunkte hierfür: Kostenfunktion, Ablegen und Suchen der

Knoten in den beiden Listen- wie Kosten und Distanz/Heuristik zu berechnen sind, muss von

Anwendung zu Anwendung gestaltet werden; das Grundgerüst von A* bleibt bestehen

2. Generic A* Machine

- mit einer generischen A*-Maschine lassen sich weit mehr Probleme lösen als das Finden von Pfaden

- Verwendung in „Empire Earth“ für: Pathfinding, Terrainanalyse, Choke-point detection, Planen für Routen der AI, Wettererstellung und -bewegung, Mauerbau der AI, Wanderungen von Tieren auf der Karte

- A* kann Pfad finden, aber auch das Negativ eines Pfades oder sogenanntes „flood fill“

- „flood fill“ -> alle erreichbaren Knoten füllen- einen unerreichbaren Zielpunkt angeben- Beispiel: um Wald zu formen, sollen alle nebeneinander

stehenden Bäume gefunden werden

Konzept einer Generic A*-Machine?

- storage class: Speicher für die erkundeten Pfadmöglichkeiten und „open list“ / „closed list“

- goal class: die Einheit selber, Start- und Ziel, Kostenfunktion, Validisierungsfunktion (TileIsOpen)

- map: ein Raum, der durchsucht werden kann -> jegliche Formen von 2D-Arrays

- engine: zentrale Einheit zur Durchführung

das Waldproblem

Start

Start

Ziel

Start

Ziel

3. Optimierungen von A*: zeitkritische Berechnung

Das „Freeze-Problem“:

- Pathfinding benötigt zu viel Rechenzeit -> das Spiel hält so lange an, bis die Berechnungen komplett sind

- unschöne Ruckler im Spielablauf- zusätzlich: im Mehrspielerbetrieb sind Rechner der Spieler

unterschiedlich schnell -> Spiel kann dadurch „out-of-sync“ geraten

- Lösung: time-sliced pathfinding- pro Zeiteinheit stehen allen Pathfinding-Vorgängen auf der Karte

nur eine bestimmte Anzahl „Umdrehungen“ zur Verfügung- z. B. eine Umdrehung = ein Durchlauf des A*-Algorithmus

- Zuteilen von Zeitressourcen sorgt für konstante Framerate- will Spieler eine Einheit oder Gruppe von Einheiten zu einem

bestimmten Punkt losschicken, könnten die Einheiten mit Zeitverzögerung reagieren -> unerwünscht

- Lösung: Berechnung vorläufiger „quick path“

Quick path

Full path

Splice path

Final path

Schwächen

- immer ein Trade-off „looks vs. performance“- Schwierigkeit: Einheiten erreichen das Ende des „quick path“,

bevor der vollständige Pfad berechnet ist

- Lösung könnte Zuteilung von Prioritäten zu den einzelnen pathfinding threads sein: die Pfadsuche, die am dringendsten fertig werden muss, erhält mehr Umdrehungen pro Runde Zeit als Pfadsuchen mit niedriger Priorität

- eigene Pathmanager-Klasse hilfreich

4. Fortgeschrittene Geschwindigkeitsoptimierungen

- wichtig: Maßzahl für Performance- neben sogenannten „in-code timers“ (siehe Beispiel

Umdrehungen) externe Benchmarks wie „VTune“ (Intel)

- mit Feedback bessere Bewertung einer Veränderung des Algorithmus möglich

- Pathfinding so simpel wie möglich gestalten: z. B. einfach die Anzahl der vorhandenen Pfade reduzieren

- Visualisierung der Pathfinding-Vorgänge ebenfalls hilfreich, kann vom Grafik-Team leicht implementiert werden

- fortgeschritten: Verwendung eigener Routinen statt Standard-Bibliothek, Speichersystem des Algorithmus oft der bremsende Flaschenhals

- eigene verknüpfte Listen schreiben- die „open list“ und „closed list“ zu Hash-Tabellen umwandeln- memset nur auf die Teile des Speichers anwenden, die

tatsächlich „dreckig“ sind und nicht den gesamten Pool an Knoten neu initialisieren

5. Weitere Ideen

- „iterative deepening“: ein Pathfinding-Algorithmus wird zunächst mit einem sehr kleinen Zeitvorrat gestartet, sollte er nicht zum Ende gekommen sein, beim nächsten Aufruf mit einem größeren Zeitbudget u.s.w.

einfache Probleme -> schnell gelöstkomplexe Probleme -> verwenden im ersten Schritt nicht zu viel Zeit

Beispiel: mehrere Charaktere wollen durch eine Tür, sobald der erste Charakter in der Tür steht, würden die Anderen Zeit für Pfadsuche verschwenden

- blockierte Knoten direkt auf die „closed list“ setzen

- Caching von bereits gescheiterten Suchen-> unnötige Redundanz kann vermieden werden-> auch mit Teilpfaden möglich

- Wegpunkte-Funktion für Spieler:Spieler setzt Wegpunkte -> (in der Regel) weniger Arbeit für den Pathfinding-Algorithmus

- A* nicht im Übermaß benutzen, z. B. bei einfachen Problemen zunächst eine gerade Linie versuchen

6. Alternative Pathfinding-Technik

- „weighted nodes“

Bot

Sensor (anziehend)

Sensor (abstoßend)

- Knoten ziehen den Bot an oder stoßen ihn ab- jeder Knoten hat eine Gewichtung

- abstoßende Knoten könnten z. B. undurchdringliche Gebiete sein wie Wasser, Wald

- aber auch gegnerische Einheiten

- anziehende Knoten könnten nahe dem gesetzten Ziel liegen- denkbar auch freundliche, verbündete Einheiten oder

Reperatur- / Heilmöglichkeiten

- ziemlich realistische Pfade möglich- die gewichteten Knoten können einen begrenzten Radius

erhalten („sensitivity zone“):

7. Preprocessed solutions

- A* ist eine runtime solution- ist Rechenzeit während des Spielvorgangs knapp und steht

ausreichend Speicher zur Verfügung, können Pathfinding-Vorgänge bereits vor Start des Spielablaufes geschehen

- besonders Effektiv: das Terrain zu Beginn in durchsuchbare Einheiten zu unterteilen, z. B. grid, quadtree u.s.w.

- Generierung einer Tabelle, die alle besten Pfade zwischen zwei Knoten festhält-> Zusammensetzung eines Pfades zur Laufzeit dann erheblich schneller

- vor dem Start eine Terrainanalyse: bestmögliche Repräsentation der Spielelandschaft durch ein System von Knoten

- höhere Anzahl von Knoten und Kanten wirkt sich exponentiell auf die Rechenzeit von A* aus

- eine eingängige Terrainanalyse zu Beginn kann z. B. ein großes Gebirge direkt ausschließen oder einen festgelegten Pfad definieren, wenn um ein spezielles Objekt navigiert werden soll

- Nachteil: alles muss im Speicher festgehalten werden, Abwägungssache