The first time I implemented A* from scratch, I thought I understood it. I’d read the theory, seen the pseudocode, understood the concept of f = g + h. Then I ran it in my game and watched enemies take bizarre routes, get stuck in loops, and occasionally just give up entirely. Turns out there’s a massive gap between understanding an algorithm conceptually and making it work reliably in production. A* is deceptively simple on paper and endlessly nuanced in practice.
What Makes A* Special
A* (pronounced “A-star”) has dominated game pathfinding since the mid-1980s because it hits a sweet spot: it’s guaranteed to find the shortest path, it’s reasonably efficient, and it’s conceptually straightforward enough that most programmers can implement it without a PhD in computer science.
The algorithm is essentially an informed search. Unlike breadth-first search that explores outward blindly in all directions, A* uses a heuristic to guide its search toward the goal. This makes it dramatically faster for typical pathfinding problems.
Here’s the core idea: A* maintains two scores for each node it evaluates. The g-score is the actual cost to reach that node from the start. The h-score (heuristic) is an estimate of the cost from that node to the goal. Add them together and you get the f-score: your best guess for the total path cost if you go through that node.
A* always expands the node with the lowest f-score next. This means it explores paths that seem most promising first, dramatically reducing wasted computation.
The Mechanics: How It Actually Works
Let me walk through what’s happening under the hood, because this is where implementation details matter.
You start with two lists: an open list (nodes to evaluate) and a closed list (nodes already evaluated). The open list begins with just your start node. Each iteration, you:
- Pull the lowest f-score node from the open list
- If it’s the goal, you’re done reconstruct the path and return
- Otherwise, examine all neighboring nodes
- For each neighbor: calculate its g-score (current node’s g-score plus movement cost to neighbor)
- If this neighbor is already in the closed list with a better g-score, skip it
- If it’s not in the open list, or we found a better path to it, update its scores and add/update it in the open list
- Move the current node to the closed list
- Repeat
The open list needs to be a priority queue for efficiency. I’ve seen implementations using simple arrays with linear searches for the minimum f-score this works for tiny graphs but becomes a bottleneck quickly. A binary heap is the classic choice, though I’ve used Fibonacci heaps for specific cases where we were doing tons of decrease-key operations.
The Heuristic: Where the Magic Happens
The heuristic function is what makes or breaks A* performance. It needs to be admissible never overestimate the actual distance to the goal. Overestimate and you lose the guarantee of finding the shortest path.
For grid-based pathfinding, Euclidean distance (straight-line) is common and admissible since you can’t travel shorter than a straight line. For navmesh pathfinding, I typically use Euclidean distance between polygon centers, though this has edge cases.
Manhattan distance (sum of absolute differences in coordinates) works for grid movement that’s restricted to cardinal directions. It’s slightly faster to calculate than Euclidean.
The interesting thing is that a more accurate heuristic makes A* faster. If your heuristic is exactly right, A* makes a beeline to the goal without exploring unnecessary nodes. If it’s zero (completely uninformed), A* degrades to Dijkstra’s algorithm and explores in all directions.
I’ve tuned heuristics by multiplying them by small constants (1.0 to 1.5) to make A* more aggressive. This speeds up pathfinding but can find suboptimal paths. For games, a path that’s 2% longer but calculated 50% faster is often a good trade. Players don’t notice slight suboptimality, but they definitely notice frame drops.
Implementation Pitfalls I’ve Hit
Floating point comparison errors caused me days of headaches once. Checking if a node was “already in the closed list with a better score” failed intermittently because g-scores weren’t exactly equal due to floating point precision. I learned to use epsilon comparisons or, better yet, avoid floating point for path costs when possible.
Memory allocation kills performance if you’re not careful. Early implementations would allocate new node objects constantly. Now I use object pools pre-allocate a bunch of node structures and reuse them. For a typical pathfinding operation, you might evaluate hundreds of nodes; allocating each individually tanks performance.
Hash table overhead for the open and closed lists can surprise you. I’ve seen teams use unordered_map/Dictionary for everything and wonder why pathfinding is slow. For small node counts, simple arrays with linear search can actually be faster due to cache locality. Profile your specific case.
The parent pointer tracking for path reconstruction needs careful handling. Each node needs to remember which node it came from so you can backtrack from the goal to the start. I’ve had bugs where parent pointers formed cycles due to incorrect updates, causing infinite loops during path reconstruction.
Optimization Techniques That Actually Work
Bidirectional A* runs two searches simultaneously one from start toward goal, one from goal toward start. When they meet, you’ve found a path. This can be 2-3x faster for long paths because you’re searching two smaller areas instead of one large one. The implementation complexity is significant though, and it doesn’t help much for short paths.
Jump Point Search is brilliant for uniform-cost grids. It “jumps” over symmetric paths instead of exploring every node. For grid-based games, I’ve seen 10x speedups over standard A*. The catch is it only works on uniform grids navmeshes need different optimizations.
Hierarchical pathfinding is my go-to for large environments. Divide the world into regions, precompute connections between regions, and run A* at two levels: high-level between regions, then low-level within regions. For open-world games, this is often essential.
Path caching and sharing helps when multiple characters path to the same destination. If five enemies are all converging on the player’s position, calculate one path and share it (with some variation to avoid identical movement). This requires infrastructure to manage cached paths and invalidate them when the environment changes.
I’ve used iterative deepening A* when path calculation absolutely must complete within a fixed time budget. Set a maximum node expansion count, and if you hit it before finding the goal, return a partial path toward the goal. Characters start moving in the right direction while calculation continues in subsequent frames.
When A* Isn’t the Answer
For massive numbers of units (hundreds or thousands), individual A* paths per unit becomes impractical. Flow fields or influence maps work better calculate once, use for many units.
For highly dynamic environments where obstacles constantly change, invalidating paths continuously, you might need reactive planning approaches or potential fields instead of pre-calculated paths.
Very simple navigation sometimes doesn’t need A*. If you’re just moving toward a target in mostly open space, a direct approach with local obstacle avoidance can be faster and simpler.
I worked on a puzzle game where the AI needed to find any path, not the shortest one. Breadth-first search was simpler and sufficient. Using A* would’ve been overengineering.
Debugging A* (Because You Will Need To)
Visualization is absolutely critical. I always build tools to draw:
- The navmesh or grid
- The open list (what we’re considering)
- The closed list (what we’ve evaluated)
- The final path
- F/g/h scores at each node
Without this, debugging is guessing. With it, you can usually spot issues immediately oh, the heuristic is wrong here, or this edge cost is incorrect, or the goal node isn’t in the navmesh at all.
Unit tests for pathfinding are invaluable. Create known scenarios: straight path, path around obstacle, path through narrow passage, unreachable goal. If these don’t work consistently, your implementation has bugs.
I keep a “pathfinding test level” in every project a purpose-built environment with various navigation challenges. Anytime I modify pathfinding code, I run characters through this level to catch regressions.
Modern Context and Tools
Most game developers don’t implement A* from scratch anymore. Unity’s NavMeshAgent, Unreal’s navigation system, and other middleware handle it. But understanding how A* works is still crucial for:
- Debugging when pathfinding behaves unexpectedly
- Optimizing performance for your specific game
- Implementing custom navigation for special cases
- Making informed decisions about navigation parameters
The fundamental algorithm hasn’t changed in decades, but implementations keep getting smarter. Modern engines use optimizations like pre-computed navigation queries, compressed pathfinding graphs, and SIMD operations for batch processing.
Practical Takeaways
If you’re implementing A* yourself: start simple, verify correctness with basic tests, then optimize. A correct but slow implementation beats a fast but buggy one every time.
Use engine-provided solutions when possible, but know how they work. You’ll need to tune costs, adjust heuristics, and diagnose failures.
For most games, A* on a navmesh is still the right answer. It’s been refined over 40+ years of game development and handles the vast majority of pathfinding needs efficiently.
The algorithm itself is elegant. The devil, as always, is in the implementation details, performance optimization, and handling the infinite edge cases that real game worlds throw at you. But once you’ve wrestled A* into submission, it’s an incredibly reliable workhorse that you’ll use in project after project.
Frequently Asked Questions
What does the “star” in A mean?*
It’s just notation indicating it’s an improved version of algorithm A. The asterisk denotes optimality A* is guaranteed to find the optimal (shortest) path given an admissible heuristic.
How fast is A in practice?*
Depends heavily on graph complexity and path length. Simple paths might take 0.1-0.5ms, complex long-distance paths can take 5-20ms. Optimization techniques and async processing are essential for games.
What’s the difference between A and Dijkstra’s algorithm?*
Dijkstra’s is essentially A* with a heuristic of zero. A* adds the heuristic to guide the search toward the goal, making it much faster for point-to-point pathfinding.
Can A handle moving targets?*
Not directly—it calculates a path to a fixed goal. For moving targets, you need to either recalculate periodically, predict target movement, or use pursuit behaviors that don’t rely on pathfinding.