A Study on the Partial Path Generation in the A* Path Search

Abstract

When moving to a target position in a computer game, the NPC( non-player character ) performs a path search to that position. While the path search is running, NPC has to wait for the search results before starting the actual movement. This increases the amount of time it takes to process all the path search requests with limited CPU resources in games with hundreds of agents or large graphs, making this approach slow to play. Although overall game play can be facilitated by limiting the CPU resource allocated to path search, the allocated path search time should be shared by many NPCs. If the delay becomes too long with limited search time, NPC will either wait vaguely or proceed aimlessly into walls or other obstacles. In this case, one solution is for the NPC to determine the partial path to the target position early before waiting for the completed path. This means changing the A* algorithm to return a path to the node closest to the target after a user-defined number of search cycles or search depth has been reached. The NPC can then follow this sub-path until a complete path is generated and arrived in between and arrive at the final destination reflecting the entire path. Experiments have shown that when partial path is generated, real-time game has a much more realistic effect.