|Fruit stealing simulation: A simulation of 96 fruit pickers (yellow dots) in an orchard with 64K fruit (dark blue and purple) on 64 trees (brown trunks) and 4 farmers (white shirts). Each agent maintains an independent goal. Left: Initial top view of the orchard Middle: Top view in the middle of simulation with many fruit collected Right: Perspective view of same time step. Our multi-agent navigation graph based algorithm can perform path planning at 8 fps on a high-end PC.|
We present a novel approach for real-time path planning of multiple virtual agents in complex dynamic scenes. We introduce a new data structure, Multi-agent Navigation Graph (MaNG), which is constructed from the first- and second-order Voronoi diagrams. The MaNG is used to perform route planning and proximity computations for each agent in real time. We compute the MaNG using graphics hardware and present culling techniques to accelerate the computation. We also address undersampling issues for accurate computation. Our algorithm is used for real-time multi-agent planning in pursuit-evasion and crowd simulation scenarios consisting of hundreds of moving agents, each with a distinct goal.
Sud, Erik Andersen, Sean Curtis, Ming Lin,
and Dinesh Manocha
Real-time Path Planning in Dynamic Virtual Environments Using Multi-agent Navigation Graphs Accepted for publication to IEEE TVCG
Interactive 3D Distance Field Computation using Linear Factorization
DiFi: Fast 3D Distance Field Computation Using Graphics Hardware
Proximity Query and Collision
Detection Research at the UNC Computer Science GAMMA Group.
Army Research Office
National Science Foundation