tutorial

SteerPlex: Estimating Scenario Complexity for Simulated Crowds

Authors:

Mubbasir Kapadia,

Petros FaloutsosAuthors Info & Claims

MIG '13: Proceedings of Motion on Games

Pages 67 - 76

https://doi.org/10.1145/2522628.2522650

Published: 06 November 2013 Publication History

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.

References

[1]

Axel Buendia, J. H., 2002. SpirOps: Scientific Research Labs in Artificial Intelligence.

[2]

Bauer, A., and Popovic, Z., 2012. Rrt-based game level analysis, visualization, and visual refinement.

[3]

Berseth, G., Kapadia, M., and Faloutsos, P. 2013. Automated parameter tuning for steering algorithms. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Poster Proceedings).

[4]

Boatright, C., Kapadia, M., and Badler, N. I. 2012. Pedestrian Anomaly Detection using Context-Sensitive Crowd Simulation. In First International Workshop on Pattern Recognition and Crowd Analysis.

[5]

Chenney, S. 2004. Flow tiles. In SCA '04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, Eurographics Association, Switzerland, 233--242.

Digital Library

[6]

Darken, C., 2007. Level annotation and test by autonomous exploration: Abbreviated version.

[7]

Guy, S. J., van den Berg, J., Liu, W., Lau, R., Lin, M. C., and Manocha, D. 2012. A statistical similarity measure for aggregate crowd dynamics. ACM Trans. Graph. 31, 6 (Nov.), 190:1--190:11.

Digital Library

[8]

Hart, P., Nilsson, N., and Raphael, B. 1968. A formal basis for the heuristic determination of minimum cost paths. Systems Science and Cybernetics, IEEE Transactions on 4, 2, 100--107.

[9]

Hartigan, J. A. 1975. Clustering Algorithms, 99th ed. John Wiley & Sons, Inc., New York, NY, USA.

Digital Library

[10]

Heckel, F. W. P., Youngblood, G. M., and Hale, D. H. 2009. Influence points for tactical information in navigation meshes. In Proceedings of the 4th International Conference on Foundations of Digital Games, ACM, New York, NY, USA, FDG '09, 79--85.

Digital Library

[11]

Helbing, D., Buzna, L., Johansson, A., and Werner, T. 2005. Self-organized pedestrian crowd dynamics: Experiments, simulations, and design solutions. Transportation Science 39, 1, 1--24.

Digital Library

[12]

Kapadia, M., and Badler, N. I. 2013. Navigation and steering for autonomous virtual humans. Wiley Interdisciplinary Reviews: Cognitive Science, n/a--n/a.

[13]

Kapadia, M., Singh, S., Allen, B., Reinman, G., and Faloutsos, P. 2009. Steerbug: an interactive framework for specifying and detecting steering behaviors. In SCA '09: Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, ACM, 209--216.

Digital Library

[14]

Kapadia, M., Singh, S., Hewlett, W., and Faloutsos, P. 2009. Egocentric affordance fields in pedestrian steering. In Proceedings of the 2009 symposium on Interactive 3D graphics and games, ACM, New York, NY, USA, I3D '09, 215--223.

Digital Library

[15]

Kapadia, M., Wang, M., Singh, S., Reinman, G., and Faloutsos, P. 2011. Scenario space: characterizing coverage, quality, and failure of steering algorithms. In Proceedings of the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, ACM, New York, NY, USA, SCA '11, 53--62.

Digital Library

[16]

Kapadia, M., Wang, M., Reinman, G., and Faloutsos, P. 2011. Improved benchmarking for steering algorithms. In Fourth International Conference on Motion in Games, 266--277.

Digital Library

[17]

Kapadia, M., Singh, S., Hewlett, W., Reinman, G., and Faloutsos, P. 2012. Parallelized egocentric fields for autonomous navigation. The Visual Computer 28, 12, 1209--1227.

[18]

Kapadia, M., Beacco, A., Garcia, F., Reddy, V., Pelechano, N., and Badler, N. I. 2013. Multi-domain real-time planning in dynamic environments. In Proceedings of the 12th ACM SIGGRAPH/Eurographics Symposium on Computer Animation, ACM, New York, NY, USA, SCA '13, 115--124.

Digital Library

[19]

Lamarche, F., and Donikian, S. 2004. Crowd of virtual humans: a new approach for real time navigation in complex and structured environments. In Computer Graphics Forum 23.

[20]

Lerner, A., Chrysanthou, Y., Shamir, A., and Cohen-Or, D. 2010. Context-dependent crowd evaluation. Comput. Graph. Forum 29, 7, 2197--2206.

[21]

Martin, P. 2011. A spatial analysis of the jba headquarters in splinter cell: Double agent. In Proceedings of the 6th International Conference on Foundations of Digital Games, ACM, New York, NY, USA, FDG '11, 123--130.

Digital Library

[22]

Mononen, M., 2009. Recast: Navigation-mesh Construction Toolset for Games.

[23]

Musse, S. R., Cassol, V. J., and Jung, C. R. 2012. Towards a quantitative approach for comparing crowds. Computer Animation and Virtual Worlds 23, 1, 49--57.

Digital Library

[24]

Ondřej, J., Pettré, J., Olivier, A.-H., and Donikian, S. 2010. A synthetic-vision based steering approach for crowd simulation. In ACM SIGGRAPH 2010 papers, ACM, New York, NY, USA, SIGGRAPH '10, 123:1--123:9.

Digital Library

[25]

Pelechano, N., Allbeck, J. M., and Badler, N. I. 2007. Controlling individual agents in high-density crowd simulation. In SCA '07: Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 99--108.

Digital Library

[26]

Pelechano, N., Allbeck, J. M., and Badler, N. I. 2008. Virtual Crowds: Methods, Simulation, and Control. Synthesis Lectures on Computer Graphics and Animation. Morgan & Claypool Publishers.

Digital Library

[27]

Penn, A. 2001. Space syntax and spatial cognition: or why the axial line? In 3rd International Space Syntax Symposium, 11.1--11.17.

[28]

Perkins, L., 2010. Terrain analysis in real-time strategy games: An integrated approach to choke point detection and region decomposition.

[29]

Regelous, S., 2002. Massive. http://www.massivesoftware.com/.

[30]

Reynolds, C. W. 1987. Flocks, herds and schools: A distributed behavioral model. In SIGGRAPH '87: Proceedings of the 14th annual conference on Computer graphics and interactive techniques, ACM, 25--34.

Digital Library

[31]

Reynolds, C. W. 1999. Steering behaviors for autonomous characters. Game Developers Conference 1999, 9602, 763--782.

[32]

Schuerman, M., Singh, S., Kapadia, M., and Faloutsos, P. 2010. Situation agents: agent-based externalized steering logic. Comput. Animat. Virtual Worlds 21 (May), 267--276.

Digital Library

[33]

Singh, S., Kapadia, M., Faloutsos, P., and Reinman, G. 2009. An open framework for developing, evaluating, and sharing steering algorithms. In Proceedings of the 2nd International Workshop on Motion in Games, Springer-Verlag, Berlin, Heidelberg, MIG '09, 158--169.

Digital Library

[34]

Singh, S., Kapadia, M., Faloutsos, P., and Reinman, G. 2009. SteerBench: a benchmark suite for evaluating steering behaviors. Computer Animation and Virtual Worlds 20, 5--6, 533--548.

Digital Library

[35]

Singh, S., Kapadia, M., Hewlett, B., Reinman, G., and Faloutsos, P. 2011. A modular framework for adaptive agent-based steering. In Symposium on Interactive 3D Graphics and Games (I3D), ACM, 141--150.

Digital Library

[36]

Singh, S., Kapadia, M., Reinman, G., and Faloutsos, P. 2011. Footstep navigation for dynamic crowds. Computer Animation and Virtual Worlds 22, 2-3, 151--158.

Digital Library

[37]

Sturtevant, N. 2012. Benchmarks for grid-based pathfinding. Transactions on Computational Intelligence and AI in Games 4, 2, 144--148.

[38]

Thalmann, D. 2008. Crowd simulation. In Wiley Encyclopedia of Computer Science and Engineering.

[39]

Treuille, A., Cooper, S., and Popović, Z. 2006. Continuum crowds. ACM Trans. Graph. 25, 3, 1160--1168.

Digital Library

[40]

van den Berg, J., Guy, S., Lin, M., and Manocha, D. 2011. Reciprocal n-body collision avoidance. In Robotics Research, C. Pradalier, R. Siegwart, and G. Hirzinger, Eds., vol. 70 of Springer Tracts in Advanced Robotics. Springer Berlin Heidelberg, 3--19.

[41]

Yeh, H., Curtis, S., Patil, S., van den Berg, J., Manocha, D., and Lin, M. 2008. Composite agents. In Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SCA '08, 39--47.

Digital Library

Cited By

Liu HChoi MKao DMousas C(2023)Synthesizing Game Levels for Collaborative Gameplay in a Shared Virtual EnvironmentACM Transactions on Interactive Intelligent Systems10.1145/355877313:1(1-36)Online publication date: 9-Mar-2023
https://dl.acm.org/doi/10.1145/3558773
Gutiérrez A. MVexo FThalmann DGutiérrez A. MVexo FThalmann D(2023)Virtual CharactersStepping into Virtual Reality10.1007/978-3-031-36487-7_4(81-124)Online publication date: 12-Aug-2023
https://doi.org/10.1007/978-3-031-36487-7_4
Yu RZheng YQu X(2021)Dynamic driving environment complexity quantification method and its verificationTransportation Research Part C: Emerging Technologies10.1016/j.trc.2021.103051127(103051)Online publication date: Jun-2021
https://doi.org/10.1016/j.trc.2021.103051
Show More Cited By

Index Terms

SteerPlex: Estimating Scenario Complexity for Simulated Crowds
1. Computing methodologies
  1. Computer graphics
    1. Image manipulation
    2. Rendering

Recommendations

LCrowdV: Generating labeled videos for pedestrian detectors training and crowd behavior learning
Abstract
We present a novel procedural framework to generate an arbitrary number of labeled crowd videos (LCrowdV). The resulting crowd video datasets are used to design accurate algorithms or training models for crowded scene understanding. ...
Modeling Gap Seeking Behaviors for Agent-based Crowd Simulation
CASA '16: Proceedings of the 29th International Conference on Computer Animation and Social Agents

Research on agent-based crowd simulation has gained tremendous momentum in recent years due to the increase of computing power. One key issue in this research area is to develop various behavioral models to capture the microscopic behaviors of ...
The hierarchical behavior model for crowd simulation
VRCAI '09: Proceedings of the 8th International Conference on Virtual Reality Continuum and its Applications in Industry

We present a hierarchical behavior model to simulate realistic crowd behaviors. This model is composed of two parts. One is the low density behavior module, emphasizing the autonomy and diversity of the behaviors. The other is high density behavior ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MIG '13: Proceedings of Motion on Games

November 2013

30 pages

ISBN:9781450325462

DOI:10.1145/2522628

Conference Chair:
Rachel McDonnell
Trinity College Dublin, Ireland
,
Program Chairs:
Nathan Sturtevant
University of Denver
,
Victor Zordan
University of California Riverside

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Tutorial
Research
Refereed limited

Conference

MIG '13

Sponsor:

SIGGRAPH

MIG '13: Motion in Games

November 6 - 8, 2013

Dublin 2, Ireland

Acceptance Rates

MIG '13 Paper Acceptance Rate -9 of -9 submissions, 100%;

Overall Acceptance Rate -9 of -9 submissions, 100%

Upcoming Conference

MIG '24

Sponsor:
siggraph

The 17th ACM SIGGRAPH Conference on Motion, Interaction, and Games

November 21 - 23, 2024

Arlington , VA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
119
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu HChoi MKao DMousas C(2023)Synthesizing Game Levels for Collaborative Gameplay in a Shared Virtual EnvironmentACM Transactions on Interactive Intelligent Systems10.1145/355877313:1(1-36)Online publication date: 9-Mar-2023
https://dl.acm.org/doi/10.1145/3558773
Gutiérrez A. MVexo FThalmann DGutiérrez A. MVexo FThalmann D(2023)Virtual CharactersStepping into Virtual Reality10.1007/978-3-031-36487-7_4(81-124)Online publication date: 12-Aug-2023
https://doi.org/10.1007/978-3-031-36487-7_4
Yu RZheng YQu X(2021)Dynamic driving environment complexity quantification method and its verificationTransportation Research Part C: Emerging Technologies10.1016/j.trc.2021.103051127(103051)Online publication date: Jun-2021
https://doi.org/10.1016/j.trc.2021.103051
Musse SCassol VThalmann D(2021)A history of crowd simulation: the past, evolution, and new perspectivesThe Visual Computer10.1007/s00371-021-02252-wOnline publication date: 5-Aug-2021
https://doi.org/10.1007/s00371-021-02252-w
Palachano NAllbeck JKapadia MBadler N(2016)Scenario Space: Characterizing Coverage, Quality, and Failure of Steering AlgorithmsSimulating Heterogeneous Crowd with Interactive Behaviors10.1201/9781315370071-10(161-177)Online publication date: 19-Oct-2016
https://doi.org/10.1201/9781315370071-10
Haworth BUsman MBerseth GKapadia MFaloutsos P(2015)Evaluating and optimizing level of service for crowd evacuationsProceedings of the 8th ACM SIGGRAPH Conference on Motion in Games10.1145/2822013.2822040(91-96)Online publication date: 16-Nov-2015
https://dl.acm.org/doi/10.1145/2822013.2822040
Berseth GUsman MHaworth BKapadia MFaloutsos P(2015)Environment optimization for crowd evacuationComputer Animation and Virtual Worlds10.1002/cav.165226:3-4(377-386)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1002/cav.1652
Berseth GHaworth MKapadia MFaloutsos PShapiro AAmato NHodgins J(2014)Characterizing and optimizing game level difficultyProceedings of the 7th International Conference on Motion in Games10.1145/2668084.2668100(153-160)Online publication date: 6-Nov-2014
https://dl.acm.org/doi/10.1145/2668084.2668100
Berseth GHaworth MKapadia MFaloutsos PShapiro AAmato NHodgins J(2014)Characterizing and optimizing game level difficultyProceedings of the 7th International Conference on Motion in Games10.1145/2668064.2668100(153-160)Online publication date: 6-Nov-2014
https://dl.acm.org/doi/10.1145/2668064.2668100

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents