Jump to content
  • Advertisement
Sign in to follow this  
homojedi

Flocking algorithm problem

This topic is 3210 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 ) //if its not itself
		{
			Fvector memberToTestAgainst = flockElements->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->get_pEntityVelocity( );

		if( flockTester != flockElements )
		{
			Fvector memberToTestAgainst = flockElements->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->get_isLeader( ) )
		{
			currentVel = flockElements->get_pEntityVelocity( );
			deltaVel = flockElements->get_pEntityAcceleration( ) * deltaTime;
			currentVel += deltaVel;
			newPos = flockElements->get_pEntityPosition( ) + currentVel * deltaTime;
			
			flockElements->set_pEntityVelocity(newVel);
			flockElements->set_pEntityPosition(newPos);

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

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

			constrainFlock( i );

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

			flockElements->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) * 5.0f;
			targetPos.z = cosf(time) * 5.0f;

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

			flockElements->set_pEntityVelocity( newVel );
			flockElements->set_pEntityPosition( newPos );
		}


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

		flockElements->set_pEntityAcceleration( flockElements->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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!