Abstract
Navigation in virtual environments for autonomous characters is tipically handled by the combination of a path planning algorithm which decides the cells to walk through in the navigation mesh, and a local movement algorithm that carries out the frame to frame trajectory within each cell. Local movement is driven by intermediate goals (attractors) along the portals that connect cells in the navigation mesh. In both cases, clearance should be taken into consideration, since it is relevant when choosing the right sequence of cells that each character can walk by, and also when deciding the location of goals within portals. Previous work has considered clearance for path planning, but it has not been taken into account when assigning attractors within portals. We demonstrate in this work that although a path with clearance guarantees that the character can walk through, it does not guarantee a collision free trajectory. In this work we present three novelties: first a general method for calculating clearance in Navigation Meshes consisting of convex cells of any type which allows for a small degree of concavities, second a novel method for assigning attractors within portals that guarantee collision free paths, and third a new method to dynamically locate attractors over portals based on current trajectory, destination, and clearance.
Media
