Real-time Adaptive GPU Multiagent Path Planning

This chapter presents a graphics processing units (GPU) path planning algorithm that is derived from the sequential A* algorithm to allow massively parallel, real-time execution. Many types of computer games involve player and nonplayer characters moving over terrain. In real-time strategy games the player doesn't control any characters directly. Instead, the player selects a group of characters (or agents) and then selects a target position with the mouse. The target position can be in a known position or an unknown position. The agents then have to find their own way to the target position. If they observe that their current trajectory is blocked after they have started moving, they have to search for another path. A* is the most famous algorithm for finding cost-minimal paths in state spaces, which are usually represented as graphs. The search performed by A* is ideal for off-line artificial intelligence applications, but it is not suitable for computer games where agents have to search paths in real time. Real-Time Adaptive A* is a real-time heuristic search method that chooses its local search spaces in a very fine-grained way. The main idea is to update the heuristics of all states in the local search space very quickly and to save the heuristics to speed up future A* searches. This approach uses a variable called look ahead, which specifies the largest number of states to expand during an A* search. The key aim in designing and implementing a RTAA* multiagent path plan in the GPU is to reduce the memory required for all states.