Crowd simulation has become an increasingly popular research topic because of its potential applications in virtual reality and computer animation. Most of the existing research utilizes methods

including social force

hydrodynamic

and data-driven models

to control the movement of the groups. Social force models treat agents as independent individuals with mass and velocity and control the movement of the agents by applying external controlling force. Hydrodynamic models introduce the concept of fluid dynamics into crowd simulation

which is appropriate for simulating large-scale groups. Data-driven models extract data from videos of real crowds and enter the data into crowd simulation to obtain authentic group behavior. These methods focus on the simulation of groups

which contain a large number of free-moving agents. However

these methods cannot be applied in simulating groups that move in a specific formation

which extensively exist in social activities (e.g.

a marching army or a dancing group). In group formation control

the agents are expected to move in a similar direction with similar velocity among other agents in the group while maintaining an overall formation. The major difficulty of group formation control lies in the conflict between maintaining formation and collision avoidance. These problems can be solved traditionally by using a formation mesh to represent the group. However

in the previous methods

the agents are often strongly bound to the target location in the formation

thereby leading to the stiff behavior and inefficient movement of agents. A modified mesh-guide method is employed

and a deformable mesh is adopted to control the group motion

thereby achieving a group simulation with a certain formation. The formation is initially divided into a triangular mesh to connect all agents. The formation mesh is then transformed by the potential field of the obstacle during the process of group motion; thus

the agents can move with a certain formation without collision. Finally

an attraction point-based mesh-guide method is proposed to address the "dislocation phenomenon" in potential local agents

which may occur when the obstacles pass through the formation mesh. The implementation of the proposed algorithm can be mainly divided into three phases

namely

initialization

deformation

and recovery phases. In the initialization phase

the agents are grouped in a virtual environment and their locations are stored within the same group into different queues. The points in each queue are then reconstructed using Delaunay triangulation to form a triangle list

that is

the formation mesh. The virtual environment should also be considered in this phase. The environment is divided into uniform grids

and the potential field for each grid is computed according to the distribution of the obstacles. At the end of this phase

the target area of each group is set. This area has a strong attraction force to the group agents and has no obstacles. In the deformation phase

the vertexes of the formation mesh are driven by the influence of attraction force. The velocities of the vertexes that enter into a potential field depend on the resultant of the attraction and repulsive forces. The velocities of other vertexes in the formation mesh are calculated using the error of their current and desired positions. The desired position of each agent can be obtained by the deformation rules that minimizes the error metric. If the distance between two vertexes goes beyond the deformation range

then the meshes between the two vertexes will be removed from the current formation mesh to enhance the calculation efficiency of the mesh deformation stage. After the formation mesh is calculated

the agent will move along with the nearest vertex

which has not been occupied by other agents. Moreover

the potential fields should be updated in real time along with dynamic obstacles. In the last recovery phase

when the removed meshes recover within the deformation range

these meshes are added again into the current formation mesh based on the initial formation. Finally

the proposed method can recover the groups to the initial formation fast after passing through the obstacles. The formation motions of various multi-agent groups are simulated in different virtual scenes

such as marching army march

dynamic traffic flow

and group show scenes

using unity. A series of contrasting experiments is performed in various numbers of agent. Results showed that the time cost of the proposed algorithm is focused on the mesh deformation stage. When the number of the vertex in the formation reached 1 000

the average running time of the mesh deformation stage within one simulation step is 20.15 ms. The formation mesh generation stage is a previous process that will not affect the real-time performance of the algorithm. The proposed algorithm can improve the global efficiency of the agent movement by adapting the attraction point-based mesh-guide method

thereby transforming the formation transform easily and gracefully. The proposed approach can work well in the simulation of agent groups with formation control because the group collision with obstacles

either static or dynamic

can be effectively avoided while maintaining the stability of the formation. The experimental results strongly suggest the effectiveness of the proposed algorithm.