Generating and Solving Mazes with Python

Everyone seems to love a good maze - we've been into them for thousands of years at this point.

Webster defines 'maze' as a confusing intricate network of passages, and something confusingly elaborate or complicated.

Many of us have experienced this confusion, whether on paper, in video games, or for those who prefer total immersion, at one of these mazes you can visit in-person.

It's a nice feeling of accomplishment when you finally weave your way to finding the exit, but if that seems like a lot of work, you could always have a computer solve the maze for you.

I'm going to go over a few algorithms you can use to generate and solve mazes.

The code for everything in this post can be found here.

Generating a random maze

The first thing we have to do is create the maze. I used Kruskal's algorithm to generate this maze, and am using matplotlib for the visualizations.

Then I added a random entry point on one side, in blue, and a random exit point on each of the other sides of the maze, in red.

Kruskal's algorithm

Kruskal's algorithm finds a minimum spanning tree in a weighted, connected graph.

A maze can be viewed as a graph.

You can see from the image above that the graph I started with was a grid, and after removing some of the edges(walls), it became a maze.

If you're not familiar with graph theory, a connected graph means that there is a path from each vertex in the graph to every other vertex.

A weighted graph means the edges have weights - an example of this could be a street map with roads(edges) and intersections(vertices), and the edge weight might be the speed limit on each road.

A minimum spanning tree contains all of the vertices of the graph, with the minimum number of edges to connect them.

It won't have any loops or cycles.

The maze

One way to generate a maze is to assign random weights to each edge of a connected graph and then run Kruskal's algorithm on it.

So I added random weights to the edges of the grid I mentioned earlier.

Kruskal's algorithm starts with each vertex in the graph considered as its own cluster, and then merges the clusters together.

To merge the clusters together and build the spanning tree, first sort the edges by weight in ascending order - you want to pick the 'cheapest' edges first.

Then go through the sorted edges and for each one, check to see which cluster each vertex connected by that edge is in.

If the vertices are not in the same cluster, add the edge to the minimum spanning tree solution and join the two clusters together.

The output is a minimum spanning tree that is also a perfect maze, meaning there one unique solution between any two points in the maze.

Other algorithms to generate mazes

There are other algorithms you could use to generate a maze, such as Prim's algorithm, which is also used to find minimum spanning trees.

You can also use path-finding algorithms to generate mazes, as well as solve them, such as Depth-first search.

Or build mazes based on Voronoi diagrams.

There are MANY different ways to generate a maze.

Solving the maze with path-finding algorithms

We've drawn the maze and created entry and exit points, and now it's time to find a path or paths through it.

Breadth-first search

Breadth-first search, bfs, spreads out like a wave over the maze and can be used for finding the shortest path from one point to another in a graph.

With breadth-first search, you look at each neighbor of a point in the graph that is on the same level before moving on to the next level, which creates the wave effect.

Backtracking

The backtracking algorithm works incrementally to build each solution path, and would eventually find all solutions if you don't stop it earlier.

At each step of the path, this algorithm picks a random valid neighbor square to move to.

When it follows a path in the maze and finds a dead-end, it will backtrack to where it can continue building a solution from the last viable step.

In this animation you can see the backtracking when the path turns yellow.

Dijkstra / A*

Dijkstra's algorithm and the A* algorithm are both versions of breadth-first search, but the edges in the graph are weighted and in the case of A*, some kind of heuristic is used to help guide the search towards the target.

Dijkstra's algorithm can be used to find the shortest path from one vertex in a graph to another, as well as from one vertex to every other vertex.

It only works on graphs with positive edge weights. There are other algorithms for when there are negative edge weights, but we won't go there today.

The A* algorithm is similar to Dijkstra's algorithm but uses a heuristic to guide the path to the goal destination.

A heuristic could be anything depending on your goals, but often it is something like a distance equation.

For this solver, I gave each edge in the maze a weight based on how far it is from an exit, using the Manhattan distance, or L1 norm.

Here's the formula for that in Python.

abs(x1-x2) + abs(y1-y2)

At each step in the path, the algorithm looks at the options for the direction it could take next: forward, backwards, left or right, and picks the one that has the minimum distance to an exit.

If you compare this visualization with the earlier ones for breadth-first search or backtracking, it is more focused on guiding the path towards the exit, while the other two do not do anything to guide the path in a particular direction.

Thanks for reading!

All of the code used for this project is in Python.

I made the visualizations and animations in matplotlib.

Mazes are an interesting type of problem and are a great way to learn graph algorithms because you can use so many common graph algorithms to generate and solve a maze.

Here are some links if you want to read about mazes in general and their history.

National Building Museum: A Brief History of Mazes

Smithsonian: The Winding History of the Maze

Mental Floss: 15 Intricate Facts About Mazes

Let me know if you have other questions or comments. Write them below or reach out to me on Twitter @LVNGD.