Pathfinding playground

1BFS counts steps, Dijkstra counts cost

Breadth-first search explores in rings of equal step count, using a plain queue. On a board where every move costs the same that is already the shortest route, and it is the fastest exact method there. Add mud (3 per step) or water (6) and BFS still takes the fewest steps, straight through the swamp.

The mazes come from five carving algorithms; the space station is grown instead, tile by tile, by Wave function collapse, whose own backtracking is the same depth-first search as the recursive backtracker. Its solar trusses are mud and its reactor coolant water, and any finished station or drawing there opens here with race it in pathfinding.

Dijkstra swaps the queue for a priority queue keyed by g, the cost so far, so its rings are of equal cost instead. It pays a log factor for the heap and never gets the cost wrong while costs are not negative.

g(v) = min over arcs u→v of g(u) + c(u, v)Dijkstra settles nodes in order of g; BFS assumes every c = 1here: BFS route … in … steps, Dijkstra … in …

BFS O(V + E) · Dijkstra O((V + E) log V)V nodes, E arcsthis board: V = …, E = …

2A*: guess the rest of the way

A* adds h, a guess of the cost still to go, and always explores the frontier node with the smallest f = g + w·h. The guess leans the search towards the goal instead of flooding outwards. At w = 0 it is Dijkstra; greedy best-first drops g altogether and trusts h alone, which is quick when the guess is right and wild when it is not.

On a grid the natural guesses are Manhattan distance for 4-way moves and octile distance (diagonals cost √2) for 8-way. The same idea runs on real streets in Shortest path, and joins a day's stops in the Trip planner; on a city board, shortest path ↗ opens the same A and B there. Game programs search too, but a game tree has an opponent choosing every other move, so Minimax scores whole branches instead of guessing a distance.

f(n) = g(n) + w · h(n)g: cost from the start · h: guess to the goal · w: the weight sliderA* now expands n = …: g = …, h = …, f = …

octile(dx, dy) = max(dx, dy) + (√2 − 1) · min(dx, dy)Manhattan = dx + dy · Euclidean = √(dx² + dy²) · Chebyshev = max(dx, dy)start to goal: h = … against a true cost of …

3Admissible: never overestimate

If h never exceeds the true remaining cost h*, then when A* takes the goal off the frontier nothing it skipped could have been cheaper, so the route is the shortest. Octile is admissible with 8-way moves; Manhattan is not, because a diagonal step covers 2 Manhattan units for a cost of √2. Portals break every distance guess: they are shortcuts the straight line knows nothing about.

Decoys and mirages here are sly: they only ever lower h (to the nearest of goal and decoys, or to zero in a mirage), so A* stays exact but wastes work, while greedy has nothing else to go on.

h(n) ≤ h*(n) for every nh*: the true cost from n to the goal, from one reverse Dijkstraw·h overestimates at … of … nodes, worst by …

cost(A*) ≤ w · cost(shortest)with an admissible h and weight w ≥ 1here: A* … vs shortest …

4Consistent: the guess keeps its story straight

Consistency is the triangle inequality for guesses: stepping along an arc can lower h by at most that arc's cost. With a consistent h, A* never finds a better way to a node it already explored. A mirage breaks it: h drops to zero at its edge in a single step, so A* can come back to nodes it had settled and explore them again.

h(u) ≤ c(u, v) + h(v) for every arc u→vconsistent implies admissible (with h(goal) = 0)broken on … of … arcs; A* re-expanded … nodes

5Jump point search: skip the symmetric paths

On an open uniform grid there are many equally short paths, and A* explores them all. Jump point search prunes neighbours that some other shortest path already reaches, then runs in a straight line until something interesting happens: the goal, or a forced neighbour where a wall ends and a new route opens. Only those jump points go on the heap; the scanned cells are drawn faintly.

It needs a uniform-cost grid, so here it sees walls only: mud and water cost it nothing, gates are walls, portals are invisible. Its route is then costed on the real board, which is why it can lose on a swamp.

forced: n + d blocked behind, n + d⊥ opena straight jump stops at x when a wall beside the previous cell ends at xJPS put … jump points on the heap and scanned … cells; A* expanded …

6Two ends meet in the middle

Bidirectional Dijkstra grows one search from the start and one backwards from the goal, always extending the smaller frontier, and stops once the best meeting cost cannot improve. Two discs of radius r/2 cover half the area of one of radius r.

stop when top(F) + top(B) ≥ μμ: best start-to-goal cost through any touched nodehere … nodes expanded vs Dijkstra's … (…)

2 · π(r/2)² = ½ · πr²the ideal saving in open space

7Flow fields: one search, every start

A flow field runs Dijkstra once, backwards from the goal, over the whole board. Every node learns its distance to the goal and which neighbour is one step closer: the arrows. Any number of units can then follow the arrows for free, which is how crowds and tower-defence creeps move. Drop the goal and keep only the distances, and the rings are isochrones: on a city board, isochrones from A ↗ draws them from the same start.

next(v) = argmin over arcs v→u of c(v, u) + d(u)d: distance to the goal, from a reverse Dijkstrafield covers … nodes; the farthest is … away

8Detours: where straight lines lie

The detour ratio of a place is how much longer the real route is than the straight line to it. Rivers, railways, cul-de-sacs and one-way systems push it up. The awkward places list runs one Dijkstra from the start and ranks everywhere at least … away by this ratio.

One priority queue, eight ways to choose what to explore next, and each choice is a different idea of where the goal probably is.

detour(n) = d(start, n) / |start − n|route length over straight-line distanceto the goal: … · most awkward here: …