Pathfinding with A* (A-Star)

When an enemy navigates around walls to reach the player instead of walking straight into a corner, it's usually running A* (pronounced "A-star") — the most popular pathfinding algorithm in games. The idea is intuitive once you see what it's actually doing.

The setup: a graph of nodes

Pathfinding works on a graph — a set of nodes (positions) connected by edges (moves between them). In 2D games this is usually a grid: each walkable tile is a node connected to its neighbors, and walls are simply removed from the graph. A* finds the cheapest path from a start node to a goal node through that graph.

The A* idea: smart searching

You could flood outward in every direction until you stumble on the goal (that's Dijkstra/BFS), but it wastes time exploring away from the target. A* is smarter: for each node it scores

f = g + h

• g — the actual cost to reach this node from the start (steps taken so far).
• h — a heuristic estimate of the remaining cost from this node to the goal.

A* always expands the node with the lowest f next, so it naturally pushes toward the goal while still accounting for the distance already traveled. That combination is what makes it both fast and optimal.

The heuristic

h is an educated guess of remaining distance — commonly Manhattan distance (horizontal + vertical steps) on a 4-direction grid, or Euclidean (straight-line) when diagonal movement is allowed. A good heuristic must never overestimate the real remaining cost; if it doesn't, A* is guaranteed to find the shortest path. A closer (but honest) estimate makes the search faster.

Weighted terrain

Edges can have different costs. Make mud or water cost more to cross, and A* will naturally prefer the road even if it's longer — because "cheapest path" isn't always "fewest tiles." This is how you get AI that avoids hazards.

When to use it (and not)

• Great for: navigating static or slowly-changing maps — enemies chasing through a level, units in a strategy game.
• Watch out: on huge maps or with hundreds of agents, running A* constantly is expensive. Common fixes are pathfinding on a coarser grid, spreading recalculation across frames, or caching paths.
• Overkill for: open areas with no obstacles — there, just steer straight toward the target (see raycasting for obstacle sensing).

Mental model

A* is flood-fill that's biased toward the goal. It balances "how far have I come" (g) with "how far is left" (h), always exploring the most promising node next — which is why it reliably finds short paths without searching the whole map.