stopping jumping in enforcing seperation

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

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);

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

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

++a;
}

}



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 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.