Game AI: FSM and Behavior Trees

Halo: Combat Evolved (2001) was a revolution - players talked about the AI as if it were 'smart'. Elites sought cover, flanked, retreated, and coordinated attacks. All of this intelligence was built on Behavior Trees. Since then, BT has become the industry standard for game AI.

• **Halo, Far Cry, GTA:** Behavior Trees for NPCs with tactical behavior
• **The Sims, RimWorld:** Utility AI for simulating needs and character motivations
• **Unreal Engine BehaviorTree Editor:** a visual BT editor is built into the engine

FSM: states, transitions, and state explosion

An NPC guard stands at a post - patrolling. Spots the player - chasing. Loses sight - searching. Gets close enough - attacking. Each behavior is a **state**, transitions between them are triggered by conditions. This is a **Finite State Machine (FSM)**.

FSM is simple, easy to debug, and fast. But adding new states breaks the system: 20 states = 20x19 = 380 possible transitions. Most need to be explicitly allowed or forbidden. This is **state explosion** - the fundamental problem with FSM at scale.

**Hierarchical FSM (HFSM)** partially addresses this: states are grouped into super-states (e.g. COMBAT = CHASE + ATTACK + SEARCH). A transition into COMBAT activates the super-state; its own internal FSM runs inside. This reduces the number of explicit cross-state transitions.

Behavior Trees: a tree instead of a graph

**Behavior Tree (BT)** replaces the transition graph with a task tree. Each frame the tree is ticked from the root, visiting nodes. Each node returns SUCCESS, FAILURE, or RUNNING. The tree structure defines the behavior logic.

**Key advantage of BT:** modularity and reuse. A 'TakeCover' subtree can be plugged into any character. With FSM, this requires adding states and transitions to every specific state machine.

Blackboard: shared memory for BT

BT nodes are independent - they cannot directly exchange data. The **Blackboard** is a shared key-value dictionary read and written by all nodes in the tree. It separates perception from decision-making.

**Blackboard benefit:** multiple systems can write data independently. Vision system, hearing system, damage system - each writes to the blackboard. BT nodes only read, unaware of the data source. This allows swapping perception systems without changing the tree.

Utility AI: action selection by numeric score

FSM and BT select actions through logic (if/else, tree). **Utility AI** selects actions through numbers: each action has a utility function returning a score [0,1]. The action with the highest score wins. This is how The Sims AI works.

**The Sims (2000):** each object in the house (fridge, bed, TV) advertises its utility for each need (hunger, tiredness, fun). The Sim picks the object with the highest total score. This gives the feeling of 'living' characters - they respond to context rather than following a script.

Game AI approach hierarchy

• **FSM:** states + explicit transitions, simple for small state counts, explodes at scale
• **BT:** tick-traversed tree, Sequence (AND) + Selector (OR), readable and modular
• **Blackboard:** shared memory decoupling perception from decision-making
• **Utility AI:** numeric scores instead of logic, flexibility at the cost of predictability

Related topics

Game AI is built on top of physics and navigation systems.

• Collision Detection — AI uses collision data for navigation and obstacle avoidance
• Pathfinding: A* and Navigation Meshes — BT leaf nodes delegate movement to the pathfinding system

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

• Under what conditions is FSM preferable to Behavior Tree despite the state explosion problem?
• How can BT and Utility AI be combined in a single architecture to use the advantages of both?
• Why do near-equal scores in Utility AI cause indecisive behavior, and what architectural patterns fix this?

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

• ml-01-intro