GDC Vault is part of the Informa Tech Division of Informa PLC
This is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.
|Session Name:||Hierarchical Dynamic Pathfinding for Large Voxel Worlds|
|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.|