Game AI: FSM и Behavior Trees

Halo: Combat Evolved (2001) произвёл революцию - игроки впервые говорили об AI как об «умном». Элиты искали укрытие, флипались, отступали и атаковали скоординированно. Весь этот «интеллект» строился на Behavior Trees. С тех пор BT стали стандартом индустрии.

• **Halo, Far Cry, GTA:** Behavior Trees для NPC с тактическим поведением
• **The Sims, RimWorld:** Utility AI для симуляции нужд и мотиваций персонажей
• **Unreal Engine BehaviorTree Editor:** визуальный редактор BT встроен в движок

FSM: состояния, переходы и проблема взрыва

NPC-охранник. Стоит на посту - патрулирует. Увидел игрока - преследует. Потерял из виду - ищет. Поймал - атакует. Каждое поведение - отдельное **состояние**, переходы между ними запускаются условиями. Это и есть **Finite State Machine (FSM)**.

FSM прост, отлаживается легко, работает быстро. Но добавление новых состояний ломает систему: 20 состояний = 20×19 = 380 возможных переходов. Большинство нужно явно прописать или запретить. Это **state explosion** - главная проблема FSM.

**Hierarchical FSM (HFSM)** частично решает проблему: состояния объединяются в суперсостояния (например, COMBAT = CHASE + ATTACK + SEARCH). Переход в COMBAT активирует суперсостояние, внутри работает собственный FSM. Это уменьшает число явных переходов.

Behavior Trees: дерево вместо графа

**Behavior Tree (BT)** заменяет граф переходов деревом задач. Каждый кадр дерево «тикает» от корня, обходя узлы. Каждый узел возвращает SUCCESS, FAILURE или RUNNING. Структура дерева определяет логику поведения.

**Ключевое преимущество BT:** модульность и реиспользование. Поддерево 'TakeCover' можно подключить к любому персонажу. FSM для этого требует добавления состояний и переходов в каждый конкретный автомат.

Blackboard: общая память для BT

Узлы BT независимы - они не могут напрямую обмениваться данными. **Blackboard** - это разделяемый словарь ключ-значение, к которому читают/пишут все узлы дерева. Это разделяет восприятие (perception) и принятие решений (behavior).

**Преимущество Blackboard:** несколько систем могут писать данные независимо. Vision system, hearing system, damage system - каждая пишет в blackboard. BT-узлы только читают, не зная источника данных. Это позволяет заменять системы восприятия без изменения дерева.

Utility AI: выбор действия по числовой оценке

FSM и BT выбирают действие через логику (if/else, дерево). **Utility AI** выбирает действие через числа: каждое действие имеет функцию полезности, выдающую score [0,1]. Побеждает действие с максимальным score. Так работает AI в The Sims.

**The Sims (2000):** каждый объект в доме (холодильник, кровать, ТВ) рекламирует свою полезность для каждой нужды (голод, усталость, развлечение). Sim выбирает объект с максимальным суммарным score. Именно это даёт ощущение «живых» персонажей - они реагируют на контекст, а не следуют скрипту.

Иерархия Game AI подходов

• **FSM:** состояния + явные переходы, прост для малого числа состояний, взрывается при масштабировании
• **BT:** дерево с tick-обходом, Sequence (AND) + Selector (OR), читаем и модулен
• **Blackboard:** общая память для разделения perception и decision-making
• **Utility AI:** числовые score вместо логики, гибкость ценой предсказуемости

Связанные темы

Game AI строится поверх физики и навигации.

• Collision Detection — AI использует collision data для уклонения и навигации
• Pathfinding: A* и навигационные сетки — BT-листы делегируют движение pathfinding системе

Вопросы для размышления

• При каких условиях FSM предпочтительнее Behavior Tree, несмотря на проблему state explosion?
• Как можно комбинировать BT и Utility AI в одной архитектуре, используя преимущества обоих подходов?
• Почему одинаковые score в Utility AI приводят к нерешительному поведению и какие архитектурные решения это исправляют?

Связанные уроки

• ml-01-intro