← Модуль 11/FSM и Behavior Trees
EN
Модуль 11 · Классический контроль

FSM и Behavior Trees

То, что реально крутит NPC в шипнутых играх — и почему «скучная» классика побеждает ML в управлении.
конспект~15 мин
Суть за 20 секунд
FSM — конечный автомат: NPC в одном из состояний (Idle/Chase/Attack/Flee), переходы по событиям. Прост, детерминирован, O(1) — но при 30+ состояниях превращается в спагетти. Behavior Tree — иерархия из Sequence/Selector/декораторов/действий, обходится сверху вниз каждый кадр; узел возвращает Success/Failure/Running. BT масштабируется, переиспользуется, видим в редакторе — поэтому это индустриальный стандарт со времён Halo 2 (2004).

FSM — конечный автомат

NPC — в одном состоянии; переход триггерится событием (увидел игрока, получил урон, враг умер). Боевой пример:

Combat FSM переходы
Idle   → Chase   (игрок в радиусе видимости)
Chase  → Attack  (игрок в радиусе ближнего боя)
Attack → Chase   (игрок отошёл)
Attack → Flee    (здоровье < 25%)
Flee   → Idle    (дистанция > радиуса видимости)
Idle Chase Attack Flee
Состояний мало — видно, что NPC делает прямо сейчас. В этом сила и потолок FSM.

Сила: прост, отлаживаем (видно состояние), детерминирован (хорошо для replay), O(1)/кадр, дизайнер-френдли. Слабость: хрупок при 30+ состояниях; нет эмерджентности (не закодил — не случится); 100 NPC со сложными FSM = неподдерживаемо.

Behavior Tree — индустриальный стандарт

DAG иерархических решений, обход в глубину слева-направо. Узлы: композиты (Sequence — до первой неудачи; Selector — до первого успеха; Parallel), декораторы (Inverter, Repeater, Condition-guard), действия (листья). Каждый возвращает Success/Failure/Running.

Halo 2 Elite — боевой BT (упрощённо) дерево
Root (Parallel)
 ├─ Sequence: Combat
 │   ├─ Condition: враг виден?
 │   ├─ Selector: стратегия атаки
 │   │   ├─ Sequence: ближний бой (в радиусе? → Attack)
 │   │   ├─ Sequence: граната (в радиусе? есть? → Throw)
 │   │   └─ Sequence: дальний (есть оружие? → Shoot)
 │   └─ Action: тактическое перемещение
 └─ Sequence: Patrol (Condition: враг не виден)

Сила: иерархичность (стратегия + тактика), переиспользуемые поддеревья, визуализируется в редакторе, эмерджентность от взаимодействия поддеревьев. Слабость: всё ещё рукотворно; обход сложного дерева каждый кадр стоит денег. Halo 2 (2004) вышла на BT, Bungie написала постмортем — и понеслось: теперь BT в Unreal, Unity, Godot.

🕹 В какие игры поиграть — и что заметить

Одна задача «решить, что делает NPC» — три ступени сложности: жадный автомат на перекрёстке, дерево поведения, планировщик. По каждой: как сделано и во что сыграть, чтобы увидеть это руками.

Pac-Man 1980 · FSM на призрака

Минимум: у каждого призрака крошечный автомат из режимов Scatter / Chase / Frightened (глобальный таймер их переключает), а внутри Chase — жадный выбор клетки к своей цели. Никакого дерева, никакого планирования: четыре простых FSM дают эмерджентную «облаву», потому что цели разные (Blinky — в клетку Пакмана, Pinky — на 4 впереди).

🎮 Сыграй: запусти Pac-Man, выучи ритм — призраки разом разворачиваются, когда таймер щёлкает Scatter↔Chase (это переход состояния FSM, видимый глазом). Слопай power-pellet → все уходят в Frightened. Ты буквально смотришь на конечный автомат.

Halo 2 / 3 2004 · Behavior Tree, поворотный момент

Игра, с которой BT стали индустрией. Поведение элиты — дерево: Selector выбирает стратегию (ближний бой / граната / стрельба / отступление), Sequence проверяет условия. Видимый результат — враги, которые отступают под огнём, ищут укрытие и перегруппировываются, а не тупо прут.

🎮 Сыграй: в Halo 2/3 (или MCC) прижми элиту плотным огнём — заметь, как он разрывает дистанцию и прячется, а добитый до паники сородич бежит. Это Selector, спускающийся по приоритетам, и узлы Condition по здоровью — поведение, читаемое снаружи.

F.E.A.R. 2005 · GOAP, планирование

Следующий уровень: не «дерево заранее», а планировщик. GOAP Джеффа Оркина (Monolith) адаптирует STRIPS-планирование 1971-го: у NPC есть цель (убить игрока) и действия с предусловиями/эффектами; автомат-планировщик на лету строит цепочку под ситуацию. Отсюда легендарные солдаты-реплики: фланги, подавление, переворот столов в укрытие — никем не заскриптовано, всё выведено из целей и доступных действий.

🎮 Сыграй: в F.E.A.R. вступи в перестрелку в комнате со столами/окнами и послушай переклички («Flush him out!», «Flanking!») — они озвучивают план. Заблокируй один путь — увидишь, как враги перепланируют обход. Это GOAP, ищущий новую цепочку действий в реальном времени.

Хардкор: автоматная теория за FSM и BTможно пропустить

Moore vs Mealy

В Moore-автомате выход зависит только от состояния; в Mealy — от состояния и входа. Игровые FSM — гибрид: поведение привязано к состоянию (Moore-стиль), но переходы несут действия (Mealy-стиль). Mealy при том же поведении нужно меньше состояний.

Выразительность: FSM ⇔ регулярные языки

Конечный автомат распознаёт ровно регулярные языки. У него нет стека → он не считает неограниченно и не обрабатывает произвольно вложенное/рекурсивное поведение (нужен магазинный автомат). Практически: чистый FSM не «помнит», сколько раз что-то случилось, без явного состояния под каждый счётчик.

Почему BT, а не гигантский switch

Плоский FSM, кодирующий k независимых булевых условий, требует до 2^k состояний (взрыв состояний). Иерархические автоматы (HFSM) и BT факторизуют эту комбинаторику композицией — это и есть их реальный выигрыш, а не «больше вычислительной мощности».

Семантика BT как булева алгебра

Sequence = И с коротким замыканием (∧), Selector = ИЛИ (∨), Inverter = ¬. BT без статуса Running — монотонное и-или-дерево над условиями, то есть вычисление булевой функции. Статус Running добавляет время, превращая дерево в трансдьюсер по тикам. Тик — O(числа узлов) в худшем; реактивный BT переобходит от корня каждый кадр (в отличие от событийного FSM).

Хардкор · инженерия: где реально берутся баги game-AIможно пропустить
  • Инструменты важнее теории: 90% времени — отладка «почему NPC застрял». Визуальный дебаг текущего состояния / активного узла BT экономит дни.
  • Data-driven authoring: деревья/таблицы переходов в данных, не в коде — чтобы дизайнер правил без пересборки. Граница «код vs данные» — ключевое архитектурное решение.
  • Развязка с фреймрейтом: логика AI часто тикает реже рендера (10–20 Гц) и амортизируется по кадрам — 200 NPC с BT на 60 Гц положат фрейм.
  • Источник багов №1 — состояние: рассинхрон blackboard, гонки перцепции и решения, «залипшие» переходы. Детерминизм FSM здесь — спасение для воспроизведения.
Аналогия
FSM — светофор: жёсткие состояния, переходы по правилам, мгновенно понятно. BT — должностная инструкция с приоритетами: «сначала проверь, виден ли враг; если да — выбери лучшую из атак; иначе патрулируй». Менеджер (Selector) спускается по списку, пока что-то не «сработает».
Почему это важно
Это база, на которой держится 95% игрового AI. Прежде чем мечтать про LLM-NPC и RL, нужно уметь это — потому что контроль (когда NPC стреляет, бежит, заговорит) почти всегда останется на FSM/BT, даже если контент (реплики) генерит LLM.
🔁 За пределами игр — куда это переносится
FSM и behavior trees — это явная модель состояния/поведения (конечные автоматы, и-или-деревья решений). Они повсюду:

Бэкенд / оркестрация: workflow-движки (Temporal, Step Functions) = state machines; протокольные автоматы (TCP), регэкспы, парсеры — всё FSM.

ML / AI: агентные циклы и tool-use — это BT/FSM поверх LLM (дерево решений с условиями и фолбэками); constrained/structured decoding = конечный автомат над токенами (грамматика гарантирует валидный JSON). Марковские цепи = вероятностные FSM.

UI / системы: состояния компонентов (XState), retry/circuit-breaker — машины состояний.

Принцип: явная модель состояния отлаживаема и тестируема; где «поведение по режимам» — там FSM/BT, в любой сфере.

🔧 Запусти и поковыряй — на домашнем компе
Во что поиграть — выше (🕹). Здесь — залезть в дерево руками:
🔧 Поковырять (debug) ~40 мин, Godot
Открой Godot и поставь любой BehaviorTree-аддон (LimboAI) или собери боевой FSM из урока (Idle/Chase/Attack/Flee). Включи визуальную отладку активного узла/состояния — смотри, какой лист тикает каждый кадр. Сломай нарочно: убери условие выхода из Attack — NPC залипнет в состоянии; добавь два конкурирующих перехода — получишь дрожание между состояниями.
🧪 Потестить (глазами QA) ~15 мин
Ищи классические баги game-AI: «залипший» переход, рассинхрон blackboard (перцепция говорит «враг виден», действие — нет), осцилляцию между двумя состояниями на границе радиуса, замёрзшего NPC, у которого ни одна ветка не вернула успех. Это и есть топ-источник багов из хардкор-вкладки.
Чеклист: увидел тикающий активный узел BT/состояние FSM; сломал переход и поймал «залипание»; нашёл хотя бы одну осцилляцию или рассинхрон blackboard.
Связи
дальше
Pathfinding: A* и NavMesh — действие «двигаться к игроку» из FSM/BT под капотом вызывает поиск пути.
контраст
Классика vs ML — почему FSM/BT (детерминизм, отладка) бьют RL в управлении NPC.
дальше
LLM-NPC — LLM не заменяет FSM/BT, а живёт поверх: контроль на классике, диалог на LLM.
Вопросы пытливого ума
FSM и BT эквивалентны по выразительности?
По вычислительному классу — практически да: один тик BT вычисляет функцию, выразимую достаточно большим FSM (BT — структурированный способ авторить большой автомат). Выигрыш BT — композиционность и читаемость, не мощность. Оба выходят за регулярные языки только при добавлении неограниченной памяти (blackboard) — тогда это уже фактически программа.
Почему не один гигантский switch на все случаи?
Взрыв состояний: k независимых булевых условий → до 2^k состояний и переходов вручную, плюс путаница Moore/Mealy и неподдерживаемость. BT/HFSM факторизуют дерево композицией — пишешь O(k) узлов вместо 2^k состояний. Причина структурная, а не «вкусовая».
Sequence/Selector — это буквально и-или дерево?
Да: Sequence = ∧ (короткое замыкание на первом Failure), Selector = ∨ (на первом Success), Inverter = ¬. Без статуса Running BT — монотонное и-или-дерево над условиями, вычисляющее булеву функцию. Running добавляет время: дерево становится трансдьюсером, помнящим, какой лист «в процессе».
Чем HFSM отличается от BT, если оба факторизуют состояние?
HFSM = вложенные состояния с явными переходами (граф); BT = композиты + коды возврата, поток неявный (обход каждый тик). HFSM компактнее для «режимов» с чёткими переходами; BT — для приоритетов «попробуй A, иначе B». На практике их смешивают (BT с состояниями-листьями).
FSM — это марковская цепь, а если переходы вероятностные?
Тогда это марковская цепь в чистом виде (следующее состояние ~ распределение от текущего); её можно оценивать и оптимизировать. Добавь награды и действия — получишь MDP, и ты уже в RL. Прямой мост от «скучного» FSM к ML-части модуля.
Что почитать