Abstract: The complexity of interactive virtual worlds has increased dramatically in recent years, with a rise in mature solutions for designing large-scale environments and populating them with hundreds and thousands of autonomous characters. An interesting problem that arises in this context, and that has received little attention to date, is whether we can predict the complexity of a steering scenario by analyzing the configuration of the environment and the agents involved. We statically analyze an input scenario and compute a set of novel salient features which characterize the expected interactions between agents and obstacles during simulation. Using a statistical approach, we automatically derive the relative influence of each feature on the complexity of a scenario in order to derive a single numerical quantity of expected scenario complexity. We validate our proposed metric by demonstrating a strong negative correlation between the statically computed expected complexity and the dynamic performance of three published crowd simulation techniques.