# Maze generation with the hunt and kill algorithm

## Prerequisites

### Maze generation with the hunt and kill algorithm

#### Introduction

• The hunt and kill algorithm is very similar to the Aldous-Broder algorithm.
• However the random walk is constrained so that it can only visit unvisited cells.
• Eventually the path will hit a dead end:
• I.e. none of the cells around it are unvisited.
• In this case we choose the first unvisited cell in the grid which has a visited cell next to it.
• We use this as the current cell.
• and link it to a cell next to it that has already been visited:
• If there are multiple visited cells to choose from then pick one at random

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

cells = []
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]:
cells.append(new_cell)

return cells

def hunt(visited):
for j in range(visited.shape[1]):
for i in range(visited.shape[0]):
if visited[(i, j)]:
continue

continue

return new_cell, (i, j)

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

# 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 = hunt(visited)