[Перевод] Обзор техник реализации игрового ИИ
Эта статья познакомит вас с широким диапазоном концепций искусственного интеллекта в играх («игрового ИИ»), чтобы вы понимали, какие инструменты можно использовать для решения задач ИИ, как они работают совместно и с чего можно начать их реализацию в выбранном движке.
Я буду предполагать, что вы знакомы с видеоиграми, немного разбираетесь в таких математических концепциях, как геометрия, тригонометрия и т.д. Большинство примеров кода будет записано псевдокодом, поэтому вам не потребуется знание какого-то конкретного языка.
Игровой ИИ в основном занимается выбором действий сущности в зависимости от текущих условий. В традиционной литературе по ИИ называет это управлением «интеллектуальными агентами». Агентом обычно является персонаж игры, но это может быть и машина, робот или даже нечто более абстрактное — целая группа сущностей, страна или цивилизация. В любом случае это объект, следящий за своим окружением, принимающий на основании него решения и действующий в соответствии с этими решениями. Иногда это называют циклом «восприятие-мышление-действие» (Sense/Think/Act):
- Восприятие: агент распознаёт — или ему сообщают — информацию об окружении, которая может влиять на его поведение (например, находящиеся поблизости опасности, собираемые предметы, важные точки и так далее)
- Мышление: агент принимает решение о том, как поступить в ответ (например, решает, достаточно ли безопасно собрать предметы, стоит ли ему сражаться или лучше сначала спрятаться)
- Действие: агент выполняет действия для реализации своих решений (например, начинает двигаться по маршруту к врагу или к предмету, и так далее)
- … затем из-за действий персонажей ситуация изменяется, поэтому цикл должен повториться с новыми данными.
Задачи ИИ реального мира, особенно те, что актуальны сегодня, обычно сосредоточены на «восприятии». Например, беспилотные автомобили должны получать изображения находящейся перед ними дороги, комбинируя их с другими данными (радара и лидара) и пытаясь интерпретировать то, что они видят. Обычно эта задача решается машинным обучением, которое особо хорошо работает с большими массивами шумных данных реального мира (например с фотографиями дороги перед автомобилем или несколькими кадрами видео) и придаёт им какое-то значение, извлекая семантическую информацию, например «в 20 ярдах передо мной есть ещё одна машина». Такие задачи называются задачами классификации.
Игры необычны тем, что для извлечения этой информации им не нужна сложная система, поскольку она является неотъемлемой частью симуляции. Нет необходимости выполнять алгоритмы распознавания изображений, чтобы обнаружить врага перед собой; игра знает, что там есть враг и может передать эту информацию непосредственно процессу принятия решений. Поэтому «восприятие» в этом цикле обычно сильно упрощено, а вся сложность возникает в реализации «мышления» и «действия».
Игровой ИИ обычно принимает во внимание следующие ограничения:
- В отличие от алгоритма машинного обучения, он обычно не тренируется заранее; при разработке игры непрактично писать нейронную сеть для наблюдения за десятками тысяч игроков, чтобы найти наилучший способ играть против них, потому что игра ещё не выпущена и игроков у неё нет!
- Обычно предполагается, что игра должна развлекать и бросать игроку вызов, а не быть «оптимальной» — поэтому даже если и можно обучить агентов противостоять игрокам наилучшим образом, то чаще всего дизайнерам нужно от них совершенного другое.
- Часто к агентам предъявляют требование «реалистичного» поведения, чтобы игроки ощущали, что соревнуются с человекоподобными противниками. Программа AlphaGo оказалась намного лучше, чем люди, но выбираемые ею ходы настолько далеки от традиционного понимания игры, что опытные противники говорили о ней как об игре против инопланетянина. Если игра симулирует противника-человека, то обычно это нежелательно, поэтому алгоритм нужно настроить таким образом, чтобы он принимал правдоподобные решения, а не идеальные.
- ИИ должен выполняться «в реальном времени». В этом контексте это означает, что алгоритм не может для принятия решения монополизировать ресурсы процессора на длительное время. Даже 10 миллисекунд на принятие решения — это слишком много, потому что большинство игр имеют всего 16–33 миллисекунды на выполнение всех операций для следующего кадра графики.
- В идеале хотя бы часть системы должна зависеть от данных, а не быть жёстко заданной, чтобы не владеющие программированием разработчики могли быстрее вносить изменения.
Узнав всё это, мы можем начать рассматривать чрезвычайно простые подходы к созданию ИИ, которые реализуют весь цикл «восприятие-мышление-действие» способами, обеспечивающими эффективность и позволяющими дизайнерам игры выбирать сложные поведения, похожие на действия человека.
Давайте начнём с очень простой игры, например с Pong. Задача игрока заключается в перемещении «ракетки», чтобы мячик отскакивал от неё, а не пролетал мимо. Правила похожи на теннисные — ты проигрываешь, если пропустил мяч. У ИИ есть относительно простая задача принятия решений о выборе направления движения ракетки.
Жёстко заданные условные конструкции
Если бы мы хотели написать ИИ для управления ракеткой, то существует интуитивно понятное и простое решение — просто постоянно двигать ракетку так, чтобы она находилась под мячом. Когда мяч достигает ракетки, она уже находится в идеальном положении и может отбить его.
Простой алгоритм для этого, выраженный в псевдокоде, может быть таким:
в каждом кадре/обновлении, пока игра выполняется:
если мяч слева от ракетки:
двигать ракетку влево
иначе если мяч справа от ракетки:
двигать ракетку вправо
Если считать, что ракетка может двигаться с не меньшей скоростью, чем мяч, то это будет идеальный алгоритм для ИИ-игрока в Pong. В случаях, когда для обработки есть не так много данных «восприятия» и мало действий, которые может выполнить агент, нам не требуется ничего более сложного.
Этот подход так прост, что в нём едва просматривается весь цикл «восприятие-мышление-действие». Но он есть.
- «Восприятие» — это два оператора «если». Игра знает, где находятся мяч и ракетка. Поэтому ИИ запрашивает у игры их позиции, таким образом «чувствуя», находится ли мяч слева или справа.
- «Мышление» тоже встроено в два оператора «если». В них находится два решения, которые в данном случае взаимно исключают друг друга, приводящие к выбору одного из трёх действий — двигать ракетку влево, двигать её вправо или ничего не делать, если ракетка уже расположена верно.
- «Действие» заключается в конструкциях «двигать ракетку влево» или «двигать ракетку вправо». В зависимости от способа реализации игры это может принимать вид мгновенного перемещения положения ракетки или задания скорости и направления ракетки, чтобы её можно было сдвинуть должным образом в другом коде игры.
Подобные подходы часто называются «реактивными» (reactive), потому что здесь существует простой набор правил (в нашем случае это операторы «если» в коде), который реагирует на состояние мира и мгновенно принимает решение о том, как действовать.
Деревья решений
Этот пример с Pong на самом деле аналогичен формальной концепции ИИ под названием «дерево решений». Это система, в которой решения выстроены в форме дерева и алгоритм должен обходить его, чтобы достичь «листа», содержащего окончательное решение о выбираемом действии. Давайте нарисуем графическое представление дерева решений для алгоритма ракетки Pong с помощью блок-схемы:
Видно, что она напоминает дерево, только перевёрнутое!
Каждую часть дерева решений обычно называют «узлом», потому что в ИИ для описания подобных структур используется теория графов. Каждый узел может быть одного из двух типов:
- Узлы решений: выбор из двух альтернатив на основании проверки какого-то условия. Каждая альтернатива представлена в виде собственного узла;
- Конечные узлы: выполняемое действие, представляющее собой окончательное решение, принимаемое деревом.
Алгоритм начинает с первого узла, назначаемого «корнем» дерева, после чего или принимает решение, в какой дочерний узел перейти на основании условия, или выполняет хранящееся в узле действие, после чего прекращает работу.
На первый взгляд преимущество дерева решений неочевидно, потому что оно выполняет абсолютно ту же работу, что и операторы «если» из предыдущего раздела. Но тут есть очень общая система, в которой каждое решение имеет ровно 1 условие и 2 возможных результата, что позволяет разработчику строить ИИ из данных, представляющих решения в дереве, и избегая жёсткого прописывания его в коде. Легко представить простой формат данных для описания подобного дерева:
| Номер узла | Решение (или «конец») | Действие | Действие |
| 1 | Мяч слева от ракетки? | Да? Проверить узел 2 | Нет? Проверить узел 3 |
| 2 | Конец | Сдвинуть ракетку влево | |
| 3 | Мяч справа от ракетки? | Да? Перейти к узлу 4 | Нет? Перейти к узлу 5 |
| 4 | Конец | Сдвинуть ракетку вправо | |
| 5 | Конец | Ничего не делать |
С точки зрения кода, нам нужно заставить систему считать каждую из этих строк, создать для каждой узел, прицепить логику решений на основании второго столбца и прицепить дочерние узлы на основании третьего и четвёртого столбцов. Нам по-прежнему нужно вручную жёстко прописывать условия и действия, но теперь мы можем вообразить более сложную игру, в которой можно добавлять новые решения и действия, а также настраивать весь ИИ изменением единственного текстового файла, в котором содержится определение дерева. Мы можем передать файл геймдизайнеру, который получит возможность настраивать поведение без необходимости перекомпиляции игры и изменения кода — при условии, что в коде уже есть полезные условия и действия.
Деревья решений могут быть очень мощными, когда их конструируют автоматически на основе большого множества примеров (например, с помощю алгоритма ID3). Он делает их эффективным и высокопроизводительным инструментом для классификации ситуации на основании входящих данных, но эта тема находится за пределами области создания дизайнерами простых систем выбора действий для агентов.
Скриптинг
Выше мы рассмотрели систему дерева решений, в которой используются заранее созданные условия и действия. Разработчик ИИ может перестраивать дерево любым нужным ему образом, но он должен рассчитывать на то, что программист уже создал все необходимые ему условия и действия. А что, если мы дадим дизайнеру более мощные инструменты, позволяющие ему создавать собственные условия, а может и свои действия?
Например, вместо того, чтобы заставлять кодера писать условия «Мяч слева от ракетки?» и «Мяч справа от ракетки?», он может просто создать систему, в которой дизайнер самостоятельно пишет условия проверки этих значений. В результате данные дерева решений могут выглядеть вот так:
| Номер узла | Решение (или «конец») | Решение | Действие |
| 1 | ball.position.x < paddle.position.x | Да? Проверить узел 2 | Нет? Проверить узел 3 |
| 2 | Конец | Двигать ракетку влево | |
| 3 | ball.position.x > paddle.position.x | Да? Проверить узел 4 | Нет? Проверить узел 5 |
| 4 | Конец | Двигать ракетку вправо | |
| 5 | Конец | Ничего не делать |
То же самое, что и раньше, но теперь в решениях есть собственный код, похожий на условную часть оператора «если». Код будет считывать из второго столбца узлы решений и вместо поиска конкретного условия (например, «мяч слева от ракетки?»), вычислять условное выражение и возвращать true или false. Это можно реализовать встраиванием скриптового языка, наподобие Lua или Angelscript, который позволяет разработчику брать объекты из игры (например мяч и ракетку) и создавать переменные, доступные из скрипта (например ball.position). На скриптовом языке обычно проще писать, чем на C++, и он не требует полного этапа компиляции, поэтому хорошо подходит для внесения быстрых изменений в логику игры и позволяет менее технически подкованным участникам команды создавать игровые функции без вмешательства кодера.
В показанном выше примере скриптовый язык используется только для вычисления условного выражения, но можно также описывать в скрипте и конечные действия. Например, данные действия вида «двигать ракетку вправо» могут стать конструкцией скрипта наподобие ball.position.x += 10, то есть действие тоже задаётся в скрипте без написания программистом кода функции MovePaddleRight.
Если сделать ещё один шаг вперёд, то можно (и это часто делается) дойти до логического завершения и написать всё дерево решений на скриптовом языке, а не как список строк данных. Это будет код, который похож на показанные выше условные конструкции, только они не «жёстко заданы» — они находятся во внешних файлах скриптов, то есть их можно изменять без рекомпиляции всей программы. Часто даже возможно изменять файл скрипта во время выполнения игры, что позволяет разработчикам быстро тестировать различные подходы к реализации ИИ.
Реакция на события
Показанные выше примеры предназначены для покадрового выполнения в простых играх наподобие Pong. Идея заключается в том, что они непрерывно выполняют цикл «восприятие-мышление-действие» и продолжают действовать на основании последнего состояния мира. Но в более сложных играх вместо вычисления всего чаще разумнее реагировать на «события», то есть на важные изменения в окружении игры.
Это не особо применимо к Pong, поэтому давайте выберем другой пример. Представьте игру-шутер, в которой враги неподвижны, пока не обнаружат игрока, после чего начинают выполнять действия в зависимости от своего класса — рукопашные бойцы могут броситься к игроку, а снайперы остаются на расстоянии и пытаются прицелиться. По сути это является простой реактивной системой — «если видим игрока, то что-то делаем» —, но её можно логически разделить на событие («видим игрока») и реакцию (выбираем отклик и выполняем его).
Это возвращает нас к циклу «восприятие-мышление-действие». У нас может быть фрагмент кода, являющийся кодом «восприятия», который проверяет в каждом кадре, видит ли враг игрока. Если нет, то ничего не происходит. Но если он видит, то это создаёт событие «видим игрока». В коде будет отдельная часть, в которой говорится: «когда происходит событие «видим игрока», то делаем «xyz», а «xyz» — это любой отклик, которым мы хотим обрабатывать мышление и действие. Для персонажа-бойца можно подключить к событию «видим игрока» отклик «бежать и атаковать». Для снайпера мы подключим к этому событию функцию отклика «спрятаться и прицелиться». Как и в предыдущих примерах, мы можем создавать такие ассоциации в файле данных, чтобы их можно было быстро изменять без пересборки движка. Кроме того, возможно (и это часто используется) писать такие функции откликов на скриптовом языке, чтобы могли создавать сложные решения при возникновении событий.
Хотя простые реактивные системы очень мощны, существует множество ситуаций, когда их недостаточно. Иногда нам нужно принимать разные решения на основании того, чем занимается агент в текущий момент, и представить это в виде условия бывает неудобно. Иногда просто существует слишком много условий, чтобы эффективным образом представить их в виде дерева решений или скрипта. Иногда нам нужно думать заранее и оценивать, как изменится ситуация, прежде чем принимать решение о следующем ходе. Для таких задач нужны более сложные решения.
Конечные автоматы
Конечный автомат (КА, finite state machine, FSM) — это способ сказать иными словами, что какой-то объект — допустим, один из наших ИИ-агентов — в данный момент находится в одном из нескольких возможных состояний, и что он может переходить из одного состояния в другое. Существует конечное количество таких состояний, отсюда и название. Примером из реального мира может служить множество огней светофора, переключающееся с красного на жёлтый, потом на зелёный, и снова обратно. В разных местах есть разные последовательности огней, но принцип одинаков — каждое состояние что-то обозначает («стой», «едь», «стой, если возможно» и т.д.), в любой момент времени существует только одно состояние, а переходы между ними основаны на простых правилах.
Это хорошо применимо к NPC в играх. У охранника могут быть следующие чётко разделённые состояния:
- Патрулирование
- Нападение
- Бегство
И мы можем придумать следующие правила для перехода между состояниями:
- Если охранник видит противника, он нападает
- Если охранник нападает, но больше не видит противника, то возвращается к патрулированию
- Если охранник нападает, но его серьёзно ранили, то он сбегает
Эта схема достаточно проста и мы можем записать её жёстко заданными операторами «если» и переменной, в которой будет храниться состояние охранника и различные проверки — наличие поблизости врагов, уровень здоровья охранника и т.д. Но представьте, что нам нужно добавить ещё несколько состояний:
- Ожидание (между патрулированием)
- Поиск (когда ранее замеченный враг спрятался)
- Бегство за помощью (когда враг замечен, но он слишком силён, чтобы сражаться с ним в одиночку)
И варианты выбора, доступные в каждом состоянии обычно ограничены — например, охранник, вероятно, не захочет искать потерянного из виду врага, если его здоровье слишком мало.
Рано или поздно длинный список «if » становится слишком неуклюжим, и помочь здесь может формализованный подход к реализации состояний и к переходов между ними. Для этого мы рассматриваем все состояния и под каждым состоянием пперечисляем все переходы к другим состояниям вместе с необходимыми для них условиями. Также нам нужно указать исходное состояние, чтобы мы знали, с чего начать, прежде чем применять другие условия.
При каждом обновлении (или «цикле») мы проверяем текущее состояние агента, просматриваем список переходов и если условие перехода соблюдено, то переходим к новому состоянию. Состояние «Ожидание» проверяет в каждом кадре или цикле, истекло ли время 10-секундного таймера. Если истекло, то оно запускает переход к состоянию «Патрулирование». Аналогичным образом состояние «Нападение» проверяет, не мало ли здоровья у агента, и если это так, то выполняет переход в состояние «Бегство». Так обрабатываются переходы между состояниями —, но как насчёт поведений, связанных с самими состояниями? С точки зрения выполнения самих действий для состояния обычно существует два вида прикрепления действий к КА: Пример первого вида: состояние «Патрулирование» в каждом кадре или цикле продолжает перемещать агента по маршруту патрулирования. Состояние «Нападение» в каждом кадре или цикле пытается начать атаку или переместить в позицию, откуда она возможна. И так далее. Пример второго вида: рассмотрим переход «если враг видим и враг слишком силён → Поиск помощи». Агент должен выбрать, куда двигаться для поиска помощи, и хранить эту информацию так, чтобы состояние «Поиск помощи» знало, куда двигаться. Аналогично, в состоянии «Поиск помощи», когда помощь найдена, агент снова возвращается в состояние «Нападение», но в этот момент он хочет сообщить дружественному персонажу об угрозе, поэтому может существовать действие «сообщить другу об опасности», выполняемое при этом переходе. И здесь мы снова можем рассмотреть эту систему с точки зрения «восприятия-мышления-действия». Восприятие встроено в данные, используемые логикой переходов. Мышление встроено в переходы, доступные для каждого состояния. А действие выполняется действиями, совершаемыми периодически в состоянии или при переходе между состояниями. Эта простая система хорошо работает, хотя иногда постоянный опрос условий перехода может быть затратным процессом. Например, если каждому агенту нужно выполнять в каждом кадре сложные вычисления для определения видимости врагов и принятия решения о переходе от патрулирования к нападению, то на это может уходить много процессорного времени. Как мы видели раньше, можно воспринимать важные изменения состояния мира как «события», которые обрабатываются после того, как они произошли. Поэтому вместо того, чтобы в каждом кадре явным образом проверять условие перехода «может ли мой агент увидеть игрока?», мы можем создать отдельную систему видимости, выполняющую эти проверки чуть менее часто (например, 5 раз в секунду), и создающую событие «игрок видим» при срабатывании проверки. Оно передаётся конечному автомату, у которого теперь есть условие перехода «Получено событие «игрок видим», и которое реагирует на него соответствующим образом. Получившееся поведение будет аналогичным, за исключением едва заметной (и даже увеличивающей реалистичность) задержки реакции, но производительность увеличится благодаря переносу «восприятия» в отдельную часть программы.
Вероятно, вы также заметили, что в нашем примере есть много дублируемых переходов. Большинство переходов в состоянии «Ожидание» идентичны переходам в состоянии «Патрулирование», и было бы неплохо избежать дублирования этой работы, особенно если мы захотим добавить ещё больше похожих состояний. Будет логично соединить «Ожидание» и «Патрулирование» в какую-нибудь группу «Небоевые состояния», имеющую только один общий набор переходов в боевые состояния. Если мы представим эту группу как состояние, то сможем рассматривать «Ожидание» и «Патрулирование» «подсостояниями» этого состояния, что позволит нам более эффективно описывать всю систему. Пример использования отдельной таблицы переходов для нового небоевого подсостояния: Основные состояния:
Идеальной в такой ситуации была система, в которой решения о том, в каком состоянии находиться, существуют отдельно от самих состояний, чтобы мы могли изменить всего лишь один элемент, а переходы всё равно обрабатывались правильно. Именно здесь нам пригодятся деревья поведений. Существует несколько способов реализации деревьев поведений, но суть для большинства одинакова и очень похожа на упомянутое выше дерево решений: алгоритм начинает работу с «корневого узла», и в дереве есть узлы, обозначающие решения или действия. Однако здесь существуют ключевые отличия:
Можно заметить, что у нас пока нет перехода для возврата в состояние «Ожидание» из «Патрулирования» — и тут нам пригодятся безусловные декораторы. Стандартным узлом-декоратором является «Повтор» (Repeat) — у него нет условий, он просто перехватывает дочерний узел, возвращающий «успешно» и снова выполняет дочерний узел, возвращая «выполняется». Новое дерево выглядит так:
Именно этим и занимается системы на основе полезности — это такие системы, в которых в распоряжении агента есть множество действий, и он выбирает выполнение одного на основании относительной полезности каждого действия. Полезность здесь — это произвольная мера важности или желательности для агента выполнения этого действия. Благодаря написанию функций полезности для вычисления полезности действия на основании текущего состояния агента и его окружения, агент может проверять значения полезности и выбирать наиболее подходящее в данный момент состояние. Это тоже очень сильно напоминает конечный автомат, за исключением того, что переходы определяются оценкой каждого потенциального состояния, в том числе и текущего. Стоит заметить, что в общем случае мы выбираем переход к наиболее ценному действию (или нахождение в нём, если мы уже выполняем это действие), но для большей вариативности это может быть взвешенный случайный выбор (отдающий приоритет самому ценному действию, но допускающий выбор других), выбор случайного действия из пяти лучших (или любого другого количества), и т.д. Стандартная система на основе полезности назначает некий произвольный интервал значений полезности — допустим от 0 (совершенно нежелательно) до 100 (абсолютно желательно), а у каждого действия может быть набор факторов, влияющих способ вычисления значения. Возвращаясь к нашему примеру с охранником, можно представить нечто подобное: Состояние
Условие перехода
Новое состояние
Ожидание
ожидал в течение 10 секунд
Патрулирование
враг видим и враг слишком силён
Поиск помощи
враг видим и здоровья много
Нападение
враг видим и здоровья мало
Бегство
Патрулирование
завершён маршрут патрулирования
Ожидание
враг видим и враг слишком силён
Поиск помощи
враг видим и здоровья много
Нападение
враг видим и здоровья мало
Бегство
Нападение
врага не видно
Ожидание
здоровья мало
Бегство
Бегство
врага не видно
Ожидание
Поиск
искал в течение 10 секунд
Ожидание
враг видим и враг слишком силён
Поиск помощи
враг видим и здоровья много
Нападение
враг видим и здоровья мало
Бегство
Поиск помощи
друг видим
Нападение
Начальное состояние: ожидание
Такая схема называется таблицей перехода между состояниями. Она является сложным (и непривлекательным) способом представления КА. По этим данным также можно нарисовать диаграмму и получить сложное графическое представление того, как может выглядеть поведение NPC.
Она ухватывает саму суть принятия решений для агента на основании ситуации, в которой он находится. Каждая стрелка обозначает переход между состояниями, если условие рядом со стрелкой истинно.Иерархические конечные автоматы
Всё это хорошо, но с большими конечными автоматами становится очень неудобно работать. Если мы хотим расширить состояние «Нападение», заменив его на отдельные состояния «Рукопашная атака» и «Атака издалека», то нам придётся изменять входящие переходы от каждого состояния, настоящего и будущего, которому нужна возможность перехода в состояние «Нападение».Состояние
Условие перехода
Новое состояние
Небоевые
враг видим и враг слишком силён
Поиск помощи
враг видим и здоровья много
Нападение
враг видим и здоровья мало
Бегство
Нападение
врага не видно
Небоевое
мало здоровья
Бегство
Бегство
врага не видно
Небоевое
Поиск
искал в течение 10 секунд
Небоевое
враг видим и враг слишком силён
Поиск помощи
враг видим и здоровья много
Нападение
враг видим и здоровья мало
Бегство
Поиск помощи
друг видим
Нападение
Начальное состояние: небоевое
Небоевое состояние: Состояние
Условие перехода
Новое состояние
Ожидание
ожидал в течение 10 секунд
Патрулирование
Патрулирование
завершил маршрут патрулирования
Ожидание
Начальное состояние: ожидание
И в виде диаграммы: 
По сути это та же система, только теперь здесь есть небоевое состояние, заменяющее «Патрулирование» и «Ожидание», которое само по себе является конечным автоматом с двумя подсостояниями патрулирования и ожидания. Если каждое состояние потенциально может содержать в себе конечный автомат подсостояний (а эти подсостояния тоже могут содержать в себе собственный конечный автомат, и так далее), то у нас получился иерархический конечный автомат (Hierarchical Finite State Machine, HFSM). Группируя небоевые поведения, мы отсекаем кучу излишних переходов, и можем сделать то же самое для любых новых состояний, которые могут иметь общие переходы. Например, если в будущем мы расширим состояние «Нападение» до состояний «Рукопашная атака» и «Атака снарядом», они могут быть подсостояниями, переход между которыми выполняется на основании расстояния до врага и наличия боеприпасов, имеющими общие выходные переходы на основании уровней здоровья и прочего. Таким образом, минимумом дублированных переходов можно представить сложные поведения и подповедения.Деревья поведений
С помощью HFSM мы получили способность создавать достаточно сложные множества поведений довольно интуитивно понятным способом. Однако сразу заметно, что принятие решений в виде правил переходов тесно связано с текущим состоянием. Во многих играх требуется именно это. А аккуратное использование иерархии состояний позволяет снизить количество дублируемых переходов. Но иногда нам нужны правила, применяемые вне зависимости от текущего состояния, или применяемые почти во всех состояниях. Например, если здоровье агента снизилось до 25%, он может захотеть убежать, вне зависимости от того, находится ли он в бою, или ожидает, или говорит, или находится в любом другом состоянии. Мы не хотим запоминать, что нужно дописывать это условие к каждому состоянию, которое мы, возможно, добавим персонажу в будущем. Чтобы когда дизайнер позже скажет, что хочет изменить пороговое значение с 25% до 10%, нам не пришлось бы перебирать и изменять каждый соответствующий переход.
Небольшой набор узлов можно скомбинировать, создав большое количество сложных поведений, и часто такая схема бывает очень краткой. Например, мы можем переписать иерархический КА охранника из предыдущего примера в виде дерева поведений: 
При использовании этой структуры нет необходимости в явном переходе из состояний «Ожидание» или «Патрулирование» в состояния «Нападение» или любые другие — если дерево обходится сверху вниз и слева направо, то правильное решение принимается на основании текущей ситуации. Если враг видим и у персонажа мало здоровья, то дерево завершит выполнение на узле «Бегство», вне зависимости от предыдущего выполненного узла («Патрулирование», «Ожидание», «Нападение» и т.д.).
Деревья поведения довольно сложны, потому что часто существует множество различных способов составления дерева, а поиск правильной комбинации декоратора и составляющих узлов может быть хитрой задачей. Существуют также проблемы с тем, как часто нужно проверять дерево (хотим ли мы обходить его каждый кадр или когда происходит что-то, способное повлиять на условия?) и со способом хранения состояния относительно узлов (как мы узнаем, что ждали 10 секунд? Как мы узнаем, сколько узлов было выполнено в последний раз, чтобы правильно завершить последовательность?) Поэтому существует множество разных реализаций. Например, в некоторых системах наподобие системы деревьев поведений Unreal Engine 4 узлы-декораторы заменены на строковые декораторы, которые проверяют дерево только при изменении условий декоратора и предоставляют «сервисы», которые можно подключить к узлам и обеспечивать периодические обновления даже когда дерево не проверяется заново. Деревья поведений — это мощные инструменты, но изучение их правильного использования, особенно с учётом множества разных реализаций, может быть пугающей задачей.Системы на основе полезности (Utility)
В некоторых играх требуется существование множества различных действий, поэтому им требуются более простые централизованные правила переходов, но при этом не требуется мощь полной реализации дерева поведений. Вместо создания явного набора выборов или дерева потенциальных действий с подразумеваемыми резервными позициями, задаваемыми структурой дерева, возможно, лучше просто исследовать все действия и выбирать то, которое наиболее применимо прямо сейчас? Действие
Вычисление полезности
Поиск помощи
Если враг видим и враг силён, а здоровья мало, то возвращаем 100, в противном случае возвращаем 0
Бегство
Если враг видим и здоровья мало, то возвращаем 90, иначе возвращаем 0
Нападение
Если враг видим, возвращаем 80
Ожидание
Если находимся в состоянии ожидания и уже ждём 10 секунд, возвращаем 0, в проти
