Research on the A Star Algorithm for Finding Shortest Path

摘要

With the rapid development of artificial intelligence technology, the problem of intelligent path finding is gradually important, which can optimize the robot walking route and the movement problem of NPCs in the game is improved. Among many shortest path algorithms, A-star algorithm to find the path is one very classic way. In this thesis, the authors mainly study the principle of A star algorithm and compare it with Dijkstra algorithm, and conclude that A-star algorithm is more effective and convenient. In this essay, writer used Raster Method to simulate the environment with obstacle, the distance between every two grids is calculated using Manhattan Distance Formula, which regulate the convenient way of moving is from top to bottom and move around. Through the outcome of the simulation of A star algorithm in Matlab, it shows that it is a better way to search the shortest path.