A* pathfinding is one of the most widely used algorithms in game development and robotics. Its performance depends critically on the quality of its heuristic function — the estimate of the cost from any given node to the goal. Get it wrong and you waste node expansions. Get it very wrong and you degrade to something resembling Dijkstra's algorithm.

The Role of the Heuristic

A* guarantees an optimal path only when the heuristic is admissible — it never overestimates the true cost to reach the goal. The standard choices for grid maps are Manhattan distance (for 4-directional movement) and Euclidean distance (for 8-directional or free-angle movement). Both are admissible by definition, but their tightness varies significantly depending on the map topology.

A loose heuristic (one that frequently underestimates by a large margin) causes A* to explore too many nodes before converging on the optimal path. On large maps with open areas and few obstacles, this can make the algorithm prohibitively slow.

Weighted A*

One practical improvement is weighted A*, where the heuristic is multiplied by a constant w > 1. This intentionally makes the heuristic inadmissible in exchange for dramatically reducing the number of nodes expanded. The resulting path is guaranteed to be no worse than w times the optimal cost — a useful trade-off in real-time applications where near-optimal paths computed instantly are preferable to perfect paths computed slowly.

Tie-breaking

When many nodes have identical f-values (f = g + h), A* can waste time exploring them all. A simple nudge to the heuristic — multiplying by (1 + ε) where ε is a very small constant — breaks ties in favour of nodes closer to the goal, reducing expanded nodes significantly in practice with negligible impact on path quality.

Jump Point Search

For uniform-cost grids, Jump Point Search (JPS) is a preprocessing-free optimisation that prunes symmetric paths by identifying "jump points" — nodes where the optimal path must pass. JPS can be 10–20× faster than vanilla A* on open grids while producing identical paths.