Подземелья по фэн-шую

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

Дизайн уровней — то ещё занятие. Когда вы бродите по Даунолу или разъезжаете по Либерти Сити, на вас влияет архитектура, расположение ходов, персонажей и сокровищ. Сделанные вручную уровни имеют преимущество благодаря вниманию и доводке многих дизайнеров, а вот в процедурной генерации человеческая интуиция принесена в жертву бесконечным возможностям и непредсказуемости. Возникает естественный вопрос: а нельзя получить всё и сразу? Эта статья о том, как создавать программы для дизайна, которые работали бы в сложных и гибких рамках, с которыми ежедневно сталкиваются живые дизайнеры.

Обратимся к статье Яна Хорсвилла II и Лифа Фогеда «Быстрое заселение уровня с ограничениями по играбельности». В ней описывается способ размещения объектов, таких как враги, предметы и сокровища на уровне процедурами, использующими умное программирование и математические трюки для выполнения определённых правил. Правила могут быть довольно нечёткими, вроде «за каждое сокровище игрок должен сразиться минимум с тремя монстрами», при этом уровни по-прежнему задаются случайно и имеют непредсказуемую конфигурацию. Используется несколько концепций, которые вам возможно не знакомы, но не стоит отступать — некоторые идеи действительно великолепны.

Разветвлённая структура подземелья.

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

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

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

Схема линейного подземелья.

Предположим, что в каждой комнате есть лишь один объект — монстр, сокровище или аптечка. По какому принципу они должны располагаться? В статье указано правило «Игрок должен выжить». Логично. Значит мы должны проверить все пути от начальной точки к конечной и присвоить каждой комнате значение, характеризующее «выживаемость» героя. Поскольку выживание зависит от уровня здоровья, его изменение можно считать этим значением. То есть если в комнате монстр, присваиваем ей, скажем, значение −15, а если лечебное зелье, присваиваем +20.

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

Схема линейного подземелья с монстрами и зельем.

Это крайне примитивный пример и здесь всё очевидно. Теперь рассмотрим вариант посложнее, который предлагают сами Ян и Лиф.

Макет нелинейного подземелья с множеством путей.

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

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

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

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