A* algorithm: pathfinding in games and maps

In short: A* finds shortest paths in graphs or grids efficiently by examining the most promising cells first using an estimate (heuristic) to the goal.

In more detail: Game characters, navigation devices and robots need paths around obstacles. Dijkstra safely finds the shortest path but searches in all directions. A* (A-star) steers the search toward the goal with a heuristic.

In Depth

Idea: f = g + h

Each node gets f(n) = g(n) + h(n):

• g(n): cost so far from the start to n.
• h(n): estimate of the remaining cost to the goal (heuristic). A* always takes the node with the smallest f from a priority queue (open list), expands neighbours, updates cheaper paths and remembers finished nodes (closed list). If h = 0, A* becomes Dijkstra; if g = 0, greedy best-first search.

Heuristics

• Manhattan distance |dx| + |dy|: grid without diagonals.
• Chebyshev max(|dx|, |dy|): grid with diagonals (equal cost).
• Octile/Euclid: diagonals √2 more expensive / free movement (√(dx²+dy²)).
• Admissible: h never overestimates the true cost → A* returns the optimal path. Consistent: additionally triangle inequality → each node is expanded only once.
• Too large (overestimating) h make it faster, but the path may be not shortest.

Pseudocode

open = PriorityQueue(); open.add(start, f=h(start))
g[start] = 0
while open not empty:
    n = open.pop_min()
    if n == goal: reconstruct path (predecessors)
    for each neighbour m of n:
        new = g[n] + cost(n, m)
        if new < g.get(m, ∞):
            g[m] = new; predecessor[m] = n
            open.add_or_update(m, f = new + h(m))

Example: grid with obstacles, start (0,0), goal (7,5): A* examines far fewer cells than Dijkstra. Data structure: binary heap (Python heapq). Grid vs. waypoints/navmesh in 3D games.

Practice in games

• Maps: terrain with different costs (swamp more expensive), avoid corner cutting over diagonals.
• Many units: path caching, *hierarchical search (HPA)**, flow fields, jump point search (grid).
• Dynamic world: D* Lite adapts paths when obstacles change.
• Path smoothing, steering.
• Navigation/road networks: contraction hierarchies & co. faster than plain A*.
• Puzzles: 8-puzzle, Sokoban solver.
• Related: BFS/DFS, Dijkstra, graphs, priority queue.

See also: Dijkstra’s algorithm, Breadth-first and depth-first search, Heap and priority queue, Game loop