(94507350) astar

Please download to get full document.

View again

of 10
5 views
PDF
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Document Description
ppt
Document Share
Documents Related
Document Tags
Document Transcript
  ã   Where are all gaming algorithms?   ã   Many “game algo rithms” are just applied standard algorithms   ã   We will look at Dijkstra’s algorithm for shortest paths, A* and   Bresenham’s algorithm for line plotting Shortest paths, A* andBresenham ’s algorithm Simon Ka ˚ gstro ¨ m ska@bth.se Department of Systems and Software EngineeringSchool of EngineeringBlekinge Institute of TechnologyP.O. Box 520, SE-372 25 Ronneby, Sweden ã   Bresenham? Hart? Dijkstra?   ã   If time allows, we will watch a movie!   ã   Path finding can be quite hard   ã   Good path finding is crucial for nice-looking AI in many games   ã   The problem:    –   How to get from a point A to a point B while avoidingobstacles  –   (and making the path as short as possible) ã   Since game AI should look good and realistic, a good path is    better than a shortest path ã   There are many different methods of achieving path finding   ã   crash-and-turn-based path finding is a simple algorithm to find a path:   1. Start moving in the direction towards the target2. If something blocks your way, walk along that (either way)3. If it no longer blocks the way then goto 1 ã   Features:  –   Runs fast, scales well, uses constant memory  –   Looks OK (i.e. it looks like the NPC tries to find a way)  –   BUT: With concave obstacles the algorithm can get stuck  ã   The standard gaming way around problems: cheat   ã   We can provide hints to the NPCs in the form of navigation   meshes  –   Basically provide fixed paths where NPCs can move ã   This way we either get away without path finding or with   simple ditto (few nodes) ã   Typical example could be a racing game where the NPCs try   to stay as close as possible to a predefined “route”    pres.pdf   —  January 9, 2006  —  1 Shortest paths, A* andBresenham ’ s algorithm  – p. 5/39 Shortest paths, A* andBresenham ’ s algorithm  – p. 6/39 Path finding, crash-and-turn Path finding, navigation meshes Shortest paths, A* andBresenham ’ s algorithm  – p. 3/39 Shortest paths, A* andBresenham ’ s algorithm  – p. 4/39 Path finding Path finding, II Shortest paths, A* andBresenham ’ s algorithm  – p. 1/39 Shortest paths, A* andBresenham ’ s algorithm  – p. 2/39 Outline  ã   We will look at two kinds of graphs here   ã   Types of algorithms    –   Single-source shortest path algorithms: Dijkstra,Bellman-Ford  –   All-pairs shortest path algorithms: Floyd-Warshall  –   Single-pair shortest path algorithms: A* ã   We will focus on single-source and single-pair algorithms   ã   The single-source algorithms can be generalized to solve the   all-pairs and single-pair problems as well  –   It implicitly finds single-pairs  –   Run it for every source to find all-pairs ba6 1. “ T raditional”    –    Nodes V and edges E  –   Edges have weights2. Tilemap-based  –   Each tile is a node in thegraph  –   Edges are implicit betweenthe nodes 2 0 s2 414c d 1530 ã   You will use tilemap-based in lab 4   ã   The shortest path algorithms has many things in common   ã   They work on weighted, directed graphs G = (V, E)    –   V is the set of vertices, E the set of edges ã   They use a weight function w : E →   R which associates a weight withan edge between two vertices ã   The goal is to traverse the graph from a start vertex s, assigning a labelto each vertex  –   A label for the weight d of the node and it’s predecessor  π    –   d is an upper bound of the distance from s to the vertex (best so far)  –   π tells us where we came from  –   A label-setting algorithm (Dijkstra) sets each label exactly once  –   A label-correcting algorithm (Bellman-Ford) may change the label ã   An example is shown below   ab62s 0   2 414c d ã   First we have the graph with vertices V and edges E with   weights ã   An example is shown below   a 2 ã   An example is shown below   a 2 b b 8 8 6 62 2s 0   s 0 2 4 2 4 1 4 1 4 1 14 4c d c d ã   First we have the graph with vertices V and edges E with   weights ã   A shortest path tree (from s)   ã   First we have the graph with vertices V and edges E with   weights ã   A shortest path tree (from s)   ã   Labels added to the vertices (predecessor  π and weight from s)    pres.pdf   —  January 9, 2006  —  2 Shortest paths, A* andBresenham ’ s algorithm  – p. 10/39 Shortest paths, A* andBresenham ’ s algorithm  – p. 10/39 Single-source shortest paths, how II? Single-source shortest paths, how II? Shortest paths, A* andBresenham ’ s algorithm  – p. 9/39 Shortest paths, A* andBresenham ’ s algorithm  – p. 10/39 Single-source shortest paths, how? Single-source shortest paths, how II? Shortest paths, A* andBresenham ’ s algorithm  – p. 7/39 Shortest paths, A* andBresenham ’ s algorithm  – p. 8/39 Some terminology Shortest paths  ã   Edges are relaxed during the execution of a single-source   shortest path algorithm ã   For this, the R ELAX function is used   ã   Edges are relaxed during the execution of a single-source   shortest path algorithm ã   For this, the R ELAX function is used   R ELAX (u, v, w)1 if d[v] > d[u] + w(u, v) R ELAX (u, v, w)123if d[v] > d[u] + w(u, v)then d[v] ←   d[u] + w(u, v)   π [v] ←   u   7 u 14 7 u 14 23then d[v] ←   d[u] + w(u, v)   π [v] ←   u   2 2v v ã   Relaxation updates the label of v if the path from s becomes   shorter if passing through u ã   In the book, this is the if currDist(u) > currDist(v)   ... on page 379 ã   Relaxation updates the label of v if the path from s becomes   shorter if passing through u ã   In the book, this is the if currDist(u) > currDist(v)   ... on page 379 ã   Edges are relaxed during the execution of a single-source   shortest path algorithm ã   For this, the R ELAX function is used   ã   The initialization of a single-source shortest path algorithm   sets all lab els’    –   Distance d to infinity  –   Predecessor  π to NIL (NULL) I NITIALIZE -S INGLE -S OURCE (G, s) R ELAX (u, v, w)1 if d[v] > d[u] + w(u, v)1234for each vertex v ∈   V [G]   do d[v] ←   ∞   π [v] ←   NIL   d[s] ←   0   7 194 then d[v] ←   d[u] + w(u, v)   π [v] ←   u   23 2uv ã   Relaxation updates the label of v if the path from s becomes   shorter if passing through u ã   In the book, this is the if currDist(u) > currDist(v)   ... on page 379 ã   This is the for all vertices v ... on page 378/379   ã   General idea:    –   Two sets, Q, all vertices to be checked, S, the set of vertices which have been determined  –   Select the node u with the lowest shortest-path estimate  –   Relax all edges leaving u D IJKSTRA (G, w, s) ba62s 0   2 414c d D I J K S T R A (G, w, s) 12345678 I NITIALIZE -S INGLE -S OURCE (G, s)S ←   ∅   Q ←   V [G]   while Q = ∅   do u ←   E XTRACT -M IN (Q)   S ←   S ∪ { u }   for each vertex v ∈   Adjacent[u] and v ∈   Q   do R ELAX (u, v, w) 12345678 I N I T I A L I Z E -S I N G L E -S O U R C E (G, s)S ←   ∅   Q ←   V [G]   while Q = ∅   do u ←   E X T R AC T -M I N (Q)   S ←   S ∪ { u }   R E L A X (u, v, w)123if d[v] > d[u] + w(u, v)then d[v] ←   d[u] + w(u, v)   π [v] ←   u   for each vertex v ∈   Adjacent[u] and v ∈   Q   do R E L A X (u, v, w)  pres.pdf   —  January 9, 2006  —  3 Shortest paths, A* andBresenham ’ s algorithm  – p. 13/39 Shortest paths, A* andBresenham ’ s algorithm  – p. 14/39 Dijkstras algorithm Dijkstra, II Shortest paths, A* andBresenham ’ s algorithm  – p. 11/39 Shortest paths, A* andBresenham ’ s algorithm  – p. 12/39 Relaxation Initialization Shortest paths, A* andBresenham ’ s algorithm  – p. 11/39 Shortest paths, A* andBresenham ’ s algorithm  – p. 11/39 Relaxation Relaxation  b ba a 2 Q={ 0 INF } Q={ 1 } INF INF INF 2 INF INF 6 6 s a b c d c a b d 2 2s 0 s 0 2 4 2 4S={ S={} S }1 1 1 0 4 4c d c d D I J K S T R A (G, w, s) D I J K S T R A (G, w, s)12345678 I N I T I A L I Z E -S I N G L E -S O U R C E (G, s)S ←   ∅   Q ←   V [G]   while Q = ∅   do u ←   E X T R AC T -M I N (Q)   S ←   S ∪ { u }   12345678 I N I T I A L I Z E -S I N G L E -S O U R C E (G, s)S ←   ∅   Q ←   V [G]   while Q = ∅   do u ←   E X T R AC T -M I N (Q)   S ←   S ∪ { u }   R E L A X (u, v, w) R E L A X (u, v, w)123if d[v] > d[u] + w(u, v)then d[v] ←   d[u] + w(u, v)   π [v] ←   u   123if d[v] > d[u] + w(u, v)then d[v] ←   d[u] + w(u, v)   π [v] ←   u   for each vertex v ∈   Adjacent[u] and v ∈   Q   do R E L A X (u, v, w)for each vertex v ∈   Adjacent[u] and v ∈   Q   do R E L A X (u, v, w) b ba aQ={ 2 } Q={ d } 2 5 INF 2 8 8 6 6 a d b 4 b 2 2s 0 s 0 2 4 2 4S={ S={ 1 1 2 } } 1 5 1 4 1 1 c c a 4 4c d c d D I J K S T R A (G, w, s) D I J K S T R A (G, w, s) I N I T I A L I Z E -S I N G L E -S O U R C E (G, s)S ←   ∅   Q ←   V [G]   while Q = ∅   do u ←   E X T R AC T -M I N (Q)   S ←   S ∪ { u }   I N I T I A L I Z E -S I N G L E -S O U R C E (G, s)S ←   ∅   Q ←   V [G]   while Q = ∅   do u ←   E X T R AC T -M I N (Q)   S ←   S ∪ { u }   1234567812345678 R E L A X (u, v, w)1 if d[v] > d[u] + w(u, v) R E L A X (u, v, w)1 if d[v] > d[u] + w(u, v)23then d[v] ←   d[u] + w(u, v)   π [v] ←   u   23then d[v] ←   d[u] + w(u, v)   π [v] ←   u   for each vertex v ∈   Adjacent[u] and v ∈   Q   do R E L A X (u, v, w)for each vertex v ∈   Adjacent[u] and v ∈   Q   do R E L A X (u, v, w) b ba 2 a 2 Q={ 8 } Q={ } 8 8 6 6 b 2 2s 0   s 0 2 4 2 4S={ S={ 1 2 4 } 1 2 4 8 } 1 4 1 4 1 1 c a d c a d b 4 4c d c d D I J K S T R A (G, w, s) D I J K S T R A (G, w, s)12345678 I N I T I A L I Z E -S I N G L E -S O U R C E (G, s)S ←   ∅   Q ←   V [G]   while Q = ∅   do u ←   E X T R AC T -M I N (Q)   S ←   S ∪ { u }   12345678 I N I T I A L I Z E -S I N G L E -S O U R C E (G, s)S ←   ∅   Q ←   V [G]   while Q = ∅   do u ←   E X T R AC T -M I N (Q)   S ←   S ∪ { u }   R E L A X (u, v, w) R E L A X (u, v, w)123if d[v] > d[u] + w(u, v)then d[v] ←   d[u] + w(u, v)   π [v] ←   u   123if d[v] > d[u] + w(u, v)then d[v] ←   d[u] + w(u, v)   π [v] ←   u   for each vertex v ∈   Adjacent[u] and v ∈   Q   do R E L A X (u, v, w)for each vertex v ∈   Adjacent[u] and v ∈   Q   do R E L A X (u, v, w)  pres.pdf   —  January 9, 2006  —  4 Shortest paths, A* andBresenham ’ s algorithm  – p. 14/39 Shortest paths, A* andBresenham ’ s algorithm  – p. 14/39 Dijkstra, II Dijkstra, II Shortest paths, A* andBresenham ’ s algorithm  – p. 14/39 Shortest paths, A* andBresenham ’ s algorithm  – p. 14/39 Dijkstra, II Dijkstra, II Shortest paths, A* andBresenham ’ s algorithm  – p. 14/39 Shortest paths, A* andBresenham ’ s algorithm  – p. 14/39 Dijkstra, II Dijkstra, II
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks