Overview
Open-world games need large crowds of pedestrians to make their cities feel alive, yet there was no controlled comparison of how the common NPC behavior architectures perform at that scale. Studios usually choose one on intuition.
I implemented five architectures in C++ on top of Epic's City Sample: a flat finite state machine, a hierarchical FSM, a State Tree, a Behavior Tree and Utility AI. All five follow the same behavior specification and share perception, movement and animation, so the decision-making framework is the only thing that changes. Each one was tested at three complexity levels (4, 10 and 18 states) and five crowd sizes from 100 to 2,000 NPCs, with 10 runs per condition and 750 runs in total.
Key findings
- Below 500 NPCs, the choice of architecture had no measurable effect on frame rate. At 100 NPCs every system ran at 73 to 74 FPS.
- The Behavior Tree had the lowest AI decision time, yet the State Tree delivered the best frame rate, 33.75 FPS against 27.18 for the Behavior Tree at 1,000 NPCs. Timing one component on its own can point you to the wrong architecture.
- The State Tree scaled best at higher complexity. Going from 1,000 to 2,000 NPCs multiplied its cost by about 1.7 instead of 2.
- Utility AI scores every action on every tick, which makes it impractical for crowds. It reached 462 ms of AI time per frame at 2,000 NPCs with complex behavior, about 25 times the Behavior Tree.
- The flat FSM consistently outperformed the hierarchical one. At 2,000 NPCs with complex behavior, the hierarchical FSM cost 45% more.
At 1,000 NPCs, medium complexity. Best value per column in bold.
| Architecture | AI time (ms) | Frame rate (FPS) |
How cost grows with crowd size
For each architecture I fitted AI time ∝ Pn across the five crowd sizes. Every system scaled sublinearly (n < 1), and the lower n, the better it scales.
Scaling exponent n per complexity level. Lowest per column in bold.
| Architecture | Simple | Medium | Complex |
| State Tree | 0.900 | 0.793 | 0.763 |
| Flat FSM | 0.852 | 0.884 | 0.899 |
| Hierarchical FSM | 0.855 | 0.911 | 0.935 |
| Behavior Tree | 0.882 | 0.945 | 0.923 |
| Utility AI | 0.928 | 0.925 | 0.922 |
What I built
- Five behavior systems in C++: flat and hierarchical state machines built on an Enter, Execute and Exit state interface, an event-driven Behavior Tree, a compiled State Tree, and Utility AI with response curves and hysteresis
- A replacement for the City Sample's Mass AI crowd pipeline, keeping Zone Graph lanes, animation and traffic as shared infrastructure
- A custom spawning system for reproducible tests and a shared perception system that gives every architecture identical input
- Behavior specifications for 18 pedestrian states, from fleeing and sitting to photographing landmarks and reporting crimes
- An automated pipeline that runs every test headless, records Unreal Insights traces, exports them to CSV and analyzes them in Python
- Statistical analysis with a three-way ANOVA and Bonferroni-corrected Welch's t-tests
What I would test next
- The same comparison with LOD systems active, since every NPC got full AI processing here
- The State Tree running inside Unreal's Mass AI framework
- Matched evaluation scheduling and a range of tick rates, to separate scheduling cost from architecture cost
- Hybrid setups, such as Utility AI choosing actions and state machines executing them
Paper
A Comparative Performance Analysis of NPC Behavior Architectures for Crowd-Scale Pedestrians in Open-World Games, written for my Master Game Technology at Breda University of Applied Sciences, 2026.