| Abstract [eng] |
The paper reviews various methods for hierarchical pathfinding and path optimization. The knowledge gained from the analysis is applied to the design of improvements to the Convolutional Hierarchical Path A* (CHPA*) algorithm. The first change corrects abstraction layer errors by removing edges leading out of a segment, where the algorithm sees a path from the top and left segments, but there is no diagonal path across the segment. Second, a new more optimal method of coordinate translation is presented, which stops the search for intermediate paths when at least one segment vertex is reached and is able to find the shortest path between segments. Third, the algorithm is adapted to work on octile grids. Experimental studies compare the results of A*, Jump Point Search (JPS) and CHPA* on randomly generated, maze, square room and strategy game maps. Results show, that the enhancements to the CHPA* algorithm improve the path length and do not significantly affect the search time. |
