A* finds the way by guessing well

A* explores a maze one square at a time, always expanding the square that looks most promising. It ranks squares by how far it has already come plus an optimistic guess of how far is left. With a guess that never overestimates, A* is guaranteed to find the cheapest path, and usually looks at far fewer squares than an uninformed search.

f(n) = g(n) + w · h(n) g = exact cost from the start · h = heuristic guess to the goal · the square with the lowest f is expanded next

Open (frontier, in the queue) Closed (already expanded) Current / final path Mud (costs 5 to enter) Wall

Speed4/s

Algorithm

Heuristic h(n)

Heuristic weight ww > 1 is "weighted A*": faster, may not be optimal

1.00

Maze

Mud patches

Draw

Show g / h / f in squares (small maze)

A* · step by step

0expanded

0in open set

–path cost

–path squares

Square being expanded

–

Its neighbors

Square	g	h	f	Result

Priority queue (lowest f first)

#	Square	g	h	f

Hover a square to see its values.

Race: same maze, three strategies

Dijkstra uses only g, so it spreads out evenly like a flood: always optimal, but it explores a lot. Greedy best-first uses only h, so it rushes toward the goal: often fast, but fooled by dead ends and mud. A* balances both.

Uses the maze, heuristic and weight set above.

Admissible heuristics

If h never overestimates the true remaining cost, A* returns an optimal path. Manhattan distance is admissible here because each step costs at least 1 and moves are up, down, left or right.

Open and closed sets

The open set is a priority queue of discovered squares waiting to be expanded. Once a square is expanded it is closed: with a consistent heuristic, its g value can never improve again.

Ties and mud

Paint mud across the shortest corridor. A* and Dijkstra route around it when the detour is cheaper; greedy search ploughs straight through because it ignores cost.

Try w = 3

Weighted A* trusts the heuristic three times as much. It expands far fewer squares but can return a path that costs more. A common trade in games and robotics.