A Practical Guide to A* Optimal Pathfinding

Every journey through a street network, dungeon, warehouse, or robot floor can be reduced to a graph problem. A* search combines the cost already travelled with an estimate of the cost still ahead, allowing it to explore useful routes first instead of blindly enumerating every possibility. The result is a practical foundation for navigation software, game AI, and autonomous systems.

The important word is optimal. Many heuristics find a route quickly, but the least-cost path is guaranteed only when the heuristic and search rules are correct. This guide covers weighted graphs, grid maps, admissible and consistent heuristics, implementation details, complexity, and the situations where a simpler algorithm may be preferable.

Examples use Australian settings where distance is measured in kilometres and speed in kilometres per hour. They also reflect a country where traffic keeps left, urban roads include complex bridges, tunnels, trams, and one-way streets, and regional travel can span hundreds of kilometres between services.

Core ideas and graph models

A pathfinding problem begins by turning locations into vertices and permitted movements into edges. A street intersection, tile, warehouse bay, or robot pose can each become a vertex. An edge carries a non-negative cost, such as travel time, distance, fuel use, or a combination of penalties. The task is to find a sequence of edges from the start vertex to the goal vertex with the smallest total cost.

Along a partial route, A* records g(n), the known cost from the start to node n, and estimates h(n), the remaining cost from n to the goal. It orders the frontier with f(n) = g(n) + h(n), always expanding the candidate with the smallest estimated total. When the goal is removed from the frontier, the associated parent pointers reveal the selected route. This separates expensive travel already committed from uncertain travel still to come.

Standard A* assumes non-negative edge costs. A negative edge can create a cycle with an ever-lower cost and weaken the monotone frontier argument used for optimality. A directed graph may allow one-way streets and turn restrictions; an undirected graph treats movement as reversible. For contrast, a minimum spanning tree guide solves a different graph problem: it connects vertices cheaply rather than finding one best route between two endpoints.

Heuristics, optimality, and termination

A heuristic is admissible when it never overestimates the true remaining cost. If the cheapest possible continuation from n to the goal is h*(n), then h(n) <= h*(n) for every reachable node. With an admissible heuristic and an open frontier, A* returns an optimal route when it stops on the goal's removal, rather than merely on the goal's first discovery, and allows previously expanded nodes to reopen if a cheaper route is found.

Consistency provides the stronger condition h(n) <= c(n, n') + h(n') for neighbouring nodes n and n'. A consistent heuristic means each node needs to be expanded at most once in a closed implementation, so it is especially useful for large road and grid searches. An inconsistent but admissible heuristic can still produce an optimal result if reopening is supported. Multiplying the heuristic by a factor above one creates weighted A*, which often searches faster but gives up the general optimality guarantee.

Useful heuristics match the cost model. Manhattan distance fits four-way movement on a uniform grid; Euclidean distance suits eight-way movement with geometric edge costs; octile distance combines both. On a road graph, straight-line geographic distance is usually a safe lower bound after conversion to the edge-cost unit, but can be weak; dividing a road-distance lower bound by the maximum speed can strengthen a time-based estimate. Every heuristic value and edge cost must use compatible units, whether those units are metres, kilometres, seconds, or minutes.

Designing maps for Australian routes

A grid is convenient for games and warehouse robots because each cell has a fixed set of neighbours. If crossing one cell takes one unit and diagonal movement costs sqrt(2), an octile heuristic closely reflects unobstructed travel. Obstacles, one-way gates, terrain, and restricted turns require edge costs or directed connections; they can also make a geometric estimate less informative without making it inadmissible.

Real road networks need a richer model than drawing a line between two postcodes. Travel time depends on speed limits, intersection delays, lane changes, tolls, ferry schedules, and peak traffic. Sydney Harbour forces routes around or across major bridge and tunnel infrastructure, while Melbourne's narrow laneways, trams, and one-way streets favour fine-grained pedestrian or cycling graphs. Australia's left-hand traffic pattern and distances quoted in kilometres should be reflected consistently in the cost rules.

Data quality can dominate the search. OpenStreetMap, council roadworks notices, public transport feeds, and commercial traffic datasets each have different update cycles, and the Australian market for navigation services must reconcile them. Missing footpaths, temporary closures, school-zone rules, and new suburbs can change the cheapest legal route. A route intended for one purpose should permit only the movement modes it supports, rather than mixing walking, driving, and freight constraints in one graph.

Building an A* implementation

The usual implementation stores the frontier in a binary min-heap, the best known g-value in a dictionary, and parent nodes for reconstruction. This version accepts a neighbour generator yielding (node, cost) pairs and a heuristic function. A monotonically increasing counter breaks priority ties without requiring graph nodes themselves to be comparable.

from itertools import count
import heapq

def astar(start, goal, neighbours, heuristic):
    sequence = count()
    frontier = [
        (heuristic(start, goal), 0.0, next(sequence), start)
    ]
    best_cost = {start: 0.0}
    came_from = {start: None}

    while frontier:
        _, current_cost, _, current = heapq.heappop(frontier)

        if current_cost > best_cost[current]:
            continue

        if current == goal:
            path = []
            node = current
            while node is not None:
                path.append(node)
                node = came_from[node]
            return path[::-1], current_cost

        for neighbour, edge_cost in neighbours(current):
            tentative_cost = current_cost + edge_cost
            if tentative_cost < best_cost.get(neighbour, float("inf")):
                best_cost[neighbour] = tentative_cost
                came_from[neighbour] = current
                estimate = tentative_cost + heuristic(neighbour, goal)
                heapq.heappush(
                    frontier,
                    (estimate, tentative_cost, next(sequence), neighbour)
                )

    return None, float("inf")

The heap can contain stale entries after a cheaper route reaches a node; the best_cost check discards them. Because the code has no permanently closed set, it reopens nodes when necessary and therefore supports admissible but inconsistent heuristics. The cost returned is the sum of edge weights, so the same route may be shortest by distance but not by travel time. Tests should cover an unreachable goal, a zero-cost edge, a start equal to the goal, and cases where a later path improves an already discovered node.

Performance limits and common failure modes

For a graph with V vertices and E edges, consistent-heap A* generally requires O((V + E) log V) time and O(V) state storage, plus up to O(E) queued entries. Breadth-first search is simpler but only finds minimum-edge paths on unweighted graphs. Dijkstra's algorithm uses g alone, always gives the least-cost path with non-negative edges, and becomes the baseline when no trustworthy lower bound is available.

Several failures look algorithmic but are usually modelling errors. Manhattan distance is inadmissible when diagonal movement costs less than two orthogonal steps. Euclidean kilometres cannot be added to edge costs measured in minutes. A heuristic inflated for speed may return a shorter-looking route while violating optimality. Dead ends, duplicate nodes, and a tie-breaker that favours shallow nodes can also inflate the explored region without changing the correct answer.

Large regional networks expose weak heuristics and stale map data. A drive from Sydney toward Broken Hill can cover many hundreds of kilometres, so a straight-line estimate is tiny compared with the true cost; sealed roads, unsealed sections, closures, fuel stops, and fatigue limits may matter more than kilometres per hour. Learned models can help rank promising edges, and a neural network overview introduces the architecture behind such estimates, but predicted costs still require calibration against real journeys and safety constraints.

Choosing and validating a routing approach

The main choices differ in how much guidance they use, whether they guarantee an optimal result, and where they fit best.

Method	Frontier guidance	Optimality	Best fit
A*	g(n) + h(n)	Guaranteed with an admissible heuristic and proper termination	General weighted pathfinding
Dijkstra	g(n)	Guaranteed with non-negative edge costs	No useful heuristic or a correctness baseline
Breadth-first search	One edge per step	Optimal only when every edge has equal cost	Small unweighted grids and tutorials
Greedy best-first	h(n)	Not generally guaranteed	Fast approximate exploration
Weighted A*	g(n) + w × h(n)	Not generally guaranteed when w > 1	Speed-sensitive applications accepting a near-optimal route

Operational needs determine which behaviour is most valuable:

• A logistics service prioritising minimum travel time benefits from A* with time-based edges and a dependable lower-bound estimate.
• A grid-based game usually benefits from Manhattan or octile distance because movement costs are uniform and easy to compare.
• A warehouse robot needs directed edges for one-way aisles, congestion penalties, and occupancy that changes between searches.
• A national journey planner may need hierarchical search, contraction hierarchies, or landmark heuristics to avoid expanding millions of road vertices.
• Dijkstra remains valuable for verifying a small route network because it provides an uncomplicated optimal reference.

A deployment should be checked against these properties:

• The graph states, legal movements, and edge-cost units match the real task.
• The heuristic never exceeds a defensible lower bound on the remaining cost.
• The algorithm stops when the goal is expanded and supports reopening when required.
• Results are compared with Dijkstra or an exhaustive search on small test maps.
• Australian test cases include left turns, bridge and tunnel links, tram corridors, regional distances, and temporary closures.

Optimal pathfinding comes from combining a faithful graph with a bounded estimate, then enforcing the search rules that preserve that guarantee. The algorithm is powerful precisely because that estimate guides exploration without replacing the evidence accumulated along the route.