Pathfinding on Weighted Terrain - 2D Search Map: BFS, Dijkstra, A* and Greedy Frontier Heatmap

Setup

Map

Algorithm

Heuristic h

A* weight w

Search speed (cells/s)

8-way moves show costs heatmap

Paint terrain (drag on the map)

Compare all algorithms

Graphs

Cells expanded per algorithm (current map)

A* weight sweep: expanded cells and cost ratio vs optimal

Numerical checks

running...

How to use

Pick a map and an algorithm and press Restart: cells turn from cool to warm in the order they are expanded, outlined squares mark the frontier, and the final route is drawn in white. Try the Greedy trap with greedy search, then switch to A*. Drag on the map to paint mud, water or rock and watch the route and the table update. Turn on 8-way moves and set Manhattan as the heuristic to see an inadmissible heuristic return a costlier route. Raise w to trade optimality for speed.

The science

Graph. Each cell is a node. A move between neighbours a and b costs the mean of their terrain costs, times sqrt(2) for a diagonal step (no corner cutting through rock):

c(a,b) = (cost(a) + cost(b)) / 2 x (1 or sqrt 2)

Algorithms. All keep a frontier and repeatedly expand one node; only the priority key differs:

BFS: FIFO Dijkstra: g A*: g + w h Greedy: h

Dijkstra is optimal because an expanded node's g is final when edge costs are non-negative. A* with w = 1 is optimal if h never exceeds the true remaining cost (admissible) and never expands more nodes than Dijkstra. For w > 1 the cost is at most w times the optimum. BFS minimises steps, not cost, so it ignores the terrain.

Heuristics. The cheapest step costs 1, so Euclidean and octile distance are admissible. Manhattan is admissible only with 4-way moves: a diagonal covers 2 Manhattan units for 1.414 cost.

octile(dx,dy) = dx + dy + (sqrt 2 - 2) min(dx,dy)

Verification. The optimum shown is computed by an independent Bellman-Ford solver (no heap, no heuristic). Closed forms are also checked on an open grid: BFS steps = Manhattan distance, Dijkstra cost = octile distance.

Honest simplifications. The costs 1/3/6/10 are illustrative, not measured walking energies. A 28 x 28 grid is tiny; real routing uses millions of nodes and speed-up techniques. Ties are broken by insertion order, which can change counts by a few cells. This page shares its model with the 3D version, so both give identical numbers.