Простенький алгоритм генерации идеальных лабиринтов в самом обычном двухмерном пространстве. Nuff said, остальное под катом.
Поиск и разочарование
Начну без лишних подробностей и прелюдий — мне в ходе моей студенческой жизнедеятельности понадобился алгоритм генерации прямоугольного лабиринта. С молитвой на грешных устах я с головой погрузился в бесконечные недра гугла и накопал вот эту статью. Алгоритм был прост и понятен, он давал необходимые мне идеальные, не цикличные лабиринты (из любой точки лабиринта можно попасть в любую другую его точку, причем только одним путем), но из-за своих скудных на тот момент познаний в программировании, я затянул полноценную реализацию на полгода. Так получилось. И, откровенно говоря, разочаровался в результате. Алгоритм выдавал более-менее интересные лабиринты при размерности меньше 20, однако где-то с этого рубежа начались проблемы.
1. Предсказуемость
Как я не пытался, попасть из левого верхнего угла лабиринта в правый верхний можно было только пройдясь по двум нижним уровням. Что давало некоторые возможности, вроде сделать их чем-то вроде широкого коридора, но мне это было не нужно.
2. Потребление памяти
Алгоритм я писал на старом добром Pascal, который запускал через эмулятор DOSBox. Это ограничивало мою оперативную память 64-килобайтным обрубком. Поскольку лабиринт я хранил в массиве структур, которые включали в себя три байтовых переменных, то создание лабиринта размерностью больше 150х150 без привлечения динамической памяти было проблемным.
3. Несовершенство алгоритма
Так уж получилось, что алгоритм рассматривал не все возможные варианты развития событий, что приводило к появлению различных нежелательных артефактов.
После осознания этих трех пунктов, я решил отказаться от этого алгоритма и создать свой.
Идея и реализация
Итак, мне нужен был идеальный и не цикличный лабиринт. Предыдущий алгоритм подразумевал возведение стен в пустом помещении, поэтому я решил пойти другим путем, а именно — прокапывать дороги в сплошном грунте. Делать это будет небольшая «землеройка», которая будет для нас оставаться двухмерными координатами. Но какой алгоритм будет руководить движениями «землеройки»? Никакой! «Землеройку» по нашему необъятному подземелью будет гонять Великий Корейский Рандом.
Собственно, алгоритм
Обозначим 1 как проход и 0 как стену. Начальные условия — двухмерный массив, заполненный нолями. Размерность массива — любые нечетные числа. Считаем что левый верхний угол стены имеет координаты (1;1). Координаты «землеройки» всегда четные, передвигается она, соответственно, только прыжками длинной в два элемента массива.
- Случайным образом выбираем точку приземления «землеройки» — генерируем случайные ненулевые координаты. Точке приземления присваивается значение 1.
- Случайно выбираем одно из направлений — верх, низ, лево, право.
- Если после прыжка в выбранном направлении мы окажемся во внешней стене или в проходе, то вернуться к предыдущему пункту. Иначе — прыгаем в указанном направлении. Присваиваем значение 1 клетке, в которую приземлились и через которую перепрыгнули.
- Если после приземления мы не можем совершить прыжок (попадание в тупик), то мы случайным образом генерируем координаты. Иначе — переходим ко второму пункту.
- Повторяем пункт выше до тех пор, пока в указанных координатах не будет проход.
Все до неприличности просто. Рано или поздно мы зациклимся в последних двух пунктах. Прерыванием для алгоритма может быть либо счетчик, либо простая проверка — если в каждой ячейке с четными координатами находится 1, то алгоритм можно смело прерывать.
Преимущества:
- простота в реализации
- работает с двумя состояниями ячейки
- простые входящие и исходящие данные
- работает без ошибок при любых размерах лабиринта
Недостатки:
- простые по структуре лабиринты
На этом все. Надеюсь, что пригодится хоть кому-нибудь.
Автор: BestMordaEver
