Algorithm Laboratory

Six searches, one map, the same start bell

Every algorithm below is given an identical map, an identical start and goal, and one cell-expansion per tick. They are all correct in the sense that they terminate and return a route. What separates them is how much of the map they have to touch to do it, and whether the route they hand back is the cheapest one — two things that trade against each other, and that no single algorithm wins on both. Watch the shapes: the way a search spreads tells you more about it than any complexity class.

Map:

Moves:

Marsh cost 6.0

Cells per frame 12

settled cells, oldest → newest backward front (bidirectional only) frontier route returned goal

Map

–

Free cells

–

Optimal route cost

–

Ticks elapsed

First to finish

–

Cheapest route

–

The scoreboard — work done against quality of the answer

cells settled (less is better) route cost optimal cost — anything to the right of this line is a worse route Bars fill live while the race runs. An algorithm that finishes early with a long bar bought its speed with quality.

The six

Breadth-first `Moore, 1959`	Take the oldest cell on the frontier. Settles cells in order of step count, so the first arrival at the goal is by a route with the fewest cells — optimal if and only if every step costs the same. On the marsh map it is confidently, expensively wrong. Memory is its real cost: the frontier is the whole boundary of a growing disc, which on a large open map is the dominant term. `frontier.shift()`
Depth-first `Trémaux, 1882`	Take the newest cell. Commits to a direction and rides it until it hits a dead end, then unwinds. The route it returns has no guarantee of any kind and is routinely several times longer than necessary — watch the cost bar run off the end of its axis. Worth checking the folklore here: DFS is famous for using O(depth) memory, but that describes recursive DFS on a tree. This is an iterative DFS on a graph, pushing every unsettled neighbour on discovery, so its stack grows to a large fraction of the map — often far bigger than BFS's queue. On a perfect maze it finally looks good, because with essentially one route between any two cells there is nothing to be suboptimal about. `frontier.pop()`
Dijkstra `Dijkstra, 1959`	Take the cell with the smallest cost so far. This is BFS with a priority queue, and it is the correct algorithm the moment terrain costs differ. It is also the honest baseline for everything else here: with no information about where the goal is, it must grow a disc in every direction, so it settles the most cells of any correct method on this page. Requires non-negative weights — a single negative edge invalidates the argument that a settled cell is finished. `pop min g`
Greedy best-first `Doran & Michie, 1966`	Ignore what the trip has cost so far; take the cell that looks closest to the goal. Frequently the fastest thing on this page — on an open map it drives almost straight at the target. It is also the only one here that can be spectacularly wrong: on concave traps it walks into a pocket because the pocket points at the goal, then has to fill the entire pocket before it will consider going around. No optimality guarantee at all. `pop min h`
A* `Hart, Nilsson & Raphael, 1968`	Take the cell with the smallest estimated total trip, `f = g + h`. Combines Dijkstra's accounting with greedy's sense of direction, and with an admissible `h` it returns exactly Dijkstra's answer while typically settling a fraction of the cells. The famous result is stronger than "it works": among algorithms with the same heuristic information, no correct algorithm settles fewer cells. Its weakness is that it is only as good as `h` — set the heuristic to Manhattan on 8-way movement and watch the optimality badge flip. `pop min g + h`
Bidirectional `Dantzig, 1962`	Two Dijkstras, one forward from the start and one backward from the goal, alternating and stopping when no unexplored join can beat the best join already found. Uses no heuristic whatsoever and still roughly halves the settled area, because two discs of radius `d/2` cover half of one disc of radius `d`. The catch is structural, not numerical: you need the reverse graph, and the stopping rule is subtle enough that a plausible-looking version — "stop when the fronts touch" — is simply wrong. `stop when g_f + g_b ≥ best`

Things worth trying

Concave traps	The clearest failure on the page. Greedy dives into a pocket that happens to point at the goal and fills it completely before backing out, often settling more cells than Dijkstra while still returning a worse route — the worst of both. A* walks up to the same pocket and turns around early, because `g` keeps rising while `h` stops falling, and the frontier outside the pocket quietly becomes cheaper.
Marsh	Set the marsh cost to 12 and compare BFS's route cost with Dijkstra's. BFS finishes sooner and returns a route that costs far more — it optimised the wrong quantity and has no way to know. Then drop the marsh cost to 1.0: every route cost converges, because on a uniform graph BFS is Dijkstra.
Manhattan on 8-way	Switch moves to 8-way and `h` to Manhattan. A's settled count drops — and its optimality badge turns coral. Manhattan overestimates diagonal travel by up to √2, so A stops being A* and becomes weighted A* with `w ≈ 1.41`. Switch back to octile and the guarantee returns at a modest cost in cells. This is § 04 of the course, on a map you chose.
Open field	The cleanest look at the shapes. Dijkstra draws a disc, bidirectional draws two smaller discs, A* draws a cigar pointed at the goal, greedy draws a line. The areas of those four shapes are the running times, and you can read them off the screen without a single measurement.
Perfect maze	The great equaliser. Every algorithm returns the same route, because there is only one — so the entire comparison collapses to cells settled, and DFS, normally the worst thing here, becomes competitive with A*. Whenever a benchmark makes a bad algorithm look good, check whether the benchmark accidentally removed the choice.
Bottlenecks	Watch bidirectional's advantage narrow. When the map forces every route through a few gaps, both fronts must reach the same gaps, and the two-disc argument stops applying — geometry helps you only when the search is free to spread.