Research And Application On Dynamic Pathfinding Algorithm For 3D Game Scenes

For the dynamic pathfinding of objects in a three-dimensional game scene there are too many search nodes low efficiency and avoiding oscillation problems caused by dynamic obstacles.This paper makes improvements in global path search and local dynamic avoidance.In the global path search the octree tree voxelization method is used to rasterize 3D search space then the walkable region is generated according to the voxel slope and height and the navigation grid is generated by the Delaunay triangulation algorithm.Finally for the navigation grid the heuristic function of the A* algorithm and the data structure of the path finding node are improved respectively and the generated path is smoothed thereby improving the search efficiency and the accuracy of the search path of the A* algorithm.In the aspect of local dynamic collision avoidance the concept of speed obstacle is introduced and the cause of vibration in dynamic collision avoidance process is analyzed.The priority collision speed avoidance algorithm based on target region is given which breaks the symmetry in collision avoidance process.Effectively solves the oscillation problem in dynamic pathfinding.In the experimental simulation part based on the Unity3 D game engine the global path search experiment simulation was built and the performance difference between the navigation grid optimization A* algorithm and the conventional grid map A* algorithm was compared.Finally a dynamic pathfinding simulation of the 3D game scene is made which simulates the state of the dynamic path finding of the game character in the 3D scene.Finally through experiments and simulations it is concluded that the navigation grid optimization A* algorithm combined with the target region mutual velocity dynamic collision avoidance algorithm can greatly improve the search efficiency in dynamic path finding and solve the oscillation problem caused by dynamic collision avoidance.