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

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

Кейс

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

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

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

Концепт решения

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

1. Очевидно, что должна быть какая-то поведенческая система, которая будет определять, что в конкретный тик выгоднее всего для данного NPC. Это мы добавим в предусловие, так как непосредственно на саму механику диалога эта система не влияет

2. Естественно, должен быть механизм управления симуляцией – основная тик-система. Это тоже предусловия. Сразу оговорюсь, что пункты 1 и 2 могут отличаться от игры к игре как архитектурно, так и идейно. Конкретно в моём примере у меня симуляция построена по логическим "тикам".

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

4. NPC должны подойти друг к другу – у нас должен быть сервис запроса маршрута. Это тоже предусловия.

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

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

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

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

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

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

Допустим, что предусловия у вас, как и у меня есть. В рамках этой статьи я не буду рассказывать разные интересные кейсы, связанные с проектированием этих сервисов, поскольку материала очень много. В любом случае, кажется, что пункты 5-8 не тянут на полтора месяца работы по вечерам, не так ли?

Но есть еще несколько нюансов.

Поведенческая система агентов

Есть несколько подходов к тому, как организовать поведенческую систему. У меня реализован самодельный гибрид HTN + Utility. Вкратце объясню, что это такое.

HTN (Hierarchical Task Network) – это значит, что у меня есть атомарные задачи, которые могут компоноваться в более высокоуровневые задачи, те – в ещё более высокоуровневые и так далее.

Например, задача пойти в туалет складывается из следующих атомарных активностей:

1. Дойти до туалета (GoTo)

2. Использовать объект по назначению

3. Помыть руки

Задача поесть складывается из:

1. Дойти до столовой (GoTo)

2. Помыть руки

3. Взять еды

4. Сесть за стол

5. Поесть

6. Убрать за собой

Задача разговора складывается из:

1. Дойти до собеседника (GoTo)

2. Пригласить его к беседе

3. Кидать реплики (разговаривать)

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

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

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

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

Проблема

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

• Ноги (задачи перемещения)

• Руки (что-то делать руками)

• Рот (еда, питье)

И так далее.

Раньше у меня была примерно такая модель

Поведенческая тик-система создает задачу, которая наилучшим образом подходит для данного NPC и затем «тикает» эту задачу для опроса статуса. Если задача «тикается» первый раз, то она кидает запрос на создание работы на «сборочной линии» - через фабрику работ -> затем тик-система работ «тикает» активные работы, каждая работа сама отвечает на вопрос «Готова?» и, внимание, задача завершается тогда, когда на соответствующей линии нет активных работ. Это очень плохой критерий, и ниже я попробую объяснить, почему.

Во-первых, на одну и ту же линию могут прийти несколько запросов на сборку: например, агент дошел ногами от точки А до точки B и просто встал на месте – это дефолтное состояние агентов, если нет других активных действий. Но в контексте игры, «Стоять на месте» — это тоже действие, которое занимает ноги (нельзя стоять на месте и идти одновременно). Получается, что задача в принципе не завершалась и дальше по HTN-дереву алгоритм не проходил.

Во-вторых, в этой модели вам «тупой» станок, задача которого заключатся в выполнении работ, говорит о том, что работа завершена. Т.е. не вы, как постановщик задачи, решаете, когда именно задачу требуется прекратить и снять со сборочной линии, а сама линия говорит – «окей, я считаю, что на этом всё». Это плохо тем, что уровень ответственности за результат размывается между задачей (Task) и работой (Job). А ещё тем, что вы не можете обновить контекст действий и переоценить вес выполняемой работы в процессе её выполнения и, например, просто прервать её – логику прерывания надо будет прокидывать на уровень самой работы. А это уже совсем грязно.

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

Почему я раньше такого не замечал? Тут всё очень просто:

1. Простые действия вроде стоять на месте 10 секунд, или переместиться в фиксированную точку с координатами (x, y) работали абсолютно корректно даже в такой модели

2. Несмотря на то, что я занимаюсь проектом уже около 20 месяцев в свободное время – это примерно 1500 часов, я все еще оцениваю себя где-то на уровне middle (хотел поставить middle-, но передумал) разработчика, а тут решения архитектурно, мягко говоря, не простые, и, банально, я такое никогда ранее не делал, так что с первого раза не попал идеально в цель, так сказать.

Решение

Очевидно, тут требовался рефакторинг, и вот его ключевые аспекты:

1. Задача должна решать, когда завершать связанную с ней работу

2. Внедрение сквозного идентификатора Task->JobRequest->Job
   Зачем это надо? Я не хочу жестко связывать задачу и работу между собой, хочу оставить их слабо связанными, но мне нужна какая-то понятная связь между задачей и работой, чтобы я мог однозначно определить, какую работу снимать со "станка" (читай - NPC), если задача завершается. Для этой цели я не придумал ничего лучше, как сделать одинаковым идентификатор у задачи (Task) и работы (Job). Дешево и сердито.

   1. Я понял, что задачи могут сниматься по тайм-ауту – нужна какая-то защита от разного рода программных сбоев, когда по непонятным причинам задачи зависают. Чтобы они не зависали навсегда, я хочу рубить их по тайм-ауту и дать NPC второй шанс на имитацию разумного поведения.
      В общем, раскручивая эту идею дальше и придумывая разные сценарии, которые тут возникают, я пришёл к идее создания так называемых «Критериев приёмки» - классов, которые описывают различные типы условий завершения задач.
      Например, критерий по расстоянию у меня описывается так

      public class DistanceToTargetCriterion : IAcceptanceCriterion
      {
          private readonly Guid targetId;
          private readonly int maxDistance;
      
          public DistanceToTargetCriterion(Guid id, int distance)
          {
              this.targetId = id;
              this.maxDistance = distance;
          }
      
          public bool IsMet(int agentIndex, 
              IActionExecutionContextProvider actionExecutionContextProvier, 
              IAgentDecisionContext decisionCtx, 
              IWorldQueryResolver world)
          {
              var agentCell = actionExecutionContextProvier.GetByIndex(agentIndex).PositionContext.CellPosition;
              var targetCell = world.GetObjectCell(targetId);
              if (Math.Abs(agentCell.x - targetCell.x) <= maxDistance && Math.Abs(agentCell.y - targetCell.y) <= maxDistance)
              {
                  return true;
              }
              return false;
          }
      }
      

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

3. Знаю, что это плохо, но у меня не было централизованного контроллера, через который я мог бы управлять работами (Job). Еще один пункт рефакторинга – введение такого контроллера. Следующий вопрос – будет ли задача напрямую завершать связанную работу или нет? Тут смотрим на схему и видим, что между задачей и работой нет прямой связи – задача кидает запрос в очередь, который обрабатывается централизованной тик-системой в определенной фазе тика. Таким образом, тут есть развилка. Либо прокидывать жёсткую связь между задачей и работой (плохо). Либо придумать другое решение для завершения работы.
   Очевидный вариант – ввести так называемые команды, которые может кидать задача и сделать ещё одну очередь для этих команд. Тик-система бы их обрабатывала и через контроллер завершала бы задачу.

Итоговая схема выглядит примерно так:

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

Вы думаете это всё? Отнюдь, рефакторинг требовался ещё в двух местах.

Сервис поиска пути

До этого мои агенты могли перемещаться на фиксированную клетку – я говорил им, «ты, иди на клетку с позицией Vector3Int (x, y)». Т.е. целевая точка неизменна. Но, когда NPC хочет подойти к другому и поговорить, такой подход не подойдёт. Я не могу сказать агенту переместиться в фиксированную точку с координатами (x, y), потому что за время перемещения цель может сместиться и уйти из зоны диалога. В этом случае, если агенты одновременно решают подойти друг к другу, то в конце задачи перемещения они просто меняются местами - агент_1 получит в качестве целевой позиции исходную клетку агента_2, а агент_2 получит исходную клетку агента_1

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

И тут я столкнулся с необходимостью доработки своего сервиса по поиску пути. Объясню в чём суть.

Изначально, ради производительности я сделал сервис поиска пути на основе А* с распараллеливанием через C#-ные Thread-ы. То есть он работал асинхронно, и, следовательно, у NPC была задержка между временем отправки запроса и временем получения маршрута. Эта задержка приводила к тому, что не всегда – иногда агент смещался относительно той позиции, где он делал первоначальный запрос маршрута

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

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

Отсюда вытекает следующая суть рефакторинга сервиса поиска пути:

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

2. Для коротких маршрутов (если цель в «зоне видимости») я использую синхронный запрос маршрута, который возвращает путь в том же кадре. Здесь, я ввел ограничение на глубину поиска маршрута – 10-15 ячеек в длину, не более – тогда они получаются короткими, вычисление дешевое и не перегружает основной поток

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

   public interface INavigable
       {
           /// <summary> Текущий индекс узла, на котором находится объект </summary>
           public Vector3Int CurrentPosition { get; }
            /// <summary> Следующая точка, к которой движется агент </summary>
           public Vector3Int TargetPosition { get; }
           /// <summary> Маршрут агента </summary>
           public IReadOnlyList<Vector3Int> CurrentPath { get; }
           /// <summary> Индекс текущей позиции в маршруте </summary>
           public int CurrentPathIndex { get; }
           /// <summary> Устанавливает маршрут </summary>
           public void SetPath(List<Vector3Int> path);
           /// <summary> Устанавливает следующую точку движения </summary>
           public void AdvanceToNextStep();
           /// <summary> Устанавливает индекс текущей позиции агента на маршруте </summary>
           public void SetPathIndex(int step);
           /// <summary> Вызывается, когда путь пройден полностью </summary>
           public void OnPathComplete();
   }
   

Сервис опроса игрового мира

Но и это ещё не всё: давайте вернёмся к критериям приёмки и посмотрим на то, как создаётся критерий по расстоянию:

public DistanceToTargetCriterion(Guid id, int distance)

Здесь я не передаю конкретную ячейку – нет, я передаю идентификатор объекта и хочу, чтобы система как-то нашла его координату:

var targetCell = world.GetObjectCell(targetId);

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

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

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

• Хочешь ты дойти просто до туалета – окей, передаёшь идентификатор туалета, находишь его координаты – создаёшь GoTo;

• Хочешь дойти до стула – аналогично;

• Хочешь дойти до NPC – то же самое: передаёшь идентификатор агента, находишь его позицию и сравниваешь расстояние.

Разница только в том, что для каждого типа объекта логика вычисления координат может отличаться. Поэтому мне пришлось сделать вспомогательный сервис, условно говоря, «Сервис опроса игрового мира», который всегда даст ответ на вопрос «Где находится объект с таким-то идентификатором?» Для того, чтобы это сделать достаточно ввести общий интерфейс

public interface IWorldQueryProvider
{
  public bool TryResolveCellPosition(Guid id, out Vector3Int cell);
  public bool TryResolveWorldPosition(Guid id, out Vector3 pos);
}

Затем создать конкретные реализации провайдеров для различных категорий объектов и публичную "регистратуру"

public interface IWorldRegistrationService
{
    void Register(Guid id, IWorldQueryProvider provider);
    void Unregister(Guid id, IWorldQueryProvider provider);
}

Далее, надо доработать пайплайн создания объектов – теперь во всех фабриках, которые создают объекты надо не забывать регистрировать их в глобальном реестре всех объектов вместе с провайдерами. К этому времени крайне желательно, чтобы у вас были выделены чёткие пайплайны по созданию объектов - чтобы ответственность не размывалась между разными классами, а была собрана в одном месте.

Подведём итоги

Непосредственно для реализации беседы между NPC в самом минимальном объеме – без поворотов агентов друг к другу, без эффектов, без баблов – чисто базовые механики потребовали рефакторинга:

1. Сервиса поиска пути (дня 3-4)

2. Значительной переработки системы управления задачами (чуть больше трех недель). Большая часть времени на самом деле ушла на поиски решения и думанье

3. Рефакторингом системы управления работами (около недели)

4. Сервиса опроса мира (около недели)

Для того, чтобы эта механика в принципе работала, надо, чтобы в игре уже были реализованы:

1. Сервис поиска пути

2. Граф связей между агентами и поиск «знакомых» - по сути соседей по графу

3. Какая-то система управления задачами и действиями

4. Должна быть заложена база под сервис управления NPC – пайплайн создания, связи визуала с данными, запуски анимаций и их связь с работами (Job)

Здесь было бы интересно узнать ваши метрики по трудоёмкости - помните в самом начале статьи я предложил вам в качестве эксперимента попробовать оценить трудозатраты на реализацию фичи?

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

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

Да-да, у меня огромная аудитория.