One loop, many searches

Breadth-first, depth-first, Dijkstra and A* are usually taught as separate algorithms. They are one short loop with a single decision swapped out. Here you can swap it yourself and watch the search change.

The loop

Every search keeps a frontier of places it could go next and a record of places it has already visited. Each turn it asks one question: which frontier entry should I take out now? The highlighted line is where that question is answered, and it is the only place the famous algorithms differ.

p.removeChoice: Chooses which frontier entry to expand next, and returns it with the entries left over. This is the strategy.
p.isGoal: Says whether a state is the one we want.
p.nextActions: Lists the moves available from a state.
p.applyAction: Returns the state a move leads to. It must build a fresh state and never change the old one.
p.stepCost: Prices a single move.
p.heuristic: Guesses the remaining cost to the goal, for the strategies that use a guess.

The page runs the code you see here, not a lookalike. Two points are easy to miss. id(state) turns a state into a number, because two states with equal contents are different objects and === would never match them. And when a second route reaches a state already waiting in the frontier, only the cheaper route is kept.

Try it

Choose a strategy and press Play. Only the highlighted function in the right-hand panel changes. Drag the green and red markers, or paint walls and mud onto the map.

Strategy (removeChoice)

Expanded0

In frontier1

Route cost–

Route steps–

Speed

Frontier, in list order (next out is outlined)

Moves (nextActions)

4 directions 8 directions

Mud cost (stepCost): 5

Brush

Wall Mud Erase

Map

The parts that never change

Things to try

Run Breadth-first, then Cheapest-first. Which one walks straight through the mud, and which one goes round?
Run Greedy on the default map. Watch it march into the pocket in front of the goal and fill it before it escapes.
Drag the mud cost down to 1. Breadth-first and Cheapest-first now agree, because every step costs the same.
Switch to 8 directions and look at nextActions and heuristic in the panel. The strategies stay as they were, but the map around them changed.

Same map, five strategies

Each tile is a complete run on the map above, using your current walls, mud and move rules. Visited cells are shaded from the first expanded (pale) to the last (strong). Compare how many cells each strategy had to touch with how good its route is.

What each swap does

Strategy	Takes next	The frontier acts like	Guarantee
Breadth-first	The oldest entry	A queue	The route with the fewest steps. Costs are ignored.
Depth-first	The newest entry	A stack	None. It finds a route if one exists, but not a good one.
Cheapest-first	Lowest cost so far	A priority queue on cost	The cheapest route (Dijkstra's algorithm).
Greedy	Lowest estimate to goal	A priority queue on the estimate	None. Fast on friendly maps and easily trapped.
A*	Lowest cost so far plus estimate	A priority queue on both	The cheapest route, provided the estimate never overshoots.

The same idea carries well beyond maps. Sliding puzzles, route planners and action planners all supply their own isGoal, nextActions, applyAction and stepCost, then borrow a strategy from the table. The loop in the first section is the graph-search outline from Russell and Norvig, Artificial Intelligence: A Modern Approach.