Research And Implementation Of The FPS Games Pathfinding Algorithm

FPS (First Person Shooter) is a popular direction of the3D gaming market today,from acertain extent, represents the progress and development of game engine technology,3Dgraphics rendering and artificial intelligence module is an important part of the game engine,the game is to find road technology is both a considerable field of study the properties of theartificial intelligence of the game is the core content of a good FPS games, this paperconstructed a in-depth research-based FPS game model of the OGRE open source graphicslibrary and its games, the pathfinding module and algorithm improvements.The game pathfinding theory is based on the game charts used for navigation and Figuresearch pigment technology. Game navigation map is divided into the main grid, polygonmeshes and point of view navigation map, graph search technique blind search and heuristicsearch, A*algorithm is a typical representative of the heuristic search, it is widely used in thegame to find road technology, the traditional A*algorithm in practical applications there aremany efficiency bottleneck, consuming too much memory and CPU resources, there are manystudies on the A*algorithm optimization, including optimization of the Open table andsmoothing the path way finding, you can use a priority queue to implement the Open table inorder to reduce the time complexity to remove the most advantages, and use Penalty factortechnology to smooth out the game path.Do research and optimization of this article can view navigation map in FPS games,discusses the relatively traditional A*optimization method, to optimize the data storagestructure of the A*search, using a more intelligent path smoothing technique; furtheroptimization of valuation functions; and lead to inefficiencies is optimized for advanced AImodule frequently call the A*algorithm and its application with more than one source ormultiple target point of the game find its way to go.