View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        A Comparative Study of Navigation Meshes

        Thumbnail
        View/Open
        V4_Final.pdf (16.54Mb)
        Publication date
        2014
        Author
        Triesscheijn, R.A.
        Metadata
        Show full item record
        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.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/19105
        Collections
        • Theses
        Utrecht university logo