Games & AI #2
DIJKSTRA’S ALGORITHM
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson
This week
1. Look at an algorithm (Dijkstra’s) for solving general searches on graphs.
2. Try to understand how it works
3. Understand limitations
4. Think about how it could be used in games
You will implement Dijkstra in workshop 2
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson
Recap – Our Objectives for Games
Speed (Real-time) Predictable resources Ability to design game play Believability
Not really stupid
Not necessarily perfect
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson
Recap : Case Study
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson
Recap : Some theory
Generic Searching / path finding works on a “node graph” A grid is just a special case (homogenous)
3
4
6
1
1 1.4
3
5
4
4
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Recap: Breadth first vs depth first
Breadth first: Visit each level, one by one – A B C D E F G H I
Depth first: Visit each child node to its maximum depth – A B E F C D G I H
A BCD
E
F
GH I
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
What if…
We are not searching on a tree:
Games environments (or real environments) are better represented as grids or more generally as graphs.
Graphs have loops (i.e. multiple routes to same node) What if we did this?
Edges can have different costs
Searching needs to account for these more complex situations?
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson
Dijkstra’s Algorithm
Dijkstra’s algortihm solves these kind of search problems: Published 1959
Original context: routing packets around a network Cornerstone of modern search algorithms
Many improvements proposed – A* optimal (late 60s) Used extensively in games, but has some limitations
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson
Implementation
3
4
6
1
3
5
4
4
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson
Dijkstra’s: Key Ideas
Planning: works out complete route in advance (unlike AvP)
Divide and conquer – decompose planning into iterative process
There are many potential ways to get to every node / grid square (because of loops: undirected graph) Pruning “search space”… reducing number of possible route searches
Brute force:
What if we searched all possible paths to the target?
limit to length 10 : naively, search space is 810 > 1,000,000,000 Unfeasible to search all possible routes
How can we reduce the search space?
1. Check for and eliminate sub-optimal path segments: can reject a lot of paths
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson
Eliminating Loops
3
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson
Eliminating Loops
6?
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson
Dijkstra’s: Key Ideas
Remember the best route found so far to each intermediate (non-target) square, and use it to reject any partial candidate paths which get there in more steps.
Of course we might find better path segments as we go along!
When there are no possible better ways to get to that node, we know that
the best solution found so far is the actual best solution. Then (importantly!)
Use that knowledge to refine best routes to its neighbours
Leads us to a formal definition of the algorithm…
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson
Dijkstra’s: More Formally
WE NEED:
Set of nodes and pair costs to traverse from one to neighbours
Our case: Grid + cost 1 up/down/left/right, cost 1.4 diagonals
Start + end nodes (obvious)
For each node we keep:
1. Cost: current shortest total distance from start (‘3’ in our example)
2. Link to the neighbour (only) which got us there for that cost (could the coordinates, index, or direction)
Also need 2 lists of nodes: Open (not yet finalized the shortest route) Closed (have finalized shortest route)
(look again at example)
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson
Dijkstra’s: More Formally
Initialisation:
Set cost of all nodes to infinity (or just a very big number) Set cost of start node to zero
(Doesn’t matter about links)
Put all nodes on to the “open” list
Each Iteration:
Find the “open” node N with lowest current estimated cost Move to closed list (that is, take its current estimate as best) Re-estimate each neighbour (cost of N + pair cost)
If new estimate is lower, update node cost and set link to N When N == end node, we are finished
Just follow links back to start get path
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson
Lets see how it works…
∞
∞
∞
∞
∞
0
∞
∞
∞
∞
∞
∞
∞
Exercise for you: remember, might ask you about this algorithm in your exam!
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson
Dijkstra Limitations
1. Needs to work out (plan) entire solution in advance
2. Doesn’t adapt to changes in the environment
3. Doesn’t adapt to changes in the target position
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson
Dijkstra and Games
We calculate a lot of intermediate results… What does this look like?
Breadth or Depth?
Can have different pair costs: is this useful?
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson
Dijkstra vs AvP
1. How could you apply Dijkstra to AvP? Which is target – alien or player?
2. Which is best (for AvP)? Most optimal?
How many aliens? Most believable?
Most generalizable?
3. What about adaptation – changes to environment? How often do we need to recalculate?
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson
Next week
A* + advanced modifications + real games
Homework: manually work through this for yourselves
Games & AI #2: Dijkstra’s Algorithm Patrick Dickinson