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!