Python’s Path Through Mazes: A Journey of Creation and Solution

Introduction

Mazes have been fascinating humans for centuries. From the labyrinth of Greek mythology to the garden mazes of the European nobility, these intricate networks of paths and walls are both challenging and fun. But did you know that you can create and solve mazes programmatically using Python? In this blog post, we’ll walk you through the process, step by step.

Creating the Maze Algorithm

The basis of our maze generation is the depth-first search (DFS) algorithm. At the highest level, this algorithm works by starting at a given node (in our case, the upper-left cell of the maze), and exploring as far as possible along each branch before backtracking. It uses a stack data structure to remember the position of nodes that are still unexplored.

In the context of maze generation, we treat the cells of the maze as the nodes. For each cell, we consider its neighboring cells as the branches that can be explored. However, to prevent the maze from becoming a grid of open cells, we ensure that we only move to a cell if there is a wall between it and the current cell.

In the code, we initialize the maze as a grid filled with “1”s, representing walls. We represent cells as “0”s. We then define the starting point (0, 0), and initialize the stack with this starting point. The DFS algorithm starts by taking the top cell from the stack (which initially is the starting cell), and checks its neighbors in random order. If it finds a neighbor that is a wall and is within the maze boundaries, it moves to that cell (making it an open cell), and pushes it to the stack. It then starts again with the new cell.

If it cannot find such a neighbor, it means that all neighbors of the current cell have already been visited, and so it removes the cell from the stack and backtracks to the previous cell. This process continues until the stack is empty, which means that all reachable cells have been visited. The end result is a random maze that can be navigated from the starting point to any other reachable cell.

Finally, to make the maze solvable, we ensure there is an entrance and an exit. We do this by setting the first cell in the first row and the last cell in the last row as “0”s (open cells).

import matplotlib.pyplot as plt
import numpy as np
import random
from queue import Queue

def create_maze(dim):
    # Create a grid filled with walls
    maze = np.ones((dim*2+1, dim*2+1))

    # Define the starting point
    x, y = (0, 0)
    maze[2*x+1, 2*y+1] = 0

    # Initialize the stack with the starting point
    stack = [(x, y)]
    while len(stack) > 0:
        x, y = stack[-1]

        # Define possible directions
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        random.shuffle(directions)

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if nx >= 0 and ny >= 0 and nx < dim and ny < dim and maze[2*nx+1, 2*ny+1] == 1:
                maze[2*nx+1, 2*ny+1] = 0
                maze[2*x+1+dx, 2*y+1+dy] = 0
                stack.append((nx, ny))
                break
        else:
            stack.pop()
            
    # Create an entrance and an exit
    maze[1, 0] = 0
    maze[-2, -1] = 0

    return maze

Creating the Maze Solution

To solve the maze, we use the breadth-first search (BFS) algorithm. Unlike DFS, which goes as deep as possible into the maze before backtracking, BFS explores all neighbors of the current cell before moving on. This guarantees that it will find the shortest path from the starting point to the target.

The BFS algorithm also uses a queue data structure to keep track of the cells that need to be explored. However, in our case, each item in the queue is a tuple of the current cell and the path taken to reach it. This allows us to keep track of the path followed by the algorithm.

We start by adding the starting cell and an empty path to the queue. Then, as long as the queue is not empty, we take the first item from the queue, explore its neighbors, and add them to the queue. Similar to the DFS algorithm, we ensure that we only move to a cell if it is an open cell and has not been visited before.

When we add a neighbor to the queue, we also append it to the current path to keep track of the path taken to reach it. If we reach the target cell, we return the path taken to reach it. Since BFS explores all neighbors of the current cell before moving on, this path is guaranteed to be the shortest path.

At the end, if we have explored all reachable cells and have not found the target, the queue will become empty and the algorithm will stop. This indicates that there is no path from the starting point to the target.

def find_path(maze):
    # BFS algorithm to find the shortest path
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    start = (1, 1)
    end = (maze.shape[0]-2, maze.shape[1]-2)
    visited = np.zeros_like(maze, dtype=bool)
    visited[start] = True
    queue = Queue()
    queue.put((start, []))
    while not queue.empty():
        (node, path) = queue.get()
        for dx, dy in directions:
            next_node = (node[0]+dx, node[1]+dy)
            if (next_node == end):
                return path + [next_node]
            if (next_node[0] >= 0 and next_node[1] >= 0 and 
                next_node[0] < maze.shape[0] and next_node[1] < maze.shape[1] and 
                maze[next_node] == 0 and not visited[next_node]):
                visited[next_node] = True
                queue.put((next_node, path + [next_node]))

Drawing the Maze

Now that we have our maze generated, it’s time to visualize it. For this task, we are using matplotlib, a versatile plotting library in Python.

In our function draw_maze(maze, path=None), we start by creating a figure and an axis object. The figure object is a top-level container for all plot elements, while the axis represents a single plot. We're also setting a specific size for the figure to ensure that the maze is easy to view, regardless of its size.

Next, we use the imshow function of the axis object to display the maze as an image. The maze, which is represented as a 2D numpy array, translates perfectly to an image format, with "1"s representing black pixels (the walls) and "0"s representing white pixels (the open cells). We use the plt.cm.binary colormap to achieve this color representation. The interpolation parameter is set to 'nearest' to preserve the blocky nature of the maze when the image is displayed.

In the case where we want to draw a solution path onto the maze, we check if a path is provided to the function. If it is, we extract the x and y coordinates of each point on the path. Since the path is represented as a list of tuples, where each tuple is a pair of coordinates (y, x), we use list comprehension to extract the lists of x and y coordinates. We then use the plot function of the axis object to draw the path onto the maze. We set the color of the path to red and its linewidth to 2 for better visibility.

Finally, we use the set_xticks and set_yticks functions of the axis object to hide the x and y axis, as they are not relevant to the visualization of the maze. We also draw arrows representing the entrance and the exit of the maze. We use the arrow function of the axis object, setting the start points and direction of the arrows, and also their color and size.

When we run the script and input the desired dimension of the maze, the script will generate a random maze of the specified size, find the shortest path from the entrance to the exit, and draw the maze and the path onto a figure, which is then displayed to us.

def draw_maze(maze, path=None):
    fig, ax = plt.subplots(figsize=(10,10))
    
    # Set the border color to white
    fig.patch.set_edgecolor('white')
    fig.patch.set_linewidth(0)

    ax.imshow(maze, cmap=plt.cm.binary, interpolation='nearest')
    
    # Draw the solution path if it exists
    if path is not None:
        x_coords = [x[1] for x in path]
        y_coords = [y[0] for y in path]
        ax.plot(x_coords, y_coords, color='red', linewidth=2)
    
    ax.set_xticks([])
    ax.set_yticks([])
    
    # Draw entry and exit arrows
    ax.arrow(0, 1, .4, 0, fc='green', ec='green', head_width=0.3, head_length=0.3)
    ax.arrow(maze.shape[1] - 1, maze.shape[0]  - 2, 0.4, 0, fc='blue', ec='blue', head_width=0.3, head_length=0.3)
    
    plt.show()

Running the Maze

Once we have defined our maze creation, maze solving, and visualization functions, we can bring these components together and see how to actually run our maze generator and solver. Here is how to get everything working.

First, you need to have Python installed on your machine. If you haven’t done this yet, go to the official Python website, download the latest version of Python, and install it.

Additionally, you need the numpy and matplotlib libraries, which can be installed via pip:

pip install numpy matplotlib

After setting up Python and necessary libraries, save the Python code provided in the sections above to a file, say maze.py.

The if __name__ == "__main__": statement in our code is a Pythonic way of ensuring that the code block underneath it will only be executed if this module is the main program. This means, when you directly run maze.py, the code under this statement will be executed. However, if you import maze.py as a module in another script, the if __name__ == "__main__": block will not run.

if __name__ == "__main__":
    dim = int(input("Enter the dimension of the maze: "))
    maze = create_maze(dim)
    path = find_path(maze)
    draw_maze(maze, path)

This block of code kicks off the maze generation process. First, it asks the user to input the desired dimension of the maze. Then, it uses this dimension to create the maze using our create_maze function. The find_path function is then called to find a solution to the maze, and finally draw_maze is used to visualize the result.

Once you’ve saved your Python file, you can run this Python file from the terminal (or command prompt in Windows) as follows:

python maze.py

Upon running, it prompts you to enter the dimension of the maze. This number refers to the number of cells in one row or column (not the actual pixel size of the maze). For a start, you can enter 10 or 15.

The program then generates a maze of the corresponding size, solves it, and displays the maze and its solution. The black areas are walls, the white areas are free paths, the red line is the shortest path from the start to the end, and the green and blue arrows indicate the entrance and exit of the maze.

The visual representation is a powerful tool for checking the correctness of our program. If you see the red path going from the green arrow to the blue arrow and the path doesn’t traverse through any walls, you’ll know that both the maze generator and the solver are functioning correctly.

Feel free to experiment with different maze dimensions or modify the code to customize the maze generation and solution behavior. Maybe you could adapt the generator to create mazes with more than one solution, or modify the solver to implement a different pathfinding algorithm. The possibilities are limitless!

Conclusion

The generation, solution, and visualization of mazes are fascinating subjects that touch on a wide range of computer science and mathematics topics including graph theory, search algorithms, and data visualization.

In this tutorial, we created a simple maze generator using Python’s built-in data structures and a Depth-First Search approach. We then demonstrated how to solve this maze using a Breadth-First Search algorithm, which guarantees the shortest path from the start to the finish.

While our generated maze is simple and the path is straight-forward, the concepts explored in this tutorial extend well into much more complex situations. Maze generating algorithms form the backbone of procedural content generation in video games, modeling complex structures and patterns in nature, and even in the routing of PCBs in electronics.

The visualization aspect of this project is also significant. It shows how simple it is to use matplotlib to represent our data graphically. Understanding how to plot and visualize data is a crucial skill in Python and other programming languages.

Moreover, the project’s extensibility is one of its most exciting aspects. This maze generator and solver is a starting point, and there are countless ways you could expand upon it. You could introduce complexity into the maze creation, incorporate multiple solutions, add a GUI for real-time interaction, or even use these principles to create an entire game.

As we wrap up this discussion, I hope this serves as a launching pad for you to explore more about these topics and inspire you to create new and exciting projects. The ability to generate, solve, and visualize problems is a powerful tool in a programmer’s toolbox. So, keep experimenting, keep learning, and most importantly, have fun with your coding journey!

Update: Animating the Maze

Previously we just drew the path of the solution to the maze. You can actually animate the maze using the matplotlib animation library. To animate your maze, simply replace the draw maze function with the following code:

import matplotlib.pyplot as plt
import matplotlib.animation as animation


#... animate the path through the maze ...

def draw_maze(maze, path=None):
    fig, ax = plt.subplots(figsize=(10,10))
    
    # Set the border color to white
    fig.patch.set_edgecolor('white')
    fig.patch.set_linewidth(0)

    ax.imshow(maze, cmap=plt.cm.binary, interpolation='nearest')
    ax.set_xticks([])
    ax.set_yticks([])
    
    # Prepare for path animation
    if path is not None:
        line, = ax.plot([], [], color='red', linewidth=2)
        
        def init():
            line.set_data([], [])
            return line,
        
        # update is called for each path point in the maze
        def update(frame):
            x, y = path[frame]
            line.set_data(*zip(*[(p[1], p[0]) for p in path[:frame+1]]))  # update the data
            return line,
        
        ani = animation.FuncAnimation(fig, update, frames=range(len(path)), init_func=init, blit=True, repeat = False, interval=20)
    
    # Draw entry and exit arrows
    ax.arrow(0, 1, .4, 0, fc='green', ec='green', head_width=0.3, head_length=0.3)
    ax.arrow(maze.shape[1] - 1, maze.shape[0]  - 2, 0.4, 0, fc='blue', ec='blue', head_width=0.3, head_length=0.3)
    
    plt.show()

FuncAnimation is a class provided by `matplotlib.animation` module in Python’s matplotlib library. It provides a framework for creating animations and interactive plots in Python, by repeatedly calling a function (the `update` function in our case).

In FuncAnimation, we provide the figure object that we are animating, the function to call at each frame (our `update` function), the number of frames (which is the length of our path), and the interval between frames (in milliseconds).

Here’s a breakdown of how the FuncAnimation class works in our context:

- fig: This is the figure object that we are going to animate. This is the main drawing canvas in matplotlib and contains everything you see on a plot.

- update: This is the function we want to call for each frame in the animation. Here, it takes an integer parameter frame(which automatically increments for each frame) representing the current frame of the animation.

- frames=len(path): This is the total number of frames in the animation, which is set to be the number of points in the path. This means that `update` will be called `len(path)` times in total.

- interval=100: This sets the delay between frames in milliseconds. So in our case, a new frame will be drawn every 100 ms, i.e., we’re effectively running the animation at 10 frames per second.

- repeat=False: This is a flag determining whether the animation should repeat once it has completed. In our case, we only want to animate the solution path once, so we set `repeat=False`.

Overall, FuncAnimation provides an easy-to-use interface for creating animations in Python with matplotlib. By repeatedly calling an update function, we can draw complex animations like the solution path through the maze, where each step in the path is drawn one at a time to create the effect of “moving” through the maze.

BTW, if you enjoyed reading this article and you want to dive into more animated games in Python, check out my book Creating Video Games Using PyGame: