A* pathfinding algorithm modification for a 3D engine

Abstract

Frequently the quality of a path returned by a pathfinding algorithm is more important than the performance of that algorithm. This paper presents a new algorithm, based on A*, which is better suited for use in 3D game engines. The modification was evaluated by a series of comparative tests. The standard A* algorithm was used as a benchmark in the comparisons. The changes in the algorithm consist in using a different heuristic, adding vertex penalties, and post-processing of the path. A custom-built 3D graphics engine was used as the test environment. The paths generated by the new algorithm are a more natural choice for humans than the ones selected by the standard A* algorithm.