Voxel-Based Pathfinding: Algorithms and Applications

Three-Dimensional Pathfinding is a fundamental problem for practical applications such as computer games, unmanned aerial vehicle navigation, and industrial pipe routing. Yet due to the unique computational challenges associated with the large size, branching factor, and symmetries in 3D spaces, the area of 3D pathfinding remains relatively unexplored. This thesis introduces the Jump Point Search-3D pathfinding system for efficient and optimal routing in voxel environments. The development of new voxel benchmark data sets enables comparison of competing techniques in distinct application areas. This work also demonstrates how these advances can be applied to real-world pathfinding problems with complex constraints.