Неприлично простой алгоритм генерации лабиринтов

Простенький алгоритм генерации идеальных лабиринтов в самом обычном двухмерном пространстве. Nuff said, остальное под катом.

Поиск и разочарование


Начну без лишних подробностей и прелюдий — мне в ходе моей студенческой жизнедеятельности понадобился алгоритм генерации прямоугольного лабиринта. С молитвой на грешных устах я с головой погрузился в бесконечные недра гугла и накопал вот эту статью. Алгоритм был прост и понятен, он давал необходимые мне идеальные, не цикличные лабиринты (из любой точки лабиринта можно попасть в любую другую его точку, причем только одним путем), но из-за своих скудных на тот момент познаний в программировании, я затянул полноценную реализацию на полгода. Так получилось. И, откровенно говоря, разочаровался в результате. Алгоритм выдавал более-менее интересные лабиринты при размерности меньше 20, однако где-то с этого рубежа начались проблемы.

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

2. Потребление памяти
Алгоритм я писал на старом добром Pascal, который запускал через эмулятор DOSBox. Это ограничивало мою оперативную память 64-килобайтным обрубком. Поскольку лабиринт я хранил в массиве структур, которые включали в себя три байтовых переменных, то создание лабиринта размерностью больше 150х150 без привлечения динамической памяти было проблемным.

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

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

Идея и реализация


Итак, мне нужен был идеальный и не цикличный лабиринт. Предыдущий алгоритм подразумевал возведение стен в пустом помещении, поэтому я решил пойти другим путем, а именно — прокапывать дороги в сплошном грунте. Делать это будет небольшая «землеройка», которая будет для нас оставаться двухмерными координатами. Но какой алгоритм будет руководить движениями «землеройки»? Никакой! «Землеройку» по нашему необъятному подземелью будет гонять Великий Корейский Рандом.

Собственно, алгоритм


Обозначим 1 как проход и 0 как стену. Начальные условия — двухмерный массив, заполненный нолями. Размерность массива — любые нечетные числа. Считаем что левый верхний угол стены имеет координаты (1;1). Координаты «землеройки» всегда четные, передвигается она, соответственно, только прыжками длинной в два элемента массива.

  1. Случайным образом выбираем точку приземления «землеройки» — генерируем случайные ненулевые координаты. Точке приземления присваивается значение 1.
  2. Случайно выбираем одно из направлений — верх, низ, лево, право.
  3. Если после прыжка в выбранном направлении мы окажемся во внешней стене или в проходе, то вернуться к предыдущему пункту. Иначе — прыгаем в указанном направлении. Присваиваем значение 1 клетке, в которую приземлились и через которую перепрыгнули.
  4. Если после приземления мы не можем совершить прыжок (попадание в тупик), то мы случайным образом генерируем координаты. Иначе — переходим ко второму пункту.
  5. Повторяем пункт выше до тех пор, пока в указанных координатах не будет проход.

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

Преимущества:

  • простота в реализации
  • работает с двумя состояниями ячейки
  • простые входящие и исходящие данные
  • работает без ошибок при любых размерах лабиринта

Недостатки:

  • простые по структуре лабиринты

На этом все. Надеюсь, что пригодится хоть кому-нибудь.

UPD

Было бы логично приложить сюда иллюстрацию, поэтому вот. Размеры лабиринта — 320х240

image
Share post

Comments 23

    +12
    А покажете картинку с примером сгенерированного лабиринта?
      0
      По своему опыту создания лабиринтов: процесс взрывного роста гораздо интересней, поэтому лучше смотреть в динамике.
        0
        Наслаждайтесь
        Это первая реализация (читай, первая программа вне академических заданий), поэтому есть пара косяков и артефакты в виде прямых отростков по границам лабиринта.
      +1
      >Если после приземления мы не можем совершить прыжок (попадание в тупик), то мы случайным образом генерируем координаты.
      Не нравится мне этот пункт. У вас есть рабочий код? Замерьте, пожалуйста (хохмы ради не более того), как часто этот пункт приходится выполнять и как часто его приходится выполнять раз за разом. Ну т.е. после рандомного прыжка попадаем снова в тупиковое положение. Я в уме не могу прикинуть масштаб бедствия, но что-то мне подсказывает, что этот пункт нужно заменить на что-то более целенаправленное, чем рандомные прыжки.
        0
        Например вместо рандомных прыжков бежать слева направо сверху вниз до тех пор, пока не получим валидную координату для прыжка. Но не угробит ли это красивость лабиринта? Поэкспериментируйте.
          0
          Самое печальное в рандоме то, что чем меньше остаётся незанятого лабиринтом места на выбранной площади, тем чаще мы раз за разом совершаем прыжки. В конце концов всё сведётся к тому, что 99% попыток будут давать уже занятые участки и будут по сути бесполезными в решении задачи — построении лабиринта.
            –1
            Что мешает делать рандомный выбор из незанятых координат?
              0
              Ничего не мешает, но вот приведённый в статье алгоритм это не учитывает, как я понимаю — сначала выбирается случайная ячейка и направление, а потом только идёт проверка — а можно ли так вообще делать.
              0
              Похожим способом лабиринт и создавался и у меня, да замедляется, где-то до 10 секунд последние элементы дорисовывались, на очень старом компьютере. Но заканчивался всегда.
                0
                Да закончиться-то он когда-нибудь должен(если компьютер до этого момента доработает), тут вопросы только к тому, когда генератор псевдослучайных чисел всё-таки доберётся до последней непройденной пары координат, а это уже сильно зависит от размера поля, скорости выбора\проверки ячейки, ну и от везения)
                  0
                  Я поэтому и поделился статистикой, но проверить очень просто самостоятельно, сделайте SetPixel по рандомным координатам на экране, и подождите пока он будет полностью закрашен — это будет просто гигантский лабиринт, потому что в реальных, расстояние между стенками не ноль, а хотя бы 1 пиксель, а это почти в два раза меньше по координатам и в 4 по площади.
              0
              Бедствие? Это просто катастрофа! А если хотите статистику, то 20 лабиринтов размерностью 111х59 (6549 ячеек) на С++ сгенерировались за полсекунды. В каждом из них было сделано 11008 12167 11306 11667 10996 11386 11482 11918 11827 11640 12172 11359 11407 11752 11435 11270 11468 11370 11473 11278 скачков в случайную точку, среднее арифметическое — 11519.05. Вот так вот.
              +4

              Вот есть пара сайтов с огромной подборкой алгоритмов лабиринтов:
              Здесь разбор особенностей различных алгоритмов.
              А здесь непосредственная реализация с примерами (см. записи от Dec 2010 и выше).


              Нагуглил их, когда искал алгоритмы для создания "бесконечных" лабиринтов для игры. В итоге остановился на алгоритме Эллера (даже на Хабре есть) – он позволяет генерировать новую строку лабиринта лишь на основании предыдущей строки. А всё, что было раньше, роли не играет и не требует хранения в памяти.

                0

                p.s. только сейчас осознал, что в статье изначально как раз и говорится об алгоритме Эллера, хе-хе.


                Но не очень тогда понимаю, о каких проблемах с размерностью идёт речь, если этот алгоритм не зависит от размерности вообще...

                  –4
                  Вы статью хотя бы читали? Автор аж три пункта выделил болдом. Он же частный случай описывает, а не общий универсальный.
                    +2

                    Судя по выделенным пунктам, автор как-то не так реализовал алгоритм. Например, проблемы с памятью – о чём вообще речь, если для генерации необходимо хранить только две строки? А автор пишет:


                    создание лабиринта размерностью больше 150х150 без привлечения динамической памяти было проблемным

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


                    Например, в приведённых мной ссылках, алгоритм Эллера наоборот назван одним из наиболее эффективных в плане потребления памяти.

                –1
                В статью, конечно, нужен код и примеры, примеры и ещё раз примеры. Поэтому за статью минус. Но не спускайте автору карму, пусть он хоть отвечает.
                  0
                  Алгоритм я писал на старом добром Pascal, который запускал через эмулятор DOSBox. Это ограничивало мою оперативную память 64-килобайтным обрубком.


                  Видать очень старым. 5.5 не судьба была взять хотя бы? Про 7.0 вообще молчу. Про Free Pascal с его текстовой средой, имитирующей семёрку, наверное лучше даже не упоминать. :)
                    +1
                    Автор, скорее всего, студент. И во что его преподаватель ткнул носом, тем и пришлось пользоваться.
                      0
                      Компиляция в exe доступна с версии 4.0, вышедшей в 1987 году. У нас из ранних версий была наиболее распространена версия 5.5 1989 года, для который был выполнен полный перевод не только меню среды, но и справки.

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

                      Ну а вам спасибо за то, что отважно ринулись защищать другого и выносите вердикты на основании своих предположений.
                      0
                      Таки на семерке. Но, для понимания, я в ходе работы использовал тип array[1..10, 1..10, 1..21, 1..21] of record a,b,c:byte (если кратко). А это 10*10*21*21*3=132300 байт. Почему — потому, что было надо. Не осуждайте меня.
                        0
                        Долго думал, пока не дошло. У вас там опечатка, не 64-килобайтным, а 640-килобайтым? 64k предел это если бы вы в com-файл компилировали.
                        Кстати, вы плохо знали возможности своего паскаля. Седьмая версия могла свободно делать exe, работающие в защищённом режиме 286-го процессора. Там вы получали в своё распоряжение до 16 мегабайт памяти. И DOSBox, разумеется, должен это поддерживать.
                      0
                      Пост будет неполным без

                      10 PRINT CHR$(205.5+RND(1));: GOTO 10
                      


                      Only users with full accounts can post comments. Log in, please.