Voronoi-Based Real-Time Crowd Path Planning

In order to perform the collision avoidance, a new algorithm is introduced to make use of the high effectiveness of GPU to compute the discrete Voronoi diagram in real-time.And a solution for crowd path navigation based Voronoi diagram is presented.By making use of the ability that the Voronoi diagram partitions the space according to the Euclidean metric, the path planning with collision avoidance is achieved by forbidding agents to move outside their Voronoi regions.