Классические алгоритмы генерации лабиринтов. Часть 2: погружение в случайность

[Lyosha12]

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

Очень интересно почитать действительно сложные вещи, жду следующей статьи, спасибо.

[RussDragon]

Ну, здесь и правда ничего сложного нет, если имеются базовые знания о графах. Иначе некоторые моменты могут быть неочевидны. Что-то по-настоящему сложное… Ну, может быть, при пересекающихся коридорах или полярных лабиринтах сложность будет повыше. На примитивном двухмерном пространстве всё тривиально при наличии опыта в программировании и немного в математике.

[Lyosha12]

Скажу даже больше: легко представляю алгоритмом Уилсона реализацию трёхмерного лабиринта, вопросы о котором часто встречал в публикациях здесь.

[RussDragon]

А его суть-то не меняется. Даже сам процесс удаления цикла не изменится.

[jimmyjonezz]

Здорово, очень здорово! Я как раз сегодня разбирался с next (table [, index]).
Возможно я хочу слишком многого, но было бы очень наглядно с презентацией работы алгоритмов в love2D. Я конечно, уже написал свою реализацию алгоритмов (кстати, это было очень занятно и интересно!), что были представлены в прошлой статье, но хотелось бы увидеть Вашу работу…

Спойлер

[RussDragon]

Могу скинуть весь исходный код для Лав2Д в ЛС. Или опубликую его позже, так как код рендера мне стыдно выкладывать.

[jimmyjonezz]

Не стесняйтесь, публикуйте! Либо GitHub, как вариант.

[RussDragon]

Нет-нет, сейчас на публику выкладывать слишком рано весь код. Я его рефакторю в процессе написания статей. А пока костылей там слишком много.

[Mingun]

Таким образом вы его никогда не выложите. Ну и что, что костыли? Все когда-то с них начинали, особенно, когда что-то пишется в процессе.

[RussDragon]

Залил исходники на гитхаб. Без рефакторинга вообще. Всё ещё не уверен в правильности сего действа :)
Исходники

[jimmyjonezz]

поздно блуждать в сомнениях… архив успешно скачан. =P

[slavenski]

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

Извините за мою придирчивость, но не могли бы исправить опечатку? :)

И насчет статьи — очень интересно! Продолжайте цикл статей, с удовольствием читаю перед началом рабочего дня!

[RussDragon]

Спасибо! К сожалению, не могу увидеть опечатку. Можете в ЛС мне написать?

[DrZlodberg]

Сейчас (немного по другому поводу) ковыряю DLA. На выходе получаются структуры, немного похожие на лабиринты. Думаю, если немного заточить их с этой стороны — можно немного получить похожий результат. Там тоже на выходе граф без колец. Похожий — потому что там не полное заполнение сетки. Но это можно исправить.
Офтоп: А куда вообще можно картинку выложить, чтобы прицепить к комменту?

[RussDragon]

Например сюда

[DrZlodberg]

Благодарю. Не знал, что так можно.

На выходе вот такое получается

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

[Aniko]

https://bost.ocks.org/mike/algorithms/ тут есть радел про лабиринты и еще много всего.

[RussDragon]

Сайт знаю, давно в закладках. Но лабиринты там далеко не главное, они скорее как еще один красивый вариант визуализации алгоритмов.

[Shultc]

Извините, поправьте меня, если я не прав. Мне кажется с первой картинкой в разделе «Смещение и случайность» что-то не так. Кажется на лабиринт просто наложили затемнение нижнего(второго) лабиринта, ибо затемнение во многих местах идёт не по стенкам… Или я всё неправильно понял?

[RussDragon]

Очень любопытный баг. Исправлю позже, спасибо.

[Shultc]

Фух, спасибо, вы меня успокоили! А то статье уже сутки, она набрала под 40 плюсов… Я был уверен, что было бы это багом, кто-нибудь заметил бы. Думал что я чего-то недопонял.

[Piter_Y]

Можно усовершенствовать алгоритм Олдоса-Бродера. Для того, что бы не было ненужного брожения по уже отрисованной части лабиринта, необходимо помещать «красный квадрат», случайным образом, в одно из полей из которых возможно продолжение прорисовки проходов. И случайным образом выбирать одно из возможных направлений проходов.

[RussDragon]

Можно. Вот только это будет уже совсем другой алгоритм с совершенно другим принципом работы :)
Поиск с возвратом, например. Или Hunt&Kill.

[Piter_Y]

А если для того, что бы сохранить название, просчитывать вероятность выхода «красного квадрата» за пределы размеченного в каждой возможной точке (чем дальше точка входа, тем меньше вероятность, что он выйдет в этом месте). Тогда и эффективность возрастет и лабиринты будут генерироваться похожие.

[RussDragon]

Я не спорю, что Олдос-Бродер можно сделать поумнее. Уилсон в пример. Но, если хотите и если наберется достаточно материала, аптшу отдельную статью по модернизированным/самописным алгоритмам.