| Group formation control is an important branch of crowd simulation technology and computer animation, and it has great significance for formation control, formation design, etc. Group formation control has been applied in many fields, such as games, animation, and swarm robots system. Based on geometry-constrained mechanism, a heterogeneous group formation control method is proposed, which includes steps of individual distribution, path planning, collision avoidance, formation constraints and smooth control, aiming to generate high quality formation transformation results having characteristics of smoothness, optimum, regularity and stability.The main work of this thesis can be represented as follows:1) The current flock formation control methods are summarized, and their advantage and disadvantage are analyzed and discussed.2) The Lloyd’s method for power diagram, that is PD-Lloyd, is presented as a navigation algorithm for smooth and collision-free movement. Consider the actual physical characteristics of individuals moving in the scene, different agents’moving speeds should be kept the same or similar within normal levels. Two optimization strategies are proposed to enhance the effectiveness and credibility of the algorithm.3) Combining with morphing, power diagram and Lloyd’s method, a heterogeneous group formation control method is proposed. Firstly, geometry morphing method is utilized to generate a series of intermediate constraint shapes from the initial shapes to the target ones while individual is limited in constraint shapes. Then, Centroidal capacity constrained power diagram is introduced to model the internal layouts of groups in the constraint shapes in order to obtain required heterogeneous distributions. Finally, PD-Lloyd is used as path planning algorithm to compute coverage path and generate smooth and organized transformation results.4) The prototype system is designed and implemented. The effectiveness of the method is proved by experimental results. |
PDF Full Text Request