Game AI: Pathfinding, Behavior Trees, and NPC Design
Game AI is the art of creating believable, responsive non-player characters that enhance gameplay without frustrating players. From the adaptive enemy tactics of Halo to the companion AI in The Last of Us, great game AI makes worlds feel alive. This guide covers the essential algorithms and architectures, with references to GDC talks and engine documentation.
Pathfinding Algorithms
Pathfinding enables NPCs to navigate complex environments efficiently. The choice of algorithm and representation directly impacts performance and path quality.
A* Search in Depth
A* (A-star) remains the most widely used pathfinding algorithm in games. It combines the actual cost from the start (G) with a heuristic estimate to the goal (H) to prioritize the most promising paths first: F = G + H. The heuristic must be admissible — never overestimating the true cost — to guarantee optimality. The Manhattan distance works for 4-directional grid movement; Euclidean distance for 8-directional or free movement. Unreal Engine’s Navigation System uses A* with navigation meshes internally, but the engine also exposes pathfinding query filters that let developers modify traversal costs per area type (water, lava, rough terrain). Unity’s NavMesh Agent uses A* over a polygon-based navmesh, with off-mesh links for jumpable gaps and climbable ledges.
Navigation Mesh Generation
A navigation mesh (navmesh) represents walkable surfaces as a connected set of convex polygons. The navmesh is generated offline from level geometry: the engine identifies walkable surfaces (slope angle below a threshold, typically 45 degrees), voxelizes them, and generates a polygonal mesh from the voxel representation. The Unreal Engine NavMesh documentation describes how the Recast navigation system (developed by Mikko Mononen) generates navmeshes with configurable agent height, radius, max slope, and step height. Unity’s NavMesh Surface component provides similar controls with real-time baking preview. For dynamic obstacles, both engines support carving — temporary holes in the navmesh that agents path around, used for doors opening, debris falling, or vehicles blocking paths.
Optimization with Hierarchical Pathfinding
For large open worlds, A* on the full navmesh is too slow. Hierarchical pathfinding precomputes abstract graphs: the navmesh is divided into regions, and A* runs first on the region-level graph, then on the detailed mesh within each region along the path. The Skyrim engine (Gamebryo/Creation Engine) used this approach for its open-world NPC navigation, as discussed at GDC 2012 by Bethesda’s AI engineers. The Ant colony’s hierarchical pathfinding paper (Sturtevant & Geisberger, 2010) demonstrated that two-level abstraction reduces pathfinding time by 85–95% with negligible path quality loss.
Behavior Trees
Behavior trees (BTs) have become the industry standard for NPC decision-making, replacing finite state machines in most modern games. They provide modular, reusable, and debuggable AI logic.
Node Types and Execution Flow
A behavior tree is a directed acyclic graph composed of control flow nodes and task nodes. The root node executes its child each tick. Composite nodes control flow: Sequence nodes execute children in order (failing immediately if any child fails), Selector nodes try children in order (succeeding immediately if any succeeds). Decorator nodes modify child execution — they can invert results, repeat execution, or apply time limits. Task (leaf) nodes perform actual work: moving to a position, playing an animation, or firing a weapon. Unreal Engine’s Behavior Tree documentation provides a full reference with detailed execution order for each node type.
Blackboard and Environment Queries
The blackboard is the behavior tree’s working memory — a key-value store that holds shared state like target positions, health values, and boolean flags. Tasks and decorators read from and write to the blackboard, decoupling AI logic from data. Environment Query System (EQS) in Unreal performs spatial tests and scores locations based on configurable generators and tests. For example, an EQS query finds the nearest cover position that has line-of-sight to enemies and is outside their detection radius. GDC 2017’s “F.E.A.R. AI: The Behavioral Mathematics of Fear” demonstrated how EQS-style scoring created the flanking and suppression behaviors that made F.E.A.R.’s enemies feel intelligent over a decade ago.
Modular BT Design Patterns
Production BTs are organized hierarchically: a root selector chooses between combat, patrol, and investigation subtrees. Each subtree is a separate BT asset that can be authored and tested independently. The combat subtree itself contains sub-selectors for ranged attack, melee attack, and retreat, each with conditions (has ammo, distance to target, health percentage). Epic’s Paragon AI documentation (released publicly in 2018) showed a subtree composition pattern where designers could assemble new enemy types by reusing existing subtrees with different parameters.
Finite State Machines
While behavior trees dominate, FSMs remain valuable for simpler AI and for understanding foundational AI architecture.
Hierarchical State Machines (HSMs)
Flat FSMs become unmanageable beyond 10–15 states. HSMs group related states under parent states — a “Combat” parent state contains child states for Chase, Attack, Reload, and Retreat. Transitions between child states are evaluated before parent transitions, allowing natural priority ordering. Unity’s Animator Controller is an HSM primarily used for animation but can drive AI logic via script state behaviors. Godot’s StateMachine plugin (available in the asset library) implements HSMs with stack-based state push/pop.
State Machine Design Patterns
Common AI states map to distinct behaviors. An Idle state plays a random idle animation, looks around, and listens for disturbances. A Patrol state follows a waypoint path with configurable wait times. An Alert state investigates the last known player position using spherecast sight checks. A Combat state selects weapons, finds cover, and communicates with allied AI via a shared sensory database. Transition conditions use distance checks, timer expirations, or event-based triggers. The Unity AI documentation recommends polling in Update for time-critical transitions and using events (via C# delegates or UnityEvents) for predictable state changes like death or objective completion.
Sensory Systems
AI perception involves sight, hearing, and memory. Sight is typically implemented using cone-based raycasts or overlap spheres filtered by team and visibility. Hearing uses spherecasts with configurable radius depending on noise intensity — a gunshot has larger detection radius than footsteps. Memory stores known enemy positions with confidence decay over time, creating realistic search behavior when the player breaks line of sight. Unreal’s AIPerceptionComponent provides built-in sight, hearing, and damage sensing configuration with automatic stimulus processing and forget timers.
Utility AI and Advanced Techniques
Utility systems evaluate each possible action and assign a score based on contextual factors — distance, health, ammo, threat level. The AI selects the highest-scoring action, creating nuanced, emergent behavior without explicit state transitions. The Sims uses utility AI for character decision-making, where each Sim scores actions like eating, sleeping, or socializing based on their current needs. The utility curve shape matters: a linear falloff with distance produces different behavior than exponential. Designers tune curves in the editor.
GOAP (Goal-Oriented Action Planning) plans a sequence of actions to achieve a goal, as seen in F.E.A.R. The AI has a set of available actions (find cover, reload, throw grenade, flank) and a goal (kill the player). The planner searches for the cheapest sequence of actions that achieves the goal, accounting for world state. If the player is behind cover, the planner might select throw grenade to flush them out, then flank while they are suppressed. GOAP produces adaptive behavior without explicit scripting of every scenario.
Hierarchical Task Networks (HTNs) decompose high-level tasks into subtasks until primitive actions are reached, used in Killzone’s AI as detailed at GDC 2009. A “Clear Room” task decomposes to “Enter doorway,” “Scan corners,” and “Suppress threats,” each further decomposed into movement, aiming, and firing actions. HTNs provide clear authoring while maintaining the flexibility of dynamic planning.
For integration with physics-based interactions, see Game Physics Guide. For multiplayer AI challenges, refer to Multiplayer Game Development.
Frequently Asked Questions
Q: What is the difference between behavior trees and finite state machines? A: Behavior trees are modular, reusable, and support easy debugging with visual execution flow. FSMs are simpler but become unwieldy for complex AI. Most modern games use behavior trees for main AI logic and FSMs for simple sub-behaviors.
Q: How do I prevent NPCs from getting stuck in corners? A: Use local avoidance with velocity obstacles (RVO/ORCA) alongside pathfinding. Configure navmesh agent radius and step height appropriately. Add fail-safes: if stuck timer exceeds threshold, warp agent to last valid position.
Q: Can I use machine learning for game AI? A: Yes, reinforcement learning is increasingly used for NPC behaviors in racing games, fighting games, and character animation. Unity ML-Agents and Unreal’s Machine Learning Agents plugin support training AI in engine, but ML models require careful integration with existing behavior systems.
Q: How do I debug AI in my game? A: Visualize pathfinding paths (Unity NavMesh Agent path Gizmos, Unreal’s Debug Drawing), log state machine/behavior tree execution (Unity’s BT Debugger, Unreal’s Behavior Tree Debugger), and use in-world debug overlays showing current state and target.
Q: What is the best approach for companion AI that follows the player? A: Use a Follow behavior tree with distance-based nodes: if distance > 10m, move toward player with pathfinding; if 5–10m, move at reduced speed; if < 5m, play idle animation. Add tight-space detection to disable following through narrow corridors.
For a comprehensive overview, read our article on 2D Game Development Guide.
For a comprehensive overview, read our article on 3D Game Development Guide.