Abstracts Category : Other

Navigation for Characters and Crowds in Complex Virtual Environments

by Toll WG van

In acrowd simulation, virtual walking characters need to compute and traverse paths through a virtual environment while avoiding collisions. Simulations of large crowds occur increasingly often in computer games, in which real-time performance is required. Also, there is an increasing demand for crowd simulations ofreal-world scenarios. For example, crowd simulations can be used to predict dangerous situations during crowded events such as festivals, or to estimate if a sports stadium can be evacuated within a certain amount of time. Thus, path planning and crowd simulation are important research topics. Part I of this gives an overview of these topics and related work. Anavigation meshis an efficient representation of a virtual environment for the purpose of real-time path planning and crowd simulation. When planning a path in a navigation mesh, we actually compute a sequence ofregionsfor the character to move through. Within these regions, the character can compute anindicative route, which it can then follow in real-time while avoiding other moving characters. The rest of this thesis investigates how to use navigation meshes to model and simulate complex scenarios. Part II of this thesis revolves around the navigation mesh itself. It describes: A navigation mesh for efficient path planning for disk-shaped characters of any size in a 2D virtual environment.An extension of this navigation mesh tomulti-layeredenvironments, such as buildings with multiple floors connected by staircases. Many algorithms that existed in 2D can be extended to handle multi-layered environments as well.Algorithms for locally updating a navigation mesh when an obstacle appears or disappears during the simulation; for example, imagine a vehicle blocking a street, or a bridge collapsing.A comparative study of various navigation meshes that have been developed in the past decade. It provides a theoretical comparison as well as a practical comparison based on novel quality metrics. In Part III of this thesis, we develop new methods for path planning and crowd simulation in navigation meshes: An algorithm that efficiently recomputes a path after the navigation mesh has been updated locally. This improves the efficiency of crowd simulations in large dynamic environments.An algorithm that maps the currentcrowd densityonto the navigation mesh, such that characters can take this density into account when planning their paths. This algorithm is based onfundamental diagramsthat describe the empirically observed relation between crowd density and (typical) walking speeds.A generic five-level framework that describes how crowd simulation software can be structured. We demonstrate an implementation of this framework that can simulate tens of thousands of characters in real-time. Part IV concludes that these algorithms and implementations can be used to efficiently simulate increasingly complex scenarios. The most important topics for future work are the automatic extraction of a multi-layered environment from raw 3D geometry, the extensionAdvisors/Committee Members: van Kreveld, Marc, Geraerts, Roland.