AI Simulation (Boids Simulation)
Language: C++, Middleware: OpenGL
Overview of the project
Motivation
- How to infuse life into small (but many) objects in the scene
Problem which I had
- Since there are many objects in the scene, it is impossible to trace and compute every motions and locations of objects so that each object should determine its behaviours based on pre-defined rules.
Which features are included in this project
- Three core flocking behaviours
- Obstacle avoidance
- Group awarence
Detail of the project
1.Introduction
Boids are a good way to control large crowd of objects in the scene. In movies and games, there are thousands (even more) of moving objects, but it is daunting task to control all of them by the user or scripts in limited frame. For such a reason, giving them certain rules or defining their behaviours are one of the best solution for this situation. Boids includes crowd behaviors, which can determine the characteristics of their group. Using these, we can only consider what we are interested in.
2.Boids Simulation
Each boid behaves under Newton’s second laws. Basically, the movement of particles is decided by acceleration, which is gravity in this case. Each particle has following properties.
- Position (Position of the particle in each time step)
- Velocity (Velocity of the particle in each time step)
In addition, Boids have group behaviour in addition to individual behaviour as a particle. Each boid has three main behaviours.
- Cohesion: Each boid tries to move to the centre of the group)
- Separation: Each boid keeps distance to the others.
- Alignment: Boids try to align their speed and direction.
2.1.Cohesion
Each boids has the coverage range which is 0.3 (meter) in my implementation. If there are other boids, they will do cohesive activity. ‘Cohesion’ is the behaviour which tries to move to the centre of the group. It is computed with average of the position of all boids in the sensing coverage except itself so that boids can make a group within the range.
2.2. Separation
Each boids tries to keep distance with other, otherwise they will be located at the single point at the end. The separation force will be active when boids are within certain range which is 0.05 in my implementation. It is computed as subtracting the position between a boid and its neighbours, which is the velocity vector for counter force against ‘Cohesion’ force.
Each boids tries to keep distance with other, otherwise they will be located at the single point at the end. The separation force will be active when boids are within certain range which is 0.05 in my implementation. It is computed as subtracting the position between a boid and its neighbours, which is the velocity vector for counter force against ‘Cohesion’ force.
2.3. Alignment
Boids steer towards the average heading of local flock mates. The velocity of boid in a group will be same so that they stay in formation.
Boids steer towards the average heading of local flock mates. The velocity of boid in a group will be same so that they stay in formation.
2.4 Obstacle avoidance
Obstacle avoidance operates as computing the angle between centre of the obstacle and the velocity direction of boid when the obstacles are in the sensing range of boids.
In the figure above, if the angle ‘2’, which is the angle between centre of the obstacle and the velocity direction of boid, is smaller than angle ‘1’, which is the angle between centre and tangent line, boid will hit the obstacle. In contrast, if angle ‘2’ is bigger than ‘1’, it will be safe. In order to prevent crash, boid will rotate about 55 degree (=0.9 radiance).
Obstacle avoidance operates as computing the angle between centre of the obstacle and the velocity direction of boid when the obstacles are in the sensing range of boids.
In the figure above, if the angle ‘2’, which is the angle between centre of the obstacle and the velocity direction of boid, is smaller than angle ‘1’, which is the angle between centre and tangent line, boid will hit the obstacle. In contrast, if angle ‘2’ is bigger than ‘1’, it will be safe. In order to prevent crash, boid will rotate about 55 degree (=0.9 radiance).
However, boids have to decide which direction they turn between left and right because the angle calculation above does not tell us which is the best rotation between 55 and -55 degree.
For example, in the figure above, ‘1’ denotes the rotation by 55 degree and ‘2’ is the rotation by -55 degree. In this case, the rotation ‘1’ will be the best solution. Namely, we have to decide between clockwise and counter-clockwise rotation.
So in my algorithm, I computed future cost.
(1) Computes both 55 and -55 degree.
(2) Compute the angles between the line from the boid to the centre and both velocity direction of the boid from (1).
(3) If the angle after 55 degree rotation is bigger than that after -55 degree, the velocity after 55 degree rotation will be new direction vector.
For example, in the figure above, ‘1’ denotes the rotation by 55 degree and ‘2’ is the rotation by -55 degree. In this case, the rotation ‘1’ will be the best solution. Namely, we have to decide between clockwise and counter-clockwise rotation.
So in my algorithm, I computed future cost.
(1) Computes both 55 and -55 degree.
(2) Compute the angles between the line from the boid to the centre and both velocity direction of the boid from (1).
(3) If the angle after 55 degree rotation is bigger than that after -55 degree, the velocity after 55 degree rotation will be new direction vector.
2.5. Group Rejoining
A separated boid will speed up to rejoin the group. If the boid is separated by a obstacle, its speed will be accelerated to catch up the group.
A separated boid will speed up to rejoin the group. If the boid is separated by a obstacle, its speed will be accelerated to catch up the group.