BestMordaEver 27 дек 2016 в 10:03

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

3 мин

22K

Алгоритмы*

Из песочницы

Комментарии 23

impwx 27 дек 2016 в 10:09

А покажете картинку с примером сгенерированного лабиринта?

+12

VaalKIA 27 дек 2016 в 15:14

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

BestMordaEver 8 янв 2017 в 19:32

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

НЛО прилетело и опубликовало эту надпись здесь

Germanets 27 дек 2016 в 13:24

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

LoadRunner 27 дек 2016 в 14:22

Что мешает делать рандомный выбор из незанятых координат?

-1

Germanets 27 дек 2016 в 14:39

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

VaalKIA 27 дек 2016 в 15:21

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

Germanets 27 дек 2016 в 16:25

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

VaalKIA 27 дек 2016 в 19:04

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

BestMordaEver 8 янв 2017 в 19:58

Бедствие? Это просто катастрофа! А если хотите статистику, то 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. Вот так вот.

norlin 27 дек 2016 в 11:00

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

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

norlin 27 дек 2016 в 11:16

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

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

LoadRunner 27 дек 2016 в 12:04

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

-4

norlin 27 дек 2016 в 12:24

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

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

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

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

myxo 27 дек 2016 в 12:45

В статью, конечно, нужен код и примеры, примеры и ещё раз примеры. Поэтому за статью минус. Но не спускайте автору карму, пусть он хоть отвечает.

-1

pda0 27 дек 2016 в 12:46

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

Видать очень старым. 5.5 не судьба была взять хотя бы? Про 7.0 вообще молчу. Про Free Pascal с его текстовой средой, имитирующей семёрку, наверное лучше даже не упоминать. :)

НЛО прилетело и опубликовало эту надпись здесь

pda0 27 дек 2016 в 13:38

Компиляция в exe доступна с версии 4.0, вышедшей в 1987 году. У нас из ранних версий была наиболее распространена версия 5.5 1989 года, для который был выполнен полный перевод не только меню среды, но и справки.

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

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

BestMordaEver 8 янв 2017 в 20:11

Таки на семерке. Но, для понимания, я в ходе работы использовал тип array[1..10, 1..10, 1..21, 1..21] of record a,b,c:byte (если кратко). А это 10*10*21*21*3=132300 байт. Почему — потому, что было надо. Не осуждайте меня.

pda0 8 янв 2017 в 20:49

Долго думал, пока не дошло. У вас там опечатка, не 64-килобайтным, а 640-килобайтым? 64k предел это если бы вы в com-файл компилировали.
Кстати, вы плохо знали возможности своего паскаля. Седьмая версия могла свободно делать exe, работающие в защищённом режиме 286-го процессора. Там вы получали в своё распоряжение до 16 мегабайт памяти. И DOSBox, разумеется, должен это поддерживать.

JTG 8 янв 2017 в 20:15

Пост будет неполным без

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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Показать лучшие за всё время

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

Комментарии 23

Публикации

Истории