Поиск и разочарование
Начну без лишних подробностей и прелюдий — мне в ходе моей студенческой жизнедеятельности понадобился алгоритм генерации прямоугольного лабиринта. С молитвой на грешных устах я с головой погрузился в бесконечные недра гугла и накопал вот эту статью. Алгоритм был прост и понятен, он давал необходимые мне идеальные, не цикличные лабиринты (из любой точки лабиринта можно попасть в любую другую его точку, причем только одним путем), но из-за своих скудных на тот момент познаний в программировании, я затянул полноценную реализацию на полгода. Так получилось. И, откровенно говоря, разочаровался в результате. Алгоритм выдавал более-менее интересные лабиринты при размерности меньше 20, однако где-то с этого рубежа начались проблемы.
1. Предсказуемость
Как я не пытался, попасть из левого верхнего угла лабиринта в правый верхний можно было только пройдясь по двум нижним уровням. Что давало некоторые возможности, вроде сделать их чем-то вроде широкого коридора, но мне это было не нужно.
2. Потребление памяти
Алгоритм я писал на старом добром Pascal, который запускал через эмулятор DOSBox. Это ограничивало мою оперативную память 64-килобайтным обрубком. Поскольку лабиринт я хранил в массиве структур, которые включали в себя три байтовых переменных, то создание лабиринта размерностью больше 150х150 без привлечения динамической памяти было проблемным.
3. Несовершенство алгоритма
Так уж получилось, что алгоритм рассматривал не все возможные варианты развития событий, что приводило к появлению различных нежелательных артефактов.
После осознания этих трех пунктов, я решил отказаться от этого алгоритма и создать свой.
Идея и реализация
Итак, мне нужен был идеальный и не цикличный лабиринт. Предыдущий алгоритм подразумевал возведение стен в пустом помещении, поэтому я решил пойти другим путем, а именно — прокапывать дороги в сплошном грунте. Делать это будет небольшая «землеройка», которая будет для нас оставаться двухмерными координатами. Но какой алгоритм будет руководить движениями «землеройки»? Никакой! «Землеройку» по нашему необъятному подземелью будет гонять Великий Корейский Рандом.
Собственно, алгоритм
Обозначим 1 как проход и 0 как стену. Начальные условия — двухмерный массив, заполненный нолями. Размерность массива — любые нечетные числа. Считаем что левый верхний угол стены имеет координаты (1;1). Координаты «землеройки» всегда четные, передвигается она, соответственно, только прыжками длинной в два элемента массива.
- Случайным образом выбираем точку приземления «землеройки» — генерируем случайные ненулевые координаты. Точке приземления присваивается значение 1.
- Случайно выбираем одно из направлений — верх, низ, лево, право.
- Если после прыжка в выбранном направлении мы окажемся во внешней стене или в проходе, то вернуться к предыдущему пункту. Иначе — прыгаем в указанном направлении. Присваиваем значение 1 клетке, в которую приземлились и через которую перепрыгнули.
- Если после приземления мы не можем совершить прыжок (попадание в тупик), то мы случайным образом генерируем координаты. Иначе — переходим ко второму пункту.
- Повторяем пункт выше до тех пор, пока в указанных координатах не будет проход.
Все до неприличности просто. Рано или поздно мы зациклимся в последних двух пунктах. Прерыванием для алгоритма может быть либо счетчик, либо простая проверка — если в каждой ячейке с четными координатами находится 1, то алгоритм можно смело прерывать.
Преимущества:
- простота в реализации
- работает с двумя состояниями ячейки
- простые входящие и исходящие данные
- работает без ошибок при любых размерах лабиринта
Недостатки:
- простые по структуре лабиринты
На этом все. Надеюсь, что пригодится хоть кому-нибудь.
Комментарии (18)
A-Stahl
27.12.2016 10:22+1>Если после приземления мы не можем совершить прыжок (попадание в тупик), то мы случайным образом генерируем координаты.
Не нравится мне этот пункт. У вас есть рабочий код? Замерьте, пожалуйста (хохмы ради не более того), как часто этот пункт приходится выполнять и как часто его приходится выполнять раз за разом. Ну т.е. после рандомного прыжка попадаем снова в тупиковое положение. Я в уме не могу прикинуть масштаб бедствия, но что-то мне подсказывает, что этот пункт нужно заменить на что-то более целенаправленное, чем рандомные прыжки.A-Stahl
27.12.2016 10:24Например вместо рандомных прыжков бежать слева направо сверху вниз до тех пор, пока не получим валидную координату для прыжка. Но не угробит ли это красивость лабиринта? Поэкспериментируйте.
Germanets
27.12.2016 13:24Самое печальное в рандоме то, что чем меньше остаётся незанятого лабиринтом места на выбранной площади, тем чаще мы раз за разом совершаем прыжки. В конце концов всё сведётся к тому, что 99% попыток будут давать уже занятые участки и будут по сути бесполезными в решении задачи — построении лабиринта.
LoadRunner
27.12.2016 14:22-1Что мешает делать рандомный выбор из незанятых координат?
Germanets
27.12.2016 14:39Ничего не мешает, но вот приведённый в статье алгоритм это не учитывает, как я понимаю — сначала выбирается случайная ячейка и направление, а потом только идёт проверка — а можно ли так вообще делать.
VaalKIA
27.12.2016 15:21Похожим способом лабиринт и создавался и у меня, да замедляется, где-то до 10 секунд последние элементы дорисовывались, на очень старом компьютере. Но заканчивался всегда.
Germanets
27.12.2016 16:25Да закончиться-то он когда-нибудь должен(если компьютер до этого момента доработает), тут вопросы только к тому, когда генератор псевдослучайных чисел всё-таки доберётся до последней непройденной пары координат, а это уже сильно зависит от размера поля, скорости выбора\проверки ячейки, ну и от везения)
VaalKIA
27.12.2016 19:04Я поэтому и поделился статистикой, но проверить очень просто самостоятельно, сделайте SetPixel по рандомным координатам на экране, и подождите пока он будет полностью закрашен — это будет просто гигантский лабиринт, потому что в реальных, расстояние между стенками не ноль, а хотя бы 1 пиксель, а это почти в два раза меньше по координатам и в 4 по площади.
norlin
27.12.2016 11:00+4Вот есть пара сайтов с огромной подборкой алгоритмов лабиринтов:
Здесь разбор особенностей различных алгоритмов.
А здесь непосредственная реализация с примерами (см. записи от Dec 2010 и выше).
Нагуглил их, когда искал алгоритмы для создания "бесконечных" лабиринтов для игры. В итоге остановился на алгоритме Эллера (даже на Хабре есть) – он позволяет генерировать новую строку лабиринта лишь на основании предыдущей строки. А всё, что было раньше, роли не играет и не требует хранения в памяти.
norlin
27.12.2016 11:16p.s. только сейчас осознал, что в статье изначально как раз и говорится об алгоритме Эллера, хе-хе.
Но не очень тогда понимаю, о каких проблемах с размерностью идёт речь, если этот алгоритм не зависит от размерности вообще...
LoadRunner
27.12.2016 12:04-4Вы статью хотя бы читали? Автор аж три пункта выделил болдом. Он же частный случай описывает, а не общий универсальный.
norlin
27.12.2016 12:24+2Судя по выделенным пунктам, автор как-то не так реализовал алгоритм. Например, проблемы с памятью – о чём вообще речь, если для генерации необходимо хранить только две строки? А автор пишет:
создание лабиринта размерностью больше 150х150 без привлечения динамической памяти было проблемным
Ну тут либо любой алгоритм будет вызывать проблемы с памятью (чисто из-за того, что надо будет весь результат куда-то сохранять), либо что-то не так с реализацией.
Например, в приведённых мной ссылках, алгоритм Эллера наоборот назван одним из наиболее эффективных в плане потребления памяти.
myxo
27.12.2016 12:45-1В статью, конечно, нужен код и примеры, примеры и ещё раз примеры. Поэтому за статью минус. Но не спускайте автору карму, пусть он хоть отвечает.
pda0
27.12.2016 12:46Алгоритм я писал на старом добром Pascal, который запускал через эмулятор DOSBox. Это ограничивало мою оперативную память 64-килобайтным обрубком.
Видать очень старым. 5.5 не судьба была взять хотя бы? Про 7.0 вообще молчу. Про Free Pascal с его текстовой средой, имитирующей семёрку, наверное лучше даже не упоминать. :)A-Stahl
27.12.2016 12:56+1Автор, скорее всего, студент. И во что его преподаватель ткнул носом, тем и пришлось пользоваться.
pda0
27.12.2016 13:38Компиляция в exe доступна с версии 4.0, вышедшей в 1987 году. У нас из ранних версий была наиболее распространена версия 5.5 1989 года, для который был выполнен полный перевод не только меню среды, но и справки.
Можно конечно представить себе садиста, который последовательно мучает всех не только DOS компилятором, но и за 35 лет ни разу не удосужился посмотреть на новую версию среды.
Ну а вам спасибо за то, что отважно ринулись защищать другого и выносите вердикты на основании своих предположений.
impwx
А покажете картинку с примером сгенерированного лабиринта?
VaalKIA
По своему опыту создания лабиринтов: процесс взрывного роста гораздо интересней, поэтому лучше смотреть в динамике.