Big fast crowds on PS3

ABSTRACT

Crowds and other flock-like group motion are often modeled as interacting particle systems. These multi-agent simulations are computationally expensive because each agent must consider all of the others, if only to identify its neighbors. For large crowds, simple implementations are too slow since computation grows as the square of agent population. Faster approaches often rely on spatial hashing where a partitioning of space is used to accelerate crowd simulation. This same partitioning can form the basis of a scalable multi-processor approach to large, fast crowd simulations, as in [Quinn et al. 2003]. This paper describes an implementation of that approach for PLAYSTATION®3 which supports simulation and display of simple crowds of up to 15,000 individuals at 60 frames per second.

REFERENCES

• 1: Arnaud, R. 2006. PSGL (PlayStation Graphics Library). GDC 2006 presentation, http://www.khronos.org/developers/content/GDC_2006/GLESTutorial07-PlayStation_GL.pdf
• 2: Bajec, I. L., Zimic, N. and Mraz, M. 2005. Simulating flocks on the wing: the fuzzy approach. Journal of Theoretical Biology 233(2), 199--220. DOI= http://dx.doi.Org/10.1016/j.jtbi.2004.10.003 http://lrss.fri.uni-lj.si/people/ilbajec/papers/ilb_jtb05.pdf
• 3: Nathan Bell , Yizhou Yu , Peter J. Mucha, Particle-based simulation of granular materials, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073379]
• 4: Bouvier, E., Cohen, E., and Najman, L. 1997. From Crowd Simulation to Airbag Deployment: Particle Systems, a New Paradigm of Simulation. Journal of Electronic Imaging 6(1), 94.107 http://www.esiee.fr/~najmanl/papers/particlesystem.pdf
• 5: Courty, N. and Musse, S. R. 2005. Simulation of large crowds in emergency situations including gaseous phenomena. In Proceedings of IEEE Computer Graphics International 2005, 206--212. DOI= 10.1109/CGI.2005.1500417 (see http://home.tele2.fr/ncourty/fastCrowd.htm)
• 6: Erra, U., De Chiara, R., Scarano, V., Tatafiore, M. 2004. Massive Simulation using GPU of a distributed behavioral model of a flock with obstacle avoidance. Proceedings of Vision, Modeling and Visualization 2004 (VMV). http://wonderland.dia.unisa.it/projects/gebs/
• 7: Evans, M. W. and Harlow, F. H. 1957. The particle-in-cell method for hydrodynamic calculations. Los Alamos Scientific Laboratory report LA-2139
• 8: Frank, T., Bernert, K. and Pachler, K. 2001. Dynamic Load Balancing for Lagrangian Particle Tracking Algorithms on MIMD Cluster Computers. In PARCO'2001 - International Conference on Parallel Computing 2001. Naples, Italy, September 4-7, 2001, pp. 1--9. http://www.imech.tu-chemnitz.de/mpf/publication/frank/parco_2001.ps.Z
• 9: Gingold, R. A., Monaghan, J. J. 1977. Smoothed particle hydrodynamics - Theory and application to non-spherical stars. Royal Astronomical Society, Monthly Notices. Vol 181, 375--389. http://adsabs.harvard.edu/abs/1977MNRAS.181..375G
• 10: Harlow, F. H. and Meixner, B. D. 1961. The particle-and-force computing method for fluid dynamics. Los Alamos Scientific Laboratory report LA-2567-MS.
• 11: Harlow, F. H., and Sandoval, D. L. 1986. Human Collective Dynamics: The Mathematical Modeling of Mobs. In Mathematical Modeling of Biological Ensembles, Los Alamos National Laboratory report LA-10765-MS.
• 12: Lorek, H. and White, M. 1993. Parallel Bird Flocking Simulation. http://citeseer.ist.psu.edu/lorek93parallel.html
• 13: Lorek, H. and Sonnenschein, M. 1995. Using parallel computers to simulate individual-oriented models in ecology: A case study. In Proceedings of the 1995 European Simulation Multi-conference (ESM), 526--531, June 1995. http://citeseer.ist.psu.edu/lorek95using.html
• 14: IBM, Sony and Toshiba. 2005. Cell Broadband Engine Architecture. Version 1.0, August 8, 2005. http://www-306.ibm.com/chips/techlib/techlib.nsf/techdocs/1AEEE1270EA2776387257060006E61BA/$file/CBEA_01_pub.pdf
• 15: Miles, D. 2006. Crowds In A Polygon Soup: Next-Gen Path Planning. GDC 2006 presentation, http://www.babelflux.com/gdc2006_miles_david_pathplanning.ppt
• 16: F. Merchant , L. F. Bic. , M. B. Dillencourt, Load Balancing in Individual-Based Spatial Applications, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.350, October 12-18, 1998
• 17: nVIDIA Corporation. 2006. Cg Toolkit User's Manual. Release 1.4.1 http://developer.nvidia.com/object/cg_toolkit.html
• 18: O'Neill, J. C. 2004. Efficient Navigation Mesh Implementation. Journal of Game Development 1(1) 71--90.
• 19: Pham, D., et al. (20 authors). 2005. The Design and Implementation of a First-Generation CELL Processor. In Solid-State Circuits Conference, 2005. ISSCC 2005 IEEE International. http://www-306.ibm.com/chips/techlib/techlib.nsf/techdocs/7FB9EC5D5BBF51ED87256FC000742186/$file/ISSCC-10.2-Cell_Design.PDF
• 20: Pelechano, N., O'Brien, K., Silverman, B., Badler, N. 2005. Crowd Simulation Incorporating Agent Psychological Models, Roles and Communication. Workshop on Crowd Simulation (V-CROWDS 2005), 24-25. http://www.seas.upenn.edu/~npelecha/Pelechano_V_CROWDS05.pdf
• 21: Steve Plimpton, Fast parallel algorithms for short-range molecular dynamics, Journal of Computational Physics, v.117 n.1, p.1-19, March 1, 1995 [doi>10.1006/jcph.1995.1039]
• 22: Quinn, M. J., Metoyer, R. A., and Hunter-Zaworski, K., 2003 Parallel Implementation of the Social Forces Model. In Proceedings of the Second International Conference in Pedestrian and Evacuation Dynamics (August 2003), pp. 63--74. http://eecs.oregonstate.edu/gait/pubs/QuinnFinal.pdf
• 23: W. T. Reeves, Particle Systems—a Technique for Modeling a Class of Fuzzy Objects, ACM Transactions on Graphics (TOG), v.2 n.2, p.91-108, April 1983 [doi>10.1145/357318.357320]
• 24: Craig W. Reynolds, Flocks, herds and schools: A distributed behavioral model, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.25-34, August 1987
• 25: Reynolds, C. W. 2000. Interaction with Groups of Autonomous Characters, in proceedings of the Game Developers Conference 2000, CMP Game Media Group, San Francisco, California, 449--460. http://www.red3d.com/cwr/papers/2000/pip.html
• 26: Sandoval, D. L., Harlow, F. H, and Genin, K. E. 1988. Human Collective Dynamics: Two Groups in Adversarial Encounter. Los Alamos National Laboratory report LA-11247-MS.
• 27: Wei Shao , Demetri Terzopoulos, Autonomous pedestrians, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073371]
• 28: Karl Sims, Particle animation and rendering using data parallel computation, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.405-413, September 1990, Dallas, TX, USA
• 29: Anthony Steed , Roula Abou-Haidar, Partitioning crowded virtual environments, Proceedings of the ACM symposium on Virtual reality software and technology, October 01-03, 2003, Osaka, Japan [doi>10.1145/1008653.1008658]
• 30: Tecchia, F., Loscos, C., Conroy, R., and Chrysanthou, Y. 2001. Agent behaviour simulator (ABS): A platform for urban behaviour development. In Games Technology 2001 (GTEC 2001) Hong Kong, China, http://www.cs.ucl.ac.uk/staff/Y.Chrysanthou/crowds/papers/TecchiaGTEC2001.pdf see also: http://www.cs.ucl.ac.Uk/staff/Y.Chrysanthou/crowds/sketch/
• 31: Teschner, M., Heidelberger, B., Mueller, M., Pomeranets, D. Gross, M.. 2003. Optimized spatial hashing for collision detection of deformable objects. Proceedings of Vision, Modeling and Visualization (VMV 2003), pages 47--54. http://citeseer.ist.psu.edu/teschner03optimized.html
• 32: Adrien Treuille , Seth Cooper , Zoran Popović, Continuum crowds, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 33: Bo Zhou , Suiping Zhou, Parallel simulation of group behaviors, Proceedings of the 36th conference on Winter simulation, December 05-08, 2004, Washington, D.C.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Animation

Keywords:
behavioral animation, boids, crowd simulation, distributed processing, flocking, interacting particle systems, multi-agent simulation, multi-processor, parallel processing