Efficient obstacle avoidance using autonomously generated navigation meshes

With the increasing demand for ever more depth and detail of modern video games, developers are faced with the problem of how to create and manage large amounts of content. One aspect of this is how to cheaply enable game entities to travel through their virtual worlds in a natural and realistic fashion. Game map sizes and complexity have however risen to such an extent that there is a strong demand for automization in order to relieve artists and designers from their medial tasks, and enable them to focus more on the creative aspect of game design. As a solution to this, we introduce systems for the autonomous generation of precomputed Navigation Meshes (NavMeshes) and their in-game application. These meshes contain abstractions of all walkable surfaces of a static map environment in the form of a set of convex areas and a matching graph topology. We discuss the pros and cons of generating them solely from map collision volumes using a 'lightweight' form of Boundary Representation (B-rep or BREP) algorithm, to help remove areas that cannot be reached due to the dimension of the traveling objects. This B-rep approach provides compact yet accurate NavMeshes abstractions that are ideal for classic path-finding algorithms. Natural movement around dynamic obstacles is achieved using a combination of 'fuzzy' whiskers sensory systems, and a 'deterministic' fall-back mechanism that temporarily enhances the resolution of the NavMesh graph locally. Further speed-ups are obtained by parallelizing classic A* algorithms for nowadays common multi-core architectures. We introduce the 'Parallel Bidirectional Search' that significantly outperforms traditional A* implementations.MediamaticsElectrical Engineering, Mathematics and Computer Scienc