A* Search Algorithm

A (A-star)* is an informed search algorithm that extends Dijkstra's algorithm by adding a heuristic function to guide the search towards the goal. It is widely used in pathfinding and graph traversal, particularly in game AI and robotics. At A-Level, you need to understand how A* works, the role of the heuristic, and how it compares to Dijkstra's algorithm.

---

The Key Idea

Dijkstra's algorithm explores vertices in order of their distance from the source, expanding outwards in all directions equally. This means it may explore many vertices that are far from the goal.

A* improves on this by estimating the total cost of a path through each vertex:

f(n) = g(n) + h(n)

Component	Meaning
f(n)	Estimated total cost of the cheapest path through n
g(n)	Actual cost from the start to n (known, calculated)
h(n)	Heuristic estimate of the cost from n to the goal (estimated)

A* always selects the vertex with the lowest f(n) value next.

---

The Heuristic Function h(n)

The heuristic h(n) is a guess of the remaining distance from n to the goal. For A* to find the optimal (shortest) path, the heuristic must be admissible — it must never overestimate the true cost to the goal.

Common Heuristics for Grid-Based Pathfinding

Heuristic	Formula	When to use
Manhattan distance		x₁ - x₂
Euclidean distance	√((x₁-x₂)² + (y₁-y₂)²)	Movement in any direction
Zero heuristic	h(n) = 0	Reduces A* to Dijkstra's algorithm

Key Insight: If h(n) = 0 for all n, A* behaves exactly like Dijkstra's algorithm. The heuristic is what makes A* "smarter" — it focuses the search towards the goal.

---

Pseudocode

PROCEDURE AStar(graph, start, goal, h)
    openSet = priority queue ordered by f value
    closedSet = empty set

    g[start] = 0
    f[start] = h(start, goal)
    ADD start TO openSet

    WHILE openSet IS NOT EMPTY
        current = vertex in openSet with lowest f value

        IF current = goal THEN
            RECONSTRUCT path from start to goal
            RETURN path
        END IF

        REMOVE current FROM openSet
        ADD current TO closedSet

        FOR EACH neighbour OF current
            IF neighbour IN closedSet THEN
                CONTINUE
            END IF

            tentativeG = g[current] + weight(current, neighbour)

            IF neighbour NOT IN openSet THEN
                ADD neighbour TO openSet
            ELSE IF tentativeG >= g[neighbour] THEN
                CONTINUE
            END IF

            previous[neighbour] = current
            g[neighbour] = tentativeG
            f[neighbour] = g[neighbour] + h(neighbour, goal)
        END FOR
    END WHILE
    RETURN "No path found"
END PROCEDURE

---

Trace Example

Consider a grid where S is the start, G is the goal, and # is a wall. Movement costs 1 per step (4-directional). We use Manhattan distance as the heuristic.