ABSTRACT
Regular grids, corridor maps, and navigation meshes are all very well known and documented problem spaces. However, navigating in full three-dimensional environments where the agents are not constrained to the ground is quite a challenging problem space and is compounded when having to deal with very large, sparsely populated volumes that have clusters of dense, complex regions. Sparse voxel octrees (SVOs) are a popular graphics structure used for lighting and ray-tracing. This chapter accommodates SVOs for use in 3D flight navigation in Warframe, discuss modifications to the A* search algorithm to work on this adaptive grid representation and go into the details of tuning the heuristic to speed up the search by sacrificing optimality. Neighbors are calculated implicitly between voxels based on the 3D coordinates within the voxel grid. The voxel grid representing each leaf is a 64-bit integer. The adaptive grid nature of the octree certainly helps the search jump over large tracts of open space.
