NPC

NPC в SS14 используют иерархическую сеть задач (HTN). Лучший справочник для понимания того, что это такое, находится в gameaipro. Особенно полезна диаграмма на странице 9.

Быстрый старт

Чтобы заставить NPC работать:

  1. Создайте составную задачу. Она состоит из n ветвей, где каждая ветвь состоит из n задач (составных или примитивных) по порядку.
  2. Добавьте HTNComponent к NPC.
  3. Дайте NPC корневую задачу. Она должна быть составной задачей.

Теперь ваш NPC должен работать.

Чёрная доска

Все соответствующие данные для NPC хранятся в NPCBlackboard. Это Dictionary<string, object>. Некоторые данные могут извлекаться во время планирования, будучи реализованными вместо этого в виде switch case, например, если вы хотите получить координаты владельца чёрной доски.

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

На практике это хранится во временном словаре, который может очищаться.

Планирование

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

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

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

План с меньшим обходом ветвей (по аналогии с semver) считается лучшим планом, чем план с большим обходом ветвей.

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

Задачи

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

Составные задачи:

  • Имеют n ветвей.
  • Каждая ветвь может иметь предусловия, необходимые для выполнения.
  • Каждая ветвь имеет n составных или примитивных задач

Примитивные задачи:

  • Могут иметь предусловия, необходимые для выполнения.
  • Имеют метод «Plan», который используется только во время планирования. Он может потенциально завершиться неудачей (помимо предусловий) и также может привести к дальнейшим обходам ветвей.
  • Имеют оператор, который представляет собой фактический код, выполняемый во время исполнения.

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

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

Задачи реализуются в yaml следующим образом, на примере турелей:

# -- Дальний бой --
# Пытается выстрелить в цель в пределах прямой видимости и радиуса действия.
- type: htnCompound
  id: TurretCompound
  branches:
  	# Это ветвь 0. Если эта ветвь успешна, то окончательный план будет включать только эти 2 примитивные задачи.
    - tasks:
        - id: PickRangedTargetPrimitive
        - id: RangedAttackTargetPrimitive
    # Это ветвь 1. Эта составная задача помещается в стек и декомпозируется путём последовательного перебора каждой ветви.
    - tasks:
        - id: IdleSpinCompound

# Повернуться на случайный угол и бездействовать.
- type: htnCompound
  id: IdleSpinCompound
  branches:
  # Это ветвь 1, 0, так как IdleSpinCompound является ветвью 1 в TurretCompound, а это ветвь 0 в IdleSpinCompound.
    - tasks:
        - id: WaitIdleTimePrimitive
    # Выбрать новый угол и повернуться туда
  	# Это ветвь 1, 1.
    - tasks:
        - id: PickRandomRotationPrimitive
        - id: RotateToTargetPrimitive
        - id: SetIdleTimePrimitive
        - id: WaitIdleTimePrimitive


# Примитивы
- type: htnPrimitive
  id: PickRandomRotationPrimitive
  # Это фактический код, который выполняется. Он может выполняться во время планирования, а также во время обновления. Некоторые операторы могут заботиться только о планировании (как этот), чтобы выбрать некоторые данные, тогда как другие могут заботиться только о выполнении во время обновления.
  operator: !type:PickRandomRotationOperator
  	# Операторы часто принимают ключ целевой чёрной доски, откуда брать их данные.
    targetKey: RotateTarget
  
- type: htnPrimitive
  id: RotateToTargetPrimitive
  operator: !type:RotateToTargetOperator
    targetKey: RotateTarget
  
- type: htnPrimitive
  id: RandomIdleTimePrimitive
  operator: !type:RandomOperator
    targetKey: IdleTime
    minKey: MinimumIdleTime
    maxKey: MaximumIdleTime

- type: htnPrimitive
  id: WaitIdleTimePrimitive
  operator: !type:WaitOperator
    key: IdleTime
  preconditions:
    - !type:KeyExistsPrecondition
      key: IdleTime

Обновления

Большинство NPC обновляются, когда выполняются HTNOperator; однако там, где требуются сложные системы, например координация между NPC, лучше передать это выделенной системе и компоненту. Это также упрощает отладку.

Предотвращение столкновений

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

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

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

См. http://www.gameaipro.com/GameAIPro2/GameAIPro2_Chapter18_Context_Steering_Behavior-Driven_Steering_at_the_Macro_Scale.pdf для дальнейшего чтения.

Поиск пути

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

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

Граф

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

Обновление графа выглядит следующим образом:

  • Каждый грязный граф обновляется последовательно, при этом каждый грязный чанк на графе обновляется параллельно.
  • Каждый тайл в чанке подразделяется на 4x4 «хлебные крошки». Каждая из них подобна мини-узлу на графе и содержит соответствующие данные, например маску коллизий, есть ли шлюз, можно ли его сломать и т. д.
  • Затем эти мини-узлы объединяются, если у них одинаковые данные, на каждом тайле в полигоны. Например, тайл, на котором только стена, будет 1 полигоном, тогда как тайл с 2 раздвижными окнами может быть 3 полигонами (1 для открытого пространства и 1 для каждого раздвижного окна).
  • Эти данные сверяются с существующими данными. Если они совпадают, изменений не происходит. Если они отличаются, мы очищаем существующие данные, и любые пути с этим узлом становятся недействительными.
  • Затем все эти полигоны соединяются друг с другом, и мы получаем подходящий граф, который можно использовать для перемещения.

Порталы

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

Поиск пути

A* используется для получения пути к цели, а поиск в ширину (BFS) используется для расширения наружу.

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

Команды

npc показывает доступные кнопки, которые переключают другие команды. Это охватывает как команды NPC, так и команды поиска пути. showhtn показывает, чем NPC занимаются в данный момент.

Subpages