Thursday, November 19, 2015

3D Boids flocking


3D flocking algorithm using Boids simulation model. Each boid is represented as a blue sphere with a smaller green sphere used to visually track the direction vector. The 3 rules used are:
1. boids fly to perceived flock center
2. boids avoid other boids
3. boids match flock direction
Flock center and direction are calculated by looking at each boids' local neighbors, changing the size of this parameter changes the overall flock sizes.
Avoiding other boids uses a 1/x function to determine the multiplier applied to the vector between 2 boids. This means the closer the boids are, the more 'force' repells them. The nearby boids calculation for this rule uses a smaller size than the first and third rules.

In this video we see direction propagation inside a boids flock, as it starts in one end of the formation and propagates throughout. Notice how the boids maintain a respectable distance from each other.

Where it Breaks Down


This video shows 2 boids in direct opposition repelling each other perfecty, as there are no forces to apply variation that would allow them to align.

This video shows the 'strength' of the repelling force, these boids are not perfectly aligned, yet as they get closer the repelling force of rule 2 and the flock direction variable from rule 3 combine to make he boids swerve away from eachother instead of combining.
In addition, the boids jitter a great deal, especially when Rule 2 comes into play. This could be fixed by implementing a maximum turning speed for each boid which should help smooth the way they turn, and implement a better algorithm for dealing with boids intruding too far into each others' space.

Obstacles and Pathfinding



In these videos, black obstacles have been added, along with the a* algorithm from homework 3. To have the boids properly interact with these new objects, 2 new rules are required:
4. boids want to travel to some point on the path
5. boids want to avoid objects
Rule 4 is simply the direction vector pointing to the next point on the path returned by the A* algorithm, and Rule 5 is simply a copy of rule 2, only instead of summing the local boids, uses all objects. One global path is used for all boids, updated to path to a random point in the obstacle maze whenever the end is reached. This path is shown as a red line, a small red sphere marking the current node the boids are pathing to. Notice how even with these new rules, the boids still travel in flocks.

Where it Breaks Down

You may have noticed in the earlier videos, boids will get stuck on the black obstacles, bouncing back and forth on them, slowly moving around it. This is due to the other Rules upon the boid overpowering Rule 5 until Rule 5 overpowers them, creating a very fast flip-flop effect in the direction vector.

Very occasionally, the point picked randomly by the A* algorithm will situate the boids such that the function used to determine whether the goal is reached will fail to register. This function simply determines if for each boid if the distance from the boid to its perceived flock center is larger than the distance from the current path node to the perceived flock center. This will produce jittery behaviour as the boids try to situate themselves as close as possible to the node wild obeying all the other rules.

Boids Source
Boids with Obstacles Source

No comments:

Post a Comment