RightSignal
1 of 4

Your RightSignal

Concept of the day1 / 3

A* search

The concept

How 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.

  1. Goal (3,4), grid moves of cost 1, h = |dx| + |dy|
  2. (1,0): g = 1, h = 2 + 4 = 6, so f = 7
  3. (0,−1): g = 1, h = 3 + 5 = 8, so f = 9, explored later