Hierarchical Path Finding Based On Decision Tree Division

Path-finding is a fundamental problem in computer games, and its efficiency is mainly determined by the number of nodes it will expand. A* algorithm isn't suit for path-finding on large map under restrictions of limited computer sources and Real-time demand, because the number of nodes it will expand grows fast with the size of the search space. HPA* can promote the efficient of path finding using a hierarchical approach and find near optimal paths. HPA* divides a complex path-finding problem into many very simple problems.Terrain is one of the most important factors should be considered. In this paper we find that the efficient of A* is sensitive to the terrains, especially the terrain around the target point in grid-based environment. To a certain degree, the equal division of HPA* reduces the influence form terrain factor. We present DT-HPA* (Hierarchical Path-Finding A* based on Decision Tree), a hierarchical path-finding approach on the map which has been divided by decision tree. This approach views each point on the map as an instance, divides the map according to cut points of continuous valued decision tree. The result of division is that the map is cut into some rectangular regions, and retains the regions contain a kind of terrain. The experimental results show that this technique can find better paths effectively. Compared to HPA*, DT-HPA* can find more optimal paths with fewer nodes to be detected.