Maze generation algorithms with matrices in Python (II) — Sidewinder

Photo by Tobias Rademacher on Unsplash

Through dangers untold and hardships unnumbered I have fought my way here to the castle beyond the Goblin City to take back the child you have stolen, for my will is as strong as yours and my kingdom as great. You have no power over me! (Jim Henson)

The sidewinder algorithm is a slight variation of the binary tree one: we flip a coin in every cell of the matrix again and if we obtain tails (0) we carve east, if we obtain heads (1) we look back at the cells we visited until that moment, randomly choose one and carve north.

We start again with a binomial distribution over a matrix of a chosen size:

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

It makes sense again to preprocess the grid to avoid digging out the maze, changing ones in the first row with zeros and zeros in the last column with ones:

def preprocess_grid(grid, size):
  # fix first row and last column to avoid digging outside the maze 
  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
  return grid

In order to choose a random cell among the ones we previously visited, we need to keep track of a list “previous_l”.

if toss == 0 and k+2 < size*3:
  output_grid[w,k+1] = ' '
  output_grid[w,k+2] = ' '
  previous_l.append(j)
if toss == 1:
  # it's impossible to carve outside after preprocessing
  # look back, choose a random cell
  if grid[i,j-1] == 0:
    # reaching from 0
    # mandatory to be sure that previous_l has at least one element
    # if coming from a list of previous cells, choose one and...
    r = rd.choice(previous_l)
    k = r * 3 + 1
  # ...just carve north
  # just carve north also if this is the 1st of the row (1 element loop)
  output_grid[w-1,k] = ' '
  output_grid[w-2,k] = ' '
  # and clear the list for this run
  previous_l = []

If the coin is a tails, we just carve east and append this cell to the list of the previous visited cell for this run; if the coin is a heads, we look back at the visited cells, choose randomly one of those and carve north. Since we closed a loop, we clear the list of visited cells.

Note that:

• if we are on the first row of the grid, it’s useless to check for current row index because we will surely carve east as a result of preprocessing the grid. 😉
• if this is the first column of the row, then we are just closing the run on the current cell (in this case, the previous_l list is empty and it would be impossible to choose among a previously visited cell).

Running the script gives the following result:

A maze generated with the sidewinder algorithm

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