Hierarchical Path Finding to Speed Up Crowd Simulation
Palabras clave:
Hierarchical path finding, path planning, crowd simulation, navigation meshes, HPA*, A*Resumen
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.
Descargas
Referencias
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.
Descargas
Publicado
Número
Sección
Licencia
Aviso de derechos de autor/a
Los autores/as que publiquen en esta revista aceptan las siguientes condiciones:
- Los autores conservan los derechos de autor y ceden a la revista el derecho de la primera publicación, con el trabajo registrado con la Creative Commons Attribution-Non-Commercial-Share-Alike 4.0 International, que permite a terceros utilizar lo publicado siempre que mencionen la autoría del trabajo y a la primera publicación en esta revista.
- Los autores pueden realizar otros acuerdos contractuales independientes y adicionales para la distribución no exclusiva de la versión del artículo publicado en esta revista (p. ej., incluirlo en un repositorio institucional o publicarlo en un libro) siempre que indiquen claramente que el trabajo se publicó por primera vez en esta revista.
- Se permite y recomienda a los autores a compartir su trabajo en línea (por ejemplo: en repositorios institucionales o páginas web personales) antes y durante el proceso de envío del manuscrito, ya que puede conducir a intercambios productivos, a una mayor y más rápida citación del trabajo publicado.
Descargo de Responsabilidad
LAJC en ningún caso será responsable de cualquier reclamo directo, indirecto, incidental, punitivo o consecuente de infracción de derechos de autor relacionado con artículos que han sido presentados para evaluación o publicados en cualquier número de esta revista. Más Información en nuestro Aviso de Descargo de Responsabilidad.
