A-Maze

Web App: a-maze-creation.vercel.app

I like to play with puzzles with my kids. Mazes are especially good for the small ones, as the rules are simple and help them train their focus and motor coordination. I also like mazes, and even more so their connection with tree data structures.

If we represent every valid position in a maze as a node in a graph, the valid paths that you can walk (traversing the edges in the graph) will be part of a spanning tree.

To generate a maze, we can start with a fully connected graph representing the area of the maze and then generate a tree to determine where we have pathways and where we have walls. The goal is to visit every node (so we cover the entire maze area) and to visit each node only once (so the maze has dead ends but no loops).

We can use different algorithms to generate this tree, and the choice of algorithm will determine the structure of the maze. For example, depending on how the tree is created, we might get mazes with long corridors or mazes with shorter corridors but many dead ends.

• Depth-First Search: The algorithm walks the grid randomly, always going deeper into unvisited cells. When it gets stuck, it backtracks to the last cell with unvisited neighbors. Because it commits to a direction, it creates long corridors before ever branching.

• Prim’s Algorithm: The algorithm keeps a growing set of candidate edges on the border between visited and unvisited cells. At each step it picks a random edge from that frontier and adds it to the path. Because the frontier expands in all directions simultaneously, the tree it builds is bushy and symmetric.

• Kruskal’s Algorithm: The algorithm starts with every cell in its own disconnected component and adds edges randomly, one by one, as long as they don’t create a loop. As any edge is a candidate to be added, the maze paths grow with no spatial bias, resulting in a maze with uniform texture.

• Wilson’s Algorithm: The algorithm uses loop-erased random walks to generate a uniform spanning tree. Each path added to the maze is a random walk that starts at an unvisited node and ends at a visited node already part of the maze. If the random walk creates a loop (revisits a node from the current walk), the loop is discarded and the walk continues from that point. This produces a maze that is hard to solve, as there is no visual bias in the texture to hint at which way to go at a fork.

What I find interesting is that Prim’s algorithm generates many dead ends, but because they are short corridors, we can easily skim past them, resulting in a maze that looks complicated but has an almost straight path from start to end. When growing the tree, both DFS and Prim’s have a bias on where to explore next. For a uniform texture, the maze corridors need to expand without any structural bias, and that is what we get with Kruskal’s and Wilson’s algorithms (their expansion points don’t depend on the existing maze structure).

Combining all these together in an app is easy with vibe-coding. I created an app to make it easier to print new mazes for them. If you also like mazes, generate some here: a-maze-creation.vercel.app

Happy maze solving!
CB