Graph-based map representations for efficient path planning in virtual environments

• Main Author: Wardhana, Nicholas Mario
• Other Authors: Seah Hock Soon
• Format: Theses and Dissertations
• Language: English
• Published: 2016
• Subjects: DRNTU::Engineering
• Online Access: http://hdl.handle.net/10356/69025
• Institution: Nanyang Technological University

Path planning is fundamental in various Computer Graphics (CG) applications to determine a character's path so that it can move from one location to a new location in a virtual environment. Path planning requires a map of the environment to work, as it acts as a spatial knowledge for the characters. Some examples of existing map representations are waypoint graph, roadmap, and navigation mesh. In this dissertation, we consider three challenges of planning a path in CG applications. Firstly, the environment is commonly designed as a list of polygons without connectivity information, which makes it difficult to analyse for automatic generation of map representations. Secondly, modern applications feature heterogeneous, variously-sized characters that perform different motions. For example, some move strictly on the ground, while others can move on a wall and fly. However, this is rarely addressed by existing map representations. Thirdly, path planning is computationally heavy if performed on the increasingly common large environments. Based on these challenges, our aim in this dissertation is to design map representations for efficient path planning of heterogeneous characters in virtual environments. We specifically propose \emph{enhanced waypoint graph} and \emph{subregion graph} data structures, as well as the algorithms to generate and use them. Since these map representations are graph-based, we can perform Dijkstra's or A* algorithm on them to plan a path. An enhanced waypoint graph is a graph-based map representation that consists of point nodes (called waypoints), representing the environment features such as corners and openings; as well as edges connecting the waypoints. Every waypoint is associated to a radius, indicating the largest character that can go to and through that location, whereas every edge is labelled with a valid motion type that can be performed along the edge. We also propose two algorithms to automatically generate enhanced waypoint graph. The first algorithm generates a 2-manifold surface from the environment and creates waypoints using corner detection on the manifold surface. The second algorithm performs voxelisation locally, and creates waypoints on voxel level. This algorithm generates higher quality enhanced waypoint graphs, and is also able to handle very large environments, due to the minimum intermediary data structures. When planning a path, only waypoints and edges that support a character's size and motion types are chosen. A subregion graph is a map representation for path planning acceleration in very large 3D virtual environments. Given a 3D waypoint graph and a grid of regions, the basic idea is to cluster locally connected waypoints in every region, and represent them as one node which acts as their abstraction called subregion. When planning a path, Dijkstra's algorithm is performed on subregion graph to yield a subregion path, which contains successive subregions. By only considering waypoints in the subregion path, the path planning process can be accelerated. Based on our experiments, paths planned using subregion graph have average length ratios as low as 102.5\% of the optimal lengths, while up to 8 times average speedup can be achieved. %When original paths do not exist, average speedup can be over 200 times. In summary, the key to make path planning more efficient using the proposed map representations lies on their automatic generation algorithms and, during path planning, on selectively choosing the nodes and edges, for different characters as well as for acceleration purpose. In this way, our map representations and algorithms are useful to plan paths for heterogeneous characters in CG applications that require fast path planning, such as computer games, real-time crowd simulation, and virtual reality.