How do we make a maze? It’s not a trivial question. We could start by taking an NxN grid and randomly add walls between squares. Then I suppose we could start at a random square and do a breadth-first search to check that all squares are reachable (assuming we want our maze to be fully connected) and if not, start over. But this kind of brute-force approach quickly runs into problems. The long and short of it is: if your wall-adding rate is conservative enough to build a connected maze in a reasonable amount of time, you can be sure your maze won’t really be a maze per se, more of a wide open grid with a few walls scattered here and there. Thankfully, Wilson’s Algorithm comes to the rescue. The algorithm itself is as follows: Pick a random square to declare as the beginning to the maze. Pick a random square not yet connected to the maze and start a random walk until you hit a square that’s already part of the maze. If the walk forms a loop, erase that loop and continue. Once the walk connects to the maze, add that path to the maze Repeat until all squares connect to the maze. The process is kind of tough to follow by just reading the steps, but seeing it in action makes things a lot clearer. Recently I’ve been exploring mazes and maze algorithms from a topological perspective. What maze-solving and maze-generating algorithms work well on a torus? Or double-torus? Projective plane? I’m nowhere near ready to say, but my implementation of Wilson’s Algorithm below will let you see how it works on the surface of a torus (the left edge of the grid connects to the right, and the top to the bottom.)