Understanding the Theseus Maze Algorithm
The Theseus algorithm is a maze generation technique inspired by the Greek myth. You have a grid of cells. Each cell starts as a bare square with all four walls intact. The algorithm picks a starting cell, carves a path through the grid by removing walls between adjacent cells, and marks each visited cell. The result is a perfect maze - one where every cell is reachable from every other cell and there are no loops. I wrote my first version of this in Python years ago for a game jam. The basic structure is straightforward. You create a 2D array representing your maze grid. Each cell holds wall data - which of its four sides are still blocked. Then you run a recursive function that randomly picks an unvisited neighbor, removes the shared wall, and recurses. When there are no more unvisited neighbors, you backtrack. That backtracking is the "thread" in the myth, the path that keeps you from getting permanently lost. Here is the core function:
def generate_maze(width, height):
maze = create_grid(width, height)
visited = set()
stack = [(0, 0)]
visited.add((0, 0))
while stack:
current = stack[-1]
neighbors = get_unvisited_neighbors(current, maze, visited)
if neighbors:
next_cell = random.choice(neighbors)
remove_wall(current, next_cell, maze)
visited.add(next_cell)
stack.append(next_cell)
else:
stack.pop()
return maze This iterative version using an explicit stack avoids Python recursion limits, which matter more than you might think. A 50x50 maze will blow past the default recursion depth pretty quickly on a recursive implementation. One thing people overlook is the difference between a perfect maze and a more open maze. The standard Theseus algorithm always produces a perfect maze - single solution between any two points. If you want multiple paths, you need to add extra carved passages after generation. I do this by running a second pass where I remove random walls between already-connected cells at a controlled probability, maybe 5 to 10 percent. Too high and the maze loses its structure. Too low and the player barely notices the difference.
The actual file I use is available on GitHub. Search for the repository and grab the main maze_generator.py file along with the render module. The render module supports ASCII output, pygame rendering, and a simple HTML canvas exporter. The HTML exporter is useful if you want to drop a maze into a web project without setting up a graphics library. Here is a practical problem I hit once that took me a while to figure out. I was generating mazes for a top-down dungeon crawler and the exit point was sometimes unreachable from certain starting positions if I used a non-standard grid alignment. The issue was that my wall-removal logic only checked cardinal directions but the map coordinates were offset by half a cell for rendering purposes. The fix was to keep the logical grid and the rendering grid completely separate. The algorithm runs on the integer grid. The renderer translates that to whatever coordinate system the game engine uses. Never mix the two. Another detail that matters is performance. For mazes up to about 100x100, this runs in under a second on modern hardware. Beyond that, you start seeing noticeable delays. If you need larger mazes, consider using a bitwise representation for the walls instead of boolean flags per side. It cuts memory usage significantly and the cache behavior improves on larger datasets. I switched to this approach when working on a level that was 500x500 and the generation time dropped from roughly four seconds to under half a second.
Get the Full Details
If you are using this for a game, the entrance and exit placement matters more than most people account for. The standard approach puts the start at the top-left and the end at the bottom-right. But if your game has multiple spawn points or procedural placement, the distance between them can vary wildly depending on the random seed. I add a post-processing check that measures the shortest path between spawn and goal and regenerates if the path is shorter than a minimum threshold or longer than a maximum threshold. For a 100x100 maze, I keep the path length between 80 and 200 cells. This keeps the game from having trivially short corridors or frustratingly long back-and-forth routes. The algorithm itself has a limitation worth noting. Because it is entirely random, you cannot predict the difficulty before generation. Two mazes of the same size can feel completely different. Some will have long winding corridors that take a player minutes to traverse. Others will have clusters of short dead ends that slow progress through constant backtracking. If your game requires consistent pacing, you will need additional balancing logic on top of the raw generation. For visual output, the ASCII renderer is the quickest way to test your maze during development. Just pipe it to a terminal and print it out. It takes about 50 milliseconds for a 30x30 grid and gives you immediate visual feedback on whether the generation is working correctly. If the maze looks completely blocked, something went wrong with the wall removal logic rather than the traversal.
The script is released under MIT license so you can modify it freely. The repository includes documentation on each function and the configuration options for wall density, grid size, and output format. I keep it updated because I still use it in small personal projects and occasionally fix edge cases that come up.
