Генерация и население уровней для жанра dungeon crawler

Компьютерная генерация

Eye Of the Beholder (DOS, 1993)

Думаю, тут почти все знают, что такое данжн кроулер, а кто не знает, тому подскажет Гугл.

Я ставлю и рассматриваю две цели в данной статье.

  1. Генерировать подземелье с отдельными областями, обладающими своими архитектурными особенностями.
  2. Указывать шансы спауна тех или иных видов объектов (враги, сундуки, двери) в зависимости от областей на карте.

В плане механики я ориентируюсь на эпохальную игру своего времени - Eye Of Beholder. Только там не было генерации.

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

Этот пост — не «Игра изнутри», скорее «Движок изнутри». Но так как движок — Game Maker, то это скорее суб-движок. Короче, все всё поняли, кому надо.

 

1. Генерация уровней/локаций/карт/пространств

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

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

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

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

Итак, алгоритмы и структуры данных, которые я придумал.

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

  1. Выбираем число N между 10 и 15 — это будет количество комнат.
  2. Инициализируем нулями двухмерный массив размера N на N. Он будет хранить, какая комната с какой соединена. Математики называют это матрицей инцидентности.
  3. Массив проходим по почти-диагонали, устанавливая все элементы оной в единицу (истину, то есть соединение комнат на пересечении текущих строки и столбца). Под почти-диагональю я имею в виду диагональ, но плюс одна клетка вправо, а в последней строке соответственно будет первый элемент. Для пояснения:

    0100...0
    0010...0
    0001...0
    ..................
    0000...1
    1000...0

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

  4. Рандомно выбранные комнаты «соединяем» между собой, выставляя единицы в рандомные места этого же массива. Также есть идея ставить не единицы, а двойки, что будет обозначать закрытые комнаты, для открытия которых нужны ключи. Ключи можно будет в свою очередь получать от монстров, сундуков или NPC. Итого мы имеем один точно соединённый главный маршрут и побочные локации, в которые можно и не заходить. Правда может выйти смешной случай (точнее по этому алгоритму именно он и выходит), что в одну и ту же комнату ведёт одновременно и ход 1 (открытый) и ход 2 (закрытый). Поэтому, если использовать закрытые ходы, имеет смысл отсоединять от комнаты с только что назначенным ходом 2 все остальные ходы. Ну, понятно, можно делать ходы 3 ещё большей или меньшей секретности или другого назначения.

Это всё была работа ещё не с картой, а только со структурами данных (то есть с левой частью иллюстраций выше). Теперь карта.

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

  1. Инициализировать двухмерный массив единицами (так как это стены).
  2. «Поставить» в массив прямоугольники — просто назначить им координаты, но не трогать сам массив. Ставить их можно по-разному, но я предлагаю начальные координаты раскидывать просто рандомно, а потом, проверяя столкновение каждого прямоугольника с каждым другим, постепенно разносить их в стороны, причём с учётом того что вокруг каждого из них должна быть оболочка в 1 единицу расстояния карты — иначе две комнаты сливаются в одну. Хотя, иногда это может быть и хорошо? Как альтернатива, можно не разводить комнаты, а ставить их одна в другую, как на второй иллюстрации. Тогда с коридорами работать вообще не нужно — достаточно просто рисовать комнаты со стенами внутри комнат и «открывать» им вход, удаляя стену с той или иной стороны. Тогда пункты 3-5 не нужны.
  3. «Отрисовать» на этом массиве все прямоугольники, то есть задать нули во все области, которые им соответствуют.
  4. Вспомнить по существование массива соединений между комнатами и «поставить» в массив коридоры между комнатами. Вообще говоря, нужно проверять, чтобы коридоры между собой не пересекались, и тем более чтобы не вели в комнаты, в которые они вести не должны. Задача не совсем из простых, но то или иное решение найти всегда можно.
  5. «Отрисовать» коридоры соответственно.

Далее следует этап 2.

2. Спаун объектов

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

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

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

  • Совершенно пустыми
  • Сокровищницами
  • Охраняемыми
  • Особо охраняемыми
  • С ловушками
  • С боссом
  • С квестом/квестами
  • Странными
  • Магазинами (можно купить чего-нибудь)
  • Пещерами (часть стен по краям «побита», и текстура соответствующая)
  • И прочее

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

А коридоры между комнатами могут быть:

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

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

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

Похожие статьи

  • jSFXR
    -Всем привет! я jSFXR! -Что ты такое? -Я как SFXR, только яваскрипт -нононо! Ведь тебя можноисполЬЗОВАТЬ ПРЯМ В БРАУЗЕРЕ! -Конечно -А ну-ка иди сюда! Так я и сделал. И вот ...
  • synthWave — основной компонент звукогенератора bfxr версии 1.4.1
    Это пост о том, по каким принципам и в каком порядке генерируется звук в bfxr — популярном в среде инди-геймдевелоперов генераторе аудио, доступного на момент написания поста...
  • Генерация мира: Ландшафт и характеристики местности
    Что нам стоит мир построить?Задачи генерации целого мира в игре никогда не давала мне покоя. Полностью созданный мир на основе псевдо-случайных чисел делает опыт каждого игрока ...
  • Недообзор (Ретро): Volfied
    В то время, когда у меня был очень старый компьютер, угловатый монитор, я играл в старые DOS'вские игры. Их было много, однако были те, в которые играл (чуть ли не) постоянно....
14 комментариев
Eldar

Интересная тема. Для начала, хочу немного поправить:

Математики называют это матрицей инцидентности.

Эта матрица называется матрицей смежности. И да, она удобна и полезна. А вот матрица инцидентности, на мой взгляд, громоздка и нужна только для каких-нибудь слишком странных графов. Например, с рёбрами, которые ведут из одной вершины в эту же вершину.

http://www.progamer.ru/dev/procedural-dungeon-generation.htm — вот я как раз недавно видел статью с ещё одним алгоритмом генерации подземелий. Она не ориентирована на dungeon crawler'ы, но, похоже, тоже интересная.

Проблема, решения которой я сейчас не могу понять у тебя — это планарность графа подземелья. Хотя, возможно ты просто не добавляешь слишком много рёбер. Ну и я не до конца осознал переход между графом и подземельем. С самими комнатами ещё всё хорошо. У тебя и в статье по ссылке способ примерно одинаковый — «Раскидать случайно комнат, а потом их друг от друга отодвинуть». Но вот с коридорами, где «Задача не совсем из простых», для меня это выглядит как «Задача из очень сложных». Ведь получается, что у нас есть много комнат. И известно, какие комнаты с какими нужно связывать. Но вполне могут возникнуть ситуации, когда единственная возможная связь двух комнат будет коридором, петляющим через всё подземелье. Ну или граф просто будет непланарен.

Поэтому мне кажется, что либо нужно идти в обратную сторону (не хочется говорить: «Как в статье по ссылке», но там именно так) — сначала расположить всё это на плоскости, а потом наделать соединений, либо при проектировании графа просто держать в голове расположение всего этого на плоскости и учитывать его в алгоритме.

Xitilon
www.progamer.ru/dev/procedural-dungeon-generation.htm — вот я как раз недавно видел статью с ещё одним алгоритмом генерации подземелий. Она не ориентирована на dungeon crawler'ы, но, похоже, тоже интересная.

Вот я как раз её помнил, когда писал про комнаты это:

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

Она слишком громоздкая. Автор чего-то много мудрит — сначала делает триангуляцию, потом остовное дерево ищет, потом выкидывает часть, потом возвращает часть (Зачем, спрашивается, выкидывал лишнее? Можно ведь быть выкидывать ровно столько сколько нужно). Вот про коридоры там неплохо написано, а всё остальное слишком узко, для одной игры и концепта. Правда, у меня оно слишком широко, и не подходит в таком виде ни для какой игры вообще. Ну, я только начал. Это не полноценная статья, скорее размышления.

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

Кстати это пример того, что иностранные разработчики часто ведут блоги разработки на Reddit — совершенно недооценённом в бывше-СССР ресурсе.

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

Xitilon
Если же мне совсем всё надоест, я буду просто генерировать пещеры алгоритмами из Тэксса.
buntarsky
Она слишком громоздкая. Автор чего-то много мудрит — сначала делает триангуляцию, потом остовное дерево ищет, потом выкидывает часть, потом возвращает часть (Зачем, спрашивается, выкидывал лишнее? Можно ведь быть выкидывать ровно столько сколько нужно).
По словам автора/переводчика, минимальное остовное дерево ищется, чтобы гарантированно обеспечить связность комнат. А триангуляция — для дополнительных «нескучных» маршрутов. Да, слегка запутывает нехронологичность изложения.
А вот использование физического движка для «раздвигания» комнат, это из пушки по воробьям. Лихо, конечно, придумано, но… НО!
veloc1

Скорее всего видел, но все равно оставлю: http://www.roguebasin.com/index.php?title=Articles#Map

Вдруг надумаешь разные типы подземелий делать :)

DarkDes
Из этого только BSP делал и то, оно получилось каким-то полу QuadTree и это-то в генерации — корче я лихо игрался.

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

Но так и не смог ещё решить — всё будет задизайнено или же генерированное. Думал даже отдельно такой режим ввести типа «рогалик» — всё генерируется и одна жизнь и всякое такое. Хочется очень высокую реиграбельность.
Xitilon
Как много текста-то! Впрочем, иллюстрации (если так можно сказать про текстовые карты) помогают, есть пара идей. Спасибо за ссылку.
Raseri
Идея с такими статьями хороша, коленке нужна своя фишечка.
Raseri
Кстати, методы генерации — это тоже тема для конкурса.
Rs11
да чтоуж там давай сразу рандом…
Xitilon
«Генерация» и «Рандом» — разные темы. «Генерация» таки лучше.
pevzi
Eldar
Вспомнил про этот джем, но забыл, как он называется и где его искать. А гуглить было лень =)
Xitilon
Оно самое. Кстати, они его не первый раз проводят — в прошлом году был в декабре, кажется, такой же.
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.