HAS: Hierarchical A-Star Algorithm for Big Map Navigation in Special Areas

摘要

The problem of path-finding has to be solved in transportation, city planning, commercial computer games, navigation and many other fields. How to find the shortest path is the key point of this problem. For computer games and many other fields, since the maps are usually not very big, traditional algorithms such as Dijkstra algorithm and AStar algorithm work well. But if we want to find the shortest path of two points in a big city or even a country, the memory and CPU resources are limited and these algorithms may result in bad performance. To solve the problem of navigation in big maps, this paper introduces and analyzes the use of Hierarchical A-Star algorithm which adds the hierarchical mechanism into traditional A-Star algorithm and save the resources of CPU and memory. For a big map such as the map of a country, to find the shortest path of two points, we successively divide the map of the country into maps of states, cities, towns, and blocks. Then we implement A Star algorithm for each layer and recursively find the shortest path of these two points.