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):

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:

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:

Full-time Human-computer interpreter