ABSTRACT
A Sparse Voxel Octree (SVO) is a spatial structure used in graphics rendering, particularly ray-tracing. This chapter covers how readers adapted SVOs for use in 3D flight navigation in Warframe, discusses 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. There are several techniques for constructing SVOs, some of which boast interactive frame-rate performance by optimizing and parallelizing the construction algorithm. The SVO is now a connected graph representing the free space that agents can traverse. A graph search algorithm can be used to find paths through this space. Adding visualizations and statistics to the search shows how much space A* is actually searching. The results can be significantly larger than anticipated. The adaptive grid nature of the octree certainly helps the search jump over large tracts of open space.
