A* Pathfinding Algorithm

Also Known As

TL;DR

Explanation

A* is a best-first graph search algorithm that extends Dijkstra’s algorithm by adding a heuristic function h(n), which estimates the remaining cost to the goal. Nodes are prioritised using f(n) = g(n) + h(n), where g(n) is the known cost from the start. With an admissible and consistent heuristic, A* is both complete and optimal. Its efficiency depends heavily on heuristic quality — a good heuristic drastically reduces explored nodes compared to Dijkstra. Common heuristics include Manhattan distance for grid movement and Euclidean distance for continuous space. In PHP, A* is most applicable in routing systems, game AI, logistics optimisation, and path-based simulations.

Common Misconception

Why It Matters

Common Mistakes

• Using a heuristic that overestimates — breaks optimality guarantees.
• Using arrays instead of a priority queue — leads to O(n) extraction instead of O(log n).
• Revisiting nodes without checking for better gScore — causes unnecessary expansions.
• Not separating g(n) and f(n) — mixing them leads to incorrect path selection.

Avoid When

• Graph has no meaningful heuristic — use Dijkstra instead.
• All edge costs are equal and graph is small — BFS may be simpler.

When To Use

• Finding shortest paths in weighted graphs with spatial structure.
• Game AI movement or map routing with clear distance heuristics.

Code Examples

<?php
// ❌ BFS — ignores edge weights and heuristic guidance
function bfsPath(array $grid, array $start, array $goal): array
{
    $queue = [[$start, [$start]]];
    $visited = [];

    while (!empty($queue)) {
        [$node, $path] = array_shift($queue); // O(n)

        if ($node === $goal) {
            return $path;
        }

        foreach (neighbours($grid, $node) as $next) {
            if (!in_array($next, $visited, true)) {
                $visited[] = $next;
                $queue[] = [$next, [...$path, $next]];
            }
        }
    }

    return [];
}

<?php
// ✅ A* with proper priority queue and scoring
function astar(array $grid, array $start, array $goal): array
{
    $open = new SplMinHeap();
    $gScore = [];
    $cameFrom = [];

    $key = fn($n) => $n[0] . ',' . $n[1];

    $h = fn($n) => abs($goal[0] - $n[0]) + abs($goal[1] - $n[1]);

    $startKey = $key($start);
    $gScore[$startKey] = 0;

    $open->insert([0 + $h($start), $start]);

    while (!$open->isEmpty()) {
        [, $current] = $open->extract();

        if ($current === $goal) {
            return reconstructPath($cameFrom, $current);
        }

        foreach (neighbours($grid, $current) as $next) {
            $currentKey = $key($current);
            $nextKey = $key($next);

            $tentativeG = ($gScore[$currentKey] ?? INF) + cost($current, $next);

            if ($tentativeG < ($gScore[$nextKey] ?? INF)) {
                $cameFrom[$nextKey] = $current;
                $gScore[$nextKey] = $tentativeG;

                $fScore = $tentativeG + $h($next);
                $open->insert([$fScore, $next]);
            }
        }
    }

    return []; // no path
}

References

• ↗ https://en.wikipedia.org/wiki/A*_search_algorithm

Tags

Related Terms