A* search
The conceptHow a game character finds the shortest way around a wall
A* ("A-star") finds the shortest path between two points on a map by always exploring the spot that looks most promising next. The map is a graph: places are nodes, and moves between them are edges with a cost, like distance.
For each spot it adds two numbers: how far it has already travelled to get there, and a guess of how far is left to the goal. It keeps a to-do list sorted by that total and always expands the lowest one first.
Say a character stands at (0,0) on a grid and wants to reach (3,4). A step right to (1,0) has a total of 7, while a step down to (0,−1) has 9, so A* looks right first.
What it’s forScores each spot so A* knows which one to explore next.
f(n) = g(n) + h(n)
- n
- a spot (node) on the map
- g(n)
- the real cost already travelled from the start to n
- h(n)
- the heuristic: a quick guess of the cost left from n to the goal, e.g. straight-line distance
- f(n)
- the estimated total cost of the best path through n
What it givesA priority for every spot; the lowest f is explored next.
- Goal (3,4), grid moves of cost 1, h = |dx| + |dy|
- (1,0): g = 1, h = 2 + 4 = 6, so f = 7
- (0,−1): g = 1, h = 3 + 5 = 8, so f = 9, explored later