程序代写代做代考 AI case study database algorithm Games & AI #3

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