Study Of Artificial Intelligence Path-finding Algorithm In Game Development

Artificial Intelligence is an important component of game development. Path finding is one of the most fundamental questions in artificial intelligence applied to games. In today's game industry, A~* algorithm is the most widely used pathfinding algorithm of Artificial Intelligence, and it is one of the most effective shortest-path search algorithms, too. A~* algorithm is a heuristic search algorithm , which is based on breadth-first search. Commonly, it uses valuation function to estimate the current position. The normal A~* algorithm get a path according to Closed table. If there is a blind road, the node in which will be included in the Closed table, and result in crooked road phenomena of path finding.To solve the problem, an improved A~* algorithm is proposed, which increases a father pointer for each node. Finally, we can get the most optimal path according to the information of father pointer table and Closed table, by keeping back from target node to start node. With the experiment, the method can avoid the phenomena of crooked road and have a better catholicity. Because the query of AI transfer A~* algorithm repetitiously, result in bad influence of programme. To solve this problem, a derived A~* algorithm is proposed, which is based on the improved A~* algorithm. By accepting some start nodes and stop nodes, we can get a well result of query. In the course of running, AI module need transfer the modified A~*algorithm only once and can improve its efficiency. In addition, some problems in game development be discussed to get a better result. Such as path smoothness, cost of different landform, collision of player in the game.Last, the thesis makes use of Maze Problem to construct a numerical experiment for the improved A~* algorithm, compares and analyzes the data of four commonly used pathfinding algorithms, such as search time, the number of enpand nodes and the number of most nodes in memory. The result of experimentation shows that time efficiency and space efficiency of the improved A~* algorithm in artificial intelligence pathfinding.