Главная » Хабрахабр » [Перевод] Процедурная генерация подземелий в roguelike

[Перевод] Процедурная генерация подземелий в roguelike

image

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

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

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

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

Этот пост является результатом моей работы над генерацией карт для Cogmind.

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

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

BSP-деревья

BSP-деревья можно использовать для создания простейших и наиболее характерных для roguelike карт — прямоугольных комнат, соединённых друг с другом коридорами.

BSP-дерево, пример 1 (источник)

BSP-дерево, пример 2 (источник)

Алгоритмы туннелирования

Алгоритмы туннелирования (tunneling algorithms) прокапывают в сплошной «земле» коридоры и комнаты, почти так же, как это бы делал настоящий архитектор подземелий. За исключением того, что при использовании алгоритмов часто получаются бесполезные или излишние пути.

Пример прокладчика туннелей (источник)

Алгоритм туннелирования с высокой степенью рандомизации Drunkard's Walk («походка пьяницы») полезен при создании пещерообразных карт со смешением открытых и замкнутых пространств.

Drunkard's Walk, пример 1 (источник)

Drunkard's Walk, 2 (источник)

Клеточные автоматы

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

Клеточные автоматы, пример 1 (источник)

Клеточные автоматы, пример 2 (источник)

Действие большинства roguelike происходит под землёй, что логично с точки зрения дизайна. Как видно из перечисленных выше типов алгоритмов, в статье я хочу поговорить о процедурной генерации подземелий. В подземельях присутствует достаточный объём отрицательного пространства, которое можно использовать для управления видимыми и невидимыми из точки обзора областями, и всё это представлено в легко усваиваемой форме, т.е. Сама рандомизированная природа «рогаликов» означает, что в какой-то момент времени (и довольно часто) игрок может встретиться с противником, к которому совершенно не готов и должен бежать. Разделение встреч с врагами на комнаты позволяет создать более напряжённый игровой процесс и умещать больше контента в небольшом пространстве. в виде прямоугольных комнат, коридоров и стен пещер. Да, когда вы пытаетесь сбежать, встреча с одним врагом может закончиться встречей с другим, но именно поэтому каждый опытный любитель roguelike посоветует вам никогда не бежать в неизвестность!

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

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

Исследование и увлекательность

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

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

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

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

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

Техника генерирования карт на основе графов, обеспечивающая общее количество петель (источник).
Ещё одной сложной задачей является расположение на картах объектов. Её решение очень сильно зависит от самой игры. Случайное расположение объектов может быть интересным (да именно так я и делал для 7DRL!), но наиболее увлекательный игровой процесс можно получить, только учитывая рельеф и разумно выбирая места. Этот этап часто зависит от параметров подземелья, чему ниже будет посвящён отдельный раздел.

Такие области-заготовки необходимо встраивать в готовые алгоритмы генерации подземелий. Стоит упомянуть, что в моей игре Cogmind используются области подземелья, частично созданные вручную. До изготовления таких заготовок у меня возникала проблема их создания и изменения; этот процесс удобнее выполнять в REXPaint в сочетании с текстовыми файлами.

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

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

Часть 2. Генерирование карты: алгоритм туннелирования

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

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

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

Почему он никогда не создаёт коридоры чётной ширины?* Думаю, что многие его недостатки никогда не становились очевидными, потому что создатель алгоритма не применял его в реальной игре: Конкретно у этого алгоритма есть некоторые странности — зачем нужны все эти бесполезные и избыточные коридоры?

Выглядит здорово, но не слишком реалистично.

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

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

Мне нравятся коридоры шириной 2 ячейки с точки зрения геймплея, потому что они узки, но всё равно дают достаточное пространство для манёвра вокруг других юнитов. Я могу не волноваться об использовании коридоров чётной ширины, потому что они с большей вероятностью создают смещённые от центра соединения, которые выглядят не очень красиво. Но в качестве стандарта для игры наподобие Cogmind скорее всего лучше будут коридоры шириной 3 ячейки, потому что бои в ней обычно ведутся на расстоянии — для подбора нужной линии стрельбы нужно достаточно пространства.

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

В поведении механизма туннелирования можно управлять множеством параметров: шириной, направлением, скоростью, вероятностью поворота, вероятностью создания комнат, размером и формой создаваемых комнат, пространством, оставляемым между механизмом и другими объектами подземелья, моментом завершения работы…

Пример: увеличенная граница между коридорами и комнатами может быть желательна, если вы не хотите облегчать игроку прокладывание пути к следующей комнате/коридору. В своём случае я сделал границу маленькой, ведь что хорошего в разрушаемом рельефе, если его нельзя использовать в свою пользу, чтобы сделать ситуации более динамичными? (Но аккуратнее — решительно настроенный враг может даже стрелять в вас сквозь стену!)

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

Многие карты Cogmind будут ещё больше, чем на 7DRL, и в них будет больше открытых пространств. Основное подземелье имело размер 100×100 на карту, а самые крупные карты будут иметь размер до 200×200. Это в четыре раза больше:

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

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

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

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

На текущем этапе генерации карт алгоритм интересует только связанность карты, её прохождение и соотношение открытых/замкнутых пространств; расположение объектов мы рассмотрим ниже. Многие области карты, которые на 7DRL пустыми, теперь будут заняты машинами, поэтому свободным будет меньшее пространство карты.

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

В версии для 7DRL было гораздо больше потайных коридоров и мест, поэтому казалось, что спрятаться проще, чем это есть на самом деле — враг может без особых проблем найти вас или даже обойти вас по короткому пути, потому что знает подземелье лучше вас!

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

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

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

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

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

Идея присутствия в соединениях коридоров терминалов использовалась ещё в самом первом макете игры.

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

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

Мы ещё вернёмся к генерируемым туннелированием картам в следующих частях поста.

Часть 3. Генерация карты: клеточные автоматы

В отличие от игры для 7DRL, которая простиралась только на десятиуровневое «основное подземелье», Cogmind будет покрывать гораздо более масштабную область. Естественно, чем больше мир, тем выше должна быть вариативность областей для исследования. Действие происходит под землёй, поэтому многие области окажутся пещерами, а для их генерирования обычно лучшим выбором являются клеточные автоматы.

(О стандартом процессе написано здесь, здесь и здесь; я не буду рассматривать его подробно.) Вместо этого я буду использовать полюбившуюся мне идею Энди “Evil Scientist” Стобирски, которую он описал в своём блоге. Но на самом деле я не буду использовать стандартное решение клеточных автоматов.

В этом методе тоже используются клеточные автоматы — мы применяем правила соседства для раскрытия и закрытия ячеек естественным образом, но вместо постоянного применения правил для всей карты одновременно мы выбираем ячейки случайно. (Мы же делаем roguelike и любим рандом, поэтому рандом и используем!)

У меня нет большого опыта работы с клеточными автоматами, но поэкспериментировав с ними, я с трудом мог настраивать их для получения хорошего результата. С точки зрения производительности при полной оптимизации метод Энди быстрее, чем стандартный, при этом даёт сравнимые результаты и при этом он намного гибче для моих целей. Разумеется, «хорошие» — это субъективная точка зрения, но то, чего я хотел, у меня не получалось достичь с помощью ванильных клеточных автоматов. Метод Энди с лёгкостью создаёт хорошие результаты. Я уверен, что вариативности можно достичь с помощью клеточных автоматов (благодаря изменению правил в процессе генерации), но это будет не так просто, как это удалось мне: Мне нужна была бОльшая вариативность, и гибкость этого метода позволила очень просто добиться множества красивых карт.

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

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

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

Один из вариантов — «выращивать» некоторые области, чтобы они снова соединялись с другими. Поэтому лучше будет создавать для соединения этих областей новые связи. Я предпочитаю соединения туннелями, потому что они 1) соответствуют нужным мне стилю и теме, а также 2) создают систему пещер из множества маленьких пещер, которые по отдельности можно считать комнатами и располагать в них предметы (это преимущество станет очевидным в следующей части, посвящённой метрикам подземелий). Второй — прорывать между ними туннели.

что я учитываю специфику его применения в игре, а он создаёт более общий генератор). Здесь моё решение немного отличается от решения мистера Evil Scientist (в основном потому. Иногда он решает рыть более широкие туннели на основании заданных параметров, а также относительного размера соединяемых пещер. В моём решении устраняется большинство U-образных сгибов, оно выполняет несколько фаз рытья коридоров, которые могут применяться не ко всем пещерам, имеет настраиваемое соотношение создаваемых как пещеры коридоров и ответвляющихся коридоров.

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

Путь прохождения квадратной пещерной карты.

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

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

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

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

Таким образом, мы сможем использовать резкий и острый стиль с длинными ответвлениями, но при этом всё будет двигаться в одном общем направлении.

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

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

Тайная база?

Часть 4. Метрики подземелий

Алгоритм редко может создать идеальную процедурно генерируемую карту, и даже это происходит, то требуется некоторая постобработка для анализа её схемы. Когда мы смотрим на созданную генератором карту, то довольно быстро можем понять, достаточно ли этой схемы для наших потребностей; также мы скорее всего заметим узкие места, в которых могут собираться враги, чтобы остановить игрока, и области, находящиеся вне основного пути, в которых могут лежать сокровища. Однако для программы карта — это просто координаты, сообщающие, чем является та или иная область, и не дающие никакой подсказки об общей композиции или схеме. Как мы можем научить игру понимать и использовать карту так же, как это делаем мы? Нам необходимы «метрики подземелий».
Первое и самое важное — следует убедиться, нужна ли нам получившаяся карта. Без ограничений результатов один алгоритм может создавать множество вариаций карт, и некоторые из них могут быть неподходящими или вообще неиграбельными. В таких случаях нам следует отказаться от такой карты и начать генерирование заново.

Композиция

Основное простейшее требование — получившийся объём играбельного, «открытого» пространства. Нижняя граница гарантирует, что карта не будет слишком сжатой, верхняя сделает её не слишком открытой.

Эти две пещеры сгенерированы одинаковым алгоритмом, отличающимся только по одному параметру: объёму требуемого открытого пространства (сверху — 15-30%, снизу — 40-60%).

Ещё одним важным требованием является количество отдельных комнат/пещер разного размера.

Эти две карты сгенерированы с помощью одинакового алгоритма, отличается только требуемое количество комнат (сверху — 20 или больше мелких комнат, снизу — 20 средних и 5 больших).

Поиск путей

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

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

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

Всё остальное

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

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

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

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

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

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

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

Нахождение пещер на карте с помощью заливки перед их соединением.

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

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

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

Как же мы можем использовать все эти собранные данные, кроме как для принятия решения о её пригодности? Самое очевидное применение — размещение предметов.

Логичнее будет хранить их по большей части в комнатах, как для реализма, так и с точки зрения геймплея («стоит ли открывать дверь, чтобы поискать детали, даже если мои сканеры показывают, что за ней есть роботы, которые могут оказаться враждебными?»). Роботы и детали в игре для 7DRL создавались без учёта того, находятся ли они в комнате или коридоре; можно было найти кучу деталей, валяющихся где-то в произвольном месте.

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

Связанность

Мой любимый инструмент аналитики систем пещер — определение относительной связанности каждой пещеры.

Визуализация связанности пещер. Чем ярче пещера, тем лучше она связана с системой.

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

Менее связанные пещеры в разных частях карты являются вероятными позициями для входов/выходов, другие станут хорошими кандидатами на размещение лута, секретов или неприятных для любопытных исследователей сюрпризов.

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

Изолированность

Все комнаты карт, созданных алгоритмом туннелирования, оцениваются по значению «изолированности». Для изолированности используется другой критерий вычисления, потому что связанность карты намного выше. Он основан на расстоянии до кратчайшего пути, который игрок может пройти от входа до выхода.

Визуализация изолированности комнат. Тёмно-красные комнаты дальше от кратчайших маршрутов по карте.

Заметьте, что чем дальше комната от пути, тем темнее её оттенок красного. Четыре входа/выхода (розовые точки) соединяются самыми короткими путями между ними (зелёные линии), затем от входа в каждую комнату выполняется поиск путей к ближайшей точке любой из этих линий. «Среднее» основано на значениях карты.) Чем более изолирована комната, тем вероятнее в ней будет содержаться что-то ценное или интересное игроку. (В этой визуализации не имеют красного оттенка все комнаты, значение относительной изолированности которой ниже среднего. Но это нормально, потому что игрок заслуживает небольшой награды за сильное отклонение от своего пути и преодоление большого количества препятствий. Разумеется, идея «изолированности» подразумевает, что игрок знает, куда двигаться, хотя на самом деле это не так!

Часть 5. Заготовки подземелий

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

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

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

Кроме того, они дают игрокам «общий фундамент», позволяющий обсуждать отдельные части игры. Заготовки позволяют отклониться от пути, который в противном случае был бы слишком повторяющимся игровым процессом (даже если повторяемость скрыта несколькими слоями случайного контента). Неизменяемые области позволяют открывать совершенно новую категорию обсуждений — «что мы можем сделать здесь», вместо «что мы можем сделать, когда XYZ». Чем больше рандомна и непредсказуема roguelike, тем больше обсуждение ограничивается «общими советами по выживанию».

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

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

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

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

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

В слое 2 (над слоем 1) содержится информация соединения/интеграции с картой (эта жёлтая двойка,
о которой я расскажу ниже). На рисунке выше показана полностью настроенная заготовка с тестовым контентом. В слое 4 содержатся ссылки, указывающие на расположение статичных объектов (зелёные цифры/числа). На слое 3 отрисованы уникальные машины/элементы интерьера (эти серые линии и прямоугольники).

У всех заготовок, имеющих определённые объекты (а таких большинство), должен быть сопроводительный текстовый файл, в котором описаны объекты, размещаемые на слое 4.

Тестовые данные/скрипт для заготовки черепа, в которых содержится случайный ассортимент объектов. В идеале эту информацию было бы вводить/просматривать/изменять непосредственно в редакторе заготовок, но в случае Cogmind заготовки и их объекты довольно просты, поэтому я решил использовать текстовые файлы.

Дополнительные функции, в том числе возможность рандомизированных объектво, будут реализованы при необходимости — мы создали только то, что необходимо игре для работы на самом базовом уровне. Объекты могут перечисляться в любом порядке, и мы можем использовать как ссылку любую букву или цифру.

И вот как заготовка загружается в игре на настоящей карте:

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

Жёлтая ячейка в примере с черепом указывает на то, что когда начинается построение коридоров, механизм туннелирования должен начать копать туннель шириной 2 ячейки на юг (ближайшая граница), начиная с этой точки, а затем соединиться с остальной частью карты. Во-первых, на основании инструкций из текстового файла описания карты алгоритм считывает файлы .xp (созданные REXPaint), парсит их содержимое, а затем располагает ячейки на карте (если указано, то в случайных местах), прежде чем заняться другой генерацией.

Часть файла описания карты, размещающая заготовку, где «type&» — это имя файла, содержащего изображение. Также кроме заготовок карты поддерживают другие обобщённые [FEATURE] (элементы), наиболее полезные для задания областей, находящихся за пределами действия генератора.

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

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

Я просто создаю её. Я не хочу, чтобы игроки «искали» определённую точку на карте, чтобы произошла нужная встреча.

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

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

Хм, мы можем зайти в переднюю дверь, или нет.

Часть 6. Генерация и заполнение пещер

До этого момента большинство карт Cogmind генерировалось в стиле «комнаты и коридоры». Широкий диапазон настраиваемых параметров в сочетании со множеством тематического контента (и заготовок!) дали этому стилю большой потенциал в создании уникального геймплея для разных областей мира.

Посмотрите на сборку некоторых из типов карт, используемых в Dungeon Crawl: Stone Soup: С другой стороны, «рогалики», сочетающие в себе несколько отличающихся генераторов карт, могут гораздо лучше справиться с постановкой перед игроком новых сложностей и задач.

Примеры вариативности генерации карт в DCSS (некоторые описания см. здесь).

Впечатляет!

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

К счастью, с точки зрения лора и геймплея пещеры имеют совершенно другое значение, и в них отсутствует «живая экосистема», используемая в основных областях мира, поэтому не нужно выполнять миграцию этих готовых систем для соответствия новой архитектуре. Разумеется, проблемы создания пещер отличаются от задач оригинальных карт и связанных с ними алгоритмов. Такие ответвления имеют различную композицию и предназначение; можете почитать про них, если вы ещё с ними не знакомы. (Кроме того, такая миграция бы снизила эффект от использования совершенно другого генератора карт!) Поэтому все пещеры находятся в ответвлениях — эта концепция описана в разделе Layout этой статьи.

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

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

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

Полностью исследованная шахта.

По сути, это небольшие квадратные области, содержащие в себе разбросанные пещеры вперемешку с вырытыми комнатами, которые соединены туннелями.

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

Полностью открытая карта пещер без контента. На карту наложены изображения основных петель и путей прохождения.

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

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

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

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

Шахта с распределёнными типами встреч, помеченных соответствующим цветом категории.

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

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

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

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

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

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

Надеюсь, их будет достаточно. Я добавил два способа интеграции заготовок и пещер.

Центрированные заготовки

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

Геометрическое центрирование аванпоста в родительской пещере.

Решение радикальное, но вполне подходящее здесь. Заметьте, что территория аванпоста полностью переписывает находящиеся под ним замкнутые и открытые области, а вокруг него имеется открытая буферная зона.

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

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

Это приводит забавным ситуациям для новых игроков («о, я помню это место с прошлого раза, здесь внутри стоит дружественный робот — БОЖЕ, ПОЧЕМУ ОН В МЕНЯ СТРЕЛЯЕТ»), и в то же время создаёт стратегические сложности для опытных игроков («там определённо есть полезный лут и я могу вынести обычную охрану, но стоит ли это небольшой вероятности того, что я попаду в засаду к более мощным противникам?»). Здесь я должен напомнить читателям, что заготовки не являются статичными — многие имеют разные схемы и рандомизированный контент, поэтому даже у одного типа встречи существует большая вариативность.

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

Встраиваемые заготовки

Эти системы оказались сложнее.

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

Поэтому сначала я решил, что для значительного увеличения количества земли (области, которую можно копать) между пещерами нужно выполнять генерацию пещер в два этапа: в первом этапе используется похожий на клеточные автоматы процесс задания пещерообразных пятен, помечающих границы в процессе обычного процесса генерирования карты; на втором этапе выполняется обычный процесс, который автоматически будет избегать «пустот», вырытых на первом этапе. Как видно на изображении выше, пещеры упакованы довольно плотно. Хотя это звучит и многообещающе, но чем полезнее этот подход (т.е. Эти пустоты в дальнейшем должны стать доступны для вырывания заготовок. Это решение показалось мне слишком чрезмерным. чем больше пустот), тем сильнее он влияет на пещеры в целом: удлиняет коридоры и увеличивает пространства между отдельными пещерами, даже если между ними нет никаких заготовок.

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

На выработку подходящего набора правил у меня ушло два часа.

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

Шаги по встраиванию заготовки в стену пещеры.

  1. Выбираем случайную заготовку для заданной встречи и поворачиваем её, чтобы она смотрела в случайную сторону света.
  2. Выбираем случайную открытую ячейку в пещере, которая должна стать одним передним углом местоположения заготовки. Затем на основании длины передней грани заготовки определяем, где должен находиться противоположный угол. Если второй угол находится за пределами пещеры, то пробуем подобрать другие точки.
  3. Измеряем расстояние вдоль воображаемых сторон заготовки, пока она не столкнётся со стеной.
  4. У каждой заготовки есть задаваемое вручную значение «максимальной протяжённости» (maxProtrusion). Оно является ограничением глубины, на которую она может вдаваться в родительскую пещеру. Если расстояние, измеренное по любой из сторон, превышает значение maxProtrusion, то сдвигаем углы обратно к стене, пока оба значения не будут в пределах этого значения. (Если расстояния, при котором значение протяжённости можно соблюсти с обеих сторон, то возвращаемся к этапу 2.)
  5. Проверяем правильность целевой области заготовки: «внешний прямоугольник» не может содержать лестниц (потому что он перезапишет их) а «внутренний прямоугольник» может быть только землёй — не допускаются даже открытые области той же пещеры, потому что они могут создавать неожиданные/нежелательные дополнительные входы в область заготовки.
  6. Также проверяем, что существует стена хотя бы толщиной в одну ячейку вдоль сторон и задней части внутреннего прямоугольника (то есть он, например, не касается непосредственно другой открытой пещеры или области заготовки).
  7. Располагаем заготовку на карте! Затем преобразуем в стену все ячейки земли вокруг внешней границы, которые соседствуют с открытым пространством заготовки.
  8. Добавляем объекты в соответствии с описанием заготовки, например, терминал, позволяющий открыть дверь и подобрать кучу отличного оружия.

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

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

Вот скриншоты реальных заготовок, сгенерированных в игре: Показанные выше схемы отрисованы в REXPaint.

Пример встраиваемой заготовки в игре.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Actions on Google: пишем простое приложение для Google Ассистента на Dialogflow и Cloud Functions for Firebase

В конце прошлого месяца состоялся официальный релиз Google Ассистента на русском языке, так что самое время разобраться, как делать свои приложения (экшены) для Ассистента на стандартном технологическом стеке Google. В этой статье мы рассмотрим создание экшена в Actions on Google, ...

[Из песочницы] Проблемы интерфейсов наземных переходов

Когда речь идет о недостатках пользовательских интерфейсов, представляются сложные, визуально перегруженные компьютерные программы, такие, как СЭД или графические редакторы. Но и в более простом интерфейсе, состоящем из одной кнопки и нескольких световых сигналов, найдется много проблем и недостатков. Пример такого ...