Автоматический генератор квестов

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

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

Для торопливых: визуализация одного из полученных заданий.

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

Постановка задачи

Требования, которые я выдвинул к историям, можно сформулировать так:

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

Кроме требований к самим историям есть ещё несколько требований непосредственно к генератору:

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

Определившись с требованиями, следовало определиться с тем, что, собственно, такое квест или история. В итоге я пришёл к следующему определению:

История — это направленный ацикличный связный граф. Узлы которого описывают состояние (требования к состоянию) объектов-участников и окружающей среды на конкретном этапе истории, а рёбра определяют возможные переходы между этими этапами.

Из определения плавно вытекает идея реализации истории в виде машины состояний, которая отдаётся под управление игре.

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

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

Сам интерпретатор реализуется достаточно тривиально (в конце статьи будет ссылка на пример реализации).

Структура истории

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

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

Перемещение между узлами можно представить в виде цикла:

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

Узлы истории удобно разделить на типы, определяющие их роль:

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

Генерация истории

История может состоять из нескольких «атомарных» заданий. Например, больной NPC может отправить героя за лекарством к ведьме, которая потребует за него услугу (выполнение другого «вложенного» задания).

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

Важным моментом здесь является соединение шаблонов (помним, что в итоге у нас должен быть связный граф):

• как минимум из одного узла родительской истории должно идти ребро в стартовый узел дочерней;
• как минимум из одного конечного узла дочерней истории должно идти ребро в узел родительской.

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

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

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

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

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

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

• положительный — задание положительно повлияло на объект;
• нейтральный — задание никак не повлияло на объект;
• отрицательный — задание навредило объекту.

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

Постобработка и проверка корректности

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

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

Поэтому историю надо дополнительно обработать. Это предполагает следующие действия:

1. Активируются случайные события — некоторые узлы объединены в группы альтернативных вариантов развития истории. Из каждой группы выбирается один узел, остальные удаляются.
2. Удаляются все конечные узлы, содержащие запрещённые результаты заданий для объектов.
3. Полученный граф чистится от «висящих» узлов. «Висящими» считаются следующие типы узлов:
   • узел, который не является конечным узлом самой внешней истории и из которого не выходит рёбер.
   • узел, который не является стартовым узлом самой внешней истории и который не имеет входящих рёбер.

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

Если проверка прошла успешно, то у нас появилась новая история.

Если нет — начинаем создавать её сначала.

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

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

Ссылки

Генератор написан на Python, выложен на github под BSD лицензией:

• репозиторий: questgen
• пример интерпретатора: example.py
• примеры готовых заданий
• игра, для которой делался: http://the-tale.org