Comments 35
Очень хорошая статья!
Я бы не отказался от продолжения!
Интересны хорошие алгоритмы генерации карт с комнатами.
И карты с произвольными дорогами и областями(не квадратными), но доступными к прохождению из любого «ходимого» куска карты к любому.
Я бы не отказался от продолжения!
Интересны хорошие алгоритмы генерации карт с комнатами.
И карты с произвольными дорогами и областями(не квадратными), но доступными к прохождению из любого «ходимого» куска карты к любому.
Приятно слышать :)
Алгоритмы генерации помещений, боюсь, немного выходят за рамки цикла, но, при возможности, я с радостью о них напишу. Единственное, что подойдет для таких целей, я думаю, алгоритм рекурсивного деления, который при должной настройке способен создавать планы помещений.
Насчет карт с произвольными дорогами… Тут сложнее. Прежде, чем увлечься лабиринтами, я замышлял написать свой генератор процедурных городов, со всеми правилами строительства: выбором роста города и дорог (прямые дороги, радиальные, хаотичные...), выбором различных городских занятий (туристический город/промышленный), от которых бы зависели типы и размеры районов, и всё в таком духе. К сожалению, пока до реализации такого не дошло, но, может быть, ради Хабра что-нибудь да напишу.
Алгоритмы генерации помещений, боюсь, немного выходят за рамки цикла, но, при возможности, я с радостью о них напишу. Единственное, что подойдет для таких целей, я думаю, алгоритм рекурсивного деления, который при должной настройке способен создавать планы помещений.
Насчет карт с произвольными дорогами… Тут сложнее. Прежде, чем увлечься лабиринтами, я замышлял написать свой генератор процедурных городов, со всеми правилами строительства: выбором роста города и дорог (прямые дороги, радиальные, хаотичные...), выбором различных городских занятий (туристический город/промышленный), от которых бы зависели типы и размеры районов, и всё в таком духе. К сожалению, пока до реализации такого не дошло, но, может быть, ради Хабра что-нибудь да напишу.
Пример рекурсивного деления
По картам с комнатами была статья:.
Также видел алгоритмы по генерации карт в туториалах по Юнити (ссылка). Если примерно, то алгоритм выглядит так:
1) Берём двумерный массив и рандомом заполняем его(в туториале использовалась переменная — % заполнения — генерим число от 0 до 100 и если оно меньше % заполнения, то ставим тут стенку)
2) Делаем несколько итераций «сглаживания» (берём каждую клетку, если это стенка если её окружает < N стенок то делаем её пустой. Если это не стена, но её окружает < M стенок, то делаем стенку). В итоге «одинокие» стенки и «дырки» пропадают. Повторяем эту процедуру X — раз. (N, M и X — то же переменные, с которыми можно играться и от них будет сильно зависить результат)
3) Делаем два лист листов: один — коллекция областей(область — коллекция клеток) в которых стены, второй — коллекция областей без стен. Таким образом у нас есть N — комнат, которые мы теперь можем просто соединить между собой или просто сдвинуть.
Играясь с переменными будет получаться совершенно разный результат. Тут ещё стоит учитывать что «сглаживание» увеличивает разрыв между пустыми клетками и клетками со стенами. В моём случае в 45-48% заполнения получались большие пустые области с несколькими комнатками, а в случае 52-55% — много небольших-средних комнатушек.
Также видел алгоритмы по генерации карт в туториалах по Юнити (ссылка). Если примерно, то алгоритм выглядит так:
1) Берём двумерный массив и рандомом заполняем его(в туториале использовалась переменная — % заполнения — генерим число от 0 до 100 и если оно меньше % заполнения, то ставим тут стенку)
2) Делаем несколько итераций «сглаживания» (берём каждую клетку, если это стенка если её окружает < N стенок то делаем её пустой. Если это не стена, но её окружает < M стенок, то делаем стенку). В итоге «одинокие» стенки и «дырки» пропадают. Повторяем эту процедуру X — раз. (N, M и X — то же переменные, с которыми можно играться и от них будет сильно зависить результат)
3) Делаем два лист листов: один — коллекция областей(область — коллекция клеток) в которых стены, второй — коллекция областей без стен. Таким образом у нас есть N — комнат, которые мы теперь можем просто соединить между собой или просто сдвинуть.
Играясь с переменными будет получаться совершенно разный результат. Тут ещё стоит учитывать что «сглаживание» увеличивает разрыв между пустыми клетками и клетками со стенами. В моём случае в 45-48% заполнения получались большие пустые области с несколькими комнатками, а в случае 52-55% — много небольших-средних комнатушек.
Хорошая статья на хабре про генерацию помещений( на примере карт подземелий для рогалика)
Спасибо за статью!
Помнится, в детстве развлекался тем, что рисовал подобные лабиринты на бумаге, а потом пытался пройти их, используя карманный микроскоп с небольшим увеличением (до чего только не дойдёшь, когда нет компьютера). Вот тогда бы мне точно пригодился Sidewinder!
Что скажите о таком лабиринте?
Ну, могу сказать, что он какой-то некрасивый =)
Очень странная расстановка стен, непонятно от чего зависящая. Лабиринт явно не идеальный, так как имеет циклы, судя по всему, с более вертикальным смещением.
Очень странная расстановка стен, непонятно от чего зависящая. Лабиринт явно не идеальный, так как имеет циклы, судя по всему, с более вертикальным смещением.
Зато принцип прикольный. Подскажите как видео залить попроще?
Ну, Вы можете залить видео на Youtube и кинуть сюда ссылку. Или гифку записать. На ум ничего другого как-то не приходит.
YouTube-видео через тег <oembed>...</oembed> вставляется в статьи
Попробую видео построения лабиринта методом взрыва.
https://www.youtube.com/watch?v=tVDl2Tj_vmw
ps
через oembed не хочет
https://www.youtube.com/watch?v=tVDl2Tj_vmw
ps
через oembed не хочет
Обязательно пишите!
Мне очень интересно, вылезет ли где-то алгоритм на графе, который я придумывал буквально незадолго до первой статьи на эту тему на Хабре (таки надо его запрограммировать :) )
Графы чем хороши — так это тем, что построение лабиринта в принципе отвязано от его геометрии. Долой квадратность!
Не понимаю, что все так зациклены на идеальных лабиринтах. Даже Лосяш туда же — чем больше тупиков, тем лучше :) Но такие лабиринты самые скучные, их сложность только в длине, нельзя назвать их по-настоящему сложными. Для меня «идеальный» лабиринт,— наоборот, лабиринт без тупиков (и без петель).
Очень ждал подобную статью. Информативная и понятная. Жду продолжения.
Сейчас уже готовлю материалы про алгоритм Алдоса-Бродера и Уилсона. Надеюсь уложиться в неделю. Единственое, что может задержать – необходимость переписать реализацию Уилсона на Луа, потому что в нынешнем виде мне немного стыдно её выкладывать.
Я так понял Вы хотите пройтись по следующим распространенным алгоритмам:
- Алгоритм бинарного дерева (есть)
- Алгоритм Эллера (есть)
- Алгоритм Прима
- Алгоритм Олдоса-Бродера
- Алгоритм Уилсона
- Алгоритм Крускала
- Алгоритм рекурсивного деления
- Алгоритм рекурсивного поиска с возвратом?
Кстати, могу ошибаться, но алгоритм «Sidewinder это Алгоритм Эллера, он же Simple algorithms (когда в памяти храниться текущая и предыдущая строки лабиринта).
Нет, Сайдвиндер и Эллер хоть и похожи по работе, всё-таки, это разные алгоритмы. У Эллера совсем иная работа с сетами и логика их использования. Если в Сайдвиндере мы всегда работает исключительно с одним множеством в единицу времени, то Эллер манипулирует неограниченным количнством одновременно, в том числе и объединяя некоторые из них.
А так в вашем списке не хватает еще 2-3 алгоритмов:
Алгоритм Уилсона,
Алгоритм HuntandKill,
Алгоритм растущего дерева (по сути, рекурсивный поиск с возвратом при одном из вариантов реализации)
А так в вашем списке не хватает еще 2-3 алгоритмов:
Алгоритм Уилсона,
Алгоритм HuntandKill,
Алгоритм растущего дерева (по сути, рекурсивный поиск с возвратом при одном из вариантов реализации)
Эллер манипулирует неограниченным количнством одновременно, в том числе и объединяя некоторые из них
Как раз таки наоборот, я вычитал здесь, что алгоритм Эллера особенный, и хоть он похож на алгоритм Крускала, но весь его "сахар" в том, что не обязательно держать в памяти весь лабиринт, а достаточно размерности строки.
Да, всё верно. Надо отучить себя от привычки отвечать второпях, чтобы таких казусов не происходило.
Эллер работает с ограниченным количеством множеств, вплоть до размерности строки.
То есть, если у Вас строка состоит из десяти клеток, то, теоретически, Эллер может работать с 10 отдельными множествами и не объединить ни одного. Sidewinder же всегда работает исключительно с одним.
Эллер работает с ограниченным количеством множеств, вплоть до размерности строки.
То есть, если у Вас строка состоит из десяти клеток, то, теоретически, Эллер может работать с 10 отдельными множествами и не объединить ни одного. Sidewinder же всегда работает исключительно с одним.
Когда то, еще на Спектруме делал лабиринты, которые можно было пройти используя правило правой руки. Только не стирал стенки а наоборот, строил их. Упрощенно алгоритм выглядел так: Имелся массив узлов сетки. Выбиралась случайная точка на границе сетки и из нее рисовалась стенка. Если стенка попадала на непустой узел, то она не прорисовывалась. Если на пустой, то рисовалась. Далее с помощью некоторых коэффициентов и генератора случайных чисел решалось продолжать ли рисовать стенку в том же направлении, изменить направление или выбрать для генерации другую точку. Новой точкой мог быть любой непустой узел сетки из которого можно было построить новую стенку, которая заканчивалась на пустом узле. Меняя коэффициенты можно было получить самые разные лабиринты. С прямыми длинными коридорами, наоборот, с извилистыми. Петли получались, если заранее прорисовывать участки стены не прикасающиеся к границам лабиринта. Все это было написано на Бейсике много, много лет назад)))
Тема оказалась очень увлекательной и интересной. В поисках «большего» набрел на удивительную книжку по алгоритмам — Mazes for Programmers. Советую.
Sign up to leave a comment.
Классические алгоритмы генерации лабиринтов. Часть 1: вступление