Research And System Development Of Intelligent Path Search Algorithm In Game

In recent years,how to apply artificial intelligence to improve the user experience and operation efficiency of the game has become a major research issue in game development.This thesis focuses on the path optimization in games.Its research goal is to plan a collision free path for the character in the game from the starting point to the target point.As a result,it can improve the efficiency of path search and optimize the quality of the path.Mainly,the global path planning and intelligent obstacle avoidance in the game are well studied,and are applied to the the game WAR MAINLAND.The main work of this thesis includes:1)Aiming at the global path planning problem of large-scale map,this thesis combines A* with Bresenham algorithm to improve the search efficiency.Although A* algorithm is widely used in global path planning in games,A* algorithm has low searching efficiency in large-scale maps since it searches too many invalid nodes.In this thesis,A* algorithm and Bresenham algorithm are combined to effectively reduce the number of invalid nodes.At the same time,the thesis uses the hierarchical search strategy to divide the route finding system into offline processing stage and online processing stage.The simulation results show that the algorithm can reduce the number of node searches by 45% ? 65%.Hierarchical search strategy can improve the searching efficiency by several times.It shows the larger the map scale,the more significant the improvement.2)Aiming at the problem of inaccessible target points and local minimum points in the real-time obstacle avoidance of potential field grid method,this thesis presents the improved repulsion potential field function and the simulated flow method.It can ignore invalid obstacles and reach the target point by the shortest path.In the dynamic game map,the artificial potential field method can help the character avoid obstacles in the process of moving.Based on the artificial potential field method,this thesisproposes the potential field grid method which is suitable for the grid map to find the way.Aiming at the problem of unreachable target points and local minimum points in the grid method of potential field,the improved repulsion potential field function and the simulated flow method are proposed.The simulation results show that the improved repulsion potential field function can make the global path smoother and reach the target point.Simulated flow method can help characters find the shortest path out of the local minimum point area.3)On the basis of the above researches,the intelligent path-finding system of the game WAR MAINLAND is designed and implemented.The thesis describes the designing framework and the overall function module of the game WAR MAINLAND.Especially,it shows the design and development of the path-finding module.The path-finding system of WAR MAINLAND mainly includes four modules: map building,global optimization,real-time obstacle avoidance and world map.Finally,the thesis gives the running results of the designed game.At present,WAR MAINLAND has been developed for trial operation.The path planning algorithm studied in this thesis can adapt to all kinds of maps in the game.It has stable performance and significantly improves the user's experience of the game...