Sign in to follow this  

Flocking algorithm problem

This topic is 2845 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello all, im currently at uni working on a flocking algorithm in openGL, and while i have some of the basic concepts down, and have coded them it still doesent look exactly right, it has something to do with my maths. so I have 4 functions separate,align,coheed and hunt these are the basic rules that govern the simulation and i find out what these unit vectors are based on the nearby other flock members and add all of them to an acceleration which i then add to the members velocity. and then 0 the acceleration at the end of the loop. code is as follows seperation algorithm
Fvector 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[i] ) //if its not itself
		{
			Fvector memberToTestAgainst = flockElements[i]->get_pEntityPosition( );
			float distance = distanceFinder( flockMembersPosition, memberToTestAgainst );

			if( distance < SPHERE_OF_INFLUENCE )
			{
				if( distance > 0 && distance < SPACING )
				{
					Fvector difference = flockMembersPosition - memberToTestAgainst;
					Fvector unitDifference = difference.getUnit( );
					seperationVector += ( unitDifference / distance );
					++average;
				}
			}
		}
		
	}
	if( average > 0 )
	{
		seperationVector /= average;
	}

	if( seperationVector.length( ) > 0 )
	{
		seperationVector = seperationVector.getUnit( );
		seperationVector *= MAX_SPEED;
		seperationVector -= flockTester->get_pEntityVelocity( );
		seperationVector *= MAX_FORCE;
	}
	
	return seperationVector;
	
}


alignment algorithm
Fvector Flocking::align( PointEntity* flockTester )
{
	Fvector alignmentVector = Fvector( 0.f, 0.f, 0.f );
	Fvector flockMemberVelocity = flockTester->get_pEntityVelocity( );
	float average = 0;
	for( int i = 0; i < numOfElements; ++i )
	{
		Fvector memberToTestAgainst = flockElements[i+1]->get_pEntityVelocity( );
		float distance = distanceFinder( flockTester->get_pEntityPosition( ), memberToTestAgainst );

		if( distance < SPHERE_OF_INFLUENCE)
		{
			alignmentVector = flockMemberVelocity + memberToTestAgainst;
			++average;	
		}
	}
	if( average > 0 )
	{
		alignmentVector /= average;
	}

	if( alignmentVector.length( ) > 0 )
	{
		alignmentVector = alignmentVector.getUnit( );
		alignmentVector *= MAX_SPEED;
		alignmentVector -= flockTester->get_pEntityVelocity( );
	}

	return alignmentVector;
}




cohesion algorithm
Fvector Flocking::stickTogether( PointEntity* flockTester )
{
	Fvector cohesionVector = Fvector( 0.f, 0.f, 0.f );
	Fvector flockTesterPosition = flockTester->get_pEntityPosition( );
	Fvector flockMemberVel = Fvector( 0.f, 0.f, 0.f );
	float average = 0;

	for( int i = 0; i < numOfElements; ++i )
	{
		flockMemberVel = flockElements[i]->get_pEntityVelocity( );

		if( flockTester != flockElements[i] )
		{
			Fvector memberToTestAgainst = flockElements[i]->get_pEntityPosition( );
			float distance = flockTesterPosition.distance( memberToTestAgainst );

			if( distance < SPHERE_OF_INFLUENCE)
			{
				Fvector meToThem = memberToTestAgainst - flockTesterPosition;
				meToThem = meToThem.getUnit( );
				cohesionVector += meToThem;
				++average;
			}
		}
	}
	if( average > 0 )
	{
		cohesionVector /= average;
	}

	return cohesionVector;
}


and hunt algorithm
Fvector Flocking::hunt( PointEntity* flockTester )
{
	Fvector huntVector = Fvector( 0,0,0 );
	Fvector flockTesterPosition = flockTester->get_pEntityPosition( );

	float distance = flockTesterPosition.distance( this->get_FlockLeader( )->get_pEntityPosition( ) );
	
	Fvector difference = this->get_FlockLeader( )->get_pEntityPosition( ) - flockTesterPosition;
	Fvector directionVector = difference.getUnit( );
	huntVector += directionVector;
	

	return huntVector;
}


and here is how i add the velocities and calculate the new positions
void Flocking::updateFlock( float deltaTime )
{	
	Fvector gravity (0.0, -0.05, 0.0);
	Fvector bounce(0.0, 1.0, 0.0);
	Fvector currentVel;
	Fvector newVel;
	Fvector deltaVel;
	Fvector newPos;


	setFlockLeader( flockElements[0] );
	for( int i = 0 ; i < numOfElements; i++)
	{
		if( !flockElements[i]->get_isLeader( ) )
		{
			currentVel = flockElements[i]->get_pEntityVelocity( );
			deltaVel = flockElements[i]->get_pEntityAcceleration( ) * deltaTime;
			currentVel += deltaVel;
			newPos = flockElements[i]->get_pEntityPosition( ) + currentVel * deltaTime;
			
			flockElements[i]->set_pEntityVelocity(newVel);
			flockElements[i]->set_pEntityPosition(newPos);

			Fvector seperation = this->seperate( flockElements[i] );
			Fvector align = this->align( flockElements[i] );
			Fvector coheed /*& cambria*/ = this->stickTogether( flockElements[i] );
			Fvector hunt = this->hunt( flockElements[i] );

			seperation *= 1.2f;
			align *= 1.6f;
			coheed *= 1.8f;
			hunt *= 2.0f;
			
			flockElements[i]->set_pEntityAcceleration( flockElements[i]->get_pEntityAcceleration( ) + seperation );
			flockElements[i]->set_pEntityAcceleration( flockElements[i]->get_pEntityAcceleration( ) + align );
			flockElements[i]->set_pEntityAcceleration( flockElements[i]->get_pEntityAcceleration( ) + coheed );
			flockElements[i]->set_pEntityAcceleration( flockElements[i]->get_pEntityAcceleration( ) + hunt );

			constrainFlock( i );

			deltaVel = flockElements[i]->get_pEntityAcceleration( ) * deltaTime;
			newVel = currentVel + deltaVel;
			newPos = flockElements[i]->get_pEntityPosition( ) + newVel * deltaTime;

			flockElements[i]->set_pEntityVelocity( newVel );
			flockElements[i]->set_pEntityPosition( newPos );
		}
		else
		{
			static float time = 0.0f;
			time += deltaTime;

			Fvector targetPos = Fvector( 0,0,0 );
			targetPos.x = sinf(time) * 5.0f;
			targetPos.z = cosf(time) * 5.0f;

			Fvector meToTarget = targetPos - flockElements[i]->get_pEntityPosition( );
			newVel = meToTarget;
			newPos = flockElements[i]->get_pEntityPosition( ) + newVel * deltaTime;

			flockElements[i]->set_pEntityVelocity( newVel );
			flockElements[i]->set_pEntityPosition( newPos );
		}


		glPushMatrix( );
		glTranslatef( flockElements[i]->get_pEntityPosition( ).x, flockElements[i]->get_pEntityPosition( ).y, flockElements[i]->get_pEntityPosition( ).z );
		glutSolidSphere( 0.5, 20, 20 );
		glPopMatrix( );

		flockElements[i]->set_pEntityAcceleration( flockElements[i]->get_pEntityAcceleration( ) * 0 );
	}
	
}


sorry the last one is a bit hefty, but yes as i said, the math is sort of working to a degree, they stick together for the first few seconds but then what seems to happen is the velocity accumulates too much at some point and they start to seperate more than they align and stick together cheers

Share this post


Link to post
Share on other sites
After some discussion with my friend, the formulae arent inherently wrong, they are actually fine, however its when i add them as an acceleration they dont slow down and stop next to the target they are approaching they overshoot, so i need to figure a way to dampen their approach and match velocities as soon as possible.

any suggestions?

Share this post


Link to post
Share on other sites

This topic is 2845 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this