Autonomous agents typically need a navigation mesh of a 3D virtual environment to allow efficient path planning. This mesh needs as input a continuous representation of the walkable areas. However, the walkable environment (WE), i.e. the parts of the 3D environment that an agent can walk on, may contain gaps. These may be due to the filtering steps performed to compute the WE, because of modelling errors in the 3D model, or simply be part of the geometry of the environment. We provide an algorithm that identifies and fills these gaps. We detect gaps, up to a given distance, between pairs of boundary edges of the walkable environment, and fill them with polygons. We employ a heuristic for choosing which pairs of edges should be connected. We compare our algorithm to Recast [10], a voxel-based method for navigation mesh generation. We find that our method gives more accurate results in many environments: it retains the exact representation of the walkable environment, semantically separates the gaps from the walkable areas, and requires no tweaking of parameters to obtain good results. However, our method is currently slower than Recast, and requires more memory.

Abstract Thek‐nearest neighbour (kNN) problem appears in many different fields of computer science, such as computer animation and robotics. In crowd simulation,kNN queries are typically used by a collision‐avoidance method to prevent unnecessary computations. Many different methods for finding these neighbours exist, but it is unclear which will work best in crowd simulations, an application which is characterised by low dimensionality and frequent change of the data points. We therefore compare several data structures for performingkNN queries. We find that the nanoflann implementation of ak‐d tree offers the best performance by far on many different scenarios, processing 100,000 agents in about 35 ms on a fast consumer PC.

We describe and demonstrate the Explicit Corridor Map (ECM), a navigation mesh for path planning and crowd simulation in virtual environments. For a bounded 2D environment with polygonal obstacles, the ECM is the medial axis of the free space annotated with nearest-obstacle information. It can be used to compute short and smooth paths for disk-shaped characters of any radius. It is also well-defined for multi-layered 3D environments that consist of connected planar layers. We highlight various operations on the ECM, such as dynamic updates, visibility queries, and the computation of paths (indicative routes). We have implemented the ECM as the basis of a real-time crowd simulation framework with path following and collision avoidance. Our implementation has been successfully used to simulate real-life events involving large crowds of heterogeneous characters. The enclosed demo application displays various features of our software.

A multi-layered environment (MLE) [van Toll et al. 2011] is a representation of the walkable environment (WE) in a 3D virtual environment that comprises a set of two-dimensional layers together with the locations where the different layers touch, which are called connections. This representation can be used for crowd simulations, e.g. to determine evacuation times in complex buildings, or for finding the shortest routes. The running times of these algorithms depend on the number of connections.

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.

Modern simulations feature crowds of AI-controlled agents moving through dynamic environments, with obstacles appearing or disappearing at run-time. A dynamic navigation mesh can represent the traversable space of such environments. The A* algorithm computes optimal paths through the dual graph of this mesh. When an obstacle is inserted or deleted, the mesh changes and agents should re-plan their paths. Many existing re-planning algorithms are too memory-intensive for crowds, or they cannot easily be used on graphs where vertices and edges are added or removed. In this paper, we present Dynamically Pruned A* (DPA*), an extension of A* for re-planning optimal paths in dynamic navigation meshes. DPA* has similarities to adaptive algorithms that make the A* heuristic more informed based on previous queries. However, DPA* prunes the search using only the previous path and its relation to the dynamic event. We describe the four re-planning scenarios that can occur; DPA* uses different rules in each scenario. Our algorithm is memory-friendly and robust against structural changes in the graph, which makes it suitable for crowds in dynamic navigation meshes. Experiments show that DPA* performs particularly well in complex environments and when the dynamic event is visible to the agent. We integrate the algorithm into crowd simulation software to model large crowds in dynamic environments in real-time.

We present a new method, Social Groups and Navigation (SGN), to simulate the walking behavior of small pedestrian groups in virtual environments. SGN is the first method to simulate group behavior on both global and local levels. We define quantitative metrics to measure the coherence and the sociality of a group based on existing empirical data of real crowds. SGN is designed to let groups stay in coherent and social formations without explicitly modeling such formations. For groups of four, SGN generates between 13% and 53% more socially-friendly behavior than existing methods, measured over the lifetime of a group in the simulation. For groups of three, the gain is between 15% and 31%, and for groups of two, the gain is between 1% and 4%. SGN can be used with any existing global path planner and any existing path following method. Experiments show that SGN enables the simulation of thousands of agents in real time. Due to its flexible design, it can be easily integrated into a larger crowd simulation framework.

This paper presents a GPU-accelerated approach for improving the approximated construction of Generalized Voronoi Diagrams (GVDs). Previous work has shown how to render a GVD onto the GPU framebuffer, and copy it to the CPU for extraction of a high-quality diagram. We improve upon this technique by performing more computations in parallel on the GPU, and reducing the amount of data transferred to the CPU. We also design a multi-tiled construction technique that overcomes hardware limitations and enables much higher rendering resolutions, thus reducing discretization errors. Next, we extend our approach to create an Explicit Corridor Map navigation mesh, which is an efficient data structure for path planning in modern crowd simulation systems. The new implementation allows much faster construction of GVDs and navigation meshes at virtually infinite resolutions.

The Weighted Region Problem is defined as the problem of finding a cost-optimal path in a weighted planar polygonal subdivision. Searching for paths on a grid representation of the scene is fast and easy to implement. However, grid representations do not capture the exact geometry of the scene. Hence, grid paths can be inaccurate or might not even exist at all. Methods that work on an exact representation of the scene can approximate an optimal path up to an arbitrarily small ε-error. However, these methods are computationally inefficient and thus not well-suited for real-time applications. In this paper, we analyze the quality of optimal paths on a 8-neighbor-grid. We prove that the costs of such a path in a scene with weighted regions can be arbitrarily high in the general case. If all regions are aligned with the grid, we prove that the costs are at most (4+[EQUATION]) times the costs of an optimal path. In addition, we present a new hybrid method called Vertex-based Pruning (VBP). VBP computes paths that are ε-optimal inside a pruned subset of the scene. Experiments show that VBP paths can be computed at interactive rates, and are thus well-suited as an input for advanced path-following strategies in robotics, crowd simulation or gaming applications.

ABSTRACT Modern virtual environments can contain a variety of characters and traversable regions. Each character may have different preferences for the traversable region types. Pedestrians may prefer to walk on sidewalks, but they may occasionally need to traverse roads and dirt paths. By contrast, wild animals might try to stay in forest areas, but they are able to leave their protective environment when necessary. This paper presents a novel path planning method named Modified Indicative Routes and Navigation (MIRAN) that takes a character's region preferences into account. Given an indicative route as a rough estimation of a character's preferred route, MIRAN efficiently computes a visually convincing path that is smooth, keeps clearance from obstacles, avoids unnecessary detours, and allows local changes to avoid other characters. To the best of our knowledge, MIRAN is the first path planning method that supports the aforementioned features while using an exact representation of the navigable space. Experiments show that with our approach, a wide range of different character behaviors can be simulated. It also overcomes problems that occur in previous path planning methods such as the Indicative Route Method. The resulting paths are well suited for real‐time simulations and gaming applications. Copyright © 2013 John Wiley & Sons, Ltd.

ABSTRACT Virtual characters in games and simulations often need to plan visually convincing paths through a crowded environment. This paper describes how crowd density information can be used to guide a large number of characters through a crowded environment. Crowd density information helps characters avoid congested routes that could lead to traffic jams. It also encourages characters to use a wide variety of routes to reach their destination. Our technique measures the desirability of a route by combining distance information with crowd density information. We start by building a navigation mesh for the walkable regions in a polygonal two‐dimensional (2‐D) or multilayered three‐dimensional (3‐D) environment. The skeleton of this navigation mesh is the medial axis. Each walkable region in the navigation mesh maintains an up‐to‐date density value. This density value is equal to the area occupied by all the characters inside a given region divided by the total area of this region. These density values are mapped onto the medial axis to form a weighted graph. An A* search on this graph yields a backbone path for each character, and forces are used to guide the characters through the weighted environment. The characters periodically replan their routes as the density values are updated. Our experiments show that we can compute congestion‐avoiding paths for tens of thousands of characters in real‐time. Copyright © 2012 John Wiley & Sons, Ltd.

ABSTRACT Games and simulations frequently model scenarios where obstacles move, appear, and disappear in an environment. A city environment changes as new buildings and roads are constructed, and routes can become partially blocked by small obstacles many times in a typical day. This paper studies the effect of usinglocalupdates to repair only the affected regions of a navigation mesh in response to a change in the environment. The techniques are inspired by incremental methods for Voronoi diagrams. The main novelty of this paper is that we show how to maintain a 2D or 2.5Dnavigation meshin an environment that contains dynamic polygonal obstacles. Experiments show that local updates are fast enough to permit real‐time updates of the navigation mesh. Copyright © 2012 John Wiley & Sons, Ltd.

Virtual characters often need to plan visually convincing paths through a complicated environment. For example, a traveler may need to walk from an airport entrance to a staircase, descend the staircase, walk to a shuttle, ride the shuttle to a destination, ride an elevator back to the ground floor, and finally move on the ground floor again to reach the desired airplane. Most previous research only supports path planning in a single plane because the underlying data structures are two-dimensional. The goal of this paper is to permit visually convincing paths to be efficiently computed in a multi-layered environment such as an airport or a multi-storey building. We describe an algorithm to create a navigation mesh, and our implementation demonstrates the feasibility of the approach. A multi-layered environment is represented by a set of two dimensional layers and a set of connections. Each layer is a collection of two-dimensional polygons that all lie in a single plane, and each connection provides a means of moving between layers. We first compute the traditional medial axis of each two dimensional layer in the environment. The connections are then used to iteratively merge this collection of medial axes into a single data structure. By adding a linear number of line segments to this structure, we obtain a navigation mesh that mathematically describes the walkable areas in a multi layered environment. This mesh can easily be input into existing planners to generate visually convincing paths for thousands of virtual characters in real-time.

Abstract Natural locomotion of virtual characters is very important in games and simulations. The naturalness of the total motion strongly depends on both the path the character chooses and the animation of the walking character. Therefore, much work has been done on path planning and generating walking animations. However, the combination of both fields has received less attention. Combining path planning and motion synthesis introduces several problems. In this paper, we will identify two problems and propose possible solutions. The first problem is selecting an appropriate distance metric for locomotion synthesis. When concatenating clips of locomotion, a distance metric is required to detect good transition points. We have evaluated three common distance metrics both quantitatively (in terms of footskating, path deviation and online running time) and qualitatively (user study). Based on our observations, we propose a set of guidelines when using these metrics in a motion synthesizer. The second problem is the fact that there is no single point on the body that can follow the path generated by the path planner without causing unnatural animations. This raises the question how the character should follow the path. We will show that enforcing the pelvis to follow the path will lead to unnatural animations and that our proposed solution, which uses path abstractions, generates significantly better animations. Copyright © 2011 John Wiley & Sons, Ltd.

A central problem of applications dealing with virtual environments is planning a collision-free path for a character. Since environments and their characters are growing more realistic, a character's path needs to be visually convincing, meaning that the path is smooth, short, has some clearance to the obstacles in the environment, and avoids other characters. Up to now, it has proved difficult to meet these criteria simultaneously and in real-time. We introduce a new data structure, i.e. the Explicit Corridor Map, which allows creating the shortest path, the path that has the largest amount of clearance, or any path in between. Besides being efficient, the corresponding algorithms are surprisingly simple. By integrating the data structure and algorithms into the Indicative Route Method, we show that visually convincing short paths can be obtained in real-time.

An important challenge in virtual environment applications is to steer virtual characters through complex and dynamic worlds. The characters should be able to plan their paths and move toward their desired locations, avoiding at the same time collisions with the environment and with other moving entities. In this paper we propose a general method for realistic path planning, the Indicative Route Method (irm). In the irm, a so-called indicative route determines a global route for the character, whereas a corridor around this route is used to handle a broad range of other path planning issues, such as avoiding characters and computing smooth paths. As we will show, our method can be used for real-time navigation of many moving characters in complicated environments. It is fast, flexible and generates believable paths.

A central problem in robotics is planning a collision-free path for a moving object in an environment with obstacles. Contemporary applications require a path planner that is fast (to ensure real-time interaction with the environment) and flexible (to avoid local hazards). In addition, paths need to be smooth and short. We propose a new framework, the corridor map method, which meets these requirements.

Abstract In many virtual environment applications, paths have to be planned for characters to traverse from a start to a goal position in the virtual world while avoiding obstacles. Contemporary applications require a path planner that is fast (to ensure real‐time interaction with the environment) and flexible (to avoid local hazards such as small and dynamic obstacles). In addition, paths need to be smooth and short to ensure natural looking motions. Current path planning techniques do not obey these criteria simultaneously. For example, A* approaches generate unnatural looking paths, potential field‐based methods are too slow, and sampling‐based path planning techniques are inflexible. We propose a new technique, the Corridor Map Method (CMM), which satisfies all the criteria. In an off‐line construction phase, the CMM creates a system of collision‐free corridors for the static obstacles in an environment. In the query phase, paths can be planned inside the corridors for different types of characters while avoiding dynamic obstacles. Experiments show that high‐quality paths for single characters or groups of characters can be obtained in real‐time. Copyright © 2007 John Wiley & Sons, Ltd.

Our goal is to create road maps that are particularly suited for motion planning in virtual environments. We use our reachability roadmap method to compute an initial, resolution complete roadmap. This roadmap is small which keeps query times and memory consumption low. However, for use in virtual environments, there are additional criteria that must be satisfied. In particular, we require that the roadmap contains useful cycles. These provide short paths and alternative routes which allow for variation in the routes a moving object can take. We will show how to incorporate such cycles. In addition, we provide high-clearance paths by retracting the edges of the roadmap to the medial axis. Since all operations are performed in a preprocessing phase, high-quality paths can be extracted in real-time as is required in interactive applications

The last decade, sampling based planners like the Probabilistic Roadmap Method have proved to be successful in solving complex motion planning problems. We give a reachability based analysis for these planners which leads to a better understanding of the success of the approach and enhancements of the techniques suggested. This also enables us to study the effect of using new local planners.

In robot motion planning, many algorithms have been proposed that create a path for a robot in an environment with obstacles. Since it can be hard to create such paths, most algorithms are aimed at finding a solution. However, for most applications the paths must be of a good quality as well. That is, paths should preferably be short, be smooth, and should preserve some clearance from the obstacles. In this paper, we focus on improving the clearance of paths. Existing methods only extract high clearance paths for rigid, translating bodies. We present an algorithm that improves the clearance along paths of a broader range of robots which may reside in arbitrary high-dimensional configuration spaces. Examples include planar, free-flying and articulated robots.

Many motion planning techniques, like the probabilistic roadmap method (PRM), generate low quality paths. In this paper, we study a number of different quality criteria on paths in particular length and clearance. We describe a number of techniques to improve the quality of paths. These are based on a new approach to increase the path clearance. Experiments showed that the heuristics were able to generate paths of a much higher quality than previous approaches.