Game AI: Behavior Trees, Pathfinding & Utility Systems

Game AI

Game AI has almost nothing to do with machine learning and everything to do with authored behavior that reads as intelligent. The measure of success isn't optimality — it's whether the player believes the NPC is thinking. An enemy that always makes the correct tactical choice is frustrating and, paradoxically, often reads as less intelligent than one that shouts "flanking left!" and then walks somewhere visible.

The techniques form a ladder. Finite state machines are simple and hit a complexity wall fast. Behavior trees replace state explosion with composable, reusable subtrees and dominate commercial game AI. Utility AI scores every option continuously and suits simulation-heavy games. GOAP plans a sequence of actions backwards from a goal. Underneath all of them sits movement: A\* over a navmesh to decide where to go, and steering behaviors to make getting there look natural.

TL;DR

Game AI optimizes for believability and fun, not for optimal play.
FSMs are fine up to roughly five to seven states; transitions grow as O(n²) and become unmaintainable.
Behavior trees are the industry default — composable, designer-editable, and easy to debug.
Utility AI scores actions by weighted considerations; good for sims and emergent behavior.
GOAP plans backwards from a goal; powerful, expensive, and hard to predict.
A\* finds paths; the navmesh is the graph it searches; steering makes the movement look alive.
Perception should be modeled explicitly — vision cones, hearing, memory — not read directly from world state.
Telegraph intent. An NPC that never signals what it's doing reads as random, not smart.

Quick Example

A behavior tree for a guard — the structure most commercial game AI takes:

The tree is re-evaluated from the root each tick, so a guard that spots an enemy mid-patrol immediately falls into the combat branch — priority is expressed by child order, not by wiring transitions.

Decision-Making Architectures

Finite state machines

Clear and fast to write. The problem is combinatorial: each new state must consider transitions to and from every existing one, and by ten states the transition logic is unmaintainable. Hierarchical FSMs (states containing sub-machines) push the ceiling higher, but behavior trees usually solve the same problem better.

Behavior trees

Trees of composites (Sequence, Selector, Parallel), decorators (Inverter, Repeater, Cooldown, Succeeder), and leaves (Conditions and Actions). The advantages over FSMs are concrete:

No transition explosion — priority comes from ordering, re-evaluated each tick.
Reusable subtrees — "take cover" is authored once and shared by every enemy type.
Designer-editable — the visual representation is the actual logic.
Debuggable — highlighting the active path in a tree makes "why did it do that?" answerable.

A blackboard holds shared state (the current target, the last known position, the assigned cover point) so nodes stay stateless and composable. This is exactly the model in Unreal's Behavior Tree system and most Unity behavior-tree packages.

Utility AI

Instead of a fixed structure, score every possible action each tick and take the best.

Considerations are curves over normalized inputs: "distance to target," "my health," "ammo remaining," "time since last used." Behavior emerges from tuning curves rather than authoring structure, which makes it excellent for simulation games (The Sims is the canonical example) and for agents with many competing needs. The cost is predictability — debugging "why did it choose that?" means inspecting a score breakdown, and designers can find it harder to guarantee a specific behavior happens.

GOAP

Goal-Oriented Action Planning gives each action preconditions and effects, then searches backwards from a goal to the current world state.

Agents improvise around missing preconditions, which produces genuinely emergent sequences — famously in F.E.A.R., where enemies appeared to coordinate because they replanned around each other. The costs are real: planning is expensive relative to a tree tick, behavior is hard to predict or guarantee, and debugging a plan failure is harder than debugging a tree path.

Choosing among them

Mixing is normal and often correct: a behavior tree for structure with a utility scorer inside a single "choose a combat action" node gets most of both.

Movement and Navigation

A* pathfinding

A\* is Dijkstra plus a heuristic that biases the search toward the goal. The heuristic must never overestimate the true remaining cost, or the path found may not be optimal — Euclidean distance for free movement, Manhattan for grid movement without diagonals.

Navmeshes

A grid is the obvious graph and usually the wrong one: it has far more nodes than the space needs and produces paths that hug cell boundaries.

A navmesh describes walkable surfaces as convex polygons, is generated from level geometry (offline or at runtime), and supports off-mesh links for jumps, ladders, and doors. Every major engine ships one: Unity's NavMesh and NavMeshAgent, Unreal's Navigation System, Godot's NavigationServer, and the widely used Recast/Detour library underneath several of them.

Path smoothing ("string pulling" / funnel algorithm) converts the polygon sequence into a direct line where line of sight allows, which is the difference between an agent walking toward waypoints and one walking toward its destination.

Steering behaviors

A path tells you where to go; steering makes it look natural. Craig Reynolds' behaviors compose as weighted force vectors:

Seek, flee, arrive, wander, pursue, evade, separation, alignment, and cohesion — the last three producing flocking. Local avoidance (RVO/ORCA) handles agents dodging each other in crowds, which pathfinding alone can't, since every agent replanning around every other is both expensive and oscillatory.

Perception

An NPC that reacts to player.position directly is omniscient, and players detect it immediately. Model perception explicitly:

Add memory (a last-known position that decays), hearing (sound events with a radius, attenuated by walls), and a reaction delay so detection isn't instantaneous. Those three additions do more for perceived intelligence than any decision architecture upgrade, because they give the player a legible model of what the NPC knows.

Best Practices

Telegraph everything

An enemy that winds up before attacking, shouts before flanking, or visibly looks toward a noise is readable — and readable enemies feel intelligent and let players make informed decisions. Silent optimal behavior reads as random or unfair. This is the single highest-leverage thing in game AI, and it's a design decision, not an algorithmic one.

Give NPCs sensory limits and make them visible

Vision cones, hearing radii, and reaction delays create the feedback loop stealth and combat depend on. The player must be able to reason about detection; a perfect sensor removes the game.

Make AI legible in a debug view

Draw the current behavior tree path, the perception cone, the computed path, the target, and the utility scores in-world. Game AI bugs are behavioral and nearly impossible to diagnose from a breakpoint — you need to see the state at the moment it looked wrong.

Stagger expensive work across frames

Running A\* for 200 agents in one frame is a guaranteed hitch. Time-slice pathfinding requests through a queue with a per-frame budget, re-evaluate decisions at 5–10 Hz rather than 60, and use a level-of-detail scheme where distant NPCs think less often.

Cache and reuse paths

Recomputing a full path every frame is a common and expensive mistake. Recompute on a timer, on a significant target movement, or when the path is invalidated. For fixed destinations shared by many agents, a flow field computed once beats N individual searches.

Add deliberate imperfection

Perfect aim, instant reactions, and optimal choices are not fun. Introduce aim error that shrinks over sustained fire, reaction delays, occasional wrong guesses about the player's position, and a first-shot miss. Players experience calibrated fallibility as personality.

Keep decisions and actions separate

The decision layer chooses "attack this target"; the action layer handles movement, animation, and weapon timing. Merging them produces AI where changing an animation breaks tactical logic, and it prevents reusing behaviors across enemy types.

Common Mistakes

Giving AI perfect information

Pathfinding every frame

An FSM that outgrew itself

Flip-flopping between decisions

Steering without obstacle avoidance priority

Optimizing the AI instead of the experience

An enemy that always finds the optimal flank is not more fun than one that flanks 60% of the time and announces it. Tune against playtest feedback about how the AI feels, not against a measure of how well it plays.

FAQ

Does game AI use machine learning?

Rarely for shipped NPC behavior. ML is hard to author against, hard to debug, hard to guarantee, and expensive at runtime — all fatal properties when a designer needs a specific enemy to behave a specific way. Where ML does appear: animation systems (motion matching, learned locomotion), procedural content, playtesting bots, and increasingly LLM-driven dialogue and narrative NPCs, which is a genuinely active area. The tactical behavior layer remains authored.

Behavior tree or state machine?

Start with an FSM if the agent has three or four clear modes — it's less machinery for the same result. Move to a behavior tree when you notice transition logic growing faster than behavior, when you want to share sub-behaviors across enemy types, or when designers need to edit AI without touching code. Most commercial games land on behavior trees, and hierarchical FSMs are a reasonable middle step.

How do I make enemies feel smart without being unfair?

Give them legible, telegraphed behavior and human-like limitations. Announce intentions, react with delay, miss the first shot, occasionally search the wrong place. The perception of intelligence comes from the player being able to build a mental model of the NPC and see it act on beliefs — including wrong ones. Perfect play removes that entirely.

How many agents can I run?

With time-slicing and level of detail, hundreds to low thousands in a typical engine. The limiting factors are pathfinding (batch it, use flow fields for shared destinations), perception queries (stagger them, use spatial partitioning), and decision ticks (5–10 Hz is plenty; 60 Hz is waste). Distant agents can run a much cheaper "simulate abstractly" mode. Beyond that, ECS-style data-oriented AI is how RTS games reach tens of thousands of units.

What about crowd simulation?

Combine coarse pathfinding (or a shared flow field) with local avoidance — RVO or ORCA — so agents resolve collisions with each other reactively instead of replanning. Full per-agent A\* in a crowd is both too slow and produces oscillation as agents plan around each other's stale positions.

How do I debug AI that "sometimes" misbehaves?

Record it. Log decision changes with timestamps and the inputs that caused them, and add an in-game replay of the AI's state alongside a debug overlay. Behavioral bugs depend on timing and world state that a breakpoint destroys; a log of "chose Flee because health=0.19, threat=0.8" answers the question a debugger can't.