Let's have some fun with trees! We'll use depth first search to generate a perfect maze and then use both depth first search and breadth first search to solve the maze. We'll also get some practice with bit manipulation since our maze class will represent each cell as a 16-bit number.
A perfect maze is a maze with only one path between any two cells. Since there is only one path between any two points you can represent a perfect maze as a tree. Lucky for us, perfect mazes are the easiest type of maze to create programmatically.
Check out this video for a visualization of a perfect maze transforming into a tree and back into a maze.
- Go to the assignment page
- Accept the assignment and follow the link to the created repository
- Clone the repository and use it throughout this project
This project makes use of
pygame for visualization so you'll have to install a few dependancies before it'll run. Run the following command to install the
$ brew install mercurial sdl sdl_image sdl_mixer sdl_ttf smpeg portmidi Caskroom/cask/xquartz
Now it's time to set up our virtual environment. First, find out the file path to Python 3 by running this command:
$ which python3
On my machine, this outputs
/usr/local/bin/python3, but it might be different for you.
Then, run the
virtualenv command supplying the path to the Python 3 interpreter after with the
-p flag, followed by the name of the virtual environment directory, in this case
$ virtualenv -p /path/to/python3 venv
You should see some nice logging output telling you what
virtualenv is doing.
There is still one more step before
virtualenv is activated, i.e. before we are actually using our virtual environment instead of our regular one. We need to activate it! Run this command to activate:
$ source venv/bin/activate
Now that we created our virtual environment and activated it, let's install
pygame. It's already listed in
requirements.txt so we just need to run:
$ pip3 install -r requirements.txt
Maze generation begins with a grid of cells. Each cell starts with walls between itself and its neighboring cells.
To go from a grid of unconnected cells to a perfect maze we need to knock down some of those walls. We'll choose a random cell to start from and traverse the grid using depth first search. Whenever a new cell is visited, the wall between the new cell and the previous cell is knocked down.
This means that each cell needs to store its knocked down walls. We will be solving the maze using depth first search so each cell also needs to store if the solution or backtrack path passes through it. The start cell (or root node) will always be the top-left most cell. The exit cell (or goal node) will always be the bottom-right most cell. A fully solved maze can be seen below. Green represents the solution path and red represents the backtracked path.
Cell Data Structure
- The left-most set of 4-bits store the backtrack path
- The next set of 4-bits store the solution path
- The next set of 4-bits store if a cell is on the maze border
- The right-most set of 4-bits stores which walls have been knocked down
Each bit in the 4-bit sets corresponds to a cardinal direction. From left-to-right the bits represent west, south, east, north. This means each cell will start as 16-bits of zero (
The top-left cell of the above image can be represented as
0b0000010010010110. That is:
- 0000 for no backtrack path passing through
- 0100 for solution path passing through to the south
- 1001 for maze borders to the west and the north
- 0110 for knocked down walls to the south and the east
Storing cells as 16-bits will allow us to use bit manipulation to modify and retrieve data! The maze itself is stored as a list of 16-bit numbers.
The starting code does not make use of the four border bits. It uses the minimum and maximum list indices instead. This is a bit easier to implement but means that the code needs to be updated before non-rectangular mazes can be generated and solved!
Before we can get started generating a maze, we need finish up the
Maze class. Open up
maze.py and take a look at the provided code. All of the code needed for storing and visualizing a maze is provided but the logic for manipulating each cell of the maze has been left out.
Take note of the variables provided at the top of
maze.py -- they'll be handy as you finish up the Maze class.
Let's dive right into bit manipulation and finish up the methods that maze generation needs!
In Python, we can express a number using bits by starting it off with
0b. The number is stored as an integer but we can see the binary representation using
bin(number). Play around with this notation in the Python interpreter until you get the hang of it.
$ python 3 >>> x = 0b1011 >>> x 11 >>> bin(x) '0b1011'
cell_neighbors takes a cell and returns its neighbors. It does not return every neighbor though! It filters the neighbors according to the
state of the maze. When finished, our maze will have three states: idle, create, solve. Right now we are only worried about the create state. During creation, the only neighbors we care about are those without any walls knocked down -- this means the cell has not been visited yet.
Complete the implementation of
cell_neighbors so that it:
creates empty list of neighbors for each direction calculate new cell from cell if new cell in that direction is within the bounds of maze if state is create and all of new cell's walls are up add (new cell index, COMPASS index of direction) to neighbors return neighbors
You can check if all walls are still up using a bitwise AND (
& in Python). Bitwise AND compares the bits between two numbers -- each bit of the output is 1 if the corresponding bit of x and y is both 1, otherwise it is 0. Play around with
& in the Python interpreter to get a feel for it.
We can use
WALL_BITS (0b0000000000001111) to check if any of the 4-bits representing knocked down walls have been set. If a cell has all of its walls up, the right-most bits will all be zero and
self.maze_array[cell] & WALL_BITS will evaluate to zero...
Make sure to store the new cell index and compass index as a tuple. The returned list should look something like this:
[(1, 0), (3, 3)]
This represents two unvisited neighboring cells. The first is at cell index
1 and to the left (
COMPASS), the second is at cell index
3 and to the right (
COMPASS indices will come in handy soon since the indices of
OPPOSITE_WALLS match up.
cell_neighbors method should look like this:
def cell_neighbors(self, cell): x, y = self.x_y(cell) neighbors =  for i in range(4): new_x = x + COMPASS[i] new_y = y + COMPASS[i] if self.cell_in_bounds(new_x, new_y): new_cell = self.cell_index(new_x, new_y) if self.state == 'create': if not (self.maze_array[new_cell] & WALL_BITS): neighbors.append((new_cell, i)) return neighbors
connect_cells is expected to update the 4-bits storing knocked down walls for the
from_cell and the
to_cell. To do this, we can use bitwise OR (
| in Python). Bitwise OR compares the bits between two numbers -- each bit of the output is 1 if either corresponding bit of x or y is 1, otherwise it is 0. Play around with
| in the Python interpreter to get a feel for it. Bitwise OR will allow us to add data in without erasing the old data.
Complete the implementation of
self.maze_array[from_cell] = self.maze_array[from_cell] | WALLS[compass_index] will update the
from_cell. Do the same with
OPPOSITE_WALLS. Leave the call to
draw_connect_cells or else the maze visualization will not be updated!
connect_cells method should look like this:
def connect_cells(self, from_cell, to_cell, compass_index): self.maze_array[from_cell] |= WALLS[compass_index] self.maze_array[to_cell] |= OPPOSITE_WALLS[compass_index] self.draw_connect_cells(from_cell, compass_index)
x |= y is short hand for
x = x | y. This
operator= short hand also works for
Great! We can move on to generating mazes now that we have both of those working!
Generating a maze
We want to use depth first search to generate our mazes. More specifically, we want to use randomized, pre-order depth first search. Pre-order means we visit or 'knock down walls for' a cell before continuing to its potential children (unvisited neighbors). Randomized means we pick a random but unvisited neighbor to continue our traversal.
When we hit a dead end (cell with no unvisited neighbors), we will 'backtrack' to the most recent cell that still has children to visit (unvisited neighbors). Backtrack cells are stored in a stack.
As we generate a maze, we are essentially creating a spanning tree from a grid graph. This means we are creating a tree that connects each cell in the grid.
Pseudocode for Generating a Maze
create a stack for backtracking choose a cell index at random from the grid to be current cell set visited cells to 1 while visited cells < total cells get unvisited neighbors using cell_neighbors if at least one neighbor choose random neighbor to be new cell knock down wall between it and current cell using connect_cells push current cell to stack set current cell to new cell add 1 to visited cells else pop from stack to current cell call refresh_maze_view to update visualization set state to 'solve'
Implement the pseudocode above in the
create_dfs function of
python3 generate_maze.py to see if your maze is generating correctly!
If you did everything right, your maze generation should look like this:
If you have feedback on this tutorial or find any mistakes, please open issues on the GitHub Repository or comment below.