Hierarchical Path Finding to Speed Up Crowd Simulation
Abstract
Path finding is a common problem in computer games. Most videogames require to simulate thousands or millions of agents who interact and navigate in a 3D world showing capabilities such as chasing, seeking or intercepting other agents. A new hierarchical path finding solution is proposed for large environments. Thus, a navigation mesh as abstract data structure is used in order to divide the 3D world. Then, a hierarchy of graphs is built to perform faster path finding calculations than a common A*. The benefits of this new approach are demonstrated on large world models.
Downloads
References
Loscos, Céline and Marchal, David and Meyer, Alexandre, Intuitive Crowd Behavior in Dense Urban Environments using Local Laws., Theory and Practice of Computer Graphics, 2003. Proceedings, pp. 122 - 129. Jun 2003.
F. Tecchia, C. Loscos, Y. Chrysanthou, Visualizing Crowds in Real-Time, Computer Graphics forum, pp. 753 - 765, Dec 2002.
Franco Tecchia and Céline Loscos and Ruth Conroy and Yiorgos Chrysanthou, Agent Behaviour Simulator (ABS): A Platform for Urban Behaviour Development, In GTEC’2001, pp. 17-21, 2001.
Lydia Kavraki and Petr Svestka and Jean-claude Latombe and Mark Overmars, Probabilistic Roadmaps for Path Planning in HighDimensional Configuration Spaces, Robotics and Automation, vol. 12, pp. 566 - 580, Aug 1996.
Nieuwenhuisen, D.; Kamphuis, A.; Mooijekind, M.; Overmars, M.H., Creating Small Roadmaps for Solving Motion Planning Problems, IEEE International Conference on Methods and Models in Automation and Robotics, pp. 531-536, 2005.
R. Geraerts and M.H. Overmars, Automatic Construction of High Quality Roadmaps for Path Planning, Utrecht University: Information and Computing Sciences, 2004.
M. Mononen. (2015, April 8), Navigation-mesh Toolset for games, GitHub Recast and Detour, 2014. Available: https://github.com/memononen/recastnavigation.
P. E. Hart, N. J. Nilsson, and B. Raphael., A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems, Science, and Cybernetics, vol. 4, pp. 100 - 107, July 1968.
Maxim Likhachev and Geoffrey J. Gordon and Sebastian Thrun., ARA*: Anytime A* with Provable Bounds on Sub-Optimality, Advances in Neural Information Processing Systems 16, 2004.
Koenig, Sven and Likhachev, Maxim. D*Lite, Eighteenth National Conference on Artificial Intelligence, pp. 476 - 483, 2002.
Maxim Likhachev, David Ferguson , Geoffrey Gordon, Anthony (Tony) Stentz, and Sebastian Thrun., Anytime Dynamic A*: An Anytime, Replanning Algorithm, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), Jun 2005.
Haumont, D. and Debeir, Olivier and Sillion, François X., Volumetric Cell-and-Portal Generation, Comput. Graph. Forum, 2003.
Roerdink, Jos B.T.M. and Meijster, Arnold., The Watershed Transform: Definitions, Algorithms and Parallelization Strategies., Fundam. Inf. Forum, vol. 22, pp. 303 - 312, Sep 2003.
David P. Luebke., A Developer's Survey of Polygonal Simplification Algorithms., IEEE Computer Graphics and Applications., vol. 21, pp. 24 - 35, May 2001.
G. Karypis and Vipin Kumar., Multilevel k-way Partitioning Scheme for Irregular Graphs., Journal of Parallel and Distributed Computing., vol. 48, pp. 96 - 129, Jan 1998.
Kernighan, B.W. and Lin, S., An Efficient Heuristic Procedure for Partitioning Graphs, The Bell Systems Technical Journal, vol. 49, 1970.
Adi Botea and Martin Müller and Jonathan Schaeffer, Near optimal hierarchical path-finding., Journal of Game Development., vol. 1, pp. 7 - 28, 2004.
Joseph O'Rourke, Computational Geometry in C., 2nd ed, Computational Intelligence and Games, 2008. CIG '08. IEEE Symposium On, pp. 258 - 265, Dec. 2008.
Daniel Harabor and Adi Botea., Hierarchical path planning for multi-size agents in heterogeneous environments, CIG, 2008.
This article is published by LAJC under a Creative Commons Attribution-Non-Commercial-Share-Alike 4.0 International License. This means that non-exclusive copyright is transferred to the National Polytechnic School. The Author (s) give their consent to the Editorial Committee to publish the article in the issue that best suits the interests of this Journal. Find out more in our Copyright Notice.
Disclaimer
LAJC in no event shall be liable for any direct, indirect, incidental, punitive, or consequential copyright infringement claims related to articles that have been submitted for evaluation, or published in any issue of this journal. Find out more in our Disclaimer Notice.
