1. Введение

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

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

В этом посте мы увидим, как реализовать алгоритм на Python, и воспользуемся библиотекой OpenCV, чтобы нарисовать лабиринт. Вот пример окончательного вывода:

2. Объяснение

Возможно, вы слышали о рекурсивном поиске с возвратом как об алгоритме решения лабиринтов или, в более общем смысле, поиска путей в графе. Основная идея очень проста. На самом деле, это может быть что-то, что вы подсознательно делаете для простых лабиринтов. Идите по пути и продолжайте идти, пока не упретесь в тупик. Затем повторяйте свой путь, пока не дойдете до точки, где вы сможете снова начать выбирать пути. Делайте это, пока не доберетесь до места назначения.

Теперь вы можете задаться вопросом, как алгоритм, который решает лабиринты, может также создавать их. Это очень просто. Вместо того, чтобы стены были ячейками, которые определяют, что такое тупик, мы используем ранее посещенные ячейки. Что такое клетка? Вместо того, чтобы быть в лабиринте, представьте, что мы сейчас в сетке. пространство между стенами теперь является клеткой. Кроме того, по мере продвижения по лабиринту мы будем «сломать» эти стены и отмечать каждую посещаемую нами ячейку.

Все это становится проще, если мы перечислим шаги алгоритма:

  1. Выберите случайную ячейку для начала.
  2. Выберите случайную соседнюю ячейку. Создавайте проход только в том случае, если эта ячейка еще не была посещена.
  3. Повторяйте процесс до тех пор, пока не останется соседних ячеек для выбора.
  4. Начните возвращаться назад, пока не сможете снова выбрать ячейку.
  5. Алгоритм выполняется, когда вы возвращаетесь в исходную ячейку.

Вот GIF, показывающий, как алгоритм вырезает проходы и создает лабиринт. Белые ячейки представляют собой непосещенные ячейки, черные ячейки представляют собой стены, а серые ячейки представляют посещенные ячейки.

После всего сказанного давайте приступим к работе над реальным кодом и создадим алгоритм самостоятельно.

3. Настройка

Настройка для этого проекта очень проста. Язык, который мы будем использовать, — Python. Для этого проекта требуется несколько внешних библиотек:

Нампи

Numpy — очень быстрая библиотека Python, используемая для работы с многомерными массивами. Если вы еще не заметили, наш лабиринт — это просто двумерный массив. Чтобы установить Numpy, выполните следующую команду:

pip install numpy

OpenCV

OpenCV — это библиотека, предназначенная в основном для компьютерного зрения и обработки изображений. Поскольку у него очень красивые пиксельные рисунки, мы можем использовать его для нашего проекта. Чтобы установить OpenCV, выполните следующую команду:

pip install opencv-python

4. Код

Мы начинаем с импорта библиотек в наш код Python.

Мы можем проверить правильность импорта OpenCV, добавив следующее в начало нашего кода:

Если библиотека установлена ​​правильно, вы должны получить номер версии OpenCV, который вы используете.

Когда все библиотеки настроены, мы можем перейти к реализации алгоритма. Один из способов сделать это — поместить наш алгоритм внутрь функции и просто вызывать эту функцию всякий раз, когда она нам нужна. Это работает, но по мере того, как проект становится больше и мы вводим больше алгоритмов и функций, управление всеми этими функциями может стать проблемой. Вместо этого мы инкапсулируем наш алгоритм внутри класса. Затем эти классы содержат функции, отвечающие за создание лабиринта.

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

Теперь мы готовы построить нашу сетку. Мы хотим, чтобы края нашей сетки были стенами. В конце концов, какой лабиринт не имеет внешних стен? Затем, как и в обычной сетке, мы будем чередовать ячейки и стены как по горизонтали, так и по вертикали. Мы поместим этот код в функцию с именем create_maze(), так как она также даст нам окончательную версию лабиринта.

В первой строке после замедления функции мы используем numpy для создания 2d-массива. На данный момент этот массив является сеткой, но позже он превратится в лабиринт, отсюда и название. Размер этого массива равен высоте и ширине, и мы заполним его значением 1. 1 в оттенках серого представляет белый цвет, который мы используем для обозначения непосещенных ячеек.

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

Здесь зоркий глаз может заметить проблему. Что, если наш алгоритм окажется на одной из непосещенных ячеек на краю? Затем, изучая свое окружение, он может попытаться проверить за пределами массива. Мы можем обрабатывать каждый край и угол по отдельности, но мы также можем применить хитрость. Добавьте внешний слой в лабиринт и сделайте каждое место на этом внешнем слое посещаемым узлом. Таким образом, алгоритм может проверять места, которые действительно находятся за пределами лабиринта, но все же находятся в массиве, а так как они помечены заранее, он никогда не будет пытаться пройти в эти ячейки. Это сэкономит нам немало накладных расходов.

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

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

Когда наша сетка готова, пришло время реализовать сам алгоритм. Помните, что алгоритм является рекурсивным, то есть он будет вызывать сам себя. В результате мы помещаем его в свою собственную функцию. Я собираюсь вызвать этот генератор функций и поместить его в класс Backtracking. Для функции требуется 3 входа: текущее местоположение x и y, в котором она находится, и сетка, в которой она находится.

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

Сначала может показаться немного запутанным, почему у нас есть grid[cy, cx], а не grid[cx, cy]. Это связано с тем, как numpy определяет свои оси. Ось 0 — это строки массива, а значит, это высота. Ось 1 — это столбцы массива, что означает ширину.

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

Вот где enum пригодится. Мы можем представить каждое направление числом, но помнить, какое число больше, а какое меньше, неоптимально. Вместо этого мы будем использовать перечисления. Вне класса Backtracking объявите перечисление направлений:

Передача класса Enum в качестве параметра означает, что Directions будет наследоваться от Enum и, следовательно, тоже будет перечислением. Обратите внимание, что вы можете создать перечисление (или просто константы) для цветов в нашей сетке. Здесь я этого не делал, так как таким образом немного сложнее увидеть связь между числами и оттенками серого, но это просто личное предпочтение.

Теперь мы готовы случайным образом выбрать направление.

После else мы случайным образом выбираем из него один элемент и получаем несколько значений, соответствующих этому направлению. Например, если мы движемся вверх, то новая пустая ячейка, к которой нужно перейти, расположена на 2 единицы выше (cy), а стена, через которую нужно прорезаться, находится на 1 единицу выше (my). Поскольку мы движемся вверх, нам не нужно менять значения x. Обратите внимание, что оператор else никогда не должен выполняться, поскольку в этот момент всегда есть 1 непосещенная соседняя ячейка, но я оставил ее там.

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

Взгляните на оператор while. Скажем, в ячейке у нас есть два пути: вниз и влево. Случайно мы начинаем двигаться к нижней части лабиринта. Затем мы начинаем заходить в тупики и возвращаемся к исходной ячейке. Теперь, когда у нас есть этот оператор while, у нас есть еще 3 направления для проверки, только одно из них не посещено. Поэтому на этот раз мы пойдем к левой стороне лабиринта. Теперь вы можете видеть, как проверяются все возможные направления.

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

Вернувшись в нашу функцию create_maze(), мы должны вызвать нашу функцию-генератор. Чтобы сделать функцию еще более случайной, мы случайным образом выбираем начальные точки. Убедитесь, что начальная позиция — это непосещенная ячейка, а не стена или часть внешнего слоя лабиринта.

Теперь лабиринт будет содержать… лабиринт. Просто теперь все, что не является стеной, окрашено в серый цвет, поэтому мы просто пройдемся по лабиринту и изменим цвет обратно на белый.

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

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

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

Вы можете посмотреть окончательный код на GitHub.

5. Производительность

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

Подсчет чисел покажет вам, что средняя временная сложность алгоритма равна Θ(h × w), где h — высота лабиринта, а w — ширина.

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

6. Заключительные заметки

Рекурсивный возврат — лишь один из многих алгоритмов, используемых для создания лабиринтов. Его довольно легко понять и использовать на большинстве языков программирования. Он также использует одну из самых важных концепций информатики, а именно рекурсию. Кроме того, лабиринты, которые он создает, действительно выглядят случайными. Хотя для больших лабиринтов он будет медленным и будет потреблять большой объем памяти, он прекрасно работает с лабиринтами малого и среднего размера.

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