Abstract: Group formation control technologies are ofen used for the film formation scenes of a large number of characters in film and television works, but a lot of group formation technologies tend to focus on the free-moving individual characters without considering the overall control of the formation, which causes the scene picture a lack of beauty, integrity and organization. In order to solve these problems, a group formation control method based on Voronoi diagram was proposed. Firstly, the group formation was divided into Voronoi diagram spaces to create a formation grid containing all the agents. Then, a new group formation deformation algorithm was proposed, in which artificial potential energy field and relative speed obstacle method were used to reasonably avoid obstacles, and a spring system was combined to keep the formation as stable as possible in the deformation process. Finally, Lloyd algorithm was used to quickly restore the target formation. The experimental results show that, the proposed method can simulate the group formation transformation motion well, is suitable for various complex scenes, and has an aesthetic, overall and organized formation transformation effect.

Key words: group simulation, formation control, Voronoi diagram, spring system, Lloyd algorithm

摘要： 影视作品中采用群体队形控制技术来制作大量角色处于某种队形运动的场景，但许多群体队形技术往往侧重于对自由移动的个体角色进行控制，而忽视了对队形运动的整体控制，导致场景画面缺乏美感性、整体性和条理性。针对这些问题，提出了基于Voronoi图的群体队形控制方法。首先，将群体队形进行Voronoi图空间划分，建立一个包含所有智能体的队形网格；然后，提出一种新的群体队形形变算法，采用人工势能场和相对速度障碍法进行合理避障，再结合弹簧系统使群体队形在形变过程中尽可能保持整体稳定；最后，采用Lloyd算法快速恢复到目标队形。实验结果表明，该方法可以很好地模拟群体队形变换运动，适用各种复杂场景，具有美感、整体、条理的队形变换效果。

关键词: 群体仿真, 队形控制, Voronoi图, 弹簧系统, Lloyd算法