Создаём случайные подземелья: принципы процедурной генерации 3D-пространств Статьи редакции
C подробным описанием всего процесса и ссылкой на репозиторий.
Разработчик под ником Vazgriz опубликовал на YouTube видео, в котором описал принципы работы генератора подземелий в 3D на Unity. Он отметил, что в основе лежит принцип создания 2D-карт, но многоэтажность может добавить несколько проблем. Чтобы справиться с ними, надо использовать 3D-версии алгоритмов и значительно переработать алгоритм поиска пути A*. Выбрали из видео главное.
Алгоритм создания 3D-подземелий похож на таковой для 2D-простанств, поэтому сперва опишем принципы генерации плоских карт.
Сначала нужно рандомно разместить комнаты в пространстве.
Следующий шаг — создание переходов между комнатами. Представим, что каждое помещение — это точка, а линии между ними — коридоры. В результате получится сетка. Для создания этой сетки автор решил использовать триангуляцию по алгоритмам Делоне — этот подход позволяет избежать появления длинных острых треугольников и создать множество сравнительно коротких связей между точками. Чтобы реализовать триангуляцию Делоне, автор использовал алгоритм Боуэра-Уотсона.
Теперь нужно уменьшить количество переходов между помещениями, потому что в игре не нужно так много коридоров. Для этого Vazgriz решил исключить петли и придать сетке древовидную структуру при помощи алгоритма Minimum Spanning Tree (MST). Чтобы сделать это, автор использовал алгоритм Прима.
Следующий важный шаг — поиск путей между комнатами. Для этого Vazgriz использовал алгоритм A* — он нужен, чтобы найти оптимальный путь между двумя точками.
Теперь можно переходить к 3D-подземелью. Общий принцип тот же, но на каждом шаге нужно использовать 3D-версии алгоритмов.
Сперва нужно создать помещения в 3D-пространстве. Главное отличие от предыдущего примера — теперь комнаты находятся на разных этажах.
Второй шаг — генерация сетки при помощи тетраэдрализации по алгоритмам Делоне: добавилось третье измерение, поэтому связь между помещениями нужно показывать при помощи тетраэдров (с четырьмя вершинами), а не треугольников (с тремя).
Последний шаг, поиск пути, получился самым сложным. Чтобы реализовать пэсфайндинг в 3D, разработчику пришлось добавить алгоритму A* возможность подниматься и опускаться. Но проблема в том, что в А* не заложено специфическое поведение для таких ситуаций.
Чтобы добавить лестницу, автор решил сделать особую группу тайлов, которая появляется каждый раз, когда нужно создать вертикальный переход.
Чтобы справиться с проблемой, разработчику нужно было научиться помечать всю группу тайлов как занятую — только так A* не прокладывал бы через них путь. Но это намного сложнее, чем может показаться на первый взгляд.
Всё дело в том, что A* в момент поиска пути одновременно прокладывает сразу множество дорожек и одна и та же клетка в одном случае может использоваться в качестве обычного прохода, а в другом — в качестве лестницы. И если добавить тайлы, которые больше одной базовой клетки, то это помешает прокладывать остальные пути. В результате правильный путь может быть не найден, потому что лестница займёт нужное пространство. Если же игнорировать лестницы, то тайлы будут накладываться друг на друга.
Для решения проблемы Vazgriz сделал так, чтобы тайлы сохраняли информацию о всём пути, который ведёт к ним. Если окажется, что следующий тайл находится на пути к предыдущему тайлу, то A* не будет использовать его.
Если использовать такой подход, могут получиться самые разные варианты подземелья: с широкими лестницами, двумя лестницами, ведущими к одной двери, с лестничной площадкой, объединёнными залами и так далее.
В результате весь процесс генерации 3D-подземелий можно описать пятью пунктами.
- Размещение комнат.
- Создание сетки при помощи тетраэдрализации Делоне.
- Поиск Minimum Spanning Tree.
- Устранение лишних граней.
- Поиск пути.
Если вы хотите более подробно ознакомиться с проектом, вот ссылка на репозиторий.
Мне кажется, что именно такие статьи и спасут DTF. Спасибо автору за ссылку на гитхаб.
Спасибо за Gamedev👍
Такое себе)
Это смотрелось нормально в 80х в рог лайках, но в современном мире такие лабиринты это если говорить честно - это отстой.
Впрочем такой алгоритм после доработки напильником может использоваться как система генерации естественных пещер, но если нужны именно "рукотворные подземелья" логика их создания должна быть иной . У рукотворных подземелей должна быть четкая геометрическая логика - склады, лесницы, залы, хранилища.
И затем уже нужно действовать наоборот: Добавлять завалы, дыры между уровнями и прочие "естественные разрушения"
Ну так в статье разбираются прям основы основы, говорить о них как об игре не правильно.
Хорошим тоном в таких статьях будет рассмотреть и возможность куда можно двигаться дальше. И раз автор этого не сделал - то это должны сделать комментаторы)
Не соглашусь. Это как от производителя бумаги требовать идей, как ее можно применить, или какую историю на ней можно написать.
Тебе даётся инструмент, а применений ему великое множество так то
Ага придумали бумагу для письма, а злые пользователи придумали как ею подтираться :D
Именно так) А еще оригами, упаковка и обёртка, папье-маше и скульптуры делают, а уж чего только не пишут и не рисуют.
Бедные лопухи вообще :(
Это статья, по сути, туториал - как сделать так же как и автор. Как научиться, как сделать свой первый процген данж. Куда двигаться дальше начинающему разработчику игр подскажет его богатая фантазия)
Многое зависит от геймплея. В Gunfire Reborn тоже генерятся ветвистые лабиринты, но большинство ходов искусственно перекрываются, причём в некоторых биомах перекрытие полупрозрачное (типа энергетического экрана, что ли, по визуалу), что добавляет ощущение большого мира, не усложняя при этом движение по уровню.
Еще можно припомнить пример (конкретных игр не назову, забыл) когда часть перекрытых ранее ходов может быть откупорена результатом определённого события, которое возвращает игрока на уже пройденную местность (на которой игрок уже успел сориентироваться и привыкнуть к ней) - игра так предлагает перепройти эту местность другими путями и найти спрятанные там ништяки.
В Ганфаере одна карта на уровень. Единственная "генерация" это перекрытие некоторых дверей и выбор стартовой/конечной комнаты
*одна процедурно генерируемая карта на уровень
хотя результаты выглядят настолько похоже, что и не скажешь что там процедурка)
В ганфаере, мне показалось, просто заготовленные заранее комнаты друг к другу примтыковываются дверями, вот и вся генерация. А лишние двери просто затыкаются заглушками.
Вот где реально крутой генератор, так это в deep rock galactic
В принципе достаточно генерировать симметрию, а в некоторых местах по random(0,1) делать тупики, завалы, дыры и т.д.
Верно - симметрия - это верный признак иcскуственности.
Ее удобно использовать при создании локаций.
Можно поиграться с радиальной , спиралевидной или иными видами расположения комнат.
Да, но это работает только в одном направлении. Но что если здание имеет Г-образную форму или еще сложней - форму крепости?
У этого давно есть решение - пресеты модулей.
Разработчики Даггерфола: "Найс"
В дагерфоле другой принцип генерации подземелий . они там из пресетов собирались
У @Xanathar была статья как они там генерировались.
https://dtf.ru/games/210962-dyavolskaya-lapsha-posobie-po-vyzhivaniyu-v-daggerfolle
Подташнивало из-за этого проходить Чаши в Бладборне. Хоть ты какие алгоритмы выдумывай, всегда будет ощущаться эта искусственность и скука. Через пару заходов становится очевидно, что это бездушная и глупая рандомная хуета, которую тебе насрал "робот". Ну, сам пусть по ней и бегает. Забил вообще на эту тему, выбивания там топовых камней для пушек. Обойдусь с более худшими, чем по этой унылости бродить.
Главное, сразу понятно, что за движок. (Нет)
спасибо, добавил уточнение в текст. Автор делал на Unity
На самом деле оно не сильно важно, суть в алгоритмах, повторить их можно на чём угодно
Unity же, если по ссылке на гитхаб перейти
Фон же сцены)
Точно)
Комментарий недоступен
Что такое "А*"?
Алгоритм А звезда» или "А стар" поиска кратчайшего пути, по сетке.
Одна из базовых вещей в программировании без которого каши не сваришь и ии не настроешь и локацию не сгенерируешь
Алгоритм поиска пути
Если вы хотите более подробно ознакомиться с проектом, вот ссылка на репозиторий.
🤔
Спасибо, поправил. Осталось с одной из итераций текста
Слушай, а ты прям по видео текст писал или с оглядкой на оригинальную статью?
А я всё думал, почему у меня deja vu.
по видео