Как настроить дозагрузку контента для тяжёлой игры

Генерация подземелий: принципы создания случайных запутанных локаций Статьи редакции

Поэтапное формирование уровня.

Французский инди-разработчик Пьер Вигьер продолжает описывать процесс создания игры Vagabond в своём блоге. На этот раз он рассказал о генерации подземелий и подходах, которые он использовал.

В прошлом тексте Пьер описывал процесс создания точечного источника освещения.

Есть много способов для генерации подземелий — рандомное размещение, с помощью агента, физического движка, separation steering behavior и так далее. Но Пьер в своём проекте использовал метод разбиения пространства.

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

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

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

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

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

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

На данный момент он использует алгоритм Краскала с манхэттенским расстоянием для выбора рёбер.

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

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

Идея Пьера заключается в том, чтобы использовать клеточные автоматы для получения природного вида комнат, но задавать ограничения, чтобы иметь управляемый результат. Вместо того, чтобы использовать только два состояния — «мёртвое» или «живое», он использует четыре: «однозначно мёртвое», «мёртвое», «живое», «однозначно живое». Состояния «однозначно» не могут меняться от одного шага к другому — они нужны для ограничения результата.

Комнаты и коридоры, созданные на предыдущих этапах, заполнены «однозначно живыми» клетками. Таким образом, сохраняется понятие комнат, которые связаны друг с другом. Границы заполняются «однозначно мёртвыми» клетками, чтобы не появились новые пути между комнатами. Вокруг комнат и коридоров рандомно располагаются «живые» клетки.

Затем запускается клеточный автомат, чтобы получить природный вид помещений.

Вот ещё несколько примеров.

Следующий шаг — убрать ячейки, оторванные от основной карты.

По ходу работы Пьер обнаружил интересный эффект — если повысить параметр шума вокруг комнат и увеличить их размер, то появится больше коридоров, а в некоторых случаях помещения почти объединятся.

В результате получаются очень интересные локации, но при этом сохраняется структура графа и понятие комнат.

Очевидно, что для генерации подземелий можно использовать самые разные подходы, поэтому не нужно ограничиваться описанным методом. Тем не менее Пьер создал генератор, который отвечает всем критериям и выдаёт нужные локации.

{ "author_name": "Владимир Семыкин", "author_type": "editor", "tags": ["\u043e\u043f\u044b\u0442","\u0438\u0441\u0442\u043e\u0440\u0438\u0438","\u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044f"], "comments": 58, "likes": 285, "favorites": 663, "is_advertisement": false, "subsite_label": "gamedev", "id": 82121, "is_wide": true, "is_ugc": false, "date": "Thu, 05 Dec 2019 12:12:51 +0300", "is_special": false }
0
58 комментариев
Популярные
По порядку
Написать комментарий...

Комнаты произвольной формы это хорошо... но как наполнять их интересным контентом?

12

С помощью фантазии) 

6

Точно. Как я мог забыть. Просто.
import fantasia

Боже благослови Python.

91

 import fantasia 

Почему бы не импортировать сразу интересную игру? 
Возможно даже сработает 
import hl3

21

У вас тут комп взорвался. В следующий раз введите существующее значение.

9

Нул референс эксэпшн

4

Увы, этот модуль не совместим начиная с версии Python 3.0

3

Давно попадалась статья как на Unity какой-то человек реализовал эту идею... он там просто заранее создал около 70 различных комнат и путем случайной генерации объединял их в данжи по 8-12 комнат. Так же в его описании было легко создать рандомную генерацию монстров, их количества, сундуков и лута в них.

3

Тут чувак не создал ни одной комнаты, а создал систему которая создает комнаты.

5

Ждем чувака, который создаст систему которая создает системы которая создает комнаты.

4

которая создает чуваков, которые создают систему, которая создает комнаты.

0

с помощью генератора интересного контента

3

Можно воспользоваться вот таким прекрасным генератором https://watabou.itch.io/one-page-dungeon

16

Столько усилий, что бы закопать сраный Грааль.

13
Транспортный хичхакер

Теперь его будет не скучно откапывать

0

Пользуюсь таким же методом, правда результаты выдаёт странные

11

Так а почему группы комнат остались не соединены между собой? ред.

0

Наверное случилась... ПОТЕРЯ данных
*badum-tss*

8
Довольный мангал

теперь понял

0
Сегодняшний историк

Is this???

0
Транспортный хичхакер

Просто юзай их этажами

–1

Или с порталами.

0
Транспортный хичхакер

Кстати, да. 

0

Я один вижу на картинке арены, соединённые коридорами?

9

Комментарий удален по просьбе пользователя

3

Это не обязательно плохо с точки зрения геймдизайна.

3

Почти все лутер-шутеры так устроены... Рогалики, зачастую, тоже...

0
Правоохранительный клуб

В том виде, в котором это преподнесено на картинка - это почти всегда плохо.

0

в результате получаются очень интересные локации

А что-нибудь вроде такого можно загенерить?

7

Какой эпизод, какая миссия? Не могу узнать ни одного элемента.

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

3

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

0
Транспортный хичхакер

Не думаю что сейчас с более совершенным геймдизайном будут проблемы. Добавят инструментов типа телепортов и срезок.

0

Конечно, без вручную сделанных супер-красивых комнат и без изысков в геймдизайне, но да, можно. Oblige последней версии с модами от сторонних разработчиков, и у тебя есть бесконечное количество уровней для дума в разных стилях, с разной сложностью и вообще что угодно. И выглядят лучше 90% вручную сделанных карт, кстати 

3

омг чыто это?

–1

На хабре видел эту или подобную статью

2
Сельскохозяйственный нос

там что-то подобное о генерации дорог было 

0
Сельскохозяйственный нос

омагад, зачем же такое делать?)

0

Ну он у себя в блоге много подобного материала публиковал

0
Сельскохозяйственный нос

интересно однако 

0
Русский нос

Некоторые говноигры только так и генерируют карту. И играешь ты в ней, как в лабиринте, тыкаясь постоянно лицом в тупиковые комнаты. 

2

Некоторые восхваляют такой "олдскул", забывая о том, что на таких картах приходится блуждать, а не играть. 
Не, блуждания хороши, но в меру. Я из-за этого бросил третий эпизод Doom (1993), т.к. после убийства всех демонов ещё полчаса блуждал, чтобы найти оставшиеся ключ-карты. 
А вот в Entropy : Zero таких моментов гораздо меньше, но там легко самому додуматься. Хотя есть трудноватое начало главы "Bad Cop".

1

В первых Diablo, последние подземелья выглядели как раз как что-то похожее на "интересный эффект" в результатах Пьера.

0

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

0

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

1

Или порталы,искажающие изначальную геометрию пространства.

0

Это куда ближе к топологии, что довольно сложно описывать в отличии от простоты и наглядности графов.

0

Это только в паре игр было. Дюк нюкем, прей 2006, 

0

комментарий удалён ред.

0
Православный историк

практиш квадратиш гут

0

Без примера кода это просто пересказ того, что уже  миллион раз было написано...

0
Правоохранительный клуб

Такие банальные вещи. Но ок )

0

Эх, Вот бы можно было найти неплохой генератор карт из твоих набросков...........)
Это бы так облегчило жизнь DM-aм с гигантскими кампаниями по 200-400 часов.

0

Есть же куча генераторов карт для мастеров.

0
Читать все 58 комментариев
{"hash":"ec1b00ef","params":{"id":"dtfru","service":1,"title":"\u041f\u0440\u044f\u043c\u043e\u0439 \u044d\u0444\u0438\u0440","isLegacy":false}}