Planning Feasible and Smooth Paths for Simulating Realistic Crowd

A very important challenge in many virtual applications is to plan feasible, smooth and congestion-free paths for virtual agents in dynamic and complex environments. The agents should move towards their destinations successfully while avoiding the collisions with other agents and static and dynamic obstacles. In this paper, we propose a novel approach for realistic path planning. We first create a navigation mesh for the walkable regions in a two-dimensional environment. Then an A* search on this graph determines a series of connected meshes for agents to go through from the start position to the goal position and furthermore, the walkable corridor whose radii equal to maximum clearance to the obstacles is built based on backbone path derived from the inflection point method and Catmull-Rom spline. Finally, a local collision avoidance algorithm is integrated to guarantee that agents navigating in the corridor do not collide with other agents and dynamic obstacles. Our experiments show that we can compute feasible, smooth and realistic paths for agents situated in dynamic environments in real time.