# A* Pathfinding

> A* searches a graph by always expanding the node with the lowest cost so far plus estimated cost to go. With an admissible heuristic, the path is optimal.

- Category: AI › Navigation
- Level: core
- Tags: pathfinding, graph search, heuristic, grid, navmesh
- Updated: 2026-11-01
- URL: https://gdcs.coody.app/ai/navigation/a-star-pathfinding

## What it is

A* finds the cheapest path through a graph: grid cells, waypoints or navmesh polygons. For each node it tracks `g`, the best known cost from the start, and `h`, a **heuristic** estimate of the cost to the goal. It keeps an **open set** of discovered nodes ordered by `f = g + h`. Each iteration it pops the lowest-f node, moves it to the **closed set**, and relaxes its neighbors. When the goal is popped, follow parent links back to the start.

The heuristic is what makes it fast. `h = 0` turns A* into Dijkstra's algorithm, which floods outward in every direction. A perfect `h` walks straight to the goal. If `h` never **overestimates** the true cost (admissible), the first path to the goal is optimal. Match it to your movement rules: **Manhattan** for 4-way grids and **octile** for 8-way grids with diagonal cost √2.

Use a **binary heap** for the open set. A sorted array or a linear scan turns a few-millisecond search into a frame-killer. Big worlds want a coarser graph (navmesh, hierarchical clusters), searches spread over several frames, and path smoothing with string-pulling or line-of-sight checks afterwards. Hand the finished path to [steering behaviors](https://gdcs.coody.app/ai/steering/steering-behaviors) to actually move along it.

## Key formulas

- **Priority:** $f(n) = g(n) + w\,h(n)$
- **Manhattan (4-way):** $h = |\Delta x| + |\Delta y|$
- **Octile (8-way, diagonal = √2):** $h = |\Delta x| + |\Delta y| + (\sqrt{2} - 2)\min(|\Delta x|, |\Delta y|)$ — Weighted A* (w > 1) expands far fewer nodes; the path is at most w × optimal.

## Rules of thumb

- Break ties between equal f toward larger g (or smaller h). On open grids this cuts expansions dramatically.
- Use lazy deletion: push duplicates with the better key and skip popped nodes that are already closed. It's simpler than decrease-key and just as fast in practice.
- On 8-way grids, forbid cutting corners: a diagonal move needs both adjacent orthogonal cells to be free.
- Budget searches: cap expansions (e.g. 2,000 per frame) and resume next frame, or fall back to a partial path toward the closest node found.
- Cache paths and re-plan only when the goal moves more than a cell or two, or when the map changes along the route.

## Implementation

Core loop (binary heap, lazy deletion):

```ts
g.fill(Infinity); g[start] = 0
open.push(start, h(start))
while (open.size) {
  const cur = open.pop()
  if (closed[cur]) continue            // stale duplicate
  closed[cur] = 1
  if (cur === goal) return rebuild(parent, goal)
  for (const [nb, cost] of neighbors(cur)) {
    if (closed[nb]) continue
    const ng = g[cur] + cost
    if (ng < g[nb]) {
      g[nb] = ng
      parent[nb] = cur
      open.push(nb, ng + w * h(nb))    // f = g + w·h
    }
  }
}
return null                            // unreachable
```

## Common mistakes

- Using Euclidean or Manhattan distance on an 8-way grid. Manhattan overestimates diagonals, so paths stop being optimal.
- Allowing diagonal moves through wall corners, so agents clip through geometry.
- Allocating node objects per search on a big grid. Reuse typed arrays (g, parent, closed) and clear them with a generation counter.
- Searching to an unreachable goal every frame. Flood fill connected regions once and reject impossible requests instantly.

## Interactive visual

The search animates from the green start to the red goal. Yellow tiles are the open set (frontier), blue tiles are closed (already expanded), and the orange line is the final path. Switch the heuristic to Dijkstra to watch it flood the map, or raise the weight to see it rush toward the goal, expand fewer tiles and sometimes pick a longer path.

## Prompt

```text
Implement grid A* in TypeScript for a Three.js game. Input: width, height, a Uint8Array of walls, start and goal cell indices, options {diagonal: boolean, heuristic: 'manhattan' | 'octile' | 'zero', weight: number}. Use a binary min-heap with lazy deletion, tie-break toward larger g, diagonal cost √2 with no corner cutting, and typed arrays for g/parent/closed. Return {path: number[] | null, cost, expanded: number[]} so the search can be visualized. Write Vitest tests: on a hand-made map, A* cost equals Dijkstra (heuristic 'zero') cost and A* expands no more nodes; an 8-way path around a pillar costs 4, not 2√2; a goal walled off returns null.
```

## Related

- [Steering Behaviors](https://gdcs.coody.app/ai/steering/steering-behaviors.md) — Seek, arrive and separation each compute a desired velocity; steering is desired minus current velocity, capped and summed. Simple rules, lifelike motion.
- [Finite State Machine](https://gdcs.coody.app/ai/decision/finite-state-machine.md) — An FSM keeps an AI or character in exactly one state, such as Idle, Patrol, Chase or Attack. A table of events decides every legal transition.
- [Raycasting](https://gdcs.coody.app/threejs/rendering/raycasting.md) — A ray is an origin plus a direction. Raycasting returns the nearest surface it crosses, with hit point, distance and surface normal.

## Further reading

- [Red Blob Games — Introduction to A*](https://www.redblobgames.com/pathfinding/a-star/introduction.html)
- [Red Blob Games — Heuristics (Amit's A* pages)](https://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html)

---
Source: Game Development Cheat Sheet (https://gdcs.coody.app)