Maze Generation Algorithms with Matrices in Python

Photo by Sigmund on Unsplash

Only those who leave the labyrinth can be happy, but only those who are happy can leave it. (Michael Ende)

Embracing the suggestion given by a friend, I recently bought a fabulous book about mazes (“Mazes for Programmers: Code Your Own Twisty Little Passages”): I always loved mazes, even though I didn’t have quite the chance to study and investigate them so that was the perfect fit for me to begin the journey.

In the book, various algorithms to generate/solve mazes are given, along with the author’s solution to develop them.

Since the author went for the “structure” way to generate/solve mazes, I decided to go for “hard mode”, trying to replicate the same algorithms using matrices.

Terminology

Before even beginning to code, I found myself asking about the difference between “maze” and “labyrinth” (even because, at least in Italian, the two words are used interchangeably).

After some research (source: Wikipedia), it turned out that:

• a maze refers to a complex branching multicursal puzzle with choices of path and direction
• a labyrinth has only a single path to the center

Looking at the results of the following algorithms, we are then going to generate mazes “texture” without enter/exit point (those can be added as last stage).

Binary Tree algorithm

The binary tree algorithm to generate mazes is probably the simplest.

If we think about the “maze world” as a matrix, we can start in the upper-left part of the maze and toss a coin in every “room” (cell). If we obtain a head, we go north; otherwise we go east.

We manage “edge cases” as follows:

• if we obtain heads and we can’t go north, we go east.
• if we obtain tails and can’t go east, we go north

We observe a couple of notable results here:

• the maze generation “per se” is just given by a binomial distribution over the matrix cells (n=1, p=0.5)
• every cell in the first row of the matrix will be just switched to be a“tail”
• every cell on the last column will be switched to be a “head”.

The code

Generating the maze with the binary tree algorithm

To generate the matrix “tosses” we will use numpy: numpy comes with a handy function to generate a matrix of a given size filled with 0,1 as per the per binomial distribution.

At this point, the maze matrix generation is a one-liner:

n = 1
p = 0.5
size = 5
grid = np.random.binomial(n,p, size=(size,size))

We then pre-adjust the tosses on the first line and the last column of the maze to manage the edge cases:

first_row = grid[0]
first_row[first_row == 1] = 0
grid[0] = first_row
for i in range(1,size):
  grid[i,size-1] = 1

Setting up the output grid and carving the maze

The bulk of the work in now *actually* carving the maze for the output on the console.

We set up an output grid which is, for a mere extetic reason, a grid which is 3 times in size with respect to the original maze size and which is filled with ‘#’: this way, we can carve the walls keeping the tosses into account.

We set a convention to be:

• carving along the i index to carve north
• carving along the j index to carve east

The original i,j indices are projected to the output matrix with a simple multiplication; carving the wall is the same as setting to blank character the two adjacent cells (to the north or to the east) in the output grid.

def carve_maze(grid, size):
  output_grid = np.empty([size*3, size*3],dtype=str)
  output_grid[:] = '#'
  i = 0
  j = 0
  while i < size:
    w = i*3 + 1
    while j < size:
      k = j*3 + 1
      toss = grid[i,j]
      output_grid[w,k] = ' '
      if toss == 0 and k+2 < size*3:
        output_grid[w,k+1] = ' '
        output_grid[w,k+2] = ' '
      if toss == 1 and w-2 >=0:
        output_grid[w-1,k] = ' '
        output_grid[w-2,k] = ' '
      j = j + 1
    i = i + 1
    j = 0
  return output_grid

Printing the maze to the console

The maze is returned as a list of lists of characters.

To print the maze to screen we just join the elements in each list:

for elm in output:
  print(" ".join(elm))

The output for a 5*5 size maze is the following:

A maze generated with binary tree algorithm

Playing with parameters

We can play with the probability parameter, p, to check how the output changes.

The following maze has been generated with a p=0.2:

A maze generated with binary tree algorithm (p=0.2)

Since the base matrix has a lot of zeros, the maze texture is mostly horizontal.

The following one has been generated with p=0.7, instead:

A maze generated with binary tree algorithm (p=0.7)

Since the base matrix has a lot of ones, the maze texture is mostly horizontal.

Curious about the complete code? Check out the complete source here: https://github.com/antigones/pymazes

More content at plainenglish.io