Мы делали ремастер
целый год

Создаём случайные подземелья: принципы процедурной генерации 3D-пространств Статьи редакции

C подробным описанием всего процесса и ссылкой на репозиторий.

Разработчик под ником Vazgriz опубликовал на YouTube видео, в котором описал принципы работы генератора подземелий в 3D на Unity. Он отметил, что в основе лежит принцип создания 2D-карт, но многоэтажность может добавить несколько проблем. Чтобы справиться с ними, надо использовать 3D-версии алгоритмов и значительно переработать алгоритм поиска пути A*. Выбрали из видео главное.

Алгоритм создания 3D-подземелий похож на таковой для 2D-простанств, поэтому сперва опишем принципы генерации плоских карт.

Сначала нужно рандомно разместить комнаты в пространстве.

Здесь у комнат рандомный размер

Следующий шаг — создание переходов между комнатами. Представим, что каждое помещение — это точка, а линии между ними — коридоры. В результате получится сетка. Для создания этой сетки автор решил использовать триангуляцию по алгоритмам Делоне — этот подход позволяет избежать появления длинных острых треугольников и создать множество сравнительно коротких связей между точками. Чтобы реализовать триангуляцию Делоне, автор использовал алгоритм Боуэра-Уотсона.

Каждая точка — это помещение, а линии между ними — возможные коридоры
Пример создания переходов, соединяющих помещения

Теперь нужно уменьшить количество переходов между помещениями, потому что в игре не нужно так много коридоров. Для этого Vazgriz решил исключить петли и придать сетке древовидную структуру при помощи алгоритма Minimum Spanning Tree (MST). Чтобы сделать это, автор использовал алгоритм Прима.

Minimum Spanning Tree обозначено зелёными линиями. Все серые линии — это кандидаты на удаление. Но у каждой есть вероятность в 12,5%, что она останется. Это нужно для создания более интересной карты с возможными петлями

Следующий важный шаг — поиск путей между комнатами. Для этого Vazgriz использовал алгоритм A* — он нужен, чтобы найти оптимальный путь между двумя точками.

Vazgriz добавил уточнение к A*, которое указывает, что пути могут накладываться друг на друга. Также путь не может проходить сквозь помещение, поэтому ему проще «обойти» его
Этот уровень создан алгоритмом

Теперь можно переходить к 3D-подземелью. Общий принцип тот же, но на каждом шаге нужно использовать 3D-версии алгоритмов.

Сперва нужно создать помещения в 3D-пространстве. Главное отличие от предыдущего примера — теперь комнаты находятся на разных этажах.

Второй шаг — генерация сетки при помощи тетраэдрализации по алгоритмам Делоне: добавилось третье измерение, поэтому связь между помещениями нужно показывать при помощи тетраэдров (с четырьмя вершинами), а не треугольников (с тремя).

Vazgriz отметил, что не нашёл в сети код, который позволил бы реализовать эту задумку, поэтому ему пришлось самостоятельно менять алгоритм Боуэра-Уотсона. В нём он поменял описанную окружность на описанную сферу и всё заработало в 3D
Теперь нужно определить Minimum Spanning Tree, убрать лишние переходы (и оставить некоторые с вероятностью 12,5%)

Последний шаг, поиск пути, получился самым сложным. Чтобы реализовать пэсфайндинг в 3D, разработчику пришлось добавить алгоритму A* возможность подниматься и опускаться. Но проблема в том, что в А* не заложено специфическое поведение для таких ситуаций.

A* может сгенерировать только такие лестницы. Это не соответствовало задумке автора
Ещё один вариант вертикального перехода

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

Синие квадраты — обычные тайлы. Зелёные — лестница. Зелёная группа тайлов сделана так, чтобы лестница занимала только два нижних квадрата, а два верхних — оставались пустыми. Это нужно для того, чтобы лестница была правдоподобной
Но в результате получилось, что A* считал пустые клетки в зелёной группе тайлов неиспользованными, поэтому прокладывал путь поверх них

Чтобы справиться с проблемой, разработчику нужно было научиться помечать всю группу тайлов как занятую — только так A* не прокладывал бы через них путь. Но это намного сложнее, чем может показаться на первый взгляд.

Всё дело в том, что A* в момент поиска пути одновременно прокладывает сразу множество дорожек и одна и та же клетка в одном случае может использоваться в качестве обычного прохода, а в другом — в качестве лестницы. И если добавить тайлы, которые больше одной базовой клетки, то это помешает прокладывать остальные пути. В результате правильный путь может быть не найден, потому что лестница займёт нужное пространство. Если же игнорировать лестницы, то тайлы будут накладываться друг на друга.

Для решения проблемы Vazgriz сделал так, чтобы тайлы сохраняли информацию о всём пути, который ведёт к ним. Если окажется, что следующий тайл находится на пути к предыдущему тайлу, то A* не будет использовать его.

На самом деле финальный алгоритм сложно назвать A*, потому что в нём слишком много специфичных правил. Но он позволяет искать путь в 3D-пространстве, используя те же принципы. Единственное ограничение — иногда получается найти путь не для всех переходов

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

В результате весь процесс генерации 3D-подземелий можно описать пятью пунктами.

  1. Размещение комнат.
  2. Создание сетки при помощи тетраэдрализации Делоне.
  3. Поиск Minimum Spanning Tree.
  4. Устранение лишних граней.
  5. Поиск пути.

Если вы хотите более подробно ознакомиться с проектом, вот ссылка на репозиторий.

0
37 комментариев
Популярные
По порядку
Написать комментарий...
Советский глобус

Мне кажется, что именно такие статьи и спасут DTF. Спасибо автору за ссылку на гитхаб.

Ответить
62
1 комментарий
Развернуть ветку
Духнич Дмитрий

Спасибо за Gamedev👍

Ответить
2
Развернуть ветку
Ярослав Голубев

Такое себе)
Это смотрелось нормально в 80х в рог лайках, но в современном мире такие лабиринты это если говорить честно - это отстой.

Впрочем такой алгоритм после доработки напильником может использоваться как система генерации естественных пещер, но если нужны именно "рукотворные подземелья" логика их создания должна быть иной . У рукотворных подземелей должна быть четкая геометрическая логика - склады, лесницы, залы, хранилища.
И затем уже нужно действовать наоборот: Добавлять завалы, дыры между уровнями и прочие "естественные разрушения"

Ответить
11
Развернуть ветку
Никита Лукьянов

Ну так в статье разбираются прям основы основы, говорить о них как об игре не правильно.

Ответить
3
Развернуть ветку
Ярослав Голубев

Хорошим тоном в таких статьях будет рассмотреть и возможность куда можно двигаться дальше. И раз автор этого не сделал - то это должны сделать комментаторы)

Ответить
1
Развернуть ветку
Pixel Lens 👹

Хорошим тоном
Не соглашусь. Это как от производителя бумаги требовать идей, как ее можно применить, или какую историю на ней можно написать.
Тебе даётся инструмент, а применений ему великое множество так то

Ответить
8
Развернуть ветку
Ярослав Голубев

Ага придумали бумагу для письма, а злые пользователи придумали как ею подтираться :D

Ответить
2
Развернуть ветку
Pixel Lens 👹

Именно так) А еще оригами, упаковка и обёртка, папье-маше и скульптуры делают, а уж чего только не пишут и не рисуют.

Ответить
1
Развернуть ветку
Darkusoid

Бедные лопухи вообще :(

Ответить
0
Развернуть ветку
Кирилл Сергеев

Это статья, по сути, туториал - как сделать так же как и автор. Как научиться, как сделать свой первый процген данж. Куда двигаться дальше начинающему разработчику игр подскажет его богатая фантазия)

Ответить
0
Развернуть ветку
Pixel Lens 👹

Многое зависит от геймплея. В Gunfire Reborn тоже генерятся ветвистые лабиринты, но большинство ходов искусственно перекрываются, причём в некоторых биомах перекрытие полупрозрачное (типа энергетического экрана, что ли, по визуалу), что добавляет ощущение большого мира, не усложняя при этом движение по уровню.

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

Ответить
0
Развернуть ветку
Олег Воскобоев

В Ганфаере одна карта на уровень. Единственная "генерация" это перекрытие некоторых дверей и выбор стартовой/конечной комнаты

Ответить
3
Развернуть ветку
Pixel Lens 👹

*одна процедурно генерируемая карта на уровень

хотя результаты выглядят настолько похоже, что и не скажешь что там процедурка)

Ответить
0
Развернуть ветку
Эл Хэлфрид

В ганфаере, мне показалось, просто заготовленные заранее комнаты друг к другу примтыковываются дверями, вот и вся генерация. А лишние двери просто затыкаются заглушками.

Вот где реально крутой генератор, так это в deep rock galactic

Ответить
0
Развернуть ветку
kilo1234

В принципе достаточно генерировать симметрию, а в некоторых местах по random(0,1) делать тупики, завалы, дыры и т.д.

Ответить
0
Развернуть ветку
Ярослав Голубев

Верно - симметрия - это верный признак иcскуственности.
Ее удобно использовать при создании локаций.
Можно поиграться с радиальной , спиралевидной или иными видами расположения комнат.

Ответить
0
Развернуть ветку
kilo1234

Да, но это работает только в одном направлении. Но что если здание имеет Г-образную форму или еще сложней - форму крепости?

Ответить
0
Развернуть ветку
Ярослав Голубев

У этого давно есть решение - пресеты модулей.

Ответить
1
Развернуть ветку
Vladimir Petrov

Разработчики Даггерфола: "Найс"

Ответить
0
Развернуть ветку
Ярослав Голубев

В дагерфоле другой принцип генерации подземелий . они там из пресетов собирались
У @Xanathar была статья как они там генерировались.
https://dtf.ru/games/210962-dyavolskaya-lapsha-posobie-po-vyzhivaniyu-v-daggerfolle

Ответить
6
Развернуть ветку
Чапай

Подташнивало из-за этого проходить Чаши в Бладборне. Хоть ты какие алгоритмы выдумывай, всегда будет ощущаться эта искусственность и скука. Через пару заходов становится очевидно, что это бездушная и глупая рандомная хуета, которую тебе насрал "робот". Ну, сам пусть по ней и бегает. Забил вообще на эту тему, выбивания там топовых камней для пушек. Обойдусь с более худшими, чем по этой унылости бродить.

Ответить
1
Развернуть ветку
Иван

Главное, сразу понятно, что за движок. (Нет)

Ответить
0
Развернуть ветку
Владимир Семыкин

спасибо, добавил уточнение в текст. Автор делал на Unity

Ответить
0
Развернуть ветку
Никита Лукьянов

На самом деле оно не сильно важно, суть в алгоритмах, повторить их можно на чём угодно

Ответить
7
Развернуть ветку
Советский глобус

Unity же, если по ссылке на гитхаб перейти

Ответить
0
Развернуть ветку
ДЕЛА ИГРОДЕЛА

Фон же сцены)

Ответить
3
Развернуть ветку
Советский глобус

Точно)

Ответить
0
Развернуть ветку
Arazect Shepard

принципы работы генератора подземелий в 3D на Unity

главное, что никто не долбится в глаза, прежде чем писать комментарий

Ответить
0
Развернуть ветку
Олег Листьев

Что такое "А*"?

Ответить
0
Развернуть ветку
Ярослав Голубев

Алгоритм А звезда» или "А стар" поиска кратчайшего пути, по сетке.
Одна из базовых вещей в программировании без которого каши не сваришь и ии не настроешь и локацию не сгенерируешь

Ответить
2
Развернуть ветку
Духнич Дмитрий

Алгоритм поиска пути

Ответить
1
Развернуть ветку
Andrey Apanasik

Без примеров кода
Если вы хотите более подробно ознакомиться с проектом, вот ссылка на репозиторий.
🤔

Ответить
0
Развернуть ветку
Владимир Семыкин

Спасибо, поправил. Осталось с одной из итераций текста

Ответить
1
Развернуть ветку
Andrey Apanasik

Слушай, а ты прям по видео текст писал или с оглядкой на оригинальную статью?

Ответить
2
Развернуть ветку
ДЕЛА ИГРОДЕЛА

А я всё думал, почему у меня deja vu.

Ответить
1
Развернуть ветку
Владимир Семыкин

по видео

Ответить
1
Развернуть ветку
Читать все 37 комментариев
null