A comparative study of navigation meshes

Abstract : A navigation mesh is a representation of a 2D or 3D virtual environment that enables path planning and crowd simulation for walking characters. Various state-of-the-art navigation meshes exist, but there is no standardized way of evaluating or comparing them. Each implementation is in a different state of maturity, has been tested on different hardware, uses different example environments, and may have been designed with a different application in mind. In this paper, we conduct the first comparative study of navigation meshes. First, we give general definitions of 2D and 3D environments and navigation meshes. Second, we propose theoretical properties by which navigation meshes can be classified. Third, we introduce metrics by which the quality of a navigation mesh implementation can be measured objectively. Finally, we use these metrics to compare various state-of-the-art navigation meshes in a range of 2D and 3D environments. We expect that this work will set a new standard for the evaluation of navigation meshes, that it will help developers choose an appropriate navigation mesh for their application, and that it will steer future research on navigation meshes in interesting directions.
Type de document :
Communication dans un congrès
MIG '16 - 9th International Conference on Motion in Games , Oct 2016, San Francisco, United States. ACM, pp.91 - 100, 2016, 〈http://mig2016.inria.fr/〉. 〈10.1145/2994258.2994262〉
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01392267
Contributeur : Julien Pettré <>
Soumis le : vendredi 4 novembre 2016 - 11:15:42
Dernière modification le : mercredi 16 mai 2018 - 11:23:03
Document(s) archivé(s) le : dimanche 5 février 2017 - 13:37:25

Fichier

comparative_study_of_navigatio...
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Wouter Van Toll, Roy Triesscheijn, Marcelo Kallmann, Ramon Oliva, Nuria Pelechano, et al.. A comparative study of navigation meshes. MIG '16 - 9th International Conference on Motion in Games , Oct 2016, San Francisco, United States. ACM, pp.91 - 100, 2016, 〈http://mig2016.inria.fr/〉. 〈10.1145/2994258.2994262〉. 〈hal-01392267〉

Partager

Métriques

Consultations de la notice

463

Téléchargements de fichiers

820