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

Similar documents

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