Back
Maze
A maze carves itself out one passage at a time, then a breadth-first search floods outward from the start to find the shortest way to the exit.
A maze carves itself out one passage at a time, then a breadth-first search floods outward from the start to find the shortest way to the exit.
Generation uses a randomized depth-first search, usually called a "recursive backtracker": from the current cell, carve a passage to a random unvisited neighbour and move into it, remembering the cell just left. When a cell has no unvisited neighbours left, back up to the last remembered cell and keep carving from there — that backtracking is exactly what produces the long, winding corridors instead of a grid of little disconnected rooms.
Once every cell has been visited, the maze is finished and a breadth-first search takes over: starting from the top-left cell, it explores outward one ring at a time, tracking which cell led to which. Because it expands ring by ring rather than committing to one direction first, the moment it reaches the bottom-right cell that trail of "which cell led here" is guaranteed to be the shortest possible path — not just a path.
The highlighted region during solving is that expanding search frontier; the final line is the shortest path reconstructed by walking the trail backwards from the exit to the start.