Почему с некоторыми монстрами интересно играть? Графика тут конечно играет определенную роль вначале, красивая картинка радует глаз, а музыка берет за душу. Но если враг тупит, если поведение читается на раз-два, то внимание игрока начинает подмечать ошибки в целом, быстро разрушая общее впечатление, даже графоний не поможет, так устроено внимание человека. Среднее время удержания внимания на элементе игровой механике или поведении составляет не больше пяти минут. Дизайнеры игр об этом знают и стараются в пределах этого времени переключать внимание игрока на что-то другое. Вернемся к AI монстров, это же правило действует и здесь, если в течение пяти минут, NPC не показывает новых приемов в бою или поведении, то игроки считают его "тупым", много тупых и однотипных в поведении монстров вызывают только раздражение. Можно много говорить о быстром развитие ИИ общего назначения, увидеть его применение в играх, выходящим за рамки общения и диалогов вряд-ли получится в этом десятилетии. Поэтому нам остается применять проверенные временем поведенческие деревья (BT, Behavior Tree, GOAP), но тем не менее очень мощные и нейронную сеть общего назначения на печеньках.

Сейчас Behavior Trees (BT), занимают нишу высокоуровневого языка программирования, который широко используется в игрострое для создания правдоподобного поведения NPC и разного рода логики. Но у каждого движка этот язык будет свой.

Так было не всегда, в игры BT пришли из робототехники в конце 90-х, а до этого NPC имели алгоритмы поведения, вытесанные в камне, т.е. в коде или скриптах, зачастую сложнее, чем прошивки для космических аппаратов. С развитием технологий возникла потребность в создании все более и более сложных и умных NPC за меньшее время, способных реагировать на изменяющиеся условия и принимать решения на основе меняющейся ситуации. Решение этой задачи привело к взрывному росту сложности кода AI и затрат на его поддержку, так что уже и сами программисты не всегда справлялись, не говоря уже о дизайнерах. Первые BT широко применялись в играх "Halo 2" и "Halo 3", после чего начали быстро распространяться среди компаний. Behavior Trees представляют собой структуру дерева, в которой каждый узел(нода) представляет собой отдельный элемент поведения, такой как движение, атака, бег и другие или контроля на основе которого меняется поток исполнения.

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

Ubisoft даже прикупили пару лабораторий ИИ (например https://www.ai21.com/) и на основе их разработок сделала собственную систему для Behavior Trees, называется "Patrol". Используется сериях игр Tom Clancy и Far Cry

Она предоставляет инструменты для создания и редактирования Behavior Trees, которые определяют поведение NPC и других персонажей в игре на лету. А также визуальный рантайм дебаг, запись треков, анализ поведения, логические брекпойнтов, отключение части поведения и многое другое.

Посмотреть доклады можно тут:

Информации о конкретных системах AI, которые используют Naughty Dog нет, но в докладах на GDC несколько раз звучало название "Clyde", в дань одной из первых систем АИ в играх. Cистема ведет свою историю еще с первых игр про Дрейка и большая её часть использует Lisp в качестве основного языка игровой логики.

Посмотреть можно тут:

Одной из самых продвинутых на данный момент считаются Behavior Tree в системе AI от Guirella Games, которая используется в серии игр Horizon и Death Stranding. Посмотреть проблемы реализации можно тут:

А в чём сила, брат?

Ключ к пониманию заключается в названии. В отличие от конечного автомата или кода, дерево поведения представляет собой граф состояний, которые управляют процессом принятия решений. В конечных узлах этого графа (Leaf\Node\Block), находятся завершенные блоки-команды, которые управляют NPC на уровне движка. Их называют нодами(Unreal), или блоками, реже листьями (leaf), еще реже point\flowpoint (CryEngine).

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

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

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

{
   "Tree": {
      "Root": {
         "NodeType": "Selector",
         "ChildNodes": [
            {
                "NodeType": "Task",
                "TaskType": "MoveTo",
                "NodeName": "Chase Player",
                "TaskData": {
                   "Location": "SomeLocation",
                   "AcceptanceRadius": 100.0
                }
            },
            {
               "NodeType": "Task",
               "NodeName": "Patrol"
            }
         ]
      }
   }
}

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

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

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

C++: https://github.com/BehaviorTree/BehaviorTree.CPP

Lua: https://github.com/tanema/behaviourtree.lua

Обход дерева

Алгоритм обхода это первый ключевой момент разработки своей реализации BT. От этого будет зависеть, как будет приниматься решение и какие действия будут выполняться. В классической реализации (например Unreal/Godot), дерево просматривается начиная с корня (root node) каждый фрейм, далее алгоритм спускается по активным нодам, проверяя возможность их выполнения, до текущего выполняемого узла и отдает ему управление, это могут быть различные действия, которые занимать один или несколько фреймов.

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

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

Обработка ноды (Flow)

Это второй ключевой момент разработки. Из каких бы нод или блоков (leaf) не состояло дерево, они должны возвращать минимально возможное число состояний, обычно это один из трех статусов: Success, Failed, Running (есть еще Error, но я не встречал его реального применения)

Успех (Success) - как следует из названия, сообщает о выполнение операции, возвращает управление в родительскую ноду.

Провал (Failure) - также как и успех, сообщает родительской ноде, что выполнение операции завершилось неудачей.

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

Этот минимализм является ключом к мощи поведенческих деревьев, поскольку позволяет делать универсальную и простую логику разбивая её на небольшие последовательности, каждая из которых выполняет понятный набор действий. Например, логика "Go To Point" в случае реализации на БТ, будет разбита на две части: "Find Path" и "Go To", каждый из этих блоков выполняет "свою работу", каждый из этих блоков будет возвращать статус "Running".

Если по какой-либо причине поиск пути завершился неудачей или возникли другие условия, которые не дают NPC найти или достичь целевой точки, то нода возвращает статус "Failed". Соответственно, если NPC успешно получил путь и достиг местоположения, то нода возвращает статус "Success".

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

Leaf\Node\Block

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

Composite

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

Sequence

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

for (task: tasks) { 
  task.run();
  if (task.failed()) { 
    break; 
  } 
}

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

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

Selector

Это второй фундаментальный тип последовательности. Если Sequence является оператором И (AND) и требует успешного выполнения всех потомков, чтобы завершиться успехом, то Selector вернет успех, если хотя бы один из его потомков успешно выполнится.

for (task: tasks) {
  task.run();
  if (task.success()) {
    break;
  }
}

Селектор будет обрабатывать первого потомка, и если он не выполнится успешно, будет обрабатывать второго, и если и это не выполнится успешно, то будет обрабатывать третьего, и так далее, пока не выполнится успешно хоть один из них. Или вернет неудачу, если все потомки провалятся. Selector аналогичен оператору ИЛИ (OR) и может использоваться для проверки нескольких условий, чтобы узнать, верно ли хотя бы одно из них.

Тут я немного переделал логику, и в случае если NPC не смог найти точку, дойти или пострелять, то он просто пойдет в рандомную точку.

Random selector/sequence

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

Decorator

Еще одна нода-шаблон, имеет только один узел потомок. Преобразует результат, полученный из ноды потомка, прерывает работу или повторно запускает потомка в зависимости от условий.

Inverter

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

Теперь, по новой логике, NPC будет стрелять во всех существ "не друзей".

Succeeder

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

Repeater

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

Язык для создания "умных" монстров

Если приводить аналогии с С++, то Composite/Decorator будут операторами if/for/while и другими языковыми конструкциям, а Node - как вызовы библиотечных функций, которыми они на самом деле и являются, выполняют необходимые действия на стороне движке.

Ноды могут содержать параметры, причем эти параметры могут быть взяты как из контекста переменных NPC, для которого запущено BT, так и из каких то глобальных переменных. Например, местоположение для "Goto" может быть получено с помощью ноды "Find Point" реализованной в коде или переменной внутри NPC "Find Enemy". БТ, запущенное поверх контекста NPC, в принципе может получить доступ к любым данным, которые он хранит, а использование общего контекста между всеми нодами во время обработки дерева делает разработку BT даже более понятной чем нативный код.

Context

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

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

SetVariable(varName, object) - устанавливает значение переменной с именем varName в объект object.

IsValid(object) - проверяет, является ли объект null (пустым) и возвращает успех, если так.

Кроме того, если организовать передачу контекста между деревьями, то это позволит создавать поддеревья. Т.е. BT, которые являются подчастями других BT. Например, дерево поведения "Attack Enemy" может ожидать переменную "Enemy", которую следует атаковать и родительское дерево может установить эту переменную в контексте, а затем вызывать поддерево для выполнения. В этом случае для каждого из типов NPC - заяц, волк или робот, будет выполнена единая логика из одного BT, но каждый её выполнит по своему. А behavior tree будет одно на всех, заяц фейлится на ноде Is Valid(Enemy), и поэтому живет спокойно, а вот волк постоянно огребает, потому что его BT работает правильно.

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

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

Stack

Когда только знакомишься с behavior trees, кажется что существующего функционала хватает для любой сложности. Но, как и в программировании, можно написать много кода на углубляясь в тонкости языка, так и в BT все можно реализовать на условиях и последовательностях, но при таком подходе трудно увидеть, насколько мощным может быть функционал. Как я уже говорил выше, он может быть настолько сложным, насколько это потребуется вашим дизайнерам. Например, если потребуется работа со стеком (массивом), достаточно реализовать ноды: PushToStack(item, stackVar), PopFromStack(stack, itemVar), IsEmpty(stack).

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

С помощью Repeater/Repeater Until Fail можно извлекать элементы из стека и выполнять операции над ним, пока стек не опустеет, после чего PopFromStack вернет неудачу и завершит выполнение репитера. Следующая логика заставит волка атаковать всех зайцев в округе.

Недостатки:

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

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

2. Сложность отладки: Просто дебагером тут не обойдешься, нужны специальные инструменты визуальной и временной отладки для нормальной работы. При наличии большого количества узлов отслеживание и исправление ошибок может быть затруднительным. Ошибки могут быть неочевидными из-за сложной структуры дерева.

3. Подверженность усложнению: Behavior Trees легкие в изменении, и провоцируют на усложнение общей структуры дерева, что делает их менее поддерживаемыми.

4. Статичная структура: В классических реализациях Behavior Trees структура определяется статично, что может затруднить разработку быстроменяющихся систем.

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

Материалы для ознакомления:

https://arxiv.org/pdf/1709.00084.pdf

https://py-trees.readthedocs.io/en/devel/

https://dev.epicgames.com/community/learning/tutorials/qzZ2/behavior-tree-theory

https://github.com/BehaviorTree/Groot

https://github.com/BehaviorTree/BehaviorTree.CPP

https://opensource.adobe.com/behavior_tree_editor/#/editor

https://www.csc.kth.se/~miccol/Michele_Colledanchise/Publications_files/2013_ICRA_mcko.pdf