Maze generator and pathfinder

How do pathfinding algorithms work?

Maze generation first builds a random spanning tree (exactly one path connects every cell to every other), then knocks down a few walls: loops and alternative routes appear, and part of the terrain is "rough" (triple cost).

Breadth-first search (BFS) explores layer by layer, visiting all cells at the same distance from the start before moving further out - in an unweighted graph this guarantees the shortest path, but it uses a lot of memory since it tracks many cells at once.

Depth-first search (DFS) follows one direction as far as it can go, backtracking only at dead ends - it uses far less memory, but doesn't guarantee the shortest path and often produces a more winding route.

Dijkstra's algorithm is the weighted version of BFS: it always expands the cheapest reachable cell next, so it guarantees the cheapest path even when accounting for rough terrain (triple cost).

A* is a smarter version of Dijkstra: a heuristic (typically an estimate of the remaining distance to the goal) steers the search, so it usually examines far fewer cells than Dijkstra while still guaranteeing the optimal path.

Greedy best-first search is the "one-eyed" cousin of A*: it only looks at the estimated distance left to the goal, not at the cost of the path so far. It often visits the fewest cells, but its path is not guaranteed to be the shortest or the cheapest.

Bidirectional BFS starts a breadth-first search from the start and one from the goal at the same time. The combined area of two small circles is far smaller than one big one, so it finds the same fewest-steps path while visiting far fewer cells.

The wall follower builds no map and remembers nothing: it just keeps its right hand on the wall. A person can do that too, but the actual route is often much longer than the shortest, and in a maze with loops it only works if the goal is attached to the same wall as the start.

Dead-end filling thinks the other way around: instead of looking for the path, it fills in dead ends until only the corridors joining start and goal remain. Loops are not removed by filling, so a BFS still runs on what is left here.