A Kind Of Moving Target Search Algorithm For The Local Search Space

The path-finding for moving target is one of the most challenging topics in the game Artificial Intelligence (AI). The corresponding research results can be applied to a widely range, including robots, virtual simulation, and real-time strategy games.In the paper, we firstly analyze the principle of search technology in AI and the moving target search algorithm in real-time games, MTS. Then, we propose a new moving target search algorithm, LSS-MTS, with local search space to solve the inefficient of searching and updating in MTS. LSS-MTS uses A* to determine its local searching spaces and up-date the h-values of all states in the local search spaces to learn quickly. It can satisfy hard real-time requirements of path search in large-scale game scene and the reality.The experiment shows that, compared with the MTS algorithm, the new algorithm has obvious advantages in capturing the target, success rate and the average search time. By pre-setting the lookahead value according to the elapse time of searching space, LSS-MTS algorithm reduces the searching time and satisfies real-time requirements rather well.