GPU Accelerated Path-planning for Multi-agents in Virtual Environments

Figure 1: Virtual characters controlled by the BVP Planner in a virtual environment. Many games are populated by synthetic humanoid actors that act as autonomous agents. The animation of humanoids in real-time applications is yet a challenge if the problem involves attaining a precise location in a virtual world (path-planning), and moving re-alistically according to its own personality, intentions and mood (motion planning). In this paper we present a strategy to imple-ment – using CUDA on GPU – a path planner that produces natural steering behaviors for virtual humans using a numerical solution for boundary value problems. The planner is based on the poten-tial field formalism that allows synthetic actors to move negotiat-ing space, avoiding collisions, and attaining goals, while producing very individual paths. The individuality of each character can be set by changing its inner field parameters leading to a broad range of possible behaviors without jeopardizing its performance. With our GPU-based strategy we achieve a speed up to 56 times the previous implementation, allowing its use in situations with a large number of autonomous characters, which is commonly found in games