A* (pronounced “A-star”) is a graph search algorithm that finds the shortest path between two points by combining the actual distance traveled so far with an estimate of how far remains. Introduced by Peter Hart, Nils Nilsson, and Bertram Raphael in 1968, it remains one of the most widely used pathfinding algorithms in computing, powering everything from video game character movement to GPS navigation. What makes A* enduringly useful is a deceptively simple idea: instead of blindly exploring every possible route or greedily chasing whatever looks closest to the goal, it balances both considerations at once, and this balance lets it find optimal paths while skipping large swaths of the search space.
How A* Finds a Path
Imagine you are standing at one point on a map and need to reach another. You could try every possible route exhaustively, but that is painfully slow. You could always walk toward whichever neighboring spot seems closest to the goal, but that greedy approach might walk you straight into a dead end or around a long detour. A* splits the difference. For every location it considers expanding, it calculates two values and adds them together. The first is the actual cost of getting from the start to that location, accounting for every step already taken. The second is a heuristic, an educated guess of how much farther it is from that location to the goal. The sum of those two numbers is the location’s priority score, and A* always expands the location with the lowest score next.
This two-part scoring is the entire trick. The actual-cost component keeps the algorithm honest about what it has already spent, preventing it from chasing a low estimate down an expensive detour. The heuristic component gives it foresight, steering expansion toward the goal rather than outward in every direction equally. When the heuristic never overestimates the true remaining distance, the algorithm is guaranteed to find the shortest possible path. On a flat grid with no obstacles, a straight-line distance estimate works well. On a road network, travel time along direct routes can serve the same purpose.
How A* Compares to Simpler Alternatives
Two algorithms sit on either side of A* in terms of strategy. Dijkstra’s algorithm uses only the actual cost from the start, with no heuristic at all. It fans out uniformly in every direction until it reaches the goal, which means it always finds the optimal path but explores far more of the map than necessary. Greedy best-first search does the opposite: it uses only the heuristic estimate, always expanding whatever node appears closest to the goal. That makes it fast but unreliable, because it can be fooled by obstacles into taking suboptimal routes or failing to find a solution entirely.
A comparative analysis of the three approaches found that Dijkstra’s algorithm reliably finds optimal solutions but tends to be slow because it must compare every path’s cost against every other, while Greedy search is fast but sometimes fails to find the target or returns a suboptimal route. A* landed between the two, finding shorter paths than Greedy with less wasted exploration than Dijkstra’s, though it requires more information about the map (specifically that heuristic estimate) to work.1International Journal of Advances in Data and Information Systems. Greedy, A-Star, and Dijkstra’s Algorithms in Finding Shortest Path You can think of A* as Dijkstra’s algorithm that has been given a compass: it still guarantees the best route, but it wastes less time exploring directions that clearly lead away from the destination.
What Makes a Good Heuristic
The quality of A*’s performance hinges almost entirely on its heuristic function. A perfect heuristic, one that always returns the exact remaining cost, would let A* walk straight to the goal without expanding a single unnecessary node. A heuristic of zero everywhere turns A* into Dijkstra’s algorithm, because every decision is based solely on the cost so far. The practical sweet spot lies between those extremes: a heuristic that is close to the true cost but never exceeds it.
That “never exceeds” property is called admissibility, and it is the guarantee that A* will return an optimal path. If your estimate occasionally overshoots the real distance, A* might skip over the truly cheapest path in favor of one that looked cheaper based on the inflated estimate. For grid-based maps, straight-line (Euclidean) distance is a common admissible heuristic. Manhattan distance, which sums horizontal and vertical displacement as if you can only move in four directions, works well on grids that restrict diagonal movement. On road networks, precomputed landmark distances can serve as tight lower bounds.
A second desirable property is consistency (sometimes called monotonicity). A consistent heuristic never decreases by more than the actual cost of moving between two adjacent nodes. When the heuristic is consistent, A* never needs to re-open a node it has already finished processing, which simplifies implementation and improves speed. Most heuristics used in practice, including Euclidean and Manhattan distance, are both admissible and consistent.
Speeding Up A* on Grids
Standard A* on a uniform grid can spend enormous effort examining nodes that are effectively interchangeable. Consider an open field on a game map: there might be hundreds of paths from one side to the other that differ only in the order they visit identical empty tiles. All those paths have the same cost, but A* does not know that until it has explored many of them. This redundancy is called path symmetry, and eliminating it is one of the most effective ways to accelerate grid-based search.
Jump Point Search (JPS) is a well-known symmetry-breaking technique that addresses this problem. Instead of expanding every neighbor one tile at a time, JPS “jumps” ahead along straight lines, skipping over tiles that cannot possibly lead to a shorter path than what the current expansion direction already offers. It only stops at “jump points,” which are locations where the path might need to change direction, typically near obstacles or map edges. The result is that A* with JPS examines far fewer nodes to find the same optimal path.2Journal of Artificial Intelligence Research. Regarding Goal Bounding and Jump Point Search Further refinements to JPS have introduced both online and offline optimization techniques that improve performance even more, particularly in the kinds of grid maps common in computer games.3Proceedings of the International Conference on Automated Planning and Scheduling. Improving Jump Point Search
JPS is popular because it requires no preprocessing: you can drop it into an existing A* implementation on a uniform-cost grid and immediately see results. The tradeoff is that it works best on grids where all traversable tiles have equal cost. On weighted grids, where some terrain is more expensive to cross than other terrain, the symmetry-breaking logic becomes more complicated and the speedups shrink.
Navigation Meshes and Hierarchical Search
Grids are conceptually simple, but they can be wasteful representations of space. A large open room on a game map might be represented by thousands of identical grid cells, each of which A* must consider individually. Navigation meshes take a different approach: they divide the walkable area into irregularly shaped polygons (usually triangles or convex polygons) that conform to the actual geometry. A wide hallway becomes one or two large polygons instead of hundreds of small tiles, dramatically reducing the number of nodes the algorithm needs to process.
Running A* directly on a navigation mesh is already faster than running it on a grid covering the same area, simply because there are fewer cells to expand. But for very large environments, even a navigation mesh can contain enough polygons to make search expensive. Hierarchical approaches address this by grouping nearby mesh cells into clusters and precomputing the best paths within each cluster. The search then operates at two levels: a high-level search across clusters to find the general route, followed by low-level lookups within each cluster to recover the detailed path. One such approach, HNA*, builds a multilevel hierarchy from a navigation mesh and performs up to 7.7 times faster than standard A* on the original mesh.4Computers & Graphics. Technical Section Hierarchical path-finding for Navigation Meshes (HNA*)
The hierarchical idea extends to multi-agent scenarios as well. When many characters need to path-find simultaneously across the same environment, the overhead of repeated full searches becomes a bottleneck. Hierarchical methods on navigation meshes can be adapted for parallel computation, computing paths for multiple agents more efficiently than running independent A* searches for each one.5Computers & Graphics. Multi-agent parallel hierarchical path finding in navigation meshes (MA-HNA*)
Any-Angle Pathfinding
One inherent limitation of A* on a grid is that paths are constrained to follow grid edges. If you can only move horizontally, vertically, or diagonally at 45 degrees, the resulting paths often have an unnatural, zigzagging quality. Worse, they can be measurably longer than the true shortest path through the same space, because the grid forces detours that free movement would avoid. This matters in robotics, where a wheeled robot can turn at any angle, and in games, where characters should appear to move naturally rather than in staircase patterns.
Theta* is a family of algorithms designed to fix this. Basic Theta* and its variant Angle-Propagation Theta* are both built on top of A*, using the same expansion logic and priority queue, but they allow paths to cut across grid cells in straight lines rather than sticking to edges. During expansion, Theta* checks whether a node’s grandparent has line-of-sight to the current node; if so, it connects them directly, bypassing the intermediate node and producing a shorter, smoother path. The algorithm propagates information along grid edges for search purposes but does not constrain the final paths to those edges.6Journal of Artificial Intelligence Research. Theta*: Any-Angle Path Planning on Grids
The practical effect is paths that look much more like what a human would walk: smooth diagonals through open space, tight curves around obstacles. The computational cost is modestly higher than plain A* on the same grid, because of the line-of-sight checks, but the path quality improvement is often dramatic enough to justify it in applications where natural-looking movement matters.
When Multiple Agents Need Paths at Once
Finding a path for one agent is a well-understood problem. Finding collision-free paths for dozens or hundreds of agents simultaneously is a fundamentally harder one. This is the multi-agent pathfinding problem, and it appears in warehouse robotics (where fleets of robots move packages), air traffic management, and crowded game environments. The difficulty is that agents’ paths interact: a route that is optimal for one agent might force another into a costly detour, and resolving all such conflicts jointly is computationally expensive.
One influential approach is Conflict-Based Search (CBS), a two-level algorithm. At the high level, CBS identifies conflicts, places where two agents’ planned paths would put them in the same location at the same time. At the low level, it uses A* to re-plan individual agents’ paths with added constraints that prevent the identified conflicts. CBS was shown to outperform earlier A*-based multi-agent solvers in certain scenarios by decomposing the joint search problem into a series of single-agent problems connected by conflict resolution.7Proceedings of the International Symposium on Combinatorial Search. Meta-Agent Conflict-Based Search For Optimal Multi-Agent Path Finding
Optimal multi-agent search can still be slow when conflicts are numerous. Suboptimal variants of CBS relax the optimality guarantee in exchange for faster computation, returning solutions that are guaranteed to be within a constant factor of the optimal cost rather than perfectly optimal.8Proceedings of the International Symposium on Combinatorial Search. Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem For a warehouse with hundreds of robots, a path that is five percent longer than the theoretical best but computable in milliseconds is far more useful than a perfect path that takes minutes to find.
Changing Maps and Dynamic Environments
Standard A* assumes the map does not change between the time you plan a path and the time you finish traversing it. That assumption breaks in robotics, where a mobile robot might discover new obstacles as it moves, and in real-time strategy games, where the terrain can be altered by player actions. Running A* from scratch every time something changes is one option, but it throws away all the work the previous search did, even if only a small part of the map actually changed.
D* Lite (a streamlined version of the original D* algorithm) is designed for exactly this scenario. It performs an initial search and then incrementally updates the solution when edge costs change, reusing as much of the previous search tree as possible. For environments where changes are local and frequent, this incremental approach is far cheaper than repeated full searches. Extensions like CBS-D*, which combines the multi-agent conflict resolution of CBS with D* Lite’s incremental replanning, have shown roughly a 31% improvement in average pathfinding success rate over standard D* Lite in dynamic grid environments.9ScienceDirect. Conflict-based search with D* lite algorithm for robot path planning in unknown dynamic environments
The underlying lesson is that A* is a single-shot planner: give it a fixed problem and it gives you an answer. Real-world environments are rarely fixed, so an entire family of algorithms has grown up around the core A* idea, each adapting it to handle different flavors of change, whether that is new obstacles, shifting traffic conditions, or agents that alter each other’s costs by their mere presence.
Trading Optimality for Speed
Guaranteed optimal paths are valuable, but sometimes you do not need the absolute best route. You need a route that is good enough, and you need it now. Bounded-suboptimal variants of A* address this by inflating the heuristic, multiplying it by a factor greater than one. This makes the algorithm more aggressively pursue nodes that appear close to the goal, at the risk of overlooking a slightly cheaper route. The benefit is that the search expands fewer nodes and finishes faster. The cost is a path that might be slightly longer than optimal, but the inflation factor provides a formal guarantee on how much longer: if you inflate by 1.5, the returned path is at most 1.5 times the cost of the optimal one.
This idea, often called Weighted A* or WA*, is one of the oldest and most practical A* modifications. More sophisticated versions adjust the weight dynamically during search or combine weighted search with anytime behavior, producing a quick initial solution and then refining it as time allows. Recent work on priority queue data structures has shown that the choice of queue implementation can meaningfully affect the speed of these bounded-suboptimal searches. A bucket heap structure, for instance, accelerates the priority queue operations used by both bounded-suboptimal and Anytime A* variants while also providing direct access to an underlying bucket queue that can further improve performance.10Proceedings of the International Symposium on Combinatorial Search. A Bucket-Based Priority Queue for Bounded-Suboptimal and Anytime A* Search
The practical upshot is that A* is not a single algorithm so much as a family of strategies on a spectrum. At one end, strict A* with an admissible heuristic guarantees the shortest path at potentially high computational cost. At the other end, heavily weighted variants sacrifice a bounded amount of optimality for speed improvements that can be significant on large maps or under tight time constraints. Most real applications pick a point somewhere along that spectrum based on how much path quality they can afford to lose.
Learning Heuristics with Neural Networks
The quality of A*’s heuristic determines how much of the search space gets wasted on dead ends. Hand-crafted heuristics like straight-line distance are general and cheap to compute, but they can be loose fits for complex environments, leaving A* to compensate by exploring more nodes. A growing area of research asks whether machine learning can produce tighter heuristics tailored to specific map types.
One approach trains neural networks to predict the cost-to-go from any node to the goal, then plugs those predictions into A* as the heuristic function. A study combining neural algorithmic reasoning with multi-task learning trained a model to jointly learn Dijkstra’s algorithm and a consistent heuristic for A*. At inference time, running A* with the learned heuristic greatly sped up target-node searching compared to using Dijkstra’s alone, while still finding minimum-cost paths.11arXiv. Learning heuristics for A*
Another line of work uses transformer architectures, the same attention-based models behind large language models, to learn heuristics for grid-based pathfinding. TransPath, one such system, reduced the computational effort of A* by up to a factor of four while producing solutions whose costs exceeded the optimal by less than 0.3% on average. It outperformed both conventional techniques like weighted A* and other learned planners.12Proceedings of the AAAI Conference on Artificial Intelligence. TransPath: Learning Heuristics for Grid-Based Pathfinding via Transformers The tradeoff is that these learned heuristics require training data and inference time, making them best suited for applications where the same type of environment is encountered repeatedly, like a game that generates procedural maps from a fixed set of rules, or a warehouse where the layout changes slowly over weeks.
The broader trend here is that A*’s framework is flexible enough to absorb improvements from entirely different areas of computer science. The core expansion logic stays the same; what changes is the information being fed into it. Whether that information comes from a formula, a precomputed database, or a neural network, A* can use it, and this adaptability is a big part of why the algorithm has remained relevant for over fifty years.
Where A* Struggles
For all its versatility, A* has genuine limitations that push practitioners toward other methods. Its memory consumption is the most commonly cited problem: A* stores every node it has expanded in memory, along with the path costs to reach each one. On extremely large graphs, such as continental-scale road networks with millions of intersections, this can exhaust available memory before the search finishes. Algorithms like Iterative Deepening A* (IDA*) address this by trading memory for time, performing repeated depth-first searches with increasing cost thresholds, but at the cost of re-expanding many nodes multiple times.
High-dimensional search spaces also cause trouble. A* works beautifully in two or three spatial dimensions, where heuristics are intuitive and the branching factor is manageable. In robot motion planning with six or more degrees of freedom, the number of possible states explodes so rapidly that even a good heuristic cannot prevent the search from bogging down. Sampling-based planners like RRT* tend to dominate in those settings, sacrificing A*’s optimality guarantee for the ability to find any feasible path in a reasonable time.
Finally, A*’s optimality guarantee applies only within the graph it is given. If the graph is a coarse approximation of reality, the “optimal” path through the graph might be a poor path through the real environment. A grid with large cells will miss narrow passages. A road network that models traffic as static will not account for rush-hour delays. The algorithm finds the best answer to the question it was asked, which means the quality of the answer depends heavily on the quality of the question, namely the graph representation and heuristic it was handed.