Использование алгоритма Hunt&Kill для создания клеточного лабиринта / Хабр

Сложно представить игры-головоломки без лабиринтов, которые так увлекательно разгадывать. Для создания лабиринтов существует большое множество различных алгоритмов на вкус и цвет. Одним из них является Hunt&Kill, о котором я и расскажу в этой статье.

Постановка задачи

Необходимо создать идеальный клеточный лабиринт размером на

Идеальный лабиринт - это лабиринт

без петель или замкнутых цепей и без недостижимых областей
в котором из каждой точки существует ровно один путь к любой другой точке
нет стенок, которые можно убрать и лабиринт останется идеальным.

Суть алгоритма для стеночных лабиринтов

Алгоритм Hunt&Kill (Охота и Убийство) работает по принципу чередования двух фаз.

Выбираем случайную клетку и помечаем её как посещённую.
Фаза Kill (Убийство): Выбираем случайного непосещенного соседа текущей клетки. Разрушаем стену между ними, переходим в новую клетку и помечаем её как посещённую. Повторяем, пока не зайдём в тупик.
Фаза Hunt (Охота): Если текущая клетка - тупик, начинаем сканировать поле любым известным способом. Ищем непосещённую клетку, у которой есть хотя бы один посещенный сосед.
Если такая клетка найдена, разрушаем стену между ней и её посещенным соседом. Эта клетка становится новой "текущей", и мы возвращаемся в фазу Kill.
Алгоритм заканчивается, когда фаза Hunt просканировала всё поле и не нашла новых подходящих клеток.

Рассмотрим для примера стеночный лабиринт с размером 5 на 5.

Начнём со случайной клетки (пусть будет самая левая нижняя клетка). Будем случайным образом выбирать следующих соседей, пока не попадём в тупик.

Теперь запу��кается фаза Hunt, алгоритм найдёт следующую непосещённую клетку, у которой есть посещённый сосед.

С новой клетки опять запустится фаза Kill.

Этот цикл будет повторяться до тех пор, пока алгоритм не сможет найти нужную клетку в фазе Hunt

Переход к клеточному лабиринту

Фундаментальное отличие клеточного лабиринта от стеночного заключается в том, что вместо стенок между клетками, перегородками служат сами клетки, которые помечены в качестве стенок.

В чём сложность?

Если просто закрашивать клетки, мы получим сплошные пустые пространства. Чтобы гарантированно иметь достаточно места для стен, проходы должны находиться на нечетных координатах, а стены - на четных.

Алгоритм адаптации:

Размер сетки должен быть нечетным:.
Шаг перемещения в фазе Kill равен 2 клеткам.
При переходе из в мы должны сделать "пустыми" (проходимыми) три клетки: текущую, целевую и промежуточную стену .

Логика фазы Hunt в клеточном мире:

Теперь сканирование идет только по клеткам с нечетными координатами . Мы ищем клетку , которая еще является "стеной", но на расстоянии 2 клеток от которой есть "пустая" клетка. Соединяем их, убирая промежуточную стену.

В чём проблема?

Наша адаптация берёт за данность, что лабиринт имеет нечётные размеры. Поскольку на чётных клетках всегда будут стоять стенки, самые дальние ряды в лабиринтах с чётными размерами всегда будут полностью покрыты стенами. Это противоречит третьему условию идеального лабиринта.

Для решения этой проблемы, можно использовать крайне примитивный подход: делать проходом каждую нечётную клетку на самых дальних рядах.

Реализация

import random

h, w = map(int, input().split())

maze = [[1 for _ in range(w)] for _ in range(h)]

dirs = [(0, 2), (0, -2), (2, 0), (-2, 0)]

cx, cy = random.randrange(0, w, 2), random.randrange(0, h, 2)
maze[cy][cx] = 0

while True:
    # KILL PHASE
    while True:
        unvisited = []
        for dx, dy in dirs:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] == 1:
                unvisited.append((nx, ny))

        if unvisited:
            nx, ny = random.choice(unvisited)
            maze[cy + (ny - cy) // 2][cx + (nx - cx) // 2] = 0
            maze[ny][nx] = 0
            cx, cy = nx, ny
        else:
            break


    # HUNT PHASE
    found = False
    for y in range(0, h, 2):
        for x in range(0, w, 2):
            if maze[y][x] == 1:
                visited_neighbors = []
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] == 0:
                        visited_neighbors.append((nx, ny))

                if visited_neighbors:
                    nx, ny = random.choice(visited_neighbors)
                    maze[y + (ny - y) // 2][x + (nx - x) // 2] = 0
                    maze[y][x] = 0
                    cx, cy = x, y
                    found = True
                    break
            if found: break
        if found: break

    if not found:
        break

# Заполнить крайние линии, если лабиринт имеет чётные размеры.
if w % 2 == 0:
    for y in range(0, h, 2):
        maze[y][w-1] = 0

if h % 2 == 0:
    for x in range(0, w, 2):
        maze[h-1][x] = 0

for row in maze:
    print("".join(map(str, row))) # 1 - стена, 0 - проход

Сравнение и особенности

Алгоритм	Характер лабиринта (Текстура)	Главное преимущество
Hunt&Kill	Длинные извилистые коридоры, мало тупиков.	Не требует стека, высокая "человечность" путей.
Recursive Backtracker	Очень длинные, предсказуемые коридоры.	Самый быстрый и простой в реализации.
Prim's Algorithm	Множество коротких тупиков, "пушистая" структура.	Выглядит натурально, можно сравнить с ростом плесени
Kruskal's Algorithm	Равномерное распределение коротких и длинных путей.	Позволяет создавать лабиринты любой формы (графы).

Таким образом, Hunt&Kill является отличным алгоритмом в условиях сжатого количества памяти из-за отсутствия какого-либо стека.

Источники

Jamis, Buck Mazes For Programmers: Code Your Own Twisty Little Passages / Buck Jamis. — : The Pragmatic Programmers, 2015. — 266 с. — Текст : непосредственный.
Jamis, Buck The Hunt-and-Kill algorithm / Buck Jamis. — Текст : электронный — URL: https://weblog.jamisbuck.org/2011/1/24/maze-generation-hunt-and-kill-algorithm (дата обращения: 25.02.2026).

Использование алгоритма Hunt&Kill для создания клеточного лабиринта

Оглавление