Games & AI #3
A* + MORE
Games & AI #1: A* + More Patrick Dickinson
This Week
We will look at a new algorithm: A*
1. Actually it’s not new – closely related to Dijksta’s… but better
2. See how it works
3. See how it’s better than Dijksta’s
4. Address some limitations
You will implement A* in your workshop
Games & AI #1: A* + More 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: 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
Recap : Dijkstra’s Algorithm
Efficient algorithm for pruning search space in node graph.
Iterative: re-estimate shortest distance from start to each intermediate square (node).
Looks like breadth first search
Can we optimise this at all?
Games & AI #1: A* + More Patrick Dickinson
Best-first Search
There is a third way: “best-first” search.
Breadth first: expand all directions equally Depth first: expand specific branches (arbitrarily)
Best first: Prioritizing specific branches over others, and expand those first. To do this, need some “heuristic” (i.e. “guess”) to chose which branches to prioritise.
A* is a best-first algorithm, which adds a heuristic to Dijkstra’s.
Games & AI #1: A* + More Patrick Dickinson
A* (A-Star) : Key Ideas
Optimisation of Dijkstra (Dijkstra = special case of A*) Remember how Dijkstra spreads outward in all directions?
A* modifies Dijkstra to search more likely paths first, But in a fairly simple way:
Search those which would be most direct (shortest) first, given what has been encountered so far.
This is achieved by adding a Heuristic function (i.e. a guess) to the open node costs when choosing which node to close next…
Games & AI #1: A* + More Patrick Dickinson
More formally
Define a new cost function: f(x) = g(x) + h(x)
g(x) = cost from start for node x, determined in exactly the same way as Dijkstra.
h(x) = “Heuristic” function for node x = some estimate of the minimum cost to get to the destination from x.
◦ h(x) can be defined in a number of different ways
Node with lowest f(x) is selected for closing at each step
Note: cost from start, g(x), still estimated in exactly the same way as for Dijkstra
Games & AI #1: A* + More Patrick Dickinson
Heuristic function f(x)
The heuristic function can be any function!
admissible = should not over-estimate the shortest distance from a
node to the destination (i.e. should be <= shortest distance).
If function is not admissible – not guaranteed to get shortest path
(though will still get a good one).
Examples of some suitable heuristics for searching in 2D space...
Games & AI #1: A* + More Patrick Dickinson
Heuristic function f(x)
Manhattan distance:
Total difference in X + Total difference in Y Suitable for 4-connected grid
Diagonal distance (Chebyshev distance): Max (difference in X, difference in Y) Suitable for 8-connected grid
Euclidean distance :
Sqrt((difference in X)2 + (difference in Y)2) Suitable for any 2d spatial node graph
Games & AI #1: A* + More Patrick Dickinson
Example
Use diagonal distance:
Games & AI #1: A* + More Patrick Dickinson
A* vs Dijkstra
Games & AI #1: A* + More Patrick Dickinson
Remaining Issues with A*
As an optimisation of Dijksta, have the same limitations:
1. Speed – need to pre-calculate entire route
2. Adaptation to dynamic environment
3. Independence
Games & AI #1: A* + More Patrick Dickinson
Issues with A* : Speed
Still not particularly fast – lots of maps, lots of agents.
Pre-calculate routes?
N nodes = database of NxN routes Can make some optimsations:
Route between 2 points – whole set of routes
Only need to store keep next step NxNx1byte
Games & AI #1: A* + More Patrick Dickinson
Issues with A* : Changes
If environment changes, may need to re-run A* lots of agents = lots of recalculations
Could we just “patch” existing path, if a path gets blocked?
What about pre-calculated routes?
Games & AI #1: A* + More Patrick Dickinson
Issues with A* : Coordination
Another problem with multiple agents – independent planning. No prediction. Breaks our rules of game AI (believability)
Solution: Plan around planned paths of other agents- can incorporate this into A* = cooperative A*
David Silver. Cooperative pathfinding, Proceedings of the First Annual Conference on Artificial Intelligence and Interactive Entertainment (AIIDE-05), 2005
Games & AI #1: A* + More Patrick Dickinson
Issues with A* : Coordination
Need:
◦ Time: a third dimension to search (now a 3D problem).
◦ Fixed and moving obstacles can be represented ◦ Add a “wait” state
◦ Move to layer t+1 at each step
Games & AI #1: A* + More Patrick Dickinson
Issues with A* : Coordination
Not necessarily most optimal path set (greedy) - but not dumb either.
What if agents move at different speeds? Paths get longer (wait state)
Can’t pre-process or patch easily
Games & AI #1: A* + More Patrick Dickinson
Example: Hierarchical A*
HPA*
Break problem down : imagine driving from one house, to a house in a different city
A. Botea, M. Muller, J. Schaeffer; Near optimal hierarchical path-finding, Journal of Game Development, 1 (1) (2004), pp. 7–28
Games & AI #1: A* + More Patrick Dickinson
Example: Hierarchical A*
Split grid into sections.
Find transition points between sections
Games & AI #1: A* + More Patrick Dickinson
Example: Hierarchical A*
Pre-compute inter-section routes and intra-section routes = node grid
At run time, insert start and end points, path-find on grid.
Advantages:
◦ Partial pre-computed
◦ Can patch, or rebuild section at run-time ◦ Faster (x10 on Baldur’s Gate)
◦ Nearly as optimal (1%)
Games & AI #1: A* + More Patrick Dickinson
A nice visualisation
(Courtesy of Ashley Williamson)
https://qiao.github.io/PathFinding.js/visual/
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
The End
...of games AI
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson