# Maze generation with the recursive backtracking algorithm

## Prerequisites

### Maze generation with the recursive backtracking algorithm

#### Introduction

• The backtracking algorithm is similar to the hunt and kill algorithm.
• However when hitting a dead-end:
• It backtracks through its path until it finds an adjacent cell that hasn't been visited
• The path then continues with the unvisited cell
• The algorithm is complete when the current cell goes back to its starting location.

#### Demo

• The red dot represents the current cell.

#### Code (Python)

``````import numpy as np
import random
from maze_functions import *

def possible_moves(visited: np.array, cell: (int, int)):
moves = []

for direction in [north, south, east, west]:
new_cell = direction(cell)

# check the cell is in the bounds
if not 0 <= new_cell[0] < visited.shape[0]:
continue
if not 0 <= new_cell[1] < visited.shape[1]:
continue

if visited[new_cell]:
continue

moves.append(new_cell)

return moves

def backtrack(visited: np.array, path: [(int, int)]):
path.pop()
while len(path) > 0:
last = path[-1]
moves = possible_moves(visited, last)

if len(moves) > 0:
new_cell = random.choice(moves)
return last, new_cell
else:
path.pop()

return None

def generate_maze():
width = 10
height = 10
grid = np.zeros((width, height, 2), bool)

# set the current cell to a random value
current_cell = (random.randint(0, width - 1), random.randint(0, height - 1))
path = [current_cell]

# a grid to track if the cell has been visited
visited = np.zeros((width, height), bool)
unvisited_count = width * height

visited[current_cell] = True
unvisited_count -= 1

while unvisited_count > 0:
moves = possible_moves(visited, current_cell)

if len(moves) > 0:
new_cell = random.choice(moves)
else:
current_cell, new_cell = backtrack(visited, path)

path.append(new_cell)

visited[new_cell] = True
unvisited_count -= 1

current_cell = new_cell

draw_maze(grid)

generate_maze()``````

#### Notes

• This algorithm uses a list called path as its stack.
• However you can use recursion instead and use the programs built in call stack.
• This recursive method gives the algorithm its name.