Game AI Pro 3

21

3D Flight Navigation Using Sparse Voxel Octrees

Daniel Brewer

21.1    Introduction

21.2    Alternative Techniques

21.3    Sparse Voxel Octrees

21.4    Creating the SVO

21.5    Pathfinding through a SVO

21.6    Complications and Optimizations

21.7    Conclusion

References

21.1  Introduction

Navigating two-dimensional spaces is something we are quite familiar with in the game AI field. Regular grids, corridor maps, and navigation meshes (navmeshes) 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 ...