Help with multiple 2D ball collision code

mediakitchen
mediakitchen used Ask the Experts™
on
am having problems with my code for dealing with multiple ball collisions.

The code works absolutely perfect 99% of the time however there appears to be a bug where with certain ball positions, angles and velocities the collision reaction is erratic.

I need this code to be highly optimised as it is for a mobile phone game.

I have spent weeks trying to fix this with the only outcome being my head hurting. When I trace the variable values I can see the problem appears to occur when the value of dt is greater than 1 (see code attached) but I cannot work out how to solve this issue.

Fingers crossed!
local function moveBallObjects()


	local friction = 0.8
	
	local dV = 0.08
	
	
	for i = allBallsGroup.numChildren, 1, -1 do

	
		local horizontalVelocity = allBallsGroup[i].horizontalVelocity
		local verticalVelocity = allBallsGroup[i].verticalVelocity

		local V = (horizontalVelocity * horizontalVelocity) + (verticalVelocity * verticalVelocity)
	
		if V ~= 0 then
			
			V = mSqrt(V)
	
			allBallsGroup[i][2].rotation = allBallsGroup[i][2].rotation + 10 * V
		
			local k = (V - dV) / V
	
			if k < 0 then
	
				k = 0
		
			end
			
			print ("k = " ..k)
	
			allBallsGroup[i].horizontalVelocity = horizontalVelocity * k
			allBallsGroup[i].verticalVelocity = verticalVelocity * k
			
			print ("horizontalVelocity = " .. allBallsGroup[i].horizontalVelocity)
			print ("verticalVelocity = " .. allBallsGroup[i].verticalVelocity)
		
			allBallsGroup[i].tempX = allBallsGroup[i].tempX + allBallsGroup[i].horizontalVelocity
			allBallsGroup[i].tempY = allBallsGroup[i].tempY + allBallsGroup[i].verticalVelocity
			
			for j = allBallsGroup.numChildren, 1, -1 do

				if allBallsGroup[i] ~= allBallsGroup[j] then

					checkForCollisionWithBall (allBallsGroup[i], allBallsGroup[j])

				end
			end
			
			
	
			allBallsGroup[i].x = allBallsGroup[i].tempX
			allBallsGroup[i].y = allBallsGroup[i].tempY

		end
	
		
	
			
	end

	
end


local function checkForCollisionWithBall( firstBallRef, secondBallRef )

	-- ------------------
	-- Set some constants
	-- ------------------

	local radius = 14 -- Radius of ball
	local radiusSquared = (2 * radius) * (2 * radius) -- Radius squared
	
		
	-- ---------------------------------------------
	-- Calculate distance between balls on both axis
	-- ---------------------------------------------
	
	local dx = secondBallRef.tempX - firstBallRef.tempX -- horizontal distance between the 2 balls
	local dy = secondBallRef.tempY - firstBallRef.tempY -- vertical distance between the 2 balls
	
		
	local dxy = (dx * dx) + (dy * dy)
	
	if (dxy < 0.00001) then
	
		print ("dxy less than 0.00001: dxy = " .. dxy)
	
		return
	
	end
	
	-- -----------------------------------------------------------------------------------
	-- If the distance squared is less than the radius squared then we have a collision
	-- Note this is an optimisation to prevent having to perform a square root calculation
	-- -----------------------------------------------------------------------------------
	
	
	if (dxy < radiusSquared) then
	
		-- --------------------
		-- We have a collision!
		-- --------------------
		
		-- ------------------------------------------------------------------------------
		-- We now perform the square root to calculate the distance between the two balls
		-- ------------------------------------------------------------------------------
		
		dxy = mSqrt(dxy)
		
		local cs = dx/dxy
		local sc = dy/dxy
		
		-- -----------------------------------------------------------
		-- Calculate component of velocity in the direction of (dx,dy)
		-- -----------------------------------------------------------
		
		local vp1 = firstBallRef.horizontalVelocity * cs + firstBallRef.verticalVelocity * sc
		local vp2 = secondBallRef.horizontalVelocity * cs + secondBallRef.verticalVelocity * sc
		
		local dt = (radius + radius - dxy) / (vp1 - vp2)
		
		firstBallRef.tempX = firstBallRef.tempX - (firstBallRef.horizontalVelocity * dt)
		firstBallRef.tempY = firstBallRef.tempY - (firstBallRef.verticalVelocity * dt)
			
		secondBallRef.tempX = secondBallRef.tempX - (secondBallRef.horizontalVelocity * dt)
		secondBallRef.tempY = secondBallRef.tempY - (secondBallRef.verticalVelocity * dt)
		
		dx = secondBallRef.tempX - firstBallRef.tempX -- horizontal distance between the 2 balls
		dy = secondBallRef.tempY - firstBallRef.tempY -- vertical distance between the 2 balls
		
		local distance = mSqrt(dx * dx + dy * dy)
		local ax = dx/distance
		local ay = dy/distance
		
		local va1 = (firstBallRef.horizontalVelocity * ax + firstBallRef.verticalVelocity * ay)
		local vb1 = (-1 * firstBallRef.horizontalVelocity * ay + firstBallRef.verticalVelocity * ax)
		
		local va2 = (secondBallRef.horizontalVelocity * ax + secondBallRef.verticalVelocity * ay)
		local vb2 = (-1 * secondBallRef.horizontalVelocity * ay + secondBallRef.verticalVelocity * ax)
		
		local vaP1 = va1 + (1 + 1) * (va2 - va1)/(1 + 1/1)
		local vaP2 = va2 + (1 + 1) * (va1 - va2)/(1 + 1/1)

		
		firstBallRef.horizontalVelocity = vaP1 * ax - vb1 * ay
		firstBallRef.verticalVelocity = vaP1 * ay + vb1 * ax
		
		secondBallRef.horizontalVelocity = vaP2 * ax - vb2 * ay
		secondBallRef.verticalVelocity = vaP2 * ay + vb2 * ax

		
		firstBallRef.tempX = firstBallRef.tempX + firstBallRef.horizontalVelocity * dt
		firstBallRef.tempY = firstBallRef.tempY + firstBallRef.verticalVelocity * dt
		
		secondBallRef.tempX = secondBallRef.tempX + secondBallRef.horizontalVelocity * dt
		secondBallRef.tempY = secondBallRef.tempY + secondBallRef.verticalVelocity * dt
		
		checkForCollisionWithBall ( firstBallRef, secondBallRef )

	
	end
	
end

Open in new window

Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Why radius squared is (2 * r) * (2 * r) ? This is a diameter squared!

How it is failing?

Author

Commented:
Yeah it is probably the incorrect variable name however it is basically to compare the distance between the center of 2 balls with the distance that 2 balls are apart. As an optimisation, rather than using pythagorus and doing a square root, I instead compare the distance squared.

With regards how the game is failing, I have narrowed it down to occuring when the value of dt is greater than 1 and also it seems to happen when one ball is stationary and therefore vp1 or vp2 has a value of zero.

I can't quite understand why it is getting a value of dt that is greater than one but the implications seem to be that it results in a huge movement of the ball

firstBallRef.tempX = firstBallRef.tempX - (firstBallRef.horizontalVelocity * dt)
firstBallRef.tempY = firstBallRef.tempY - (firstBallRef.verticalVelocity * dt)

I just can't get my head around the dt thing. Surely if it didn't collide in the previous enterFrame check it can have only moved a short distance to get to this collision. Weird thing is how it works perfectly most of the time - just not at certain angles and positions.

Let me know if you need any more info.

Thanks

Paul

Author

Commented:
Btw the game is set to run at 30FPS and it calls the moveBallObjects() every enterFrame.
Fundamentals of JavaScript

Learn the fundamentals of the popular programming language JavaScript so that you can explore the realm of web development.

Author

Commented:
As an example of ball positions and velocities when the bug occurs, the following was one such occurence

Ball 1 x = 96, y = 113, horizontalVelocity = 0, verticalVelocity = 0
Ball 2 x = 89, y = 124, horizontalVelocity = 7, verticalVelocity = -11

Please note I have rounded off the decimal places for speed of typing.
ftp://Public:EE@64.237.112.10
look under Balls Collision.. source included.

Author

Commented:
Thanks General - I can view the project1.exe but unfortunately do not have the required program to view the source. Ideally I would like someone to offer a solution related to my code.

Just a side note, whenever you perform a division, you should check that the divisor is not zero, because this way the resulting is infinite - and maths in this case can be dangerous.
Second, can you explain the lines 144 and 145?

In your example, the vertical speed is such that on the next frame the two balls will be concentric. (124 + (-11) = 113).
I think that dt > 1 when speed is high enough that in one frame the balls "pass through" the other. (if I correctly understood your algorithm. I think you could simplify it....)
you can view the pas files with notepad.. it is just to give you a working set of code.. pascal reads similar to basic.  thus the formulas would be easily deciphered..

You are using LUA??
ftp://Public:EE@64.237.112.10

also notice the LUA folder with machine flow which has balls that collide..   again all has pascal source but there are lua scripts too which may contain what you need.

Author

Commented:
Thanks for your help HappyCactus and the point about the division.

Lines 144 and 145 are based on the following code I found on a site where I have used a value of 1 for ed and also a value of 1 for mass

// New velocities in these axes (after collision): ed<=1,  for elastic collision ed=1
double vaP1=va1 + (1+ed)*(va2-va1)/(1+mass1/mass2);
double vaP2=va2 + (1+ed)*(va1-va2)/(1+mass2/mass1);

When I traced the velocities of the balls before the collision they were always less than the diameter of a ball (28) so I assumed that means it is not possible for balls to pass through each other. Perhaps I have overlooked something.

I would appreciate any help simplifying my algorith. I have tried numerous solutions from the web and either they are too slow when tested on the phone or they are buggy. My current code runs really smoothly and has nice movement so it would be great if I could adapt it to prevent the bug. Is there a way you can put a maximum velocity to prevent dt ever going above 1?

Thanks

Paul

Author

Commented:
Here is the entire post of the article I based my code on

The collision should have occurred if d equal r1+r2; // if(d==r1+r2)

However, there is a finite time step dt in the simulation calculation,so most often we would not be able to find the above condition (exact time when two ball real occurred).
So we check if d<= r1+r2; Then we know the collision should have occurred.

The real collision should have occurred before you detected that the distance between two center of the balls d is less than the sum of those two balls r1+r2. (d< r1+r2)

The correct way is to find the time when the two ball really collide with each other.
Suppose the center of those two ball are x1,y2 and x2,y2
dx=x2-x1, dy=y2-y1; d=sqrt(dx*dx+dy*dy);

First calculate the component of velocity in the direction of (dx,dy)
vp1= vx1 *dx/d+vy1*dy/d;
vp2= vx2*dx/d+vy2*dy/d;

Collision should have happened dt before you have detected r1+r2
and dt =(r1+r2-d)/(vp1-vp2);
 and dt =(r1+r2-d)/(vp1-vp2);// the collision should have occurred at t-dt (Actually this is also an approximation).

So you should move those two ball backward
 x1-= vx1*dt;
 y2 -= vy1*dt;
 x2-=vx2*dt;
 y2-=vy2*dt;

Now the distance between center of the two balls is d'=r1+r2;

The following code take care of collision:

double dx = x2-x1, dy = y2-y1;
// where x1,y1 are center of ball1, and x2,y2 are center of ball2
double distance = Math.sqrt(dx*dx+dy*dy);
// Unit vector in the direction of the collision
double ax=dx/distance, ay=dy/distance;
// Projection of the velocities in these axes
double va1=(vx1*ax+vy1*ay), vb1=(-vx1*ay+vy1*ax);
double va2=(vx2*ax+vy2*ay), vb2=(-vx2*ay+vy2*ax);
// New velocities in these axes (after collision): ed<=1,  for elastic collision ed=1
double vaP1=va1 + (1+ed)*(va2-va1)/(1+mass1/mass2);
double vaP2=va2 + (1+ed)*(va1-va2)/(1+mass2/mass1);
// Undo the projections
vx1=vaP1*ax-vb1*ay;  vy1=vaP1*ay+vb1*ax;// new vx,vy for ball 1 after collision
vx2=vaP2*ax-vb2*ay;  vy2=vaP2*ay+vb2*ax;// new vx,vy for ball 2 after collision

Quote
(ax,ay)  is the unit vector in the direction connected two objects.
draw a line connect two object, assign the angle between this line and x-axis is ¿,
then  cos¿=ax, sin ¿=ay
So vap1*ax=vap1*cos¿ give x-component of vap1, and vap1*ay give y-component of vap1

Because vb1 and vb2 is in the direction perpendicular to the (ax,ay)
,then the angle between vb1 and x-axis is f=¿+p/2
so cos f=cos(¿+p/2)=-sin¿=-ay, sinf=sin(¿+p/2)=cos¿=ax
to calculate x-component of vb1 we need to calculate vb1*cos f=vb1*(-ay)=-vb1*ay
,and (y-component of vb1) = vb1*sinf=vb1*ax

Because we have move time backward dt, we need to move time forward dt.
so
  x1+= vx1'*dt;
  y1+=vy1'*dt;
  x2+=vx2'*dt;
  y2+=vy2'*dt;

Now the distance between two ball will be larger than r1+r2.

If you did not correct the time dt (before you have found collision occurred, you will find balls clutch together. and they don't even let go.

Author

Commented:
Thanks General Tackett, I will have a look and see what the source looks like. However please note I have tried various examples of code from the web over the last few weeks and I haven't found any that will run fast enough on the phone or are not buggy (balls sticking together or moving erratically).

I am probably overlooking something but as my code seems to work perfectly 99% of the time, I was hoping for a solution that would identify and fix the error in my code. However I would be happy with any solution at this stage.
ah.. on phone.. well.. you could try creating lookup tables for your math  like sin, cos etc.. that way you dont have to calculate just look up in an array..
You appear to be using a method called penalty forces, that is allowing the objects to penetrate and then using a force to push them apart (the penalty force).  This is the simplest method of resolving the collision, however it is very prone to floating point accuracy problems.

This article gives a good description of the potential problems with floating point math. http://en.wikipedia.org/wiki/Floating_point

Assume two circles penetrate by a tiny amount, so dxy is 27.99999995 or something similarly tiny.  You do the (radius + radius - dxy) and the result is a very small float, you get loss of accuracy in the exponent.  You then divide that by (vp1 - vp2) creating more accuracy problems, dividing a very small number by another possibly very small number.

These problems are within the nature of the method, there are many games that have the same problems.  You can't solve it directly, you either handle the problems or change your method.

Possible solutions -

Ignore any value of dt that is unrealistically big.  Either set the force to zero or cap it to some maximum value.  This also does not produce ideal behaviour but it solves the problem.

Allow the circles to penetrate to a safe depth before forcing them apart.  Ignore any collision that is not at a depth where float accuracy is sufficient. This does not produce ideal behaviour but it solves the problem.

Use a different aproach.  A more stable method is not allowing the objects to penetrate.  Calculate when the objects will collide and modify their position and velocity accordingly.

Author

Commented:
Thanks satsumo

That is most helpful. I tried one of your suggestions i.e ignoring any value of dt that is "too big". First I tried only allowing values where the absolute value was between 0 and 1 and I found the balls were passing through each other visually on occasions (probably the same occasions where they had the erratic behaviour) I had the same resultw when I changed it to only values between 0 and 2.

From observing the original problem of the balls behaving erratically very occasionally I am nearly sure it is always when a ball passes another at a very small angle. I am not sure if the speed of the ball is a factor though as often this seems to happen when the ball is moving quite slowly.

I have implemented another approach where it calculates where the objects will collide first but it runs really slow and that is on my fastest phone too. Is it worth pasting this code in to see if anyone can optimise this?

Thanks

Paul
The small angle is a good indication of the problem.  When the circles are travelling in nearly parallel directions, they are moving toward each other very slowly, so will penetrate only a very small amount.  You're also right in thinking that speed is a factor, slower moving circles are more likely to have a tiny overlap.

I was suprised that you could see the objects penetrating visually.  Though I think it because your testing dt which is the relative change it depth from one frame to the next.  It might be more consistent to test (dxy - radius * 2), the amount of overlap rather than the change in depth.

The passing through behaviour also depends on what you do with the 'too big' value.  Assuming that the accuracy problem happens when objects penetrate a very small amount, it may be better to set dt to some small value rather than zero.  The objects still have to be pushed apart, setting dt to zero allows the circles to carry on in the same direction until the penetration gets bigger.

You might consider making the collision radius of the circle slightly bigger than its visual radius.  If the visual disruption isn't significant, you could just ignore it.  It depends on what matters for your game.

There are a few ways to optimise this method that don't invovle the math.  The same applies to another method too.  If you decide to use the different method I'd appreciate you posting your code as another question.  It makes the question/solution business simpler, and experts seem to avoid getting involved in longer threads.
Commented:
I know this isn't a general purpose fix, but, hey, go with what you got....


The problem seems to be the normal sort of "omigosh" moments that happen when you do math on a floating point unit.. very small numbers divided by smaller numbers yield big numbers, unexpectedly.

Clamp the value of dt to always be less than 1..  in other words...

if( dt > 0.9999)
then
dt = 0.9999

or whatever safe value you know.

I know it's not "correct", but as I say, it might help you move on to the next problem in your code.

Hope this helps,
-john

This is a common problem. As mentioned above it is caused by the fact that that the balls actually penetrate each other. On the next time step the ball may not entirely leave the interior of the other.  A good fix is to use collision a Flag for each ball, it is not perfect but very close to it and I find in general it works really well. It goes like this

(1) For each ball have a Flag

          Flag = true      =>   collision detected

          Flag = false     =>   no collision detected  (initialise all Flags to this)

(2)  At each time step

                  (a)  If collision detected and Flag = false calculate new velocity cause of collision and set Flag= true
                         
                  (b)  If collision detected and Flag = true  do not apply collision physics (stops re-application of collision physics)

                  (c)   If no collision detected and Flag = true set Flag = false   (two objects now apart)

All of this stops the collision physics being applied multiple times for a single collision. Your code is easily changed.

Author

Commented:
Thank you for a simple solution to implement. I have played the game about 20 times now using this new improved code and I have witnessed no glitches.

I am pleased I was able to keep my code as i really did not want to use a physics engine such as box2D due to the movement not looking so good.

Many thanks to everyone for their help on this tricky problem.

Paul

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial