Session Name: | Hierarchical Dynamic Pathfinding for Large Voxel Worlds |
Speaker(s): | Benoit Alain |
Company Name(s): | Sauropod Studio |
Track / Format: | Programming |
Overview: | This presentation explores the hierarchical pathfinding system developed for 'Castle Story', a voxel-based strategy game where intelligent agents coordinate to build castles and walls on dynamically deformable islands of up to a million voxels of walkable surface. After trying a number of approaches, from optimizing traditional A* as much as possible to implementing different hierarchical and heuristic schemes, the Sauropod Studio team developed a very efficient and straightforward approach that visits an average of 100 to 1000 times less nodes than its non-hierarchical counterparts. Their data structures are fast to initialize and maintain, and user-created maps come with no additional offline precomputations. This presentation will provide all the information developers would need to implement a system similar to Sauropod Studio's in their own game, from node creation to graph exploration, to the addition of more complex game behaviors such as moving agents, stackable ceilings, lockable doors, asymmetrical jumping and climbing, and breaking through enemy walls. |