# Maze generation with the sidewinder algorithm

## Prerequisites

### 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.