multiple entity collison detecion
Right...
I'm making a pool game and have some collison detection determining whether a ball will collide with another in the next frame using algortihm that goes something like if distance between edges < velocity magnitude the collision = true, with other bits to make sure they are on the same path etc.
Now this all works fine with just a cue ball and one color, but when you add more balls into the triangle and break off, it messes up. The problem is that it doesn't know which ball it is actually going to collide with as some of the other balls are also along its trajectory and it sometimes picks the wrong ball.
Hopefully i haven't explained that too badly, its hard to put into words but i'm sure it must be a common problem, i hope so at least.Is there some kind of search algorithm that i could use to pick the right ball for the collision without eating up my cpu time or do i need to redo the collison detection. Any help much appreciated
how are you doing your collision detection?
I'm testing for collisions in the frame before they occur, by testing if the distance between balls is less magnitude of the balls relative velocity, and also checking that they are moving towards each other. Then I get a shortened vector the move the balls to the point of contact, and then work out the physics of balls after contact.
If you detect multiple collisions (a ball is scheduled to collide with two or more other balls), then calculate the times of collision, and process the earliest collision.
JN_a at 2007-7-11 22:13:09 >
I understand what your saying but not totally clear. Here's a scenario.
A is going to collide with B and C, C turn out to be earliest. But C is also going to collide D with C, and D is the earliest for C. You already decided that there was going to be a collision between A and C as it was the earliest as far as A was concerned and then C jumps the queue so it would not hit A afterall, how do you control this?
If you then think about the happening three times it just all get too much for me. Help please
Sounds like you need to loop through all the balls and throw the vectors on a stack (i.e. ArrayList). Sort the stack from the least time to greatest time till collision. Process the first item on the stack (least time), then remove it. Now, recalculate the vectors and repeat the process until there are no balls left.
I like this idea, i've been trying something similar this afternoon but how do i keep track of which balls the vectros belong to after re aranging the list, and is it going to be fast enough for 20fps.
You could have a BallVector object that references a vector and a ball. By throwing that on the list instead of the ball or vector itself, you keep references to whos who.
HOw do i make one of them, i thought all the elements in a vector had to be of the same type, thanks for your help by the way.
sorry i was being thick, you said a BallVector 'object'. Thanks again
i have implement hat was suggested above thanks jbanes, but its painfullt slow cos it loops round and round testing balls againast each other and then redoing all the tests again. below is some of the code not the detection part, the bit that controls it all can anyone see anywhere i can speed it up. This is really starting to bug me, theres got to be an easy way to do this there are loads of pool games written in java
public void updateBalls()
{
newBalls=new Vector();
while(searchForBallCollisions());
balls=newBalls;
newBalls=null;
for (int i=0;i<balls.size();i++)
((Ball)balls.elementAt(i)).updatePosition();
}
public boolean searchForBallCollisions()
{
CollisionResult cRes;
aList=new ArrayList();
//get all possible collisions
for (int i=0;i<balls.size();i++)//check each ball against the others
{
//if(collisionDet.testWallCollision(((Ball)balls.elementAt(i))))
//{
//cRes=new CollisionResult(i,-1,collisionDet.getVectorToWall(),null,
//collisionDet.getNewVelocity(),null,collisionDet.timeToCollision());
//aList.add(cRes);
//}
for (int j=1;j<balls.size();j++)
{
if(collisionDet.testBallCollision(((Ball)balls.elementAt(i)),((Ball)balls.elementAt(j))))
{
cRes=new CollisionResult(i,j,collisionDet.getVectorToContact()[0],
collisionDet.getVectorToContact()[1],collisionDet.getNewVelocities()[0],
collisionDet.getNewVelocities()[1],collisionDet.timeToCollision());
aList.add(cRes);
}
}
}
//get first collision occurance
if(aList.size()>0)
{
cRes=(CollisionResult)aList.get(0);
for (int k=1;k<aList.size();k++)//check each ball against the others
{
CollisionResult testCRes=(CollisionResult)aList.get(k);
if (testCRes.timeToCollision >< cRes.timeToCollision)
cRes=testCRes;
}
//update ball values
((Ball)balls.elementAt(cRes.ballApos)).setVectorToContact(cRes.aCollisionVector);
((Ball)balls.elementAt(cRes.ballApos)).setVelocity(cRes.impulseA);
//remove earliest collison balls from the list of balls
newBalls.addElement(balls.remove(cRes.ballApos));
if(cRes.ballBpos>-1)//case when collison with wall only 1 ball in CollisionResult
{
//cRes.ballBpos-1 because removed ball above from vector
((Ball)balls.elementAt(cRes.ballBpos-1)).setVectorToContact(cRes.bCollisionVector);
((Ball)balls.elementAt(cRes.ballBpos-1)).setVelocity(cRes.impulseB);
//remove earliest collison balls from the list of balls
newBalls.addElement(balls.remove(cRes.ballBpos-1));
}
}
//if no omre ball collisions test for collisions with the walls
else
{
while(!balls.isEmpty())
{
newBalls.addElement(balls.remove(0));
}
return false; //no more collisons to find
}
//if no collisions move rest of balls to newBalls quicker than
//other direction when lots of collisons have taken place as new
//balls will be beigger and this is when we need to
//save time most because lots time spent resolving collisions
return true; //possibly more collisons to find
}
as you can see this beast loops and loops and loops
i have implement hat was suggested above thanks jbanes, but its painfullt slow cos it loops round and round testing balls againast each other and then redoing all the tests again. below is some of the code not the detection part, the bit that controls it all can anyone see anywhere i can speed it up. This is really starting to bug me, theres got to be an easy way to do this there are loads of pool games written in java
public void updateBalls()
{
newBalls=new Vector();
while(searchForBallCollisions());
balls=newBalls;
newBalls=null;
for (int i=0;i<balls.size();i++)
((Ball)balls.elementAt(i)).updatePosition();
}
public boolean searchForBallCollisions()
{
CollisionResult cRes;
aList=new ArrayList();
//get all possible collisions
for (int i=0;i<balls.size();i++)//check each ball against the others
{
//if(collisionDet.testWallCollision(((Ball)balls.elementAt(i))))
//{
//cRes=new CollisionResult(i,-1,collisionDet.getVectorToWall(),null,
//collisionDet.getNewVelocity(),null,collisionDet.timeToCollision());
//aList.add(cRes);
//}
for (int j=1;j<balls.size();j++)
{
if(collisionDet.testBallCollision(((Ball)balls.elementAt(i)),((Ball)balls.elementAt(j))))
{
cRes=new CollisionResult(i,j,collisionDet.getVectorToContact()[0],
collisionDet.getVectorToContact()[1],collisionDet.getNewVelocities()[0],
collisionDet.getNewVelocities()[1],collisionDet.timeToCollision());
aList.add(cRes);
}
}
}
//get first collision occurance
if(aList.size()>0)
{
cRes=(CollisionResult)aList.get(0);
for (int k=1;k<aList.size();k++)//check each ball against the others
{
CollisionResult testCRes=(CollisionResult)aList.get(k);
if (testCRes.timeToCollision >< cRes.timeToCollision)
cRes=testCRes;
}
//update ball values
((Ball)balls.elementAt(cRes.ballApos)).setVectorToContact(cRes.aCollisionVector);
((Ball)balls.elementAt(cRes.ballApos)).setVelocity(cRes.impulseA);
//remove earliest collison balls from the list of balls
newBalls.addElement(balls.remove(cRes.ballApos));
if(cRes.ballBpos>-1)//case when collison with wall only 1 ball in CollisionResult
{
//cRes.ballBpos-1 because removed ball above from vector
((Ball)balls.elementAt(cRes.ballBpos-1)).setVectorToContact(cRes.bCollisionVector);
((Ball)balls.elementAt(cRes.ballBpos-1)).setVelocity(cRes.impulseB);
//remove earliest collison balls from the list of balls
newBalls.addElement(balls.remove(cRes.ballBpos-1));
}
}
//if no omre ball collisions test for collisions with the walls
else
{
while(!balls.isEmpty())
{
newBalls.addElement(balls.remove(0));
}
return false; //no more collisons to find
}
//if no collisions move rest of balls to newBalls quicker than
//other direction when lots of collisons have taken place as new
//balls will be beigger and this is when we need to
//save time most because lots time spent resolving collisions
return true; //possibly more collisons to find
}
as you can see this beast loops and loops and loops
Have you tried just stepping through the collision detection frame by frame ? If in every frame you check all the balls that are moving to see if they are touching another ball it's not as processor intensive as you might think. I have something similar in my java game : www.student.dcu.ie/~lloydd2/GerbilsRevenge/index.html though in a much more basic way than you.
Thanks WaterWolf this has also been suggested to me but the problem with this is that if your balls have velocities greater than the diameter of your balls they can end up on the other side of the ball and appear to pass through it. This is really starting to do my head in, i've got to hand the ******* in soon, somebody must have made a pool game before that can point me in the right direction, i will soon be needing a dose of prozac to get me to the end of the project.
