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: Crowds In A Polygon Soup: Next-Gen Path Planning
Speaker(s): David Miles, David Miles, David Miles, David Miles
Company Name(s): BabelFlux LLC, , ,
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 session deals with efficient path finding, flocking, and squad movement behaviors in a complex and dynamically changing world. A graph of connected convex volumes, accurately encapsulating the usable free-space of the game world, is quickly computed from an arbitrary polygon soup of level mesh, using a straightforward 3D rasterization and volume extraction technique. Because the planning graph encapsulates the usable free-space, it supports not only path finding queries, but also repulsion field based flocking and squad behaviors, relying only on rapid checks within the planning graph, avoiding ray-casts against the collision geometry. The planning graph, while detailed enough to support these advanced motion behaviors, is simple enough that it can be updated at runtime as dynamic obstacles modify the environment.

GDC 2006

David Miles

BabelFlux LLC

David Miles

David Miles

David Miles

free content

Programming

Programming

Game Design

Design

Game Design

Design

Game Design

Design