I'm having a problem with some very simple collision detection in my break out clone. The ball does fine when it hits the left and right side of the blocks. But sometimes when it hits the top and bottom it goes through the block and takes out 2 or three blocks at once. I'm new and just can't see my mistake.

        
/*
BlockSize = 32
Level_1 is 32 blocks accross and 24 down
BallSize = 16
*/
void Ball_Collision()
	{
	for (int x = 0; x < 32; x++)
	   {
	   for (int y = 0; y < 24; y++)
	   {
	   if(Level_1[y][x] != 0)
	      {
	      if( //check if ball hit top or bottom of block

		 //check the top

	      ( Ball_x >= x*BlockSize )&& 
	      ( Ball_x <= (x*BlockSize + BlockSize)-BallSize)&& 
 	      ( Ball_y >= (y*BlockSize) -BallSize)  &&
		//check the bottom

	      ( Ball_x >= x*BlockSize) && 
	      ( Ball_x <= ((x*BlockSize)+BlockSize)-BallSize) && 
	      ( Ball_y <= (y*BlockSize)+BlockSize)
		 )
		{
		//change ball's direction

		Ball_dy = -Ball_dy;
                //remove the block

		Level_1[y][x] = 0;
		}//end if

	       if ( //check if ball hit left or right side

		   //check the left

	       ( Ball_y >= y*BlockSize ) &&
	       ( Ball_y <= (y*BlockSize)+BlockSize ) &&
	       ( Ball_x >= (x*BlockSize)-BallSize) &&
		//check the right

	       ( Ball_y >= y*BlockSize) &&
	       ( Ball_y <= (y*BlockSize)+BlockSize) &&
	       ( Ball_x <= (x*BlockSize)+BlockSize)
		   )
		{
                 //change ball's direction

		Ball_dx = -1*Ball_dx;
                 //remove the block

		Level_1[y][x] = 0;
		}//end if*/

	    }//end if Level

			
	}//end for y


    }//end for x

        

I just think I need a push in the right direction. Thanks for your help. Foxtrot Edited by - Foxtrot on 9/6/00 5:23:28 AM

Hi.

Well, I am afraid to tell you that the collision detection algorithm needed for that.

First, if the ball''s rectangle if just 1 pixel to the left of the target, or 1 pixel to the right, the top-bottom collision detection portion will fail.

Second, if the bottom side of the ball''s rectangle collides with the target, the left-right collision detection will fail.

Here is what I would do: Instead of testing if the is is "inside" the target, test is the ball is *NOT* "outside".

    while(1=1){//if ball is to the left of the target, end testing   if(Ball_x < ((x*BlockSize) - BallSize))      break;//if ball is to the right of the target, end testing   if(Ball_x >= ((x*BlockSize) + BlockSize))      break;//if ball is on top of the target, end testing   if(Ball_y < ((y*BlockSize) - BallSize))      break;//if ball is to the right of the target, end testing   if(Ball_y >= ((y*BlockSize) + BlockSize))      break;//if we get here, THE RECTABGLE of the ball (not necessarily the ball itself) is colliding with the target.   DetermineNewDirection(x,y);}    

The DetermineNeDirection function does a pixel level collision detection, and determines de new ball direction.

One way would be to draw an inmaginary circle arond the ball, and as you "plot" each inmaginary pixel test for them for collision. If the pixels at 0 degrees are colliding, ball top collided, if the pixels at 180 degres collided, the the ball bottom, etc.

Or, if you are targeting a fast machine you can just go the DetermineNewDirection function and test each tile.

Hope this helps in one way or another.

Topgoro

back on the good old Amiga using AMOS basic I wrote a break out program too and I had the same problem initially.

The problem probably is that dy gets larger than the height of your block. If this happens you will skip several blocks in on single screen update (the place you do the x+=dx and y+=dy) and those that was skipped will never be detected as being collided.

What you should do is to take the position at (x,y) and (x+dx,y+dy) and think of it as a line. Detect if there are any collisions at all on this line. If there is it is a the position on the line closest to (x,y).

When the position (lets call it (cx,cy)) has been found set (x,y) = (cx,cy) and delete that one block.

To detect that lines pass through a block you can do by testing if the line crosses one of the edges of the block. This is a simple matter of finding the position where two lines cross and doing it 4 times.
A smarter algorithm for testing for edge collision exists (that requires fewer calculations) but it is to complex to get into here unless you really wnat it.

Jacob Marner

Thanks,
I believe I have fixed it for now. What I did was,
Instead of testing for the top left corner of the ball I tested
for the center of the ball and added or subtracted the ball
radius as nesassary(spelling?). It works good enough for now.

    if ( //check if ball hit top or bottom of block	//check the top	( Ball_x+BallRadius >  x*BlockSize)&& 	( Ball_x+BallRadius < (x*BlockSize + BlockSize))&& 	( Ball_y+BallRadius > (y*BlockSize) - BallRadius)  &&	//check the bottom	( Ball_x+BallRadius >  x*BlockSize) && 	( Ball_x+BallRadius < (x*BlockSize) + BlockSize ) && 	( Ball_y+BallRadius < (y*BlockSize)+BlockSize+BallRadius)	)	{	Ball_dy = -Ball_dy;	Level_1[y][x] = 0;	}//end ifif ( //check if ball hit left or right side	//check the left	( Ball_y+BallRadius >  y * BlockSize) &&	( Ball_y+BallRadius <  y * BlockSize + BlockSize) &&	( Ball_x+BallRadius >  x * BlockSize - BallRadius) &&						//check the right	( Ball_y+BallRadius >  y * BlockSize) &&	( Ball_y+BallRadius <  y * BlockSize + BlockSize ) &&	( Ball_x+BallRadius <  x*BlockSize +BlockSize+BallRadius)	)	{	Ball_dx = -Ball_dx;	Level_1[y][x] = 0;	}//end if*/    

Thanks for your help. I''m sure I''ll need it again.

Foxtrot

I''m still having some problems with my collision detection.
Topgoro,
I see what you mean by parts of the detection failing. If the
ball contacts the block at exactly it''s x axis or y axis
it either goes right throught the block or gets caught inside it
for a couple of frames. Not good. How would I go about pixel
level collision? Never tried that before.

Hi.

Foxtrot, doing the circle thing is easy, here it is:

        //--------------------------------------------------------    //if ball is to the left of the target, end testing	if(Ball_x < ((x*BlockSize) - BallSize))		goto NoCollision;//if ball is to the right of the target, end testing	if(Ball_x >= ((x*BlockSize) + BlockSize))		goto NoCollision;//if ball is on top of the target, end testing	if(Ball_y < ((y*BlockSize) - BallSize))		goto NoCollision;//if ball is to the right of the target, end testing	if(Ball_y >= ((y*BlockSize) + BlockSize))		goto NoCollision;//if we get here, THE RECTABGLE of the ball (not necessarily the ball itself) is colliding with the target.	DetermineNewDirection((int)(x + (BallSize / 2)),(int)(y + (BallSize / 2)), &Ball_dy, &Ball_dx, Level_1);NoCollision://--------------------------------------------------------    void DetermineNewDirection(int Y, int X, int *Ball_dy, int *Ball_dx, int *Level_1){int TestY;int TestX;int Degree;double DegreeRadian;int DegreeCount = 360;int Radious = (int)(BallSize / 2);//circle around the ball testing each pixel	for(Degree = 0; Degree < DegreeCount; Degree ++)	{	//determine the next XY to test		DegreeRadian = (6.283185307)*Degree/DegreeCount;		TestY = (int)((Radious * cos(DegreeRadian)) + Y);		TestX = (int)(Radious * sin(DegreeRadian)) + X);	//if pixel is to the left of the target, end testing		if(X < (x*BlockSize))		goto NoCollision;	//if pixel is to the right of the target, end testing		if(X >= ((x*BlockSize) + BlockSize))		goto NoCollision;	//if pixel is on top of the target, end testing		if(Y < (y*BlockSize))		goto NoCollision;	//if pixel is to the right of the target, end testing		if(Y >= ((y*BlockSize) + BlockSize))		goto NoCollision;	//if we get here, we have a collision		break;NoCollision:	}//if we had a collision...	if(Degree < DegreeCount)	{	//remove target		(*Level_1)[Y][X] = 0;	//depending on the value of "Degree", is where the ball collided with the target	//Degree = 0 (or DegreeCount - 1) bottom of ball collided	//Degree = (DegreeCount /2) top of ball collided	//Degree = (DegreeCount /4) right of ball collided	//Degree = ((DegreeCount /4)*3) left of ball collided	//test for bottom		if(Degree < ((DegreeCount / 16)*1) || Degree > ((DegreeCount / 16)*15))		{			*Ball_dy = - *Ball_dy;			goto Exit;		}	//test for top		if(Degree <= ((DegreeCount / 16)*9) && Degree > ((DegreeCount / 16)*7))		{			*Ball_dy = - *Ball_dy;			goto Exit;		}	//test for left		if(Degree <= ((DegreeCount / 16)*13) || Degree > ((DegreeCount / 16)*11))		{			*Ball_dx = - *Ball_dx;			goto Exit;		}	//test for right		if(Degree <= ((DegreeCount / 16)*3) || Degree > ((DegreeCount / 16)*5))		{			*Ball_dx = - *Ball_dx;			goto Exit;		}	//if we get here, it was hit by a "corner" (so to speak)		*Ball_dy = - *Ball_dy;		*Ball_dx = - *Ball_dx;	}Exit:	return;}        

As you can see, I changed the original part because I was actually using the "break" command as a cheap goto, also I forgot the bottom break so in the event of collision you would have en endless loop.

You will have to play with the "Radious" value a bit, but I believe that value I used should do. I hope this helps you do your collision correctly.

Topgoro

PS: I don't know if you like this "goto" thing, but I am afraid is the best way I know how to implement this


Edited by - Topgoro on September 8, 2000 8:40:28 AM

You could do something like
int collid; //return value for collision
while(1){
collid=(check left)?0:1;//check left;
if(collid) collid=(check right)?0:1;
if(collid) collid=(check top)?0:1;
if(collid) collid=(check bottom)?0:1;
if(collid) (keep going);
else{
(remove block);
break;
}
}

this is a really general outline. I like the idea of checking to see if the ball is NOT colliding with something, then if that returns false, it has to be colliding with something. I would make removing the blocks a seperate function. I would also make the collision detection as a seperate function and then return 0 if no collision and 1 if collision. By doing this you can keep a lot of stuff out of the main function, thereby making it so you can move stuff around and visualize things easier.


I have a cannon, and it launches potatoes.
You will bow down to me, or you will eat mashed potatoes at 60mph.
EAT AT WAFFLE HOUSE!
The Spyders Web JavaScript Games.
Check out the JavaScript RPG!