Sign in to follow this  
Byron

stopping jumping in enforcing seperation

Recommended Posts

I am enforcing a seperation algorithm on a collection of agents in-game based on their radius. The seperation works a treat but if I have a large amount of agents I start noticing jumping where an agent is forced to the outside of the group as it is moved out of the way. What I am looking for is a good way of maintaining zero overlap of agents without jumping. Here is the code I am using:
void CAgent::SeperateAll()
{
	CAgent* pA;
	CAgent* pB;

	D3DXVECTOR2 vTemp;
	D3DXVECTOR2 vPos;
	float fDist;
	float fOverlap;

	std::list<CAgent*>::iterator a = m_lAgents.begin();

	while(a != m_lAgents.end())
	{
		pA  = *a;

		std::list<CAgent*>::iterator b = a;
		b++;

		if(b != m_lAgents.end())
		{
			while(b != m_lAgents.end())
			{
				pB = *b;

				vTemp = pA->GetPos() - pB->GetPos();
				fDist = D3DXVec2Length(&vTemp);

				fOverlap = (pA->GetRadius() + pB->GetRadius()) - fDist;

				if(fOverlap >= 0)
				{
					vPos = pA->GetPos();

					vPos += (vTemp/fDist) * fOverlap;
					pA->SetPos(vPos.x,vPos.y);
				}
				++b;
			}
		}

		++a;
	}

}

Share this post


Link to post
Share on other sites
I've encountered this problem before in optimisation problems. Essentially you're witnessing a solution where one element changing its value by a large amount saves a lot of other elements from changing by a small amount each. Indeed, many optimsiation methods intrinsically suffer from this problem. The solution: just add a further constraint to the system that limits the maximum displacement of a unit from its initial position. If no solution can be found, increase this limit and try again. Collect statistics on the required limit size versus initial density so you can use a lookup table in the future to get a good starting parameter value.

Make sense?

Cheers,

Timkin

Share this post


Link to post
Share on other sites
My current solution was to implement a seperation behaviour as well as the kinematic seperation in the code above so that rather than just ploughing onto the target and getting pushed back (hence the jumping) the seeks and seperation have weights applied that when combined stop the jumping I was seeing.

Share this post


Link to post
Share on other sites

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