Pathfinding & Spatial

A* finds the shortest path from a start cell to a goal cell on a grid by combining the cost so far (g) with an admissible estimate of the remaining cost (h, here Manhattan distance). It always expands the open-set node with the smallest f = g + h, which lets it focus exploration toward the goal rather than fanning out uniformly like Dijkstra's. With an admissible, consistent heuristic, A* is guaranteed to return an optimal path, and it routinely outperforms uninformed search on spatial maps. Pathfinding in games, robotics, and routing systems is the canonical application.

Dijkstra's algorithm specialised to a grid finds the shortest path from a start cell to a goal cell when every step costs the same. It expands the open-set node with the smallest tentative distance, relaxing each unblocked neighbour, until it pops the goal. Unlike A*, it has no heuristic — every direction is treated equally — so it explores the frontier as an expanding ring around the start. The grid version makes the difference from heuristic-guided search tangible: side-by-side with A*, you see exactly how much exploration the heuristic saves.

The recursive backtracker — also called randomised depth-first search — generates a perfect maze (one with exactly one path between any two cells) by carving passages from a starting cell. At each step it picks a random unvisited neighbour two cells away, knocks down the wall between them, and recurses; when no unvisited neighbours remain, it backtracks. The result is a long, winding maze with few short branches, distinct from algorithms like Prim's or Wilson's that produce more uniform structure. Mazes generated this way are a common test bed for pathfinding algorithms.