Kevin Johnsen
Flocking Work
To implement the flocking behavior, several basic behaviors had to be implemented. These are (in the order they were implemented): Velocity Matching, Group Centering, Separation, Approach, Obstacle Avoidance, and Unaligned Collision Avoidance. All of these are simply algorithms that, given an objects current position and velocity and the positions and velocities of the objects around it calculate a new velocity the object should have at the next timestep. In order to implement a basic idea of perception, the soldiers are only concerned about the other soldiers that are ahead of them and in close proximity. Each calculation is done for each nearby object. The newly calculated influence is then weighted depending how close the object is. This weighting is implemented with the inverse of the distance squared. This way objects very close have a very large influence, but it drops off sharply. Any object on the edge of the influence radius have a minimal impact. After all of the calculations have been made, the velocity and position are fed into an operation that convert the newly calculated direction to either turn left or right some number of degrees. This operation also detects if there is a heavy weight for obstacle avoidance and assigns it priority over the basic flocking behaviors. An overview of the algorithms used follows.
Velocity Matching -Group Centering -Separation -Approach -Obstacle Avoidance - Unaligned Collision Avoidance
Velocity matching is the simplest behavior to implement, and was also the first to be implemented. The red guy aligns itself to the direction the blue objects are facing. This essentially lines the red guy up the the average direction of the blue guys.
Group Centering traditionally means calculating an average position of the flock that the object wants to steer towards. This behavior wasn't exactly what we wanted for our project. The problem was if the guys started out in a straight line, they would all want to aim towards the center of the group. So a group of soldiers in a line (which is what we wanted from them) would want to bunch up into a cluttered mass. In order to come up with some semblance of rank and file marching a new scheme was developed. Given the red guys current position and a nearby blue guys position it would calculate the direction to the blue guys position. It would then take a cross product of this vector and the direction that it is currently facing. This vector would be either straight up or down in the Y direction. This vector is used to tell the red guy which side of the blue guy it should move towards. To accomplish this, a new cross product is taken with the red guys current direction and this newly calculated cross product. The resultant vector is perpendicular from the red guys current direction, and away from the blue guy. A point is drawn from the blue guy along this vector a length equal to the minimum distance the red guy can approach the blue guy. This is the point the red guy orients towards. The reason all of the calculations are used is that given enough time a group of randomly oriented soldiers will eventually form an offset grid form as they move. All of the cross products assure a regular geometric formation.
Separation is used to keep objects traveling in the same relative direction and speed some minimum distance from each other. This is easily implemented with a simple repulsive force. The red guy above is being repulsed from the two blue guys it is near and will eventually be pushed in the direction of the red arrow. This repulsive force is scaled linearly depending on the distance of the two objects.
Approach is used in the battle matching to have two guys approach each other and eventually come to a stop facing each other some distance apart. In the illustration above, the red guy is approaching the blue guy. The naive solution is to merely aim towards the blue guys current position every turn. This leads to guys orbiting each other and never coming to a stop. The reason this happens is that each guy aims at where the object was, not where the object will be. The actual solution is to aim at the objects future position (current position + velocity). Each guys velocity is then linearly scaled down as the distance between them shrinks.
The basic idea behind obstacle avoidance is that if an object is ahead of the guy the guy will steer to a point some distance away from the object. This is accomplished by shooting three rays to approximate a cylinder ahead of the guy. This cylinder approximates the area taken up by the guy. The ray that intersects with an object that is nearest to the guy and ahead of the guy is selected to be avoided. Much as in the group centering algorithm a series of cross products is used to calculate a vector perpendicular away from the object. The distance away from the object varies with the absolute distance the guy is from the obstacle. This way a guy is not directed perpendicularly away form the object, but merely steers to a near miss. Ideally the guy should try to maintain the same speed, but if a guy ever gets too close to an obstacle the guy will be slowed until eventually coming to a stop. A shortcoming of this implementation is that each object is treated separately. If two obstacle spheres overlap, the guy will alternate back and forth trying to avoid both obstacles. The solution to this is to detect that their are two obstacles nearby. This can be done by comparing the results from the 3 rays that are projected ahead of the guy. If two spheres are almost equidistant ( within 0.01 unit ) then replace them in the calculations with one sphere that covers the same area.
 |
 |
Unaligned Collision Avoidance:
When two guys are heading towards each other in opposite directions separation is not enough to stop them from colliding. Separation is only effective when objects are very close to each other. Plus if two objects are heading directly towards each other, separation will only slow them down. Unaligned collision avoidance is a much smarter, and computationally complex solution. Instead of looking at current positions, it checks to see when the two guys in question will make their closest approach. If they will be too close at this time, then they will steer away from each other. In the illustration above, The red and blue guys will collide at the position of their ghosted projections. The steering to avoid this is projected perpendicularly away from this point of impact. Also, an acceleration / deceleration force is applied depending on their relative speeds.