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


def get_adjacent_visited(visited, cell):
    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
                
            adjacent = get_adjacent_visited(visited, (i, j))
            if len(adjacent) == 0:
                continue
                    
            new_cell = random.choice(adjacent)
            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)

        link_cells(grid, current_cell, new_cell)

        visited[new_cell] = True
        unvisited_count -= 1

        current_cell = new_cell

    draw_maze(grid)


generate_maze()