Home▸Algorithms & AI▸A* Pathfinding

🗺️ A* Pathfinding

Watch A* find the shortest path on a grid with f(n)=g(n)+h(n). Paint walls, drag start and goal, switch heuristics, and compare A*, Dijkstra and Greedy search.

Algorithms & AI3DModerate60 FPS

About A* Pathfinding

A* (pronounced "A-star") is a best-first graph search algorithm that finds the shortest path between two points by combining Dijkstra's guaranteed-optimal cost-so-far (g) with a heuristic estimate of the remaining distance (h), giving each node a priority score f = g + h. Developed by Hart, Nilsson, and Raphael in 1968, it underpins everything from video-game character navigation and robot motion planning to Google Maps route computation. When the heuristic is admissible — meaning it never overestimates the true cost — A* is guaranteed to find the optimal path.

This simulation lets you choose between A*, Dijkstra (h = 0), and Greedy Best-First (g = 0) on a grid where you can paint walls and weighted terrain (cost ×5), drag the start and goal nodes, select a heuristic (Manhattan, Euclidean, or Chebyshev), toggle diagonal moves, and watch nodes expand one step at a time. Live statistics show nodes expanded, path length, and total cost.

Frequently Asked Questions

What does f = g + h mean?

In A*, every node in the open set is scored by f(n) = g(n) + h(n), where g(n) is the exact cost of the cheapest path found so far from the start to node n, and h(n) is the heuristic estimate of the cost from n to the goal. The algorithm always expands the node with the lowest f, ensuring that if h is admissible the first time the goal is expanded its path is optimal.

What is an admissible heuristic?

A heuristic h is admissible if it never overestimates the true cost to reach the goal — formally h(n) ≤ h*(n) for all n. Manhattan distance (sum of horizontal and vertical steps) is admissible on a 4-connected grid; Euclidean distance is admissible for any grid. An inadmissible heuristic can make A* faster but may return a suboptimal path.

How does A* differ from Dijkstra's algorithm?

Dijkstra's algorithm sets h = 0, so it expands nodes in order of their exact cost from the start, radiating outwards in all directions equally. A* adds the heuristic to guide the search towards the goal, typically expanding far fewer nodes. On an open grid without obstacles, A* with Manhattan distance can reduce node expansions by 50–90 % compared with Dijkstra.

Why is Greedy Best-First search faster but not optimal?

Greedy Best-First sets g = 0 and uses only h to rank nodes, always rushing towards the node that looks closest to the goal. This is very fast in open environments, but it ignores actual path cost, so it can be lured through expensive terrain or around obstacles into a longer route. In the worst case it finds a path that is arbitrarily worse than optimal.

When should I use Manhattan vs Euclidean vs Chebyshev distance?

Use Manhattan distance when movement is restricted to 4 directions (up, down, left, right), as it exactly counts the minimum number of steps. Euclidean distance is appropriate when diagonal moves are allowed and diagonal cost equals √2. Chebyshev distance (max of |Δx|, |Δy|) is the right choice when all 8 directions cost the same, as is common in many strategy games.

What are weighted cells and how do they affect pathfinding?

Weighted cells represent terrain that is harder to traverse — mud, shallow water, or a rough road. In this simulation a weighted cell costs 5 instead of 1 to enter, so A* will often route around several weighted cells rather than walk through them. Dijkstra and A* both handle weights correctly; Greedy Best-First ignores costs and may walk straight through expensive terrain.

What is the time complexity of A*?

In the worst case A* has O(b^d) time and space complexity, where b is the branching factor and d is the depth of the optimal solution. With a consistent heuristic (one that satisfies the triangle inequality) each node is expanded at most once, giving O(V log V) on a finite graph with V vertices — the same asymptotic bound as Dijkstra using a binary heap.

How does maze generation affect the search?

The maze generator creates a perfect maze using a randomised algorithm that carves passages through a grid, guaranteeing exactly one path between any two cells. Mazes are particularly demanding for search algorithms because the narrow corridors eliminate the heuristic advantage of A* — with only one valid path, all algorithms must explore roughly the same nodes.

What do the colours on the grid represent?

Green marks the start node, red the goal. Blue cells form the current frontier (open set), dark blue marks visited (closed) nodes, and yellow highlights the node being expanded. Weighted cells appear brown. Once a path is found, it is traced in lime green from start to goal, and you can read off the exact cost in the statistics panel.

Can A* be used in 3D or on non-grid graphs?

Yes — A* works on any graph where edge costs are non-negative and you can supply an admissible heuristic. Real-world applications include 3D robot arm motion planning (configuration-space graphs), network routing (latency as cost), and natural-language parsing (Viterbi-like lattices). The grid here is just the most visually intuitive representation of the general algorithm.

What is the significance of the "nodes expanded" counter?

Nodes expanded counts how many times the algorithm dequeued a node from the frontier and processed its neighbours — this is the primary measure of A* efficiency. A lower count means the heuristic is guiding the search well. On a 30×30 grid (900 cells) a good heuristic can often find the optimal path while expanding fewer than 100 nodes, whereas Dijkstra may expand every reachable cell.

About this simulation

This simulator visualises the A* search algorithm finding a shortest path across a weighted grid. Each frontier node carries a score f(n) = g(n) + h(n), where g is the exact distance travelled from the start and h is a heuristic estimate of the remaining distance to the goal; the algorithm always expands the lowest-f node first. Switching the algorithm dropdown to Dijkstra zeroes out h, whilst Greedy Best-First drops g altogether, so you can watch the same maze solved three different ways, node by node.

🔬 What it shows

The colour-coded grid tracks the search live: blue cells sit in the open frontier, dark blue cells have been fully expanded (closed), and yellow marks whichever node is being processed at that instant. Once the goal is reached the winning route is traced in lime green, and the sidebar reports how many nodes were expanded plus the total path cost.

🎮 How to use

Choose Algorithm and Heuristic from the dropdowns, then use the Paint tool buttons to add Walls, ×5-cost Weight terrain, or drag the Move start/Move goal markers around the board. Allow diagonal moves switches between 4- and 8-directional movement, Show g/h/f values overlays the raw scores on each cell, and Auto-run, Step, Generate maze, Clear walls and Reset control playback and the board layout.

💡 Did you know?

A* was published in 1968 by Peter Hart, Nils Nilsson and Bertram Raphael, and despite being over half a century old it is still the default pathfinding choice in most video games, robotics stacks and route planners because it never explores more nodes than necessary once given an admissible heuristic.

Frequently asked questions

What happens when I switch from Manhattan to Euclidean or Chebyshev distance?

Each heuristic changes how h(n) estimates distance to the goal, which reshapes the search frontier. Manhattan distance (horizontal plus vertical steps) is exact for 4-directional movement; Euclidean distance (straight-line hypotenuse) suits diagonal movement; Chebyshev distance (the larger of the horizontal and vertical differences) suits boards where diagonal steps cost the same as orthogonal ones. Picking a heuristic that undershoots the true distance keeps A* optimal but can expand more nodes; overshooting speeds up the search but can produce a longer path.

Why does painting a Weight tile change the route instead of just slowing it down?

A Weight tile costs 5 to enter rather than 1, so it raises g(n) for any path that crosses it. Because A* and Dijkstra always minimise total cost, they will happily take a longer route around a cluster of weighted cells if that route is cheaper overall — Greedy Best-First, which ignores g entirely, is the only mode that can walk straight through expensive terrain.

What does the frontier colouring actually track under the hood?

Blue cells are in the open set — discovered but not yet expanded — and are stored in a binary min-heap keyed on f, with ties broken by the lower h value. Dark blue cells are closed, meaning their neighbours have already been examined and their gScore is final. Yellow marks the single node popped from the heap on the current step.

Why does Generate maze make Greedy Best-First perform so much worse?

The maze generator carves a perfect maze with exactly one route between any two cells using a randomised recursive backtracker, so there are no shortcuts for a heuristic to exploit. Greedy Best-First keeps rushing toward whichever open cell looks closest to the goal in a straight line, frequently charging down dead-end corridors, whereas A* and Dijkstra methodically retreat and try the only other option.

Is the diagonal-move cost handled correctly?

Yes — when Allow diagonal moves is ticked, diagonal steps cost √2 instead of 1, matching their true Euclidean length, and the simulator blocks diagonal moves that would cut through the corner of two adjacent walls. The heuristic also switches to an octile-distance formula in this mode so it remains admissible for 8-directional movement.

⚙ Under the hood

Watch A* find the shortest path on a grid using f = g + h. Paint walls, drag start/goal, switch heuristics, and compare A* vs Dijkstra vs Greedy to see how the heuristic changes nodes expanded.

Canvas 2DPathfindingA*Heuristic SearchDijkstra

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install