Home > Explore Content > All Issues > Article View
Path-Planning for Group Movement in Dynamic Environments
Journal of The Korea Society of Computer and Information
Abbr :
JKSCI
2013, 18(2), pp.117-126
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science
2013, 18(2), pp.117-126
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science
-
Path planning is an essential problem to make virtual characters navigate in many applications including computer games. In many cases, multiple characters move in a group and qualitative aspects of planned paths are emphasized rather than optimality unlike Robotics. In this paper, we propose a two-level path planning algorithm in which the global path is planned for a single character specified as a leader and then the local path is planned to avoid dynamic obstacles while the group following this path. The space for group movement is achieved in the form of square grid array called a grid window. Member characters are located relatively to the leader within a space and moved. The static environment is reduced to the configuration space of this grid window to generate a roadmap on which a grid window can move. In local path planning, only the leader avoids dynamic obstacles by using an artificial potential field and the rest of members are located relatively to the leader in the grid window, which reduces computational load. Efficient algorithms to implement the proposed planning methods are introduced. The simulation results show that a group can handle with dynamic obstacles effectively while moving along the planned path for a static environment.
112 Viewed
Print this page
Download PDF