   flocking( boids ) help and tips...
  Ive been working on my own boids simulation through openGL and its going well so far but i need some second opinion's and possible tips and any tricks of anyone that has either possibly done it before or if you're just giving your two cents...any input is welcome.so far my algorithms are as suchSteering algorithmFvector Flocking::steer( Fvector targetPosition, PointEntity *flockMember, bool isSlowApproach ){Fvector steer;  // The steering vectorFvector desired = targetPosition - flockMember->get_pEntityPosition( );  // A vector pointing from the location to the targetfloat d = desired.length( ); // Distance from the target is the magnitude of the vector// If the distance is greater than 0, calc steering (otherwise return zero vector)if ( d > 0 ){  // Normalize desireddesired = desired.getUnit( );isSlowApproach ? desired *= (MAX_SPEED * ( d/50 ) ) : desired *= MAX_SPEED;steer = desired - flockMember->get_pEntityVelocity( );steer = steer.limit( MAX_FORCE );} else {  steer = Fvector(0,0,0);}return steer;}Pursuit algorithmFvector Flocking::predictEntityPosition( PointEntity *flockMember,PointEntity *flockMemberTarget ){Fvector steering = steer( flockMemberTarget->get_pEntityPosition( ),flockMember,false );if( steering.length2( ) == 0 ){return Fvector( 0,0,0 );}Fvector desired = flockMemberTarget->get_pEntityPosition( )- flockMember->get_pEntityPosition( );float d = desired.length( );float t = ( d / steering.length( ) );desired = flockMemberTarget->get_pEntityVelocity( ) * t;desired += flockMemberTarget->get_pEntityPosition( );glPushMatrix( );glTranslatef( desired.x, desired.y, desired.z );glColor3f(1, 1, 1);glutSolidSphere( 0.5, 20, 20 );glPopMatrix( );return steer( desired,flockMember,true );}SeparationFvector Flocking::seperate( PointEntity* flockTester ){Fvector seperationVector = Fvector( 0.f, 0.f, 0.f );Fvector flockMembersPosition = flockTester->get_pEntityPosition( );float average = 0;for( int i = 0; i < numOfElements; ++i ){if ( flockTester != flockElements ) //if its not itself{Fvector memberToTestAgainst = flockElements->get_pEntityPosition( );float distance = distanceFinder( flockMembersPosition, memberToTestAgainst );if ( ( distance > 0 ) && ( distance < SPACING ) ){ // Calculate vector pointing away from neighborFvector difference = flockMembersPosition - memberToTestAgainst;Fvector unitDifference = difference.getUnit( );seperationVector += ( unitDifference/distance );++average;  // Keep track of how many}}}if( average > 0 ){seperationVector /= average;}if (seperationVector.length( ) > 0) {seperationVector = steer( seperationVector, flockTester->get_pEntityVelocity( ) );    }return seperationVector;}And this is how i apply all of themvoid Flocking::updateFlock( float deltaTime ){Fvector currentVel;Fvector newVel = Fvector(0,0,0);FvectornewAcc;Fvector deltaVel;Fvector newPos;Fvector drag;setFlockLeader( flockElements[0] );for( int i = 0 ; i < numOfElements; i++){if( !flockElements->get_isLeader( ) ){//get the currently selected entities velcurrentVel = flockElements->get_pEntityVelocity( );//create a drag force to oppose the current entities velocity, to stop infinite movement//drag is equal to current velocity times a arbitrary constant, depends on how large you want the drag forcedrag = currentVel * DRAG;drag = drag.getUnit( );//get unit length to interpoltae smoothlyif( currentVel.length2( ) != 0 )//if the magnitude is not zero apply drag{currentVel -= drag;}//Steering behavioursFvector hunting   = predictEntityPosition( flockElements,flockElements[0] );Fvector seperation = seperate( flockElements );Fvector alignment  = align( flockElements );//Fvector pursue   = steer( flockElements[0]->get_pEntityPosition( ), flockElements );//weight the steering behvaiourshunting   *= 1.0;seperation *= 1.2f;alignment  *= 0.8f;//apply steering behaviours to entity as an accelerationflockElements->set_pEntityAcceleration( flockElements->get_pEntityAcceleration( ) + hunting );flockElements->set_pEntityAcceleration( flockElements->get_pEntityAcceleration( ) + seperation );//change in velocity is accelerationdeltaVel = flockElements->get_pEntityAcceleration( );newVel = currentVel + deltaVel;//the new velocity of the entity is the current plus the change in velocitynewVel = newVel.limit( 20 );//limit the velocity to the max speed newPos = flockElements->get_pEntityPosition( ) + ( newVel * deltaTime );//add to position//set entities new velocity and positionflockElements->set_pEntityVelocity( newVel );flockElements->set_pEntityPosition( newPos );}else{static float time = 0.0f;time += deltaTime;Fvector targetPos = Fvector( 0,0,0 );targetPos.x = sinf(time) * 30.0f;targetPos.z = cosf(time) * 30.0f;Fvector meToTarget = targetPos - flockElements->get_pEntityPosition( );newVel = meToTarget;newPos = flockElements->get_pEntityPosition( ) + newVel;flockElements->set_pEntityVelocity( newVel );flockElements->set_pEntityPosition( newPos );}}} the Constant's I use in these algorithms are#define SPACING 1.5f#define SPHERE_OF_INFLUENCE 7.0f#define MAX_SPEED 150.f#define MAX_FORCE 3.f#define DRAG  1.fand here is a video so you can see it in actionRed is the flockgreen is the target they are pursuingwhite is the predicted location of the target based on the flocks max speedHere are my concern's- It's really a mess to fiddle with the constant's to get a decent looking steering or speed towards the target. what i have here is al-right, it updates at 1/30th and the deltatime is 0.03f which I only multiply to the new position...which I think is right but i dont know- the seperation is a bit jerky an the flock as you can see at times, but i only think this is because there all trying to follow and converge on the one position of the leader however i would prefer to somehow make the seperation less sudden, like other flocking simulations you see, there is rarely any jerking- my puruist algorithm although it works as you can see, iVe heard of alternatives but am unsure which to use if it will produce a better look-At most it just doesent feel and look entirely right... unfortunately my problem isnt entirely quantifiable so as i said any suggestions are welcome, i think's its all to do with how ive balanced out my constant's along with my time frame...cheers in advance   
  I'm working on some of my own steering stuff (except in 2D), so lets see if I can be of any help here...Only thing I'm noticing right now is that you use seek behavior for the separation. I believe the separation is a separate force generated from each nearby actor, not anything to seek for. For example, here's my separation code:   public Vec2 separate(){Vec2 ret = new Vec2(0.0f, 0.0f);Collection<Actor> neighbors = getNeighbors(2);for (Actor neighbor : neighbors){if (!(neighbor instanceof SteeringActor))continue;final float SEPARATION_DIST = 2.0f;Vec2 offset = getPosition().sub(neighbor.getPosition());float dist = offset.length();Vec2 dir = offset.div(dist);float coef = SEPARATION_DIST - dist;Vec2 desiredVel = dir.mul(coef * coef);if (dist < SEPARATION_DIST)ret = ret.add(desiredVel);}return ret;}(sorry, Java [grin])Then I simply add that to the velocity directly, instead of seeking towards it. That's what made my simulation pretty smooth, maybe it'll help yours out too [smile]   ;  well mine would be smooth even with steering but, i weight the separation velocity by their distanceseperationVector += ( unitDifference/distance );which is a desired vector which i then send to an overloaded steer function( probably should have pointed this out before )Fvector Flocking::steer( Fvector desiredVector, Fvector flockMembersVelocity ){Fvector steer = Fvector( 0.f,0.f,0.f );desiredVector = desiredVector.getUnit( );desiredVector *= MAX_SPEED;steer = desiredVector - flockMembersVelocity;steer = steer.limit( MAX_FORCE );return steer;}however you have given me the idea not to make it less jerky but to complety stop any seperation once its out of seperation range....or rather to arrive at seperation range like im doing in my steer function   ;  Well, no, what I'm talking about is this part:seperationVector = steer( seperationVector, flockTester->get_pEntityVelocity( ) );Instead of steering towards the separation vector, just add it to the velocity directly. Meaning, don't return steer(separationVector), just return separationVector directly. This way you're not steering your actors in some direction, you're simply smoothly pushing them away from each other until they reach some sort of equilibrium, which was what made my simulation less jerky.   ;  awesome thanks for the suggestion. anybody else?edit:hey null squared i tried seperation your way and it seems to be a bit smoother...cheers[Edited by - homojedi on April 6, 2010 12:45:15 PM];  A principled way to design flocking-type control laws is,1 - Define a model for your agents of the form(d/dt) x_i = f(x_i, u)for all i from 1 to N, where N is the number of agents.2 - Define an interagent potential function of the form,V(x_1,...,x_N) = sum_(i,j)[ U(x_i, x_j) ]which is a sum over all pairs of agents.  By making sure that U(.,.) has limited support (i.e., when x_i and x_j are far apart, U(x_i, x_j)=0), you can ensure that this doesn't have quadratic expected complexity.3 - Compute the partial derivatives of V with respect to x_1,...,x_N.4 - At every instant, for each agent, choose the control input u_i that minimizesdV/dx_i f(x_i, u_i) .Note that in the above, dV/dx_i is a row vector and f(x_i, u_i) is a column vector, so the product is a scalar.If you give your problem just a little more structure, so that(d/dt) x_i = f(x_i) + g(x_i)uand require ||u_i|| <= R for all i, then you can write this explicitly asu_i = -R normalize[ g(x_i)^T (dU/dx_i)^T ]----------When defining these kinds of control laws, I find there are a few functions to keep in mind.The first is simple quadratic functions, of the form|| [what I have] - [what I want] ||^2 .Differentiating these gives linear control laws.I also find the so-called "poly_6" kernel extremely useful for defining an "influence" for agents that falls off radially.  It is defined,    { 0   if  r^2 > R^2k(r^2) = { (1 - r^2/R^2)^3    else   .I like this because1 - it involves no square roots2 - it has a continuous second derivative3 - it's bounded (unlike e.g. an inverse square law)and4 - it approximates a Gaussian.Another somewhat more dangerous function which is nevertheless sometimes useful is the logarithmic barrier function, defined,barrier(x) = -ln(1 - x)which you can use as a quick-and-dirty way to enforce constraints (the argument to 'barrier' is a number from 0 to 1, with 1 being "constraint totally violated."  You'll see that it goes to infinity there).  Since this can create numerical instability, I don't recommend the barrier function approach for production code though.The other things I mentioned, like the poly6 kernel, are great though.[Edited by - Emergent on April 6, 2010 7:23:43 PM];Quote:A principled way to design flocking-type control laws is,1 - Define a model for your agents of the form(d/dt) x_i = f(x_i, u)for all i from 1 to N, where N is the number of agents.2 - Define an interagent potential function of the form,V(x_1,...,x_N) = sum_(i,j)[ U(x_i, x_j) ]which is a sum over all pairs of agents. By making sure that U(.,.) has limited support (i.e., when x_i and x_j are far apart, U(x_i, x_j)=0), you can ensure that this doesn't have quadratic expected complexity.3 - Compute the partial derivatives of V with respect to x_1,...,x_N.4 - At every instant, for each agent, choose the control input u_i that minimizesdV/dx_i f(x_i, u_i) ........etcthe input is appreciated of course...but my math's is a tad rusty and such you may need t laymanize this a bit....but what i picked up from it is that the poly_6 kernal thing is good for not using square roots, unfortunatly the code you pasted is a bit fuzzled. if( r^2 > R^2 )k(r^2) = (1 - r^2/R^2)^3;   else//do nothing? you mind clearing it up so i can possibly use it?or direct me to some material that explains it?cheers;Quote:Original post by homojedithe poly_6 kernal thing is good for not using square roots, unfortunatly the code you pasted is a bit fuzzled.Oh!  I wasn't trying to post code; that was rather supposed to look like the math notation for a piecewise function.  Here, I'll write it as C code:const inline double cube(const double x){   return x*x*x;}const inline double poly6(const double rSq, const double oneOverRsq){   if(rSq > Rsq) return 0.0;    return cube(1.0 - oneOverRsq*rSq);}There you go.  Computational cost: A branch, a subtract, and 3 multiplications.   