3D Voxel Navigation
Project Type: Personal
Project Duration: In Progress
Software Used: Unreal
Languages Used: C++
Primary Role(s) : Programmer
About:
I have always been interested in navigation for NPC characters. At the time, my brother had shown me Subnautica. An oceanic story-driven survival game where the player discovers numerous types of sea life. Some of them are dangerous and some of them are friendly. As I was playing this wonderful title, I became curious about how games would have enemies navigate a complicated space such as underwater structures.
In this project, I wanted to tackle this challenge and try to create my own navigation system for NPCs that need to travel in the 3rd dimension. My approach is to generate a hierarchal voxel graph in 3d. This approach has been used in games such as Warframe. In fact, I wrote my implementation based on the ideas presented by Daniel Brewer in his article 3D Flight Navigation Using Sparse Voxel Octrees in the GameAIPro book series.
You can check out his paper here:
http://www.gameaipro.com/GameAIPro3/GameAIPro3_Chapter21_3D_Flight_Navigation_Using_Sparse_Voxel_Octrees.pdf
Here I am showing the layers and voxel sizes generated within the navigation bounds.
Standard A* search through the voxels and their neighbors.
Greedier algorithm for pathfinding is used here. The algorithm is A* but the heuristic tends to have larger voxels visited more than smaller voxels. This allows for fewer voxels to be visited at the expense of loosing the optimal path.