Pathfinding

Universität zu KölnHistorisch-Kulturwissenschaftliche Informationsverarbeitung

Softwaretechnologie II (Teil 1): Simulation und 3D ProgrammierungWS 2012/13

Dozent: Prof. Dr. ThallerDatum: 31.01.2013 Referent: Marvin Liu

Gliederung

1. Allgemeines zu Pathfinding 2. Pathfinding Algorithmen:- Dijkstra- A*

3. World Representations

Allgemeines und Anwendungsgebiete von Pathfinding

Spielfiguren müssen in der Lage sein sich in Levels zu bewegen

Dabei kann eine feste Route vom Entwickler vorgegeben sein (Patrouillieren) oder es kann ein kleinerer abgegrenzter Bereich zufällig durchwandert werden

Fixe Routen können leicht implementiert werden, geraten aber an ihre Grenzen, wenn ein Objekt in den vorgegebenen Weg gerät

Frei umherwandernde Spielfiguren können ziellos wirken und leicht steckenbleiben

Allgemeines und Anwendungsgebiete von Pathfinding

Komplexere Spielfiguren wissen nicht im voraus, wohin sie sich als nächstes bewegen müssen

In RTS-Spielen können sie zu jedem Zeitpunkt vom Spieler an jeden Punkt auf der Karte geschickt werden

Ein Plattformspiel benötigt evtl. Gegner, die den Spieler hinterherjage, ohne selbst in jeden Abgrund zu stürzen

Für diese Spielfiguren muss die AI in der Lage sein, geeignete Routen durch das Level zu berechnen, um ans Ziel zu gelangen

Diese Routen sollten sinnvoll und so kurz bzw. schnell wie möglich sein

→ Pathfinding (auch „path planning“)

Pathfinding Graph

Graphen sind mathematische Strukturen, die in Diagrammen dargestellt werden

Besteht aus: Knoten, die z.B. Räume repräsentieren und Verbindungen, die anzeigen, dass bspw. ein Raum mit einem Korridor verbunden ist

Weighted Graph

Verbindungen werden mit numerischen Zahlen versehen, die das Gewicht bzw. die Kosten einer Verbindung darstellen

Kosten stehen für die Zeit oder Distanz, die für den Weg zwischen den Knoten gebraucht wird

Werte für Kosten sind immer positiv

Weighted Graph

Knoten stehen für repräsentative Punkte von Regionen (z.B. das Zentrum)

Die Summe der Verbindungskosten vom Startknoten bis zum Zielknoten ergibt die Gesamtkosten einer Strecke

Directed Weighted Graph

Die Richtung einer Verbindung wird implementiert Verbindungen in beide Richtungen nur dann, wenn 2

Verbindungen mit gegensätzlicher Richtung zwischen 2 Knoten existieren, welche unterschiedliche Kosten haben können

Dijkstra

Aufgabe des Algorithmus besteht darin den Weg mit den geringsten Kosten von einem Startknoten zu einem Zielknoten zu finden

Vom Startknoten aus breitet sich Dijkstra über seinen Verbindungen aus und merkt sich die Verbindungen

Beim Zielknoten angelangt, kann so die kürzeste Strecke zum Startknoten zurückgeliefert werden

Dijkstra arbeitet mit Iterationen Bei jeder Iteration wird ein Knoten bearbeitet und

seine ausgehenden Verbindungen erfasst

Verarbeitung des „Current Node“

Current node bezeichnet den Knoten, der in der aktuellen Iteration verarbeitet wird

Während einer Iteration betrachtet Dijkstra alle ausgehenden Verbindungen vom current node

Für jede Verbindung findet er den Endknoten einer Verbindung und speichert den cost-so-far Wert zusammen mit der Verbindung über der er kam

Node Lists

Der Algorithmus erfasst alle Knoten die er bis jetzt „gesehen“ hat in 2 Listen

Open list: Enthält Knoten die „gesehen“ wurden, aber noch keine eigene Iteration durchlaufen haben

Closed list: Enthält Knoten, die schon ihre Iteration durchlaufen haben

Knoten die in keiner der beiden Listen auftauchen sind unvisited

Verarbeitung des „Current Node“

Dijkstra wählt für die nächste Iteration immer den Knoten zur Verarbeitung aus der open list aus, der die geringsten cost-so-far produziert

Nach Bearbeitung wird der Knoten von der open list entfernt und in die closed list eingetragen

Berechnung von cost-so-far für open und closed Knoten

Vergleich, ob die neue Route besser ist als die alte Cost-so-far wird berechnet und wenn der Wert größer

ist als der eingetragene, erfolgt kein Update Wenn der Wert niedriger ist, dann ersetze den cost-

so-far Wert und die Verbindungen und schreibe den Knoten in open list (evtl. Entfernung aus closed list)

Beendigung des Algorithmus

Der Dijkstra Algorithmus endet generell, wenn die open list leer ist

Oder wenn der Zielknoten der Knoten in der open list ist, mit dem kleinsten cost-so-far Wert

→ selbst wenn der Zielknoten bereits gefunden wurde, wird zunächst nach einer Route mit evtl. noch geringeren Kosten gesucht

Wegermittlung

Es wird beim Zielknoten gestartet und auf die Verbindungen nachvollzogen, die benutzt wurden um dort anzukommen

Beim Startknoten angelangt wird die entstehende Liste invertiert und daraus ergibt sich die vollständige Route

Pseudocode von Dijkstra

Performance von Dijikstra

Die open und closed lists verbrauchen am meisten Performance aufgrund der Operationen:

+=, -=, smallestElement, contains/find→ fast alle Optimierungsversuche finden in diesen

Bereichen statt Eine passende Balance zwischen diesen vier

Operationen zu finden ist der Schlüssel einer schnellen Implementierung

Performance von Dijikstra

n = jeder Knoten im Graphen, der näher als der Zielknoten ist

m = durchschnittliche Anzahl von ausgehenden Verbindungen pro Knoten

-> O(nm) = Algorithmus der Ausführungsgeschwindigkeit

Bei Beendung sind n Elemente in der closed list und nicht mehr als nm Elemente in der open list

-> Speicherverbrauch im schlimmsten Fall O(nm)

Schwächen von Dijkstra

Dijkstra durchsucht den gesamten Graphen nach der kürzesten Route zum Zielknoten

Fill = Anzahl der Knoten die in Betracht gezogen wurden, aber nicht zur finalen Route gehören

→ Dijkstra ineffizient für Punkt-zu-Punkt Pathfinding

A*

A* Algorithmus wird in fast jedem Spiel verwendet Leicht zu implementieren Sehr effizient Viel Spielraum für Optimierungen Entworfen für Punkt-Zu-Punkt Pathfinding und nicht

um die definitiv kürzeste Route zu finden Heuristik sorgt dafür, dass zuerst der Knoten gewählt

wird, der mit der höchsten Wahrscheinlichkeit den kürzesten Weg zum Ziel darstellt, anstelle des Knoten mit dem niedrigsten cost-so-far Wert

Verarbeitung des current node

Speicherung einer weiteren Variable, dem estimated-total-cost Wert (heuristic value)

→ Summe von: cost-so-far und der Entfernung des Knotens zum Zielknoten

Wert kann nicht negativ sein

Berechnung von cost-so-far für open und closed Knoten

Bei niedrigeren cost-so-far Werten, wird allein dieser Wert verändert

A* kann auch bei Knoten aus der closed list noch bessere Routen finden

Beendigung des Algorithmus

In vielen Implementationen wird A* beendet wenn der Zielknoten den kleinsten cost-so-far Wert von allen Knoten in der open list hat

Die heuristic function bestimmt, ob optimale Resultate oder suboptimale Resultate entstehen, welches sich in der Bearbeitungsgeschwindigkeit widerspiegeln

Wenn freiwillig suboptimale Ergebnisse akzeptiert werden, um bessere Performance zu gewährleisten, wird bspw. der Algorithmus Beendet, sobald der Zielknoten entdeckt wurde

Pseudocode von A*

Pseudocode von A*

Wegermittlung und Code

Das Abrufen der finalen Route erfolge genau wie bei Dijkstra

Der Code unterscheidet sich lediglich dadurch, dass: Überprüft wird, ob ein closed Knoten geupdated

werden muss und von der closed list entfernt werden soll

Heuristic values in die Datenstruktur integriert werden

Und die smallestElement Methode estimated-total-cost Werte berücksichtigt, statt cost-so-far Werte

Performance von A*

l = Anzahl der Knoten, dessen estimated-total-cost kleiner ist als der des Zielknoten (l sollte generell kleiner sein als n bei Dijkstra)

m = durchschnittliche Anzahl der Verbindungen eines durchlaufenen Knoten

→ O(lm) = Geschwindigkeit von A*, sowie Speicherverbrauch im schlimmsten Fall

Performanceoptimierung durch sortierte Arrays

Bislang wurden Verkettete Listen verwendet, um die Einträge der open list und closed list ungeordnet anzufügen

Dadurch ist die Speicherung der Daten sehr schnell, das Wiederauffinden von Daten mit bestimmten Werten allerdings sehr zeitaufwändig

In pathfinding von Videospielen ist es deutlich zeitsparender die Daten in geordneten Arrays zu speichern, wodurch der Speichervorgang verlangsamt, der Aufruf der Daten allerdings erheblich gesteigert wird

Performanceoptimierung durch sortierte Arrays

Priority Heaps

Bucketed Priority Queues

Wahl der Heuristik

Je genauer die Heuristik ist, desto weniger fill wird produziert und umso schneller läuft der Algorithmus

Bei zu niedriger Heuristik wird die tatsächliche Strecke zum Ziel unterschätzt und es werden mehr Knoten in Startnähe berücksichtigt, wodurch A* langsamer wird (Nullheuristik = Dijikstra)

Bei zu hoher Heuristik wird nach einer Strecke mit möglichst wenig Knoten gesucht, da die cost-so-far vernachlässigt werden. Das Resultat ist dabei selten der kürzeste Weg

→ in Videospielen werden leicht zu niedrige Heuristiken bevorzugt

Heuristiken in Games

Euclidean Distance Cluster Heuristik

Heuristiken in Games

Indoor Level:

Outdoor Level:

World Representations:Tile Graphs

World Representations:Dirichlet Domain

World Representations:Points Of Visibility

World Representations:Navigation Meshes

World Representations:Navigation Meshes

World Representations:Path Smoothing

Vielen Dank für eure Aufmerksamkeit!