Maze generation with the sidewinder algorithm

Introduction

• The sidewinder algorithm is an improvement on the binary tree algorithm in that it removes the long corridor of cells on the eastern wall.
  • Given a maze generated with a binary tree algorithm:
  • If we draw red lines for horizontal connections, and blue lines for vertical connections:
  • We see that the bottom edge of every blue line is connected to the right edge of a red line.
  • The sidewinder algorithm is similar, except the blue line can be connected at any point along the red line:

Code (Python)

import numpy as np
import random
from maze_functions import *

width = 5
height = 5
grid = np.zeros((width, height, 2), bool)

for j in range(height):
    runStart = 0

    for i in range(width):
        if i == width - 1 and j == height - 1:
            # top right cell
            # can't go east or north
            continue

        if j == height - 1:
            # top cell
            # can only go east
            goEast = True
        elif i == width - 1:
            # far right cell
            # can't go east
            goEast = False
        else:
            goEast = random.randint(0, 1) == 0

        if goEast:
            cell = (i, j)
            link_cells(grid, cell, east(cell))
            grid[i, j][EAST] = True
        else:
            cell = (random.randint(runStart, i), j)
            link_cells(grid, cell, north(cell))
            runStart = i + 1

draw_maze(grid)

Pros and Cons

• Pros:
  • Improvement on the binary tree algorithm:
    • Paths to the top right cell can go both east and west.
    • No corridor on the right edge.
  • O(n) time complexity
• Cons:
  • Top edge still has a corridor.
  • No paths to the top right cell can go downwards.