A Research On Multi-agent Path Finding System In Polygon-based Scenes

In recent years, with competition in the gaming market, the demands for the gaming technology are increasing. Artificial intelligence, with the ability to make virtual characters smarter and more intelligent, is paid more and more attention on industry and academia with the development of gaming technology. Inside it, the path-finding system is the basis and important part of today’s game and navigation system etc.For the various practical problems in complex scenes of games, this article discusses about the architecture and implementation of the whole path-finding system within the two-dimensional continuous space with several obstacles formed by polygons, which requires multi-agent to avoid collision. The main content of the path-finding system include s the following aspects:(1) In terms of scene analysis and visible point generating, this text presents the visible point generating algorithm based on morphological expansion on polygon-based obstacles with small calculation and convenience for partial modification, and presents another visible point generating algorithm based on two-dimensional cylinder to improve the connectivity of the visible points.(2) In terms of the path-finding algorithms, this text introduces a method to judge the line segments intersection based on the method of cross vector product, and puts forward the generating method of visibility graph structure cache generation, and describes the A* path-finding algorithm based on the structure in detail.(3) During the research on the rotational invariant bounding circles of agents, this text discusses about their collision detection algorithms. To avoid the collisions from each other, the text puts forward an improved forward collision prevention method, according to the position relationship between two circles and the detection of their going nearer to or away from each other, which improves the numerical robustness. To avoid the collisions from polygon obstacles, the text puts forward the idea to previously expand the polygons according to each units’radius, so as to use the judgment on whether points are in those expanded polygons to approximately see the collision.(4) In terms of the circumambulation among the agents, the text presents circumambulating algorithms by single agents, or by multiple agents sometimes with the circumambulation ahead of time, which are within the total time complexity at O(n2) to guarantee the real-time performance, and are able to let the entire agents gradually close to the destination with the improvements of them.(5) In terms of the combination on the circumambulating algorithms and the A* path-finding algorithm based on visible points, the text puts forward the range judgment method to let agents not too close to the visible points, so as to enhance the speed of multiple agents’passing through the visible points, and to improve the path-finding effects. Besides, the text lets the agents find some other paths when they hit the polygon obstacles.The main innovations in this article are the two different visible point generating algorithms, which reduce the workload of game makers, and the presented circumambulating algorithms to adjust the agents’formation, so as to guarantee the performance, and gradually make agents closer to the destination. Besides, the text also makes some optimizations and improvements in some other aspects.