36 lines
756 B
Markdown
36 lines
756 B
Markdown
A\* Pathfinding
|
|
===============
|
|
|
|
There are 3 main values usedd in reference to A\*:
|
|
|
|
f = how promisiing a new location is
|
|
g = distance from origin
|
|
h = estimate distance to goal
|
|
f = g + h
|
|
|
|
For a grid space our `h` is calculated by two straight shots to the goal
|
|
from the current location(ignore barriers). The grid space `g` value is
|
|
basiccally the number of steps we've taken from the origin. We maintain
|
|
a list of potential nodes only, so if one of the seeking nodes gets us
|
|
stuck we can freely remove that, because it succs.
|
|
|
|
Time & Space Commplexities
|
|
==========================
|
|
|
|
Best-First Search
|
|
-----------------
|
|
|
|
Time: O(VlogV + E)
|
|
|
|
Dijkstra's
|
|
----------
|
|
|
|
O(V\^2 + E)
|
|
|
|
A\*
|
|
---
|
|
|
|
Worst case is the same as Dijkstra's time
|
|
|
|
O(V\^2 + E)
|