A Comparative Study of Navigation Meshes
Summary
A navigation mesh is a data structure that models the walkable space in a virtual world in order to accelerate path planning and crowd simulation tasks. Few papers compare the performance of navigation mesh techniques using objective measurements and structured repeatable experiments. There exists no standard set of measurements to compare the findings of different researchers.
In this thesis, we compare five navigation mesh techniques using a theoretical analysis and experiments.
We introduce a set of metrics with which the performance of navigation mesh techniques can be objectively measured. Using these metrics and a set of more than 120 virtual worlds, from test cases that focus on a single metric to real-world examples, we set a standard for comparing navigation mesh techniques.
Our results show that exact techniques are often faster and more memory-efficient than sampling-based techniques. Sampling-based techniques, while in theory inexact, can approximate the walkable space with a very high accuracy. There are also large differences between techniques in terms of the complexity of their subdivision of the walkable space. Implementing navigation mesh techniques is not trivial, as many existing implementations contain serious bugs and not all techniques are able to correctly compute navigation meshes for the virtual worlds they are meant to support.
Using our theoretical analysis, experiment results, and metrics, we provide tools and information for creating measurably better navigation mesh techniques.