AI Pathfinding Algorithm In The Research And Application Of Electronic Games

In the design and development of electronic games, with the constant upgrading of hardware performance.The game sound effects and visual effects have been greatly enhanced and improved.However, the research and application of artificial intelligence technology is comparatively backward. So the behavior of Non-Player Character looks like very monotonous and stupid, seriously affecting the quality of the game.In recent years, artificial intelligence gradually improve and enhance the quality of the game's hottest topics of study.the behaviors of NPC must not only smart but also smart variety.In game software, Artificial Intelligence is an important and complicated module.Shortest-Path Search is one of the most basic questions in which artificial intelligence applied to electronic games.In today's game industry, A* algorithm is the most widely used AI Pathfinding algorithm,which also is the most effective shortest-path search algorithm. A* algorithm is based on breadth - first search, and plus heuristic search .Commonly used scored function: f (n) = g (n) + h (n) ,scoring the current position. Finding the lowest F cost node is the A* Algorithm slowest part,Binary heaps quickly sort the open list, that greatly optimize the search speed of the open list's elements.this approach will be at least 2-3 times as fast in most situations,and geometrically faster(10+ times) on longer paths.In a large map ,applying one grid-density, usually, Pathfinding will be very slowly, or not true enough to play walk.when Two-Tiered A* Pathfinding can greatly accelerate the A* search rate. At first, in the entire map scope, it uses the low-density grids to Macro-Pathfinding, until close to the target,then switched to the high-density grids to Micro-Pathfinding. Usually the game maps greater,A* Search speed to the more obviously.After applying A* algorithm in the AI Pathfinding system of the Gauntlet, we test and validate the improved and optimized A* search that have the most time-efficient and space-efficiency .