Post on 05-Apr-2015
transcript
PathfindingUniversität zu Köln
Softwaretechnologie II (Teil 1): Simulation und 3D ProgrammierungWintersemester 2011/2012
Dozent: Prof. Dr. phil. Manfred Thaller Referent: Christian Weitz (cweitz0@smail.uni-koeln.de)
2
Finden einer Route, die◦ am kürzesten/schnellsten◦ sinnvoll ist
Beispiele für Einsatzgebiete◦ 3D-Simulationen, Computerspiele◦ Verkehrsplanung◦ Routing von Paketen im Internet
Was ist Pathfinding?
3
1. Was ist Pathfinding?2. Graphen3. Dijkstra-Algorithmus4. A*-Algorithmus
Inhaltlicher Überblick
4
Für Pathfinding benötigt:Nicht-negativer, gewichteter und gerichteter Graph, der das Problem modelliert.
Graphen
5
Beispiel TES 5: Skyrim
6
Allgemeiner Graph
7
Nicht-negativer gewichteter Graph
8
Nicht-negativer gewichteter und gerichteter Graph
9
Entwickelt um kürzeste Route durch alle Punkte zu finden
Iteriert über die Knoten eines Graphen Für Punkt-zu-Punkt-Pathfinding zu
aufwändig=> Abbruchbedingung: Zielknoten ist hat kleinste
Kosten aller nicht besuchten Knoten
Dijkstra-Algorithmus
10
Dijkstra-Algorithmus
1 12
2,5
5
2,54,5
ADB
E
4
C
Start
Ziel
cost: 0
Open: AClosed:
11
Dijkstra-Algorithmus
1 12
2,5
5
2,54,5
ADB
E
4
C
Start
Ziel
cost: 0cost: 2,5
cost: 1
Open: B, CClosed: A
12
Dijkstra-Algorithmus
1 12
2,5
5
2,54,5
ADB
E
4
C
Start
Ziel
cost: 0cost: 2
cost: 1
Open: B, EClosed: A, C cost: 5
13
Dijkstra-Algorithmus
1 12
2,5
5
2,54,5
ADB
E
4
C
Start
Ziel
cost: 0cost: 2
cost: 1
Open: D, EClosed: A, B, C cost: 5
14
Dijkstra-Algorithmus
1 12
2,5
5
2,54,5
ADB
E
4
C
Start
Ziel
cost: 0cost: 2
cost: 1
Open: EClosed: A, B, C, D cost: 5
15
Schwächen: willkürlich dadurch unnötig viel fill
Dijkstra-Algorithmus
16
Grundidee wie Dijkstra-Algorithmus Nutzt Heuristiken um Abstand zum Ziel zu
schätzen Dadurch im Regelfall schneller als Dijkstra
für das gegebene Problem Abbruchbedingung:
Zielknoten hat niedrigste Schätzkosten der offenen Knoten, bzw. Zielknoten ist auf Liste der offenen Knoten
A*-Algorithmus
17
A*-Algorithmus
1 12
2,5
5
2,54,5
ADB
E
4
C
Start
Ziel
cost: 0
Open: AClosed:
heuristic: 0
heuristic: 2,3
heuristic: 4,9
heuristic: 4,2
heuristic: 6,1estimate: 6,1
18
A*-Algorithmus
1 12
2,5
5
2,54,5
AD
E
4
Start
Ziel
cost: 0
Open: B, CClosed: A
heuristic: 0
heuristic: 2,3
estimate: 7,4heuristic: 4,9
heuristic: 4,2
heuristic: 6,1estimate: 6,1
C
B
estimate: 5,2
19
A*-Algorithmus
1 12
2,5
5
2,54,5
AD
E
4
Start
Ziel
cost: 0
Open: B, CClosed: A
heuristic: 0
heuristic: 2,3
estimate: 6,9heuristic: 4,9
heuristic: 4,2
heuristic: 6,1estimate: 6,1
C
B
estimate: 5,2
20
Dijkstra und A* im Vergleich
A*Dijkstra
Bildnachweis:http://en.wikipedia.org/wiki/File:Dijkstras_progress_animation.gifhttp://en.wikipedia.org/wiki/File:Astar_progress_animation.gif
Dijkstra und A* im Vergleich
A*Dijkstra
20
Bildnachweis:http://en.wikipedia.org/wiki/File:Dijkstras_progress_animation.gifhttp://en.wikipedia.org/wiki/File:Astar_progress_animation.gif
Dijkstra und A* im Vergleich
A*Dijkstra
20
Bildnachweis:http://en.wikipedia.org/wiki/File:Dijkstras_progress_animation.gifhttp://en.wikipedia.org/wiki/File:Astar_progress_animation.gif
Vielen Dank!