Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 35
Хм, а с каких пор алгоритмы Прима и Краскала являются алгоритмами генерации лабиринтов? Нет, я понимаю, что генерация лабиринта — это по сути нахождение остовного дерева в графе, но лабиринты в таком случае будут получаться несколько… странными, особенно если используемая в одном из них сортировка случайно окажется устойчивой.
А тут ещё давно лежал какой-то алгоритм генерации и обхода лабиринта. Примеры со статьи не работают, но пример 4 был взят для эксперимента и, как ни странно, запустился на коде 2006 года без правок.
Пример: liveweave.com/17JST3, проверен в Хроме, Fx, Опера.
Видно лишь, что не по алгоритму Эллера, но получается легко и занятно, видимо, случайным подбором.
Пример: liveweave.com/17JST3, проверен в Хроме, Fx, Опера.
Видно лишь, что не по алгоритму Эллера, но получается легко и занятно, видимо, случайным подбором.
Так мы что же, всегда делаем проход по нижней линии? Ведь состояния множеств из верхних линий мы в памяти не держим, что, как я понимаю, нам память и экономит…
Состояния множеств из верхних линий мы не держим в памяти не потому что экономим память, а потому что нам они не нужны — состояния текущей линии достаточно для принятия решения.
Да, но прохождение лабиринта насколько я понимаю будет сводиться к тому чтобы
1) Пройти от выхода к нижней линии
2) пройти от входа к нижней линии
3) соединить точки (должно быть очень просто).
1) Пройти от выхода к нижней линии
2) пройти от входа к нижней линии
3) соединить точки (должно быть очень просто).
Нет. В нижней линии тоже могут быть стенки. Более того, данный алгоритм может выдать на выходе абсолютно любой корректный лабиринт, хотя и не все лабиринты равновероятны.
Да, но глобальный проход через все секции всегда будет через нижнюю линию — останется только банально перешагивать стенки.
Посмотрите на первый лабиринт в посте. Чтоб пройти из левой нижней ячейки в правую нижнюю, нужно дойти чуть ли не до самого верха.
Да, вы правы. Однако же я хочу заметить что в любом случае у нас все множества вертикальные и идут до самого низа, так что как только дошел до низа — дальше уже все все равно просто. Лабиринт бстро проходится методом правой руки.
Пару лет назад сделал такую программку, если кому интересно, можете скачать исходники: aivanov.com/maze-generator/
или просто поиграться: aivanov.com/maze/ :)
или просто поиграться: aivanov.com/maze/ :)
А какой алгоритм был заложен в вашем коде: использовали что-то своё или готовое?
Сам придумал. Идея простая: создаются ветви определённой длины и по завершению начинаются новые ветви ближе к началу пути.
Это больше похоже на дерево с ветвями и создаёт более сложные лабиринты, где много длинных ответвлений, по которым приходится возвращаться назад.
Если взглянуть на примеры лабиринтов, построенные на алгоритме Эллера, то можно визуально найти путь за несколько секунд, если видишь весь лабиринт т.к. мало запутанности (очень короткие тупики).
Также я рассматривал лабиринты, которые сделаны через рекурсию, но они получаются совсем дебильными — как правило, у них один длинный путь, который покрывает почти весь лабиринт и оооочень мало коротких ответвлений, которые по остаточному принципу созданы.
В таких лабиринтах практически невозможно «заблудиться» :)
Это больше похоже на дерево с ветвями и создаёт более сложные лабиринты, где много длинных ответвлений, по которым приходится возвращаться назад.
Если взглянуть на примеры лабиринтов, построенные на алгоритме Эллера, то можно визуально найти путь за несколько секунд, если видишь весь лабиринт т.к. мало запутанности (очень короткие тупики).
Также я рассматривал лабиринты, которые сделаны через рекурсию, но они получаются совсем дебильными — как правило, у них один длинный путь, который покрывает почти весь лабиринт и оооочень мало коротких ответвлений, которые по остаточному принципу созданы.
В таких лабиринтах практически невозможно «заблудиться» :)
Ни на сайте, ни в самом коде не указано под какой лицензией вы его распространяете. Было бы удобно, если бы вы это уточнили.
В тексте есть пометка «вы можете скачать и использовать так, как захотите». Если моего слова будет достаточно, то обещаю только радоваться за тех, кому этот код будет полезен и никогда не предъявлю никаких претензий. Упоминания об авторстве совершенно не обязательны.
Не хочется ради таких мелочей сейчас правками заниматься :)
P.S. Кстати, там если включить режим анимации, то видно, что красными квадратиками показывается стек маршрута. Лишние точки (откуда уже нет пути ни в одном из 4-х направлений) можно убрать, чтобы занимало меньше памяти. Сделать просто проверкой в методе addRoute, но я не стал заморачиваться, т.к. это вопрос всего нескольких килобайт.
P.P.S. В предыдущем комментарии я написал «создаются ветви определённой длины». На самом деле обманул. Такой вариант был, но я почему-то заменил на другой: создаётся ветвь, пока не зайдёт в тупик. Как только выхода нет — начинается ветвь как можно ближе к началу.
Не хочется ради таких мелочей сейчас правками заниматься :)
P.S. Кстати, там если включить режим анимации, то видно, что красными квадратиками показывается стек маршрута. Лишние точки (откуда уже нет пути ни в одном из 4-х направлений) можно убрать, чтобы занимало меньше памяти. Сделать просто проверкой в методе addRoute, но я не стал заморачиваться, т.к. это вопрос всего нескольких килобайт.
P.P.S. В предыдущем комментарии я написал «создаются ветви определённой длины». На самом деле обманул. Такой вариант был, но я почему-то заменил на другой: создаётся ветвь, пока не зайдёт в тупик. Как только выхода нет — начинается ветвь как можно ближе к началу.
А подскажите, зачем вы делаете & (0xFFFF ^ direct) и & (0xFFFF ^ backDirect(direct)? Почему пометки как CELL_VISITED недостаточно?
Уф) Хороший вопрос. В обоих случаях идёт сброс бита в «0» отвечающего за стенку. Это можно было бы оптимизировать, но памяти тут не сэкономишь, если не паковать биты, поэтому я поступил довольно просто:
— Ячейка массива содержит в себе информацию о стенах, которую её окружают (биты 1-4)
— Если ячейка уже посещена генератором, то устанавливается бит 7
— По умолчанию, весь массив состоит из одних стен (в каждой клетке 4 стенки)
— Каждый ход «ломается» по одной стене, но бит гасится для двух соседних клеток. Т.е. если мы пошли вправо и сломали правую стенку, то нужно убрать бит правой стенки в данной клетке и убрать бит левой стенки в клетке справа.
— Ячейка массива содержит в себе информацию о стенах, которую её окружают (биты 1-4)
— Если ячейка уже посещена генератором, то устанавливается бит 7
— По умолчанию, весь массив состоит из одних стен (в каждой клетке 4 стенки)
— Каждый ход «ломается» по одной стене, но бит гасится для двух соседних клеток. Т.е. если мы пошли вправо и сломали правую стенку, то нужно убрать бит правой стенки в данной клетке и убрать бит левой стенки в клетке справа.
Спасибо!
Удивился, как быстро даже 33x34 прохожу. Остался навык из детства — очень любил лабиринты, научился некоторым хитростям :)
Удивился, как быстро даже 33x34 прохожу. Остался навык из детства — очень любил лабиринты, научился некоторым хитростям :)
Простите. Но может быть все таки Эйлера?
На основе идеального алгоритма Эллера можно сделать кучу головоломок.
Одна из них типа netwalk.
Будет популярной под айпад (в айфон сетка 9 на 9 не влезет).
Нужен дизайнер и успех обеспечен.
Одна из них типа netwalk.
Будет популярной под айпад (в айфон сетка 9 на 9 не влезет).
Нужен дизайнер и успех обеспечен.
Я использовал такой алгоритм. (Возможно изобрёл чей то велосипед) :-)
1. Рисуем рамочку лабиринта
2. Генерируем список все нечётных координат внутри рамочки
3. Случайно выбираем любую точку из списка (тут я использовал алгоритм случайного выбора без повторов).
4. Если случайно выбранная клетка занята, то ничего не делаем. Иначе чертим в случайную сторону линию лабиринта не доходя до стены.
5. Повторять с п. 3 пока список не опустеет.
Модификации — прерывая черчение стены лабиринта на шаге 4 можно делать частично «пустые» лабиринты.
1. Рисуем рамочку лабиринта
2. Генерируем список все нечётных координат внутри рамочки
3. Случайно выбираем любую точку из списка (тут я использовал алгоритм случайного выбора без повторов).
4. Если случайно выбранная клетка занята, то ничего не делаем. Иначе чертим в случайную сторону линию лабиринта не доходя до стены.
5. Повторять с п. 3 пока список не опустеет.
Модификации — прерывая черчение стены лабиринта на шаге 4 можно делать частично «пустые» лабиринты.
Вот очень хорошая ссылка на алгоритмы генерации лабиринтов: Think Labyrinth. Я когда-то реализовал один из первых в списке алгоритмов Recursive Backtracker. Этот алгоритм характерен тем, что получающиеся лабиринты могут иметь очень длинные тупиковые ответвления, так что проходить такой лабиринт вручную — сложная задача.
Различные алгоритмы генерации лабиринтов приводят к различной средней длине тупиковых ответвлений. В статье рассматривается, что если генерировать случайные лабиринты, которые взяты из равномерного распределения по всему множеству допустимых лабиринтов — то средняя длина ответвлений получится низкой. Из этого следует, что лабиринтов с длинными ответвлениями существует меньше, чем с короткими.
Наличие циклов в лабиринте иногда бывает полезным. Например, это может запутать некоторые простые алгоритмы прохождения лабиринтов.
Различные алгоритмы генерации лабиринтов приводят к различной средней длине тупиковых ответвлений. В статье рассматривается, что если генерировать случайные лабиринты, которые взяты из равномерного распределения по всему множеству допустимых лабиринтов — то средняя длина ответвлений получится низкой. Из этого следует, что лабиринтов с длинными ответвлениями существует меньше, чем с короткими.
Наличие циклов в лабиринте иногда бывает полезным. Например, это может запутать некоторые простые алгоритмы прохождения лабиринтов.
Удивлён, что никто ещё не пошутил про это (лабиринт в пару строк JS, оригинальная идея была написана на терминалах, в одну строку). Изначально, конечно, сама идея шуточная. Там, конечно, речи нет ни о гарантированной полной связности лабиринта, ни о чём-то ещё детерминированном, т.к. рандом.
Зато, например, настраивать «общую направленность» или степень заполнения можно уже там, а затем, для придания нужной формы и свойств, детерминированными методами склеивать отдельные участки лабиринта (с разной «общей направленностью»), а также «прорубать» проходы для обеспечения требуемой связности участков. Так, для восстановления связности можно выбирать не жадным способом, а именно минимальное число проходов; для связи между блоками — выбирать область с прицелом на наименьший (а может, лучше наибольший?) общий путь прохождения.
… Или про это: генератор уровней для классических шутеров Oblidge.
Кстати, автор последнего, уже без шуток, генерирует именно проходимые уровни. По своему опыту отмечу, что порой не такие уж и плохие, а иногда и вовсе неплохие. Особенно радует в нём функция «сгенерировать полный комплект уровней», которая создаёт целую игру (например, 32 уровня для второго дума), с возрастающими сложностью, размерами карт и количествами врагов, а также учитывает стилистические особенности отдельных уровней (map07, map30...). Впрочем, это уже очень узконаправленная штука. Да и упора на сложность лабиринта там особо никто не делал. Жду — не дождусь, когда автор всё-таки выведет из беты на сносный уровень HL1/CS16.
А если без шуток, то да, очень занятно. Вкупе с материалом про прохождение лабиринта «в условиях тумана» (когда у программы нету карты) может получиться отличная пара (генератор лабиринтов-заданий и программы-Тесеи). Если с красивым визуализатором, то можно будет и speedrun-ы смотреть.
Зато, например, настраивать «общую направленность» или степень заполнения можно уже там, а затем, для придания нужной формы и свойств, детерминированными методами склеивать отдельные участки лабиринта (с разной «общей направленностью»), а также «прорубать» проходы для обеспечения требуемой связности участков. Так, для восстановления связности можно выбирать не жадным способом, а именно минимальное число проходов; для связи между блоками — выбирать область с прицелом на наименьший (а может, лучше наибольший?) общий путь прохождения.
… Или про это: генератор уровней для классических шутеров Oblidge.
Кстати, автор последнего, уже без шуток, генерирует именно проходимые уровни. По своему опыту отмечу, что порой не такие уж и плохие, а иногда и вовсе неплохие. Особенно радует в нём функция «сгенерировать полный комплект уровней», которая создаёт целую игру (например, 32 уровня для второго дума), с возрастающими сложностью, размерами карт и количествами врагов, а также учитывает стилистические особенности отдельных уровней (map07, map30...). Впрочем, это уже очень узконаправленная штука. Да и упора на сложность лабиринта там особо никто не делал. Жду — не дождусь, когда автор всё-таки выведет из беты на сносный уровень HL1/CS16.
А если без шуток, то да, очень занятно. Вкупе с материалом про прохождение лабиринта «в условиях тумана» (когда у программы нету карты) может получиться отличная пара (генератор лабиринтов-заданий и программы-Тесеи). Если с красивым визуализатором, то можно будет и speedrun-ы смотреть.
Есть дырки, нет петель, но задача выполнена, вполне себе лабиринт, пусть и без входа и выхода.
Самые интересные лабиринты получаются по алгоритмам никак не связанным с теорией графов.
Самые интересные лабиринты получаются по алгоритмам никак не связанным с теорией графов.
Ломаю голову над последней строкой.
У Вас в алгоритме в пункте 5 подразумевается, что если это последняя строка, то мы НЕ выполняем 5.1, а сразу переходим к 5.2, верно? Но в примере про последнюю строку написано так «Начнем с создания обычной строки...», это имеются в виду пункты 2, 3 и 4? Включая 5.1 или нет? Если возможно, напишите подробный план генерации именно последней строки с пункта использования предыдущей строки. Или хотя бы опишите порядок по номерам из Вашего алгоритма.
Спасибо.
У Вас в алгоритме в пункте 5 подразумевается, что если это последняя строка, то мы НЕ выполняем 5.1, а сразу переходим к 5.2, верно? Но в примере про последнюю строку написано так «Начнем с создания обычной строки...», это имеются в виду пункты 2, 3 и 4? Включая 5.1 или нет? Если возможно, напишите подробный план генерации именно последней строки с пункта использования предыдущей строки. Или хотя бы опишите порядок по номерам из Вашего алгоритма.
Спасибо.
Не понимаю пункт 4.
Это не одно ли и то же?
1. Если ячейка в своем множестве одна, то не создавайте границу снизу
2. Если ячейка одна в своем множестве без нижней границы, то не создавайте нижнюю границу
Это не одно ли и то же?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм Эллера для генерации лабиринтов