Процедурно генерируемые карты — базовая особенность roguelike. Для жанра, который почти является синонимом понятия «случайность» (и на то есть причины), рандомизированные карты стали простейшим способом демонстрации его ключевого элемента, потому что они влияют на многие аспекты геймплея — от стратегии исследования и тактического позиционирования до расположения предметов и врагов.
Заметьте — в советах по прохождению стратегических игр обычно описываются ключевые точки на общей карте боя и объясняется, что в них нужно делать — следуя указанной последовательности шагов, вы можете выигрывать каждый раз. Разумеется, игроки могут получать удовольствие от попыток решить головоломку, но какой бы увлекательной ни была игра, интерес пропадает после нахождения всех решений.
Поэтому рандомизированные карты обеспечивают нам бесконечную реиграбельность, каждый раз ставя перед нами разные задачи. Кроме того, удовольствие усиливается тем, что прогресс игрока зависит от его собственного навыка, а не от проб и ошибок. Схема каждой новой карты на 100% неизвестна, что тоже добавляет напряжённости процессу её изучения.
Конечно же, преимущества процедурных карт бессмысленны без большой вариативности механик и контента — однообразный hack-and-slash здесь не подойдёт. Поэтому все roguelike, выдержавшие испытание временем, имеют глубокий геймплей.
Этот пост является результатом моей работы над генерацией карт для 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
В картах 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. Заготовки подземелий
Процедурно генерируемые карты — это замечательно, но даже со встроенной в алгоритм вариативностью он не сможем создать ничего, выходящего за пределы его параметров. Это хорошо, потому что позволяет сохранять целостность стиля, но жертвой этого становятся отдельные области.
Созданные вручную фрагменты карт позволяют при необходимости восстановить нужную характерность стиля, будь то сочетание со сгенерированным контентом или важные для сюжета области, в которых требуется конкретная атмосфера. Заготовки, интегрированные в остальную часть карты, очень выделяются и запоминаются этим.
Просто глупый пример, но написание отдельного алгоритма для процедурной генерации черепов будет слишком уж большим перебором.
Заготовки позволяют отклониться от пути, который в противном случае был бы слишком повторяющимся игровым процессом (даже если повторяемость скрыта несколькими слоями случайного контента). Кроме того, они дают игрокам «общий фундамент», позволяющий обсуждать отдельные части игры. Чем больше рандомна и непредсказуема roguelike, тем больше обсуждение ограничивается «общими советами по выживанию». Неизменяемые области позволяют открывать совершенно новую категорию обсуждений — «что мы можем сделать здесь», вместо «что мы можем сделать, когда XYZ».
И это не единственная стратегия — благодаря неизменяемым областям может возникнуть совершенно новая категория историй, потому что читатели, игравшие в игру, будут чётче понимать, где происходит история, уже увидев такую же область своими глазами.
Создание заготовок
Я решил рисовать заготовки в REXPaint, назначая каждому типу ячеек разные цвета палитры и раскрашивая их на первом слое.
В первоначальных тестах использовалась та же палитра, что и в программе разработки алгоритма.
В других слоях изображения хранится дополнительная информация, потому что заготовки — это нечто большее, чем просто их схема.
Я изменил палитру, чтобы упростить процесс дизайна, придав ей чёрный фон, похожий на используемый в игре.
На рисунке выше показана полностью настроенная заготовка с тестовым контентом. В слое 2 (над слоем 1) содержится информация соединения/интеграции с картой (эта жёлтая двойка,
о которой я расскажу ниже). На слое 3 отрисованы уникальные машины/элементы интерьера (эти серые линии и прямоугольники). В слое 4 содержатся ссылки, указывающие на расположение статичных объектов (зелёные цифры/числа).
У всех заготовок, имеющих определённые объекты (а таких большинство), должен быть сопроводительный текстовый файл, в котором описаны объекты, размещаемые на слое 4.
Тестовые данные/скрипт для заготовки черепа, в которых содержится случайный ассортимент объектов. В идеале эту информацию было бы вводить/просматривать/изменять непосредственно в редакторе заготовок, но в случае Cogmind заготовки и их объекты довольно просты, поэтому я решил использовать текстовые файлы.
Объекты могут перечисляться в любом порядке, и мы можем использовать как ссылку любую букву или цифру. Дополнительные функции, в том числе возможность рандомизированных объектво, будут реализованы при необходимости — мы создали только то, что необходимо игре для работы на самом базовом уровне.
И вот как заготовка загружается в игре на настоящей карте:
В игре появляется тест черепа. (Генератор карты добавил в него лишнего робота и предмет, потому что эта область не выключена из границ случайного спауна объектов.)
Интеграция
Основная проблема с заготовками теперь заключается в том, как соединить их с остальной частью карты. Если просто позволить генератору делать всё, что ему вздумается, то мы можем превратить заготовку в хаос и уничтожить весь её смысл, поэтому тёмно-серые ячейки вокруг черепа запрещают генератору карты перекрывать их. Вместо этого мы контролируем соединения со стороны заготовки.
Во-первых, на основании инструкций из текстового файла описания карты алгоритм считывает файлы .xp (созданные REXPaint), парсит их содержимое, а затем располагает ячейки на карте (если указано, то в случайных местах), прежде чем заняться другой генерацией. Жёлтая ячейка в примере с черепом указывает на то, что когда начинается построение коридоров, механизм туннелирования должен начать копать туннель шириной 2 ячейки на юг (ближайшая граница), начиная с этой точки, а затем соединиться с остальной частью карты.
Часть файла описания карты, размещающая заготовку, где «type&» — это имя файла, содержащего изображение. Также кроме заготовок карты поддерживают другие обобщённые [FEATURE] (элементы), наиболее полезные для задания областей, находящихся за пределами действия генератора.
Так как элементы располагаются до начала туннелирования и случайной генерации, они тоже поддерживают рандомизированное размещение, поэтому, например, вы никогда не найдёте одну и ту же интересную точку в одной и той же области карты.
Применение
Вырезание черепов и других интересных форм из карты — это не совсем то, что я подразумеваю под её «характером». Заготовки идеально подходят для создания более функциональных схем, удовлетворяющих определённым требованиям игры, наподобие особых NPC и важных для сюжета областей.
Я не хочу, чтобы игроки «искали» определённую точку на карте, чтобы произошла нужная встреча. Я просто создаю её.
Вы встречаете в главном зале потенциального союзника, и если ему не понравится то, что вы скажете, на вас нападёт его прислуга, ошивающаяся в боковых комнатах, а в противном случае он пустит вас в потайной склад оружия в дальней комнате. (Или вы можете использовать сканер рельефа, чтобы выяснить, что можно просто прострелить/высверлить отверстие в дальней комнате из другой части карты и взять всё, что пожелаете.)
Примерно такой же способ используется для добавления созданного вручную контента в пещеры, хотя здесь вместо алгоритма туннелирования полезнее использовать прямые ссылки, чтобы они не вышли из под контроля и не заполонили пещеры.
Хм, мы можем зайти в переднюю дверь, или нет.
Часть 6. Генерация и заполнение пещер
До этого момента большинство карт Cogmind генерировалось в стиле «комнаты и коридоры». Широкий диапазон настраиваемых параметров в сочетании со множеством тематического контента (и заготовок!) дали этому стилю большой потенциал в создании уникального геймплея для разных областей мира.
С другой стороны, «рогалики», сочетающие в себе несколько отличающихся генераторов карт, могут гораздо лучше справиться с постановкой перед игроком новых сложностей и задач. Посмотрите на сборку некоторых из типов карт, используемых в Dungeon Crawl: Stone Soup:
Примеры вариативности генерации карт в DCSS (некоторые описания см. здесь).
Впечатляет!
Наряду с чисто геймплейной вариативностью мне нужно учитывать антураж, лор и атмосферу Cogmind, поэтому дизайн карт зависит от них, что снижает возможность слишком радикальных изменений. Но кроме полностью автоматически созданных частей мира существует возможность добавления более естественных областей, находящихся во внутренностях планеты, а именно пещер.
Разумеется, проблемы создания пещер отличаются от задач оригинальных карт и связанных с ними алгоритмов. К счастью, с точки зрения лора и геймплея пещеры имеют совершенно другое значение, и в них отсутствует «живая экосистема», используемая в основных областях мира, поэтому не нужно выполнять миграцию этих готовых систем для соответствия новой архитектуре. (Кроме того, такая миграция бы снизила эффект от использования совершенно другого генератора карт!) Поэтому все пещеры находятся в ответвлениях — эта концепция описана в разделе Layout этой статьи. Такие ответвления имеют различную композицию и предназначение; можете почитать про них, если вы ещё с ними не знакомы.
В этой части я не буду подробно рассматривать контент (поэтому в ней почти нет спойлеров); вместо этого мы изучим дизайнерские и технические решения, учитываемые при генерировании пещер.
Генерация пещер
Краткое введение в способ генерации пещер я уже делал выше, в части, посвящённой алгоритму рандомизированных клеточных автоматов. Здесь я не буду повторять базовую информацию, хотя на момент написания этой части ещё не были настроены параметры для добавления пещер в мир (изображения созданы в демо тестовой программы генератора карт), поэтому стоит взглянуть, как на самом деле выглядят в игре схемы пещер.
Во-первых, вам нужно знать, что после релиза в прошлом году в работающий генератор пещер добавлена одна вариация в виде шахт:
Полностью исследованная шахта.
По сути, это небольшие квадратные области, содержащие в себе разбросанные пещеры вперемешку с вырытыми комнатами, которые соединены туннелями.
Настоящие системы пещер намного больше, и поскольку у отдельных пещер есть больше места для расширения, они с большей вероятностью могут сгенерировать дополнительные закоулки.
Полностью открытая карта пещер без контента. На карту наложены изображения основных петель и путей прохождения.
Для справки я нарисовал иллюстрации, демонстрирующие относительно линейную структуру прохождения и основные петли. Разумеется, существуют и петли, которые можно использовать в тактических целях, но в целом их гораздо меньше, чем в других областях мира — для некоторых игроков это может очень сильно повлиять на стратегию. Дизайн в стиле «линейность с петлями» должен не позволять карте быть слишком линейной, одновременно избавляя игрока от надоедающего возврата назад. (И разумеется, игрок может самостоятельно создавать петли, разрушая нужные стены.)
Заполнение пещер
Хотя система создания процедурных схем пещер была готова ещё в 2014 году, первый этап генерации контента я добавил только в прошлом году.
Она имеет форму «встреч», при которой каждая пещер (аналогично комнатам на картах из комнат и коридоров) имеет собственный контент, полученный из пула возможных встреч, разделяющихся на четыре категории: мелочёвка, награды, риск и награды, угроза. Подробнее система встреч описана в конце поста о композиции карт.
Например, в случае шахты потенциальное распределение встреч может выглядеть так:
Шахта с распределёнными типами встреч, помеченных соответствующим цветом категории.
Эта функция использовалась для заполнения и других ответвлений, в том числе и для карт пещер в виде шахт. Но шахты относительно малы и в них содержится довольно ограниченный набор простых встреч, поэтому им не требуется поддержка заготовок, позволивших мне довольно просто создать более широкий диапазон уникального (но по-прежнему динамического) контента. Честно говоря, у меня не было достаточно времени для реализации заготовок пещер до выпуска версии игры в 2015 году, что тоже сыграло свою роль.
В полноразмерных пещерах, которых гораздо больше, чем шахт, тоже требуются встречи получше. И их определённо должно быть больше. В этих областях очень сильно могут помочь заготовки, потому что жёсткое задание контента — это медленный и подверженный ошибкам процесс. Поддержка скриптинга для встреч значительно улучшена по сравнению с описанием из предыдущей части, а в других ответвлениях также добавлено множество функций для контента заготовок.
Последнее, что мне очень требовалось — это поддержка заготовок в пещерах. Ну да, в пещерах есть поддержка заготовок, но не заготовок встреч, которые являются более важным и гибким типом.
Добавлять заготовки на карты Cogmind можно двумя способами. Первый — интегрировать их в сам генератор пещер, который даже не является частью игрового движка (т.е. его можно запустить без самого Cogmind), и по самой своей природе его возможности ограничены, потому что он располагает заготовки ещё до того, как будут сгенерированы пещеры. Поэтому эти заготовки должны были играть основную роль на карте, например, быть огромной и важной неизменяемой областью или специальными входами/выходами. Если использовать заготовки такого типа слишком активно, то в результате карты станут слишком повторяющимися и узнаваемыми, потому что эта система не очень гибка (по крайней мере, если не приложить дополнительные усилия по работе над каждой новой картой). Поэтому эффективнее будет добавлять большинство заготовок пещер с помощью второго метода — системы встреч.
Здесь возникает проблема: как интегрировать статичные заготовки в карту пещер, которая уже сгенерирована?
Сами по себе заготовки имеют заданную форму, и очевидно, что мы не можем изменять её, чтобы приспособить к окружению, поэтому единственный вариант для нас — терраформировать пещеры так, чтобы они подходили к заготовкам. Это процесс не должен влиять на связанность пещер, а результат обязан выглядеть хорошо и не превращать карту в хаос.
Я добавил два способа интеграции заготовок и пещер. Надеюсь, их будет достаточно.
Центрированные заготовки
Наиболее легко реализуемая заготовка пещеры очень навязчива, она просто вставляется в геометрический центр родительской пещеры. (Надо напомнить, что здесь под пещерой я подразумеваю отдельную комнату-пещеру, одну из многих, составляющих систему пещер.) Вот пример заготовки-аванпоста, вставленной прямо в достаточно большую пещеру:
Геометрическое центрирование аванпоста в родительской пещере.
Заметьте, что территория аванпоста полностью переписывает находящиеся под ним замкнутые и открытые области, а вокруг него имеется открытая буферная зона. Решение радикальное, но вполне подходящее здесь.
Я решил центрировать заготовку относительно геометрического центра её пещеры (то есть к позиции, стремящейся к самым большим открытым областям этой пещеры) на тот случай, если с одного конца родительской пещеры получится большая открытая область, а с другого — длинный протянутый коридор. В таком случаем геометрический центр пещеры будет находиться на некотором расстоянии от простого координатного центра. В такой ситуации координатный центр вероятнее всего будет нарушать одно из правил, управляющих размещением заготовок такого типа: заготовки могут накладываться на любую землю и саму родительскую пещеру, но не другие пещеры.
Одно из ограничений дизайна с центрированными заготовками заключается в том, что они должны быть прямоугольными, но в будущем я могу избавиться от этого ограничения, если оно покажется мне раздражающим. Органичные/скруглённые центрированные заготовки могут иметь тематическое предназначение, особенно в пещерах, однако технически в имеющейся системе их можно имитировать скруглением углов заготовки.
Здесь я должен напомнить читателям, что заготовки не являются статичными — многие имеют разные схемы и рандомизированный контент, поэтому даже у одного типа встречи существует большая вариативность. Это приводит забавным ситуациям для новых игроков («о, я помню это место с прошлого раза, здесь внутри стоит дружественный робот — БОЖЕ, ПОЧЕМУ ОН В МЕНЯ СТРЕЛЯЕТ»), и в то же время создаёт стратегические сложности для опытных игроков («там определённо есть полезный лут и я могу вынести обычную охрану, но стоит ли это небольшой вероятности того, что я попаду в засаду к более мощным противникам?»).
Как я упомянул несколько раз, когда говорил о структуре мира, ответвления должны стать менее предсказуемыми частями мира, по сравнению с основным комплексом, в котором активно используются процедурно управляемые системы, но они довольно постоянны и предсказуемы для опытного игрока. Таким образом, я создаю два различных типа основных областей, между которыми может перемещаться игрок. С точки зрения дизайна заготовки являются «ручным» контентом, находящимся в ответвлениях, поэтому очень важно реализовать их правильно.
Встраиваемые заготовки
Эти системы оказались сложнее.
Необходимо было найти способ добавления областей заготовок, которые бы почти не влияли на структуру, чтобы создать более стандартную систему пещер, в которой игрок находит интересные встречи вне основного маршрута, или хотя бы так, чтобы они не были вставлены прямо посередине пещеры. Это означало, что мне нужно найти способ вырывания областей для заготовок на границах существующих пещер. То есть для таких раскопок необходимо было достаточное пространство, а также способ эффективного нахождения таких пространств.
Как видно на изображении выше, пещеры упакованы довольно плотно. Поэтому сначала я решил, что для значительного увеличения количества земли (области, которую можно копать) между пещерами нужно выполнять генерацию пещер в два этапа: в первом этапе используется похожий на клеточные автоматы процесс задания пещерообразных пятен, помечающих границы в процессе обычного процесса генерирования карты; на втором этапе выполняется обычный процесс, который автоматически будет избегать «пустот», вырытых на первом этапе. Эти пустоты в дальнейшем должны стать доступны для вырывания заготовок. Хотя это звучит и многообещающе, но чем полезнее этот подход (т.е. чем больше пустот), тем сильнее он влияет на пещеры в целом: удлиняет коридоры и увеличивает пространства между отдельными пещерами, даже если между ними нет никаких заготовок. Это решение показалось мне слишком чрезмерным.
Существует гораздо более простая альтернатива, не снижающая целостность уже готовых схем пещер: можно просто расширить прокапываемую область вокруг внешних границ карты. Теперь у нас будет много места для копания! Затем наступает следующий этап: где именно начинать копать? На глаз это определить очень просто — мы сразу можем увидеть места, идеально подходящие для выкапывания небольших пещер, но в коде пещеры являются просто пронумерованными областями со списком внутренних координат. Поэтому на этом этапе вопрос заключался в подборе минимального набора правил, позволяющего выполнять поиск подходящих мест и удовлетворять всем условиям и потенциальным схемам при вырывании областей под заготовки.
На выработку подходящего набора правил у меня ушло два часа.
Получившиеся правила оказались довольно грубым перебором, но они работали, поэтому я решил их использовать.
Шаги по встраиванию заготовки в стену пещеры.
- Выбираем случайную заготовку для заданной встречи и поворачиваем её, чтобы она смотрела в случайную сторону света.
- Выбираем случайную открытую ячейку в пещере, которая должна стать одним передним углом местоположения заготовки. Затем на основании длины передней грани заготовки определяем, где должен находиться противоположный угол. Если второй угол находится за пределами пещеры, то пробуем подобрать другие точки.
- Измеряем расстояние вдоль воображаемых сторон заготовки, пока она не столкнётся со стеной.
- У каждой заготовки есть задаваемое вручную значение «максимальной протяжённости» (maxProtrusion). Оно является ограничением глубины, на которую она может вдаваться в родительскую пещеру. Если расстояние, измеренное по любой из сторон, превышает значение maxProtrusion, то сдвигаем углы обратно к стене, пока оба значения не будут в пределах этого значения. (Если расстояния, при котором значение протяжённости можно соблюсти с обеих сторон, то возвращаемся к этапу 2.)
- Проверяем правильность целевой области заготовки: «внешний прямоугольник» не может содержать лестниц (потому что он перезапишет их) а «внутренний прямоугольник» может быть только землёй — не допускаются даже открытые области той же пещеры, потому что они могут создавать неожиданные/нежелательные дополнительные входы в область заготовки.
- Также проверяем, что существует стена хотя бы толщиной в одну ячейку вдоль сторон и задней части внутреннего прямоугольника (то есть он, например, не касается непосредственно другой открытой пещеры или области заготовки).
- Располагаем заготовку на карте! Затем преобразуем в стену все ячейки земли вокруг внешней границы, которые соседствуют с открытым пространством заготовки.
- Добавляем объекты в соответствии с описанием заготовки, например, терминал, позволяющий открыть дверь и подобрать кучу отличного оружия.
Если в течение определённого количества попыток в текущей пещере не найдено подходящих областей, то пробуем подобрать другие случайные заготовки встречи, а если и они не подходят, то переходим к следующей пещере. (Встречи выбираются первыми, поэтому задача заключается в нахождении подходящего для них места.)
В отличие от центрированных заготовок, встраиваемые заготовки могут быть не прямоугольными, потому что их стороны и задние границы гарантировано будут находиться в земле, то есть их внешний вид в любом случае будет напоминать пещеру, как показано в примере выше.
Показанные выше схемы отрисованы в REXPaint. Вот скриншоты реальных заготовок, сгенерированных в игре:
Пример встраиваемой заготовки в игре.
Автор: PatientZero
