Pathfinding in Videogames: A* and Its Variants

Every time an enemy in a game chases you through a dungeon, a squad of units crosses a map in an RTS, or an NPC walks around a chair instead of through it, there's a pathfinding algorithm running under the hood. The choice of algorithm (and how it's tuned) is often the difference between a world that feels alive and one that stutters every time something moves.

A* is the answer you'll hear most often. It's taught in every intro AI course, shipped in every engine, and blogged about constantly. But A* alone doesn't scale to modern game sizes. Large open worlds, thousands of units, dynamic obstacles, all of them require variants: NavMesh for 3D traversal, Jump Point Search for open grids, hierarchical approaches for continent-scale maps.

This article explores those solutions: why simpler algorithms fall short, how A* really works under the heuristic, which variants solve which problems, and how to implement the core in Unity/C#.

1. Why Moving Characters in a Game Is Hard

At first glance, moving from A to B on a grid sounds trivial. Breadth-First Search (BFS) finds the shortest path in a grid of uniform cost in O(V + E). Drop it in, done. Except games almost never have uniform cost.

A swamp tile costs more to cross than a road. A ladder costs more than flat ground. A tile covered by enemy fire in a tactics game might cost infinitely more than walking around it. The moment costs vary, BFS gives you the fewest-tiles path, not the cheapest one, and those are usually different.

Scale makes it worse. A BFS that explores 10,000 tiles on a small map explodes into millions on a 500x500 RTS map. Expanding to 3D, or to thousands of concurrent agents, is where performance problems begin.

2. Dijkstra: The Baseline

Dijkstra's algorithm solves the weighted shortest-path problem. Starting from the source, it expands outward to the cheapest-known node each iteration, updating distances as it goes. When it reaches the target, the path is guaranteed optimal.

The problem is the word EXPAND. Dijkstra has no notion of which direction the target is in. It expands a roughly circular frontier, exploring tiles that move away from the target with the same enthusiasm as tiles that move toward it. On a 100x100 grid with the target on the opposite corner, you'll explore most of the map before reaching it.

1// Dijkstra's core loop — expand cheapest known node
2while (open.Count > 0)
3{
4    Node current = open.Dequeue(); // lowest g
5
6    if (current == target) break;
7
8    foreach (Node neighbor in current.Neighbors)
9    {
10        float tentativeG = current.G + Cost(current, neighbor);
11        if (tentativeG < neighbor.G)
12        {
13            neighbor.G = tentativeG;
14            neighbor.Parent = current;
15            open.Enqueue(neighbor, tentativeG);
16        }
17    }
18}

Dijkstra is still useful: it's exact, it handles arbitrary positive weights, and when you don't know where the target is (flow fields, multiple sources, uniform-terrain exploration) it's the right tool. But for single-source, single-target queries, it wastes effort. That's the gap A* closes.

3. A*: Dijkstra + Heuristic

A* extends Dijkstra with one idea: guess how far you still have to go. For each node, instead of prioritizing by g(n) (known cost from start), you prioritize by f(n) = g(n) + h(n), where h(n) is a heuristic estimate of the remaining cost to the target.

The effect is dramatic. A good heuristic pulls the search toward the target instead of expanding a circle. On the same 100x100 grid where Dijkstra explores 10,000 tiles, A* with a reasonable heuristic might explore 200. Same result, orders of magnitude less work.

A* is Dijkstra with a sense of direction.

Two properties of h(n) matter. Admissibility means the heuristic never overestimates the true remaining cost (if it does, A* can return a suboptimal path). Consistency (also called the monotone condition) means the heuristic respects the triangle inequality: h(n) <= cost(n, m) + h(m) for any neighbor m. Consistent heuristics are always admissible, and they let you skip re-opening nodes from the closed set, a meaningful performance gain.

4. Choosing a Heuristic

The heuristic is where most A* implementations succeed or fail. For grid-based games, the choice follows directly from the movement rules:

• Manhattan distance: 4-directional movement only (no diagonals). |dx| + |dy|.
• Chebyshev distance: 8-directional movement where diagonals cost the same as cardinals. max(|dx|, |dy|).
• Octile distance: 8-directional where diagonals cost ~1.414 (sqrt 2). max(|dx|, |dy|) + (sqrt(2) - 1) * min(|dx|, |dy|).
• Euclidean distance: any-angle movement. sqrt(dx*dx + dy*dy). Admissible for grids too, but loose. Underestimating makes A* slower.

1public static class Heuristics
2{
3    public static float Manhattan(Vector2Int a, Vector2Int b) =>
4        Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
5
6    public static float Chebyshev(Vector2Int a, Vector2Int b) =>
7        Mathf.Max(Mathf.Abs(a.x - b.x), Mathf.Abs(a.y - b.y));
8
9    public static float Octile(Vector2Int a, Vector2Int b)
10    {
11        int dx = Mathf.Abs(a.x - b.x);
12        int dy = Mathf.Abs(a.y - b.y);
13        return Mathf.Max(dx, dy) + (Mathf.Sqrt(2f) - 1f) * Mathf.Min(dx, dy);
14    }
15
16    public static float Euclidean(Vector2Int a, Vector2Int b) =>
17        Vector2Int.Distance(a, b);
18}

Tie-breaking matters too. When multiple nodes share the same f, A* picks arbitrarily, which often produces paths that zig-zag along diagonals. A small trick: multiply the heuristic by a factor slightly greater than 1 (like 1.001) to break ties in favor of nodes closer to the target. The result is straighter, more visually appealing paths with almost no cost hit.

One tip is to multiply the heuristic by a factor slightly greater than 1 (for example, 1.001) to break ties in favor of nodes closer to the target. The result is straighter, more visually appealing paths with almost no cost hit.

5. Implementing A* in Unity/C#

Here's a complete A* implementation for a 2D grid. The three things that matter are the priority queue, the closed set (a hash set, not a list), and the reconstruction step.

1public class AStarNode
2{
3    public Vector2Int Position;
4    public float G = float.PositiveInfinity;
5    public float H;
6    public float F => G + H;
7    public AStarNode Parent;
8    public bool Walkable;
9}
10
11public class AStarGrid
12{
13    private readonly AStarNode[,] _nodes;
14    private readonly int _width, _height;
15
16    public AStarGrid(bool[,] walkable)
17    {
18        _width = walkable.GetLength(0);
19        _height = walkable.GetLength(1);
20        _nodes = new AStarNode[_width, _height];
21        for (int x = 0; x < _width; x++)
22        for (int y = 0; y < _height; y++)
23            _nodes[x, y] = new AStarNode
24            {
25                Position = new Vector2Int(x, y),
26                Walkable = walkable[x, y],
27            };
28    }
29
30    public List<Vector2Int> FindPath(Vector2Int start, Vector2Int goal)
31    {
32        ResetNodes();
33        var startNode = _nodes[start.x, start.y];
34        var goalNode  = _nodes[goal.x,  goal.y];
35
36        startNode.G = 0;
37        startNode.H = Heuristics.Octile(start, goal);
38
39        var open   = new PriorityQueue<AStarNode, float>();
40        var closed = new HashSet<AStarNode>();
41        open.Enqueue(startNode, startNode.F);
42
43        while (open.Count > 0)
44        {
45            var current = open.Dequeue();
46            if (current == goalNode) return Reconstruct(current);
47
48            closed.Add(current);
49
50            foreach (var neighbor in GetNeighbors(current))
51            {
52                if (!neighbor.Walkable || closed.Contains(neighbor)) continue;
53
54                float stepCost = StepCost(current, neighbor);
55                float tentativeG = current.G + stepCost;
56                if (tentativeG >= neighbor.G) continue;
57
58                neighbor.Parent = current;
59                neighbor.G = tentativeG;
60                neighbor.H = Heuristics.Octile(neighbor.Position, goal);
61                open.Enqueue(neighbor, neighbor.F);
62            }
63        }
64        return null; // unreachable
65    }
66
67    private static float StepCost(AStarNode a, AStarNode b)
68    {
69        bool diagonal = a.Position.x != b.Position.x
70                     && a.Position.y != b.Position.y;
71        return diagonal ? 1.41421356f : 1f;
72    }
73
74    private static List<Vector2Int> Reconstruct(AStarNode end)
75    {
76        var path = new List<Vector2Int>();
77        for (var n = end; n != null; n = n.Parent) path.Add(n.Position);
78        path.Reverse();
79        return path;
80    }
81    // GetNeighbors and ResetNodes omitted for brevity
82}

6. NavMesh: When Grids Aren't Enough

3D worlds rarely decompose cleanly into grids. A tilted ramp, an overhanging ledge, a door that's half a tile wide. None of these fit the grid abstraction well. The industry solution is the Navigation Mesh: a set of convex polygons representing the walkable surface of the world.

Pathfinding on a NavMesh still uses A*, but the graph is different. Each polygon is a node, and edges connect polygons that share a border. The graph is small (hundreds of polygons instead of millions of tiles), the heuristic is Euclidean distance between polygon centers, and the path is a sequence of polygons that you then "funnel" into a concrete sequence of points.

Unity ships this out of the box. Mark geometry as Navigation Static, bake the NavMesh in the editor (or at runtime with NavMeshSurface), attach a NavMeshAgent to your character, and call SetDestination. The engine handles A*, funneling, and steering.

1using UnityEngine;
2using UnityEngine.AI;
3
4[RequireComponent(typeof(NavMeshAgent))]
5public class EnemyChaser : MonoBehaviour
6{
7    [SerializeField] private Transform target;
8    private NavMeshAgent _agent;
9
10    void Awake() => _agent = GetComponent<NavMeshAgent>();
11
12    void Update()
13    {
14        if (target == null) return;
15        _agent.SetDestination(target.position);
16    }
17}

The built-in NavMesh is fine for most games. When it isn't (moving platforms, destructible terrain, procedurally generated worlds), you reach for alternatives. Unity's AI Navigation package supports runtime baking and NavMeshLinks for off-mesh jumps. For full control, A* Pathfinding Project (Aron Granberg) is the go-to third-party option and ships its own grid, NavMesh, and hierarchical modes.

7. Jump Point Search (JPS)

On uniform-cost grids (every walkable tile costs the same), A* does a lot of redundant work. It expands every tile in a roughly elliptical region between start and goal, and most of those expansions just confirm that a straight line is still a straight line. Jump Point Search exploits this symmetry: it skips tiles that can't possibly be on an optimal path.

JPS replaces the "expand all neighbors" step of A* with a recursive jump procedure. Instead of stepping one tile at a time, it "jumps" in straight lines and diagonals, only stopping at tiles that are forced-neighbors (tiles that could lead to a shorter path around an obstacle) or at the goal. The result is an A* that can skip hundreds of tiles per step on open maps, with speedups of 10x or more compared to vanilla A*.

1// Simplified JPS jump — horizontal/vertical case
2// Returns the next "jump point" along direction (dx, dy), or null if none
3private Vector2Int? Jump(Vector2Int from, Vector2Int dir, Vector2Int goal)
4{
5    var next = from + dir;
6    if (!InBounds(next) || !IsWalkable(next)) return null;
7    if (next == goal) return next;
8
9    // Diagonal move: recurse on both cardinal components first
10    if (dir.x != 0 && dir.y != 0)
11    {
12        if (Jump(next, new Vector2Int(dir.x, 0), goal).HasValue) return next;
13        if (Jump(next, new Vector2Int(0, dir.y), goal).HasValue) return next;
14    }
15
16    // Forced-neighbor check (obstacle creates a required turn)
17    if (HasForcedNeighbor(next, dir)) return next;
18
19    // Keep jumping in the same direction
20    return Jump(next, dir, goal);
21}

The tradeoff: JPS only works on uniform-cost grids. The moment you introduce variable terrain costs (swamp, roads, etc.), the symmetries it exploits break down. There are extensions (JPS+, JPS(B), Bounded JPS), but all of them target the same grid-with-uniform-cost case. If you're building a roguelike or tile-based tactics game without variable terrain costs, JPS is essentially free performance. If you have costed terrain, plain A* is the correct choice.

8. Hierarchical A* (HPA*)

Even with JPS, a single A* call over a 2048x2048 grid is slow. When you have hundreds of RTS units pathing simultaneously across a continent, no amount of per-query optimization helps. You need to reduce the problem size.

HPA* (Hierarchical Pathfinding A*) does this by decomposing the world into clusters. You run A* at two levels: first on the abstract graph of clusters to find which clusters to traverse, then on each cluster's local grid to find the exact path through it. The result is a path that's slightly suboptimal but an order of magnitude faster to compute, and you can refine each cluster's segment lazily, only when the unit actually gets there.

• Divide the grid into NxN clusters (commonly 10x10 or 16x16).
• Identify border tiles where clusters connect. These become nodes in the abstract graph.
• Precompute cluster-to-cluster edge costs by running A* inside each cluster between its border nodes.
• At query time, A* runs on the abstract graph to pick a sequence of clusters, then refines each local segment on demand.

HPA* shines in RTS and open-world games. Classics like Age of Mythology and more recently games using the A* Pathfinding Project's Recast graph with hierarchical metadata use variations of this pattern. The cost is memory (you store precomputed cluster connections) and more complex invalidation logic when terrain changes.

Hierarchical pathfinding trades exact paths for paths that exist fast enough to matter.

9. Dynamic Environments and D* Lite

A* plans once and moves. If the world changes (a door opens, a bridge collapses, another unit blocks a corridor), you have to replan from scratch. For small paths that's fine. For long paths over large maps with frequent changes, it's wasteful. Enter D* and its modern variant, D* Lite.

D* Lite is an incremental search algorithm. It computes an initial path, then when the world changes it repairs the path locally instead of recomputing everything. Only the part of the search tree affected by the change gets updated. For agents moving through partially known or dynamic environments (fog of war, destructible terrain, robots in the real world), D* Lite can be an order of magnitude more efficient than repeatedly calling A*.

The implementation is more complex than A*: it runs the search "backward" from goal to start, maintains an rhs value alongside g, and uses a priority queue keyed on a lexicographic tuple instead of a single float. Most games don't need it: a well-tuned A* with occasional full replans is simpler and plenty fast. But when you're pathfinding in a dungeon crawler where doors open constantly or an RTS with constant terrain modification, it's worth the complexity.

10. Case Study: Otter's Hell

In Otter's Hell (a bullet-hell roguelite under development in Unity), enemies need to chase Sparkles (the player) through procedurally assembled rooms. The levels aren't static tiles: enemies spawn, obstacles move, and destructible cover comes and goes. Picking the right pathfinding approach mattered because dozens of enemies can be active at once.

The first instinct was NavMesh. Unity's built-in agent handles steering and avoidance nicely. But the procedural nature of rooms meant NavMesh baking had to happen at runtime, and 3D NavMesh on 2D content felt like overkill. Large re-bakes also spiked frame times on weaker hardware.

The final solution is a grid-based A* on a 2D cost grid per room. Each level's grid is small enough that even a naive implementation finishes in well under a millisecond per query, and cheap to rebuild when the layout mutates. Each enemy requests a path to the target on a cadence (not every frame), and between replans, local steering handles short-term avoidance.

1public class EnemyPathfinder : MonoBehaviour
2{
3    [SerializeField] private float replanIntervalSeconds = 0.25f;
4
5    private AStarGrid _grid;
6    private List<Vector2Int> _path;
7    private int _waypointIndex;
8    private float _replanTimer;
9
10    public void SetGrid(AStarGrid grid) => _grid = grid;
11
12    void Update()
13    {
14        _replanTimer -= Time.deltaTime;
15        if (_replanTimer <= 0f)
16        {
17            _path = _grid.FindPath(
18                WorldToGrid(transform.position),
19                WorldToGrid(Sparkles.Instance.transform.position));
20            _waypointIndex = 0;
21            _replanTimer = replanIntervalSeconds;
22        }
23
24        FollowPath();
25    }
26}

Replanning every 250ms is effectively free per enemy, the grids are tiny, and the gameplay result is enemies that track the player intelligently without the overhead of NavMesh or a hierarchical system the game doesn't need. The lesson: the right algorithm depends on scale. A*'s variants exist for huge maps and tight budgets. Most games can get away with the simple version.

11. Choosing the Right Algorithm

There's no universal answer, but there are recommendations for leaning toward one algorithm or another. This is, roughly, the most appropriate choice by game type:

• Small 2D grid, variable terrain cost (tactics game, roguelike with swamps/roads) → vanilla A* with Octile or Manhattan heuristic. Don't overthink it.
• Small 2D grid, uniform cost (classic roguelike, puzzle movement) → JPS for ~10x speedup over A* for effectively free.
• 3D world, moderate scale (action game, adventure) → NavMesh. Unity's built-in is fine until it isn't.
• Very large 2D map, many agents (RTS, open-world crowd simulation) → HPA* or a flow field for shared destinations.
• Highly dynamic environment, partial knowledge (stealth AI in destructible worlds, robotics) → D* Lite.
• Thousands of units to the same target (RTS units converging on a rally point, formation movement) → flow fields. One Dijkstra-from-target, every agent reads the resulting vector field.

Conclusions

Pathfinding is one of those fields where the textbook algorithm (A*) is usually the right one, and the industry variants exist to handle the edge cases the textbook version can't. Knowing which edge case you actually have is most of the battle.

• Dijkstra is exact but wasteful for single-target queries; A* beats it almost everywhere.
• A* is Dijkstra plus a heuristic. The heuristic must never overestimate (admissible) for an optimal path.
• Match the heuristic to the movement rules: Manhattan for 4-directional, Octile for 8-directional, Euclidean for any-angle.
• NavMesh is A* on a polygon graph, great for 3D, great when the engine does the baking for you.
• JPS gives huge speedups on uniform-cost grids by pruning symmetric paths.
• HPA* scales to continent-sized maps by decomposing them into clusters.
• D* Lite is for highly dynamic environments; for most games, A* with local repair is simpler and enough.
• Profile first: The fancy algorithms solve real problems, but most games never hit them.

The pattern across all of these algorithms is the same: trade a little optimality for a lot of speed, or a little memory for a lot of scale. Every variant is an answer to a specific pressure. When you feel that pressure (a slow query, a missed frame, a search that can't finish in time), you'll know which one to pick.

Good pathfinding is invisible. Players don't notice the algorithm. They only notice when it breaks.