A Comparative Study of Navigation Meshes

W.G. van Toll; Roy Triesscheijn; Marcelo Kallmann; Ramon Oliva; Nuria Pelechano; Julien Pettré; R.J. Geraerts

doi:10.1145/2994258.2994262

A Comparative Study of Navigation Meshes

W.G. van Toll, Roy Triesscheijn, Marcelo Kallmann, Ramon Oliva, Nuria Pelechano, Julien Pettré, R.J. Geraerts

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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.

Original language	English
Title of host publication	International ACM SIGGRAPH Conference on Motion in Games
Publisher	Association for Computing Machinery
Pages	91-100
Number of pages	10
ISBN (Print)	9781450345927
DOIs	https://doi.org/10.1145/2994258.2994262
Publication status	Published - Oct 2016
Event	9th International Conference on Motion in Games 2016 - Burlingame, United States Duration: 10 Oct 2016 → 12 Oct 2016 Conference number: 9 https://mig2016.inria.fr/

Conference

Conference	9th International Conference on Motion in Games 2016
Abbreviated title	MiG
Country/Territory	United States
City	Burlingame
Period	10/10/16 → 12/10/16
Internet address	https://mig2016.inria.fr/

Keywords

navigation meshes
path planning
comparative study

Access to Document

10.1145/2994258.2994262

A comparative study of navigation meshesFinal published version, 2.14 MBLicence: Taverne

Cite this

@inproceedings{09d28ea3b45f478ba1ceff3f15b434cb,

title = "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.",

keywords = "navigation meshes, path planning, comparative study",

author = "{van Toll}, W.G. and Roy Triesscheijn and Marcelo Kallmann and Ramon Oliva and Nuria Pelechano and Julien Pettr{\'e} and R.J. Geraerts",

year = "2016",

month = oct,

doi = "10.1145/2994258.2994262",

language = "English",

isbn = "9781450345927",

pages = "91--100",

booktitle = "International ACM SIGGRAPH Conference on Motion in Games",

publisher = "Association for Computing Machinery ",

address = "United States",

note = "9th International Conference on Motion in Games 2016, MiG ; Conference date: 10-10-2016 Through 12-10-2016",

url = "https://mig2016.inria.fr/",

}

van Toll, WG, Triesscheijn, R, Kallmann, M, Oliva, R, Pelechano, N, Pettré, J & Geraerts, RJ 2016, A Comparative Study of Navigation Meshes. in International ACM SIGGRAPH Conference on Motion in Games. Association for Computing Machinery , pp. 91-100, 9th International Conference on Motion in Games 2016, Burlingame, United States, 10/10/16. https://doi.org/10.1145/2994258.2994262

TY - GEN

T1 - A Comparative Study of Navigation Meshes

AU - van Toll, W.G.

AU - Triesscheijn, Roy

AU - Kallmann, Marcelo

AU - Oliva, Ramon

AU - Pelechano, Nuria

AU - Pettré, Julien

AU - Geraerts, R.J.

N1 - Conference code: 9

PY - 2016/10

Y1 - 2016/10

N2 - 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.

AB - 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.

KW - navigation meshes

KW - path planning

KW - comparative study

U2 - 10.1145/2994258.2994262

DO - 10.1145/2994258.2994262

M3 - Conference contribution

SN - 9781450345927

SP - 91

EP - 100

BT - International ACM SIGGRAPH Conference on Motion in Games

PB - Association for Computing Machinery

T2 - 9th International Conference on Motion in Games 2016

Y2 - 10 October 2016 through 12 October 2016

ER -

A Comparative Study of Navigation Meshes

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this