GDnD Wiki

GDnD Wiki

This site is for Ulster University students and staff. Enter the class access password to continue.

Pathfinding Algorithms

10 min read

Summary

Pathfinding depends on two ideas students often meet before they have names for them: the heuristic that guides search, and the spatial representation the search runs over, such as a navmesh, grid, or waypoint graph.

Pathfinding algorithms find routes through a discretised representation of game space. A* (A-star) is the near-universal default in game AI: it combines Dijkstra’s optimal shortest-path search with a heuristic estimate of remaining distance to focus exploration toward the goal. This page covers A* fundamentals, critical implementation optimisations, advanced variants (JPS+, Theta*), and how the choice of search space representation interacts with algorithm performance.

(Rabin and Sturtevant, Game AI Pro 360: Guide to Movement and Pathfinding, Ch. 1, 2, 10, 12; see source-game-ai-pro-360-movement-pathfinding)

Key ideas

The A* cost formula

f(x) = g(x) + h(x)
  • g(x) — the actual cost paid to reach node x from the start.
  • h(x) — the heuristic estimate of cost from x to the goal.
  • Nodes are sorted on the open list by f(x) and expanded in lowest-cost order.
  • A heuristic is admissible if it never overestimates the true remaining cost; admissibility guarantees an optimal path.

When the weight is adjusted: f(x) = g(x) + h(x) × weight

  • weight = 0 → degenerates to Dijkstra (no heuristic, uniform expansion)
  • weight = 1 → classic A*
  • weight > 1 → weighted A* (epsilon-A*): faster, possibly suboptimal — weight 1.1–1.5 is a practical sweet spot for games

Heuristic choice on a grid

For an 8-directional grid, the octile heuristic is the correct choice:

h = max(Δx, Δy) + 0.41 × min(Δx, Δy)

Manhattan distance overestimates and violates admissibility for diagonal movement. Euclidean (straight-line) distance underestimates, so it is admissible but less tight. Octile distance matches the actual movement model and minimises wasted node expansions.

Open and closed lists

  • Open list — nodes discovered but not yet expanded; typically a min-heap (priority queue) sorted by f.
  • Closed list — already expanded nodes; prevents re-expansion.
  • Tie-breaking towards higher g (closer to the goal) when f values are equal — this substantially reduces unnecessary expansions on maps with many equal-cost paths.

Search space representations

The choice of representation is more impactful than any other optimisation because it determines how many nodes must be considered (Sturtevant, Ch. 2).

RepresentationNodesProsCons
GridHigh (one per cell)Simple, easy to edit dynamically, easy localizationMemory-heavy for large worlds; produces 45°/90° paths unless smoothed
Waypoint graphLow (manually placed)Very fast search, easy to understandPoor path quality if sparse; hard to dynamically modify; localization issues
Navigation meshMedium (one per polygon)Accurate world representation; free-angle movement; compactComplex to build; harder to update dynamically; geometric edge cases

Hierarchical pathfinding combines representations at multiple levels of abstraction (e.g., room-to-room at high level, cell-to-cell within rooms). Used in Dragon Age: Origins (two grid abstraction levels) and Company of Heroes (hex grid + square grid). Enables fast high-level planning for large worlds.

Grids suit tower-defence and top-down 2D games. Navigation meshes suit 3D character navigation — Unity’s built-in NavMesh is a production-ready navmesh implementation. Waypoint graphs remain useful when fast planning matters more than path precision.

A* implementation optimisations

Eight optimisations from most to least impactful (Rabin and Sturtevant, Ch. 1):

1. High-quality heuristics

The tighter the heuristic, the fewer nodes A* expands. Three approaches:

Roy–Floyd–Warshall (precomputed lookup): Precompute every pairwise shortest path offline and store in a lookup table. Path generation is O(p) (just follow the table). Memory is O(n²), which becomes impractical for large node counts but is feasible on zone-divided graphs.

Euclidean embedding: Store single-source shortest-path distances from a small number of pivot nodes. The heuristic h(x,y) = |d(p,x) – d(p,y)| for pivot p improves accuracy significantly over simple geometric distance. Multiple pivots allow taking the maximum. O(kn) memory where k is pivot count. Good pivot locations: map exits in RPGs, flag locations in CTF.

2. Optimal search space representation

Use a navmesh or waypoint graph rather than a fine-grained grid wherever possible — fewer nodes = less work.

3. Preallocate all memory

Never allocate memory during search. Use a fixed-size node pool and reuse it. Per-node “search ID” flags replace clearing the closed list between searches.

4. Weighted heuristic (overestimating)

Multiply h(x) by a weight > 1. Weight 1.1–1.5 trades near-unnoticeable path quality for substantial speed gains, especially in open terrain. Weights up to 2–3 work well when backtracking is rare.

5. Better heuristics

Use the octile heuristic on 8-directional grids; use straight-line distance on navmeshes. Select the heuristic most closely matching the actual movement model.

6. Open list sorting

Use a binary heap or similar priority queue. Cache the last inserted node before insertion — in many searches it is immediately removed and re-inserting would be wasteful. When f-costs are integers or have few unique values, a bucket-sorted open list (one array per f-cost value, treated as a LIFO stack) can be dramatically faster.

7. Don’t backtrack

Never consider the parent node as a neighbour. This is free and removes ~1/branching-factor nodes from consideration (1/8 for grids, ~1/3 for navmeshes).

8. Cache successors

Store each node’s neighbours explicitly rather than recomputing from map data each expansion.

JPS+ — Jump Point Search Plus

JPS+ (Rabin and Silva, Ch. 10) is an extreme A* optimisation for static, uniform-cost grids that achieves up to 116× speedup while remaining optimal.

Core ideas

Pruning: When expanding a node, most neighbours can be provably skipped because the same or shorter path would visit them via the parent. Only forced neighbours (neighbours that would be blocked by a wall if not for the current node) need consideration alongside the natural progression direction.

Jump points: Rather than placing every node on the open list, JPS places only jump points — nodes through which at least one optimal path must pass. This dramatically reduces open-list operations, which are a major bottleneck.

JPS+ preprocessing: JPS identifies forced neighbours at runtime via recursive scan. JPS+ precomputes and stores, for every node and every direction, the distance to the next jump point (or wall if none). A positive distance means “jump point this far”, a negative distance means “wall this far”. Runtime is then a simple lookup.

Four jump point types

TypeDescription
PrimaryNode with a forced neighbour — identified once during preprocessing
StraightNode from which a cardinal direction reaches a primary jump point before a wall
DiagonalNode from which a diagonal direction reaches a primary or straight jump point
TargetSynthesised at runtime when the goal is in the direction of travel and closer than the stored jump-point distance

Performance

  • On open maps: up to 116× faster than A*, ~10× faster than JPS.
  • On dense mazelike maps: ~2.5× faster than optimised A*.
  • Trade-off: requires static map and 8 numbers stored per grid cell; map changes require full preprocessing.
// Pseudocode for JPS+ runtime (per Rabin & Silva, Ch. 10)
// Distance > 0 → jump point that many cells away in that direction
// Distance ≤ 0 → wall that many cells away (store as negative)
while (!openList.IsEmpty())
{
    Node cur = openList.Pop();
    if (cur == goal) return PathFound;
    foreach (Direction dir in ValidDirs(cur.parent))
    {
        int dist = cur.distances[(int)dir];
        if (IsCardinal(dir) && GoalInDirection(cur, goal, dir)
            && DistToGoal(cur, goal, dir) <= Mathf.Abs(dist))
        {
            // Goal is reachable directly — add goal as successor
        }
        else if (dist > 0)
        {
            // Jump point in this direction — add it as successor
        }
    }
}

Theta* — any-angle pathfinding

Theta* (Nash and Koenig, Ch. 12) solves the problem that A* on a grid constrains paths to grid edges, producing unnatural paths 8% longer than the continuous-space optimum.

The key modification

A* only allows a vertex’s parent to be a visible neighbour. Theta* allows the parent to be any vertex with line-of-sight to the current vertex. The single change is in ComputeCost:

ComputeCost(s, s′):
    // Path 2 — skip s entirely if parent(s) can see s′
    if lineofsight(parent(s), s′):
        if g(parent(s)) + dist(parent(s), s′) < g(s′):
            parent(s′) = parent(s)
            g(s′) = g(parent(s)) + dist(parent(s), s′)
    else:
        // Path 1 — standard A* update
        if g(s) + dist(s, s′) < g(s′):
            parent(s′) = s
            g(s′) = g(s) + dist(s, s′)

The triangle inequality guarantees Path 2 is never longer than Path 1 when line-of-sight holds.

Results

  • Paths approximately 4% shorter than A* paths.
  • Approximately 2–3× slower than A* with the octile heuristic.
  • Approximately 2× faster than A*-PostSmoothed with the straight-line heuristic.
  • Nearly identical runtime to A* when using the straight-line heuristic for both.

Lazy Theta* defers the line-of-sight check to expansion time rather than generation, reducing total checks and improving performance in dense environments.

Path post-processing (rubber-band smoothing)

A simpler alternative to Theta* is to run A* normally and then postprocess the path by removing waypoints while line-of-sight holds. This shortens paths by 1–3%. Simpler to implement than Theta* but less reliable — the A* path variant chosen at search time affects how well rubber-banding can shorten it.

Common mistakes (bad ideas)

Anti-patternWhy it fails
Simultaneous searches (time-slicing N paths)Requires N open lists; cache thrashing negates any benefit
Bidirectional A*Both searches can back up behind barriers simultaneously, potentially doing twice the work in the worst case
Caching successful pathsPath space is enormous; cache hit rate is negligible while memory cost is high

In practice (Unity)

Unity’s built-in NavMesh system uses a navigation mesh representation with ORCA-based local avoidance. For most 3D games this is the correct default.

Custom A* is appropriate when:

  • Using a 2D tilemap (grid representation makes A* trivial)
  • Needing JPS+ performance on static maps
  • Building an RTS with thousands of units (flow field approach — see steering-behaviours)
  • Requiring custom heuristics or movement costs Unity NavMesh cannot express

Popular Unity A* packages: A* Pathfinding Project (Aron Granberg) implements JPS, hierarchical pathfinding, and navmesh variants with Unity integration.

// Minimal A* on a 2D grid (conceptual)
public List<Node> FindPath(Node start, Node goal)
{
    var openList = new SortedSet<Node>(Comparer<Node>.Create(
        (a, b) => a.FCost.CompareTo(b.FCost)));
    var closedSet = new HashSet<Node>();
 
    start.GCost = 0;
    start.HCost = OctileDistance(start, goal);
    openList.Add(start);
 
    while (openList.Count > 0)
    {
        Node current = openList.Min;
        openList.Remove(current);
        if (current == goal) return ReconstructPath(goal);
        closedSet.Add(current);
 
        foreach (Node neighbour in current.Neighbours)
        {
            if (closedSet.Contains(neighbour)) continue;
            float tentativeG = current.GCost + Distance(current, neighbour);
            if (tentativeG < neighbour.GCost)
            {
                neighbour.Parent = current;
                neighbour.GCost = tentativeG;
                neighbour.HCost = OctileDistance(neighbour, goal);
                openList.Add(neighbour);
            }
        }
    }
    return null; // no path
}
 
float OctileDistance(Node a, Node b)
{
    float dx = Mathf.Abs(a.x - b.x), dy = Mathf.Abs(a.y - b.y);
    return Mathf.Max(dx, dy) + 0.41f * Mathf.Min(dx, dy);
}

Trade-offs

AlgorithmOptimalSpeedConstraintsBest use
DijkstraYesSlow (no heuristic)Any graphWhen no heuristic available
A*YesGoodAny graphGeneral pathfinding
Weighted A*NearVery goodAny graphGames where slight suboptimality is acceptable
JPS+YesExtremeStatic uniform-cost grid only2D tactical games, RTS
Theta*NearGoodGrid or navmeshWhen path naturalness matters (no post-processing)
Flow fieldsN/A (per-goal)O(1) per agentGridMany agents, shared goal
Precomputed (RFW)YesInstant (lookup)Static world, memory budgetMMO servers, small node sets

Graph View

Backlinks