You've been logged out of GDC Vault since the maximum users allowed for this account has been reached. To access Members Only content on GDC Vault, please log out of GDC Vault from the computer which last accessed this account.

Click here to find out about GDC Vault Membership options for more users.

close

The Number One Educational Resource for the Game Industry

Session Name: Hierarchical Dynamic Pathfinding for Large Voxel Worlds
Speaker(s): Benoit Alain
Company Name(s): Sauropod Studio
Track / Format: Programming

Did you know free users get access to 30% of content from the last 2 years?


Get your team full access to the most up to date GDC content

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.

GDC 2018

Benoit Alain

Sauropod Studio

free content

Programming

Programming