Алгоритмы для создания лабиринтов

Это обзор алгоритмов, рассматриваемых в книге Mazes for Programmers.
Мой код алгоритмов на языке Ruby можно найти на Github.

Простые алгоритмы

Binary Tree

Для каждой ячейки сетки по очереди (с юга на север и с запада на восток) строится путь в соседнюю ячейку восточнее или севернее.

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

Sidewinder

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

Получается вертикальная структура с коридором в северной строке.

Алгоритмы для максимально случайных лабиринтов

Aldous-Broder

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

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

Wilson’s

Выбираем произвольную ячейку и добавляем её в лабиринт. Потом из любой другой ячейки строим случайный путь. Когда путь упирается в ячейку, уже добавленную в лабиринт, весь путь добавляется в лабиринт. Создаём такие случайные пути пока все ячейки не окажутся в лабиринте.

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

Алгоритмы для лабиринтов с длинными путями

Hunt-and-Kill

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

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

Recursive Backtracker

Из произвольно выбранной ячейки начинаем строить путь, избегая ранее посещённые ячейки. Когда двигаться некуда, нужно вернуться к предыдущей посещённой ячейке и продолжить строить путь оттуда. Алгоритм завершается, когда мы возвращаемся к той ячейке, с которой начали.

В результате получаются длинные и извилистые пути с небольшим количеством тупиков. Этот алгоритм похож на Hunt-and-Kill, но потенциально работает быстрее, потому что проверяет каждую ячейку только два раза. Хотя ему нужно больше памяти, чтобы следить за уже посещёнными ячейками.

Дополнительные алгоритмы

Kruskal’s

Начинается с добавления каждой ячейки в отдельное множество. Потом случайным образом соединяются соседние ячейки, если они принадлежат разным множествам. Таким образом множества объединяются, пока не останется только одно.

В результате получаются очень аккуратные и регулярные лабиринты.

Prim’s (упрощённый)

Создаётся множество с произвольной ячейкой. Каждый раз из этого множества выбирается случайная ячейка. Если у неё нет непосещённых соседей, то она удаляется из множества. Иначе выбирается любой непосещённый сосед, ячейки соединяются, выбранный сосед добавляется в множество. Продолжаем, пока множество не станет пустым.

Отличается радиальной структурой вокруг начальной ячейки. Обычно создаются больше тупиков и получаются более короткие пути.

Prim's (настоящий)

Сначала каждой ячейке назначается случайный вес, затем создаётся множество со случайной ячейкой. На каждом шаге из множества выбирается ячейка наибольшего веса. Ячейка удаляется, если у неё нет непосещённых соседей. Иначе она соединяется с любым из соседей, а этот сосед добавляется в множество. Продолжаем, пока в множестве есть ячейки.

Очень много тупиков с довольно короткими путями. По текстуре оказывается похож на пазл.

Growing Tree

Это обобщение алгоритма Прима (Prim's). Из сетки выбирается произвольная ячейка и добавляется в некоторое множество. Потом из множества выбирается любая ячейка (сначала она там одна, потом будет много). Если у выбранной ячейки нет непосещённых соседей, то она удаляется из множества. Иначе ячейка соединяется с любым из непосещённых соседей, этот сосед добавляется в множество. Шаги повторяются, пока в множестве остаются ячейки.

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

Eller's

Каждая строка сетки обходится последовательно (например, с севера на юг), образовывая отдельные множества ячеек. Для каждого такого множества прокладывается путь на юг в одну из смежных ячеек, эта ячейка становится частью этого множества. В последней строке расположенные рядом множества объединяются.

Последняя строка обычно имеет меньше стен, потому что в ней происходит объединение множеств.

Recursive Division

Это обратный алгоритм. Начинаем с сеткой без стен между ячейками. Делим сетку на две части стеной, добавляя проход в случайном месте. Повторяем такое разделение до тех пор, пока не останется пустых пространств.

В результате получается прямоугольная коробочная структура. Решение обычно легче находить через поиск узких горлышек — переходом между большими областями. Одно из преимуществ: можно создавать большие пустые комнаты.