Comparing navigation meshes: Theoretical properties and practical metrics
Wouter van Toll, Roy Triesscheijn, Marcelo Kallmann, Ramon Oliva, Nuria Pelechano, Julien Pettré, Roland Geraerts
Computers & Graphics, vol. 91, pp. 52-82, 2020.
Resources:
Journal website page - Inria HAL page - Full paper (PDF)
Preceding conference publication:
A Comparative Study of Navigation Meshes
Wouter van Toll, Roy Triesscheijn, Marcelo Kallmann, Ramon Oliva, Nuria Pelechano, Julien Pettré, Roland Geraerts
In 9th International ACM SIGGRAPH Conference on Motion in Games, pp. 91-100, 2016.
Resources:
Paper (pdf) - Appendix (pdf) - Presentation (pptx)
Also presented at a national conference:
A Comparative Study of Navigation Meshes
Wouter van Toll, Roy Triesscheijn, Marcelo Kallmann, Ramon Oliva, Nuria Pelechano, Julien Pettré, Roland Geraerts
Presentation and poster in ICT.OPEN 2018, ASCI track.
Received the Poster Award 3rd Prize of ICT.OPEN 2018.
Resources:
Extended abstract (pdf) - Poster (pdf) - Presentation (pptx)
(This is the abstract of the extended journal version of this article.)
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 develop and use a framework for comparing 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. Fourth, we use these properties and metrics to compare various state-of-the-art navigation meshes in a range of 2D and 3D environments. Finally, we analyze our results to identify important topics for future research on navigation meshes.
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 in interesting directions.
@article{vanToll2020-ComparingNavMeshes,
author = {van Toll, W. and Triesscheijn, R. and Kallmann, M. and Oliva, R. and Pelechano, N. and Pettr\'e, J. and Geraerts, R.},
title = {Comparing navigation meshes: Theoretical properties and practical metrics},
journal = {Computers \& Graphics},
volume = {91},
year = {2020},
pages = {52--82}
}
@inproceedings{vanToll2016-ComparativeStudy,
author = {van Toll, W. and Triesscheijn, R. and Kallmann, M. and Oliva, R. and Pelechano, N. and Pettr\'e, J. and Geraerts, R.},
title = {A Comparative Study of Navigation Meshes},
booktitle = {Proceedings of the 9th International ACM SIGGRAPH Conference on Motion in Games},
year = {2016},
pages = {91--100}
}