Jump to content
  • Advertisement
Sign in to follow this  
Al Gorithm

improving breakout collision response

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've tried at least half a dozen methods of collision detection for my "breakout" game, even using ideas from the gamedev search engine. However,particularly at high speeds, the ball will pass through an object, regardless of my implementation. With my current best method this is rare but I would like to improve it. Any input on my current method would be appreciated. What i do is for each block and each ball is : A similar process to the below is repeated for each side of the block. I am using only the top here for simplicity's sake. I assess the ball's position in relation to the top of the block. If it is above (or below, or to whichever side that would make it not be a collision) I proceed. if(tBall.y < TOP){ If the ball's next position is on the other side of the top. . . if(tBall.y + (tBall.yVec*rTime) >= TOP){ Get the slope and Y intercept of the line formed by the ball's current and next position m = (tBall.y-((tBall.yVec*rTime)+tBall.y))/(tBall.x-(tBall.x+(tBall.xVec*rTime))); b = tBall.y-(tBall.x*m); Get the x value where the line intersects the top. If it is within the x axis boundaries of the block (the left and right). . . xlol = (TOP-b)/m; if(xlol > LEFT && xlol < RIGHT){ Reflect the y vector and set the y position to the top tBall.yVec = -tBall.yVec; tBall.y = TOP; } Of course there are problems with this method ... such as the angle reflecting straight back when the ball hits near a corner at a certain angle (detecting a side and a top/bottom hit) and possible problems with block ordering. . . but I'm not worried about those until I can get it working in more basic maps, where I have no explanation as of yet for blocks passing through as if they weren't there. Thanks in advance.

Share this post


Link to post
Share on other sites
Advertisement
Funny I just happen to be taking a break from programming my own arkanoid clone.

here the code from how I do my collision testing.


COL_INFO CBEBlock_Manager::Collision(int x, int y, int width, int height)
{
// temparay collision variable set to a default state
// state and paddle will more than likely never be
// changed here in this function.

COL_INFO col_info;
col_info.collision = false;
col_info.paddle = 100;
col_info.state = 0;
col_info.top = false;
col_info.bottom = false;
col_info.left = false;
col_info.right = false;
col_info.x = x;
col_info.y = y;

// setup grid we'll be checking based on were the ball is
// hopefully this will speed up collision detection by
// reducing the amount of blocks that need to be checked.
int bx1 = (x / 64) - 2;
if (bx1 < 0) bx1 = 0;
int bx2 = bx1 + 5;
if (bx2 > 15) bx2 = 15;

int by1 = (y / 32) - 2;
if (by1 < 0) by1 = 0;
int by2 = by1 + 5;
if (by2 > 20) by2 = 20;

for (int j=bx1; j<=bx2; j++)
{
for (int k=by1; k<= by2; k++)
{
// all of this collision detection uses diamond points for testing
// it is possible for a box to collide with the block and not
// be detecable. for the sake of speed I want to keep it this way.

if (m_block_buffer[j][k].active)
{
int bx = j * 64;
int by = k * 32;
bool collision = false;
bool top = false;
bool bottom = false;
bool left = false;
bool right = false;

// top is x+16, y
if ((x+16) > bx && (x+16) < (bx+63))
{
if (y > by && y < (by+31))
{
col_info.collision = true;
col_info.top = true;
col_info.y = (by+32);
collision = true;
bottom = true;
}
}

// bottom is x+16, y+32
if ((x+16) > bx && (x+16) < (bx+63))
{
if ((y+32) > by && (y+32) < (by+31))
{
col_info.collision = true;
col_info.bottom = true;
col_info.y = (by-32);
collision = true;
top = true;
}
}

// left is x, y+16
if (x > bx && x < (bx+63))
{
if ((y+16) > by && (y+16) < (by+31))
{
col_info.collision = true;
col_info.left = true;
col_info.x = (bx+64);
collision = true;
right = true;
}
}

// right is x+32, y+16
if ((x+32) > bx && (x+32) < (bx+63))
{
if ((y+16) > by && (y+16) < (by+31))
{
col_info.collision = true;
col_info.right = true;
col_info.x = (bx-32);
collision = true;
left = true;
}
}

// computate wether or not the block broke, depending
// on wich block and how the ball hit it.
// for now every block breaks if the ball hit it on any side
if (collision)
{
// normal blocks
if (m_block_buffer[j][k].block_id < BLOCK_INDESTRUCTABLE)
m_block_buffer[j][k].active = false;

// top blocks, can only be broke from the top
if (m_block_buffer[j][k].block_id == BLOCK_TOP && top == true)
m_block_buffer[j][k].active = false;

// sides blocks can only be broke from the sides.
if (m_block_buffer[j][k].block_id == BLOCK_SIDES)
{
if (left == true || right == true)
m_block_buffer[j][k].active = false;
}

// number blocks, 1-5, when one is hit a reverts to the nextone.
// until it's number 1 then it breaks.

if (m_block_buffer[j][k].block_id == BLOCK_ONE)
m_block_buffer[j][k].active = false;

if (m_block_buffer[j][k].block_id == BLOCK_TWO)
{
m_block_buffer[j][k].block_id = BLOCK_ONE;
m_block_buffer[j][k].texture = m_block_one;
}

if (m_block_buffer[j][k].block_id == BLOCK_THREE)
{
m_block_buffer[j][k].block_id = BLOCK_TWO;
m_block_buffer[j][k].texture = m_block_two;
}

if (m_block_buffer[j][k].block_id == BLOCK_FOUR)
{
m_block_buffer[j][k].block_id = BLOCK_THREE;
m_block_buffer[j][k].texture = m_block_three;
}

if (m_block_buffer[j][k].block_id == BLOCK_FIVE)
{
m_block_buffer[j][k].block_id = BLOCK_FOUR;
m_block_buffer[j][k].texture = m_block_four;
}
}
}
}
}

return col_info;
}



It may not be the most optimized way of doing it but it works just fine for me. I allow the ball to move it'self. After moving it calls the Collision function of my block manager and it tells the ball if it collided, what side of the ball collided, and were the ball should be.

also my blocks, at the smallest are 64x32 in size and my ball is 32x32 pixels in size. I never allow the ball to move faster that 20 pixels in any direction at a time, but no problem there, since the movement is timed to the 1000th of a sec I can increase the speed without making it move more pixels at a time.

although once and only once the ball got stuck in one of the indestructable blocks. I don't know how as I can't reproduce it.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Problems with balls that pass through other objects when they move Fast Enough. Is because you are using Static collision detection methods. Dynamic Collision detection should be used in these situations to fix the problem.

Rather than collide at 'snapshots' in time (static), you need to find the collisions that happen Inbetween those updates as well, so that rather than a series of position and collision updates, the ball is simulated as a continuous motion, with continuous collision (dynamic)

since this is a breakout game, the simplest way to do that is, whenever you update the ball position, rather than collision check from the new position; you should calculate a Line between the new and old positions, then see if that Line intersects any blocks, and if it does, what the exact positon of intersection is. Line intersection is simple algebra.... look it up...
(of course, you need to compensate for the fact that the ball has a radius larger than the line, but thats pretty simple; just pretend all the blocks are bigger by that amount)

Share this post


Link to post
Share on other sites
I implemented the line-intersection method yesterday, and for the most part I thought it worked. At slow speeds it's fine, but when I sped up the ball the same sorts of problems I had before began to occur, and I don't understand why.

This works at "normal" speeds but I want the ability to drastically accelerate the ball without it becoming embedded in a wall. The only thing I can think of is that this procedure is done for each brick--meaning a brick on the other side of the one it SHOULD be colliding with is detecting a collision since the line is so big at these speeds and it is therefore being set in the middle of a cluster of blocks. This cannot explain all the bugs I am seeing, however. I though of a possible fix, but it made things WORSE if you can believe it.

At the beginning of the procedure I made a temporary variable that mirrored the ball structure passed to the collision function. I detected the collisions as normal, then defined a new variable, distclosest -- it is the distance from the ball's last position to the temporary ball's current position. The first time through, this is equivalent the distance from the ball's last to current position.

In addition to being less than the other distances of intersection for that block, the distance must also be less than the "closest", being the distance to the last position saved to tempBall. The vector of the modified ball is that of the original, with the appropriate axis reflected, and the new position is that of the detected collision. At the end, I return the value of tempBall instead of tBall, since that is the modified structure. I thought this would work, and while i did not notice so much "popping" as the other method, even at very slow speeds, a ball would "ignore" the walls of a brick until it was all the way through, sometimes even halfway through an entire cluster of bricks. There was also a problem with "sliding" up vertical columns of bricks. If anyone can point out a better solution or a way to improve mine, I would be very grateful.

EDIT: removed code, no longer relevant

[Edited by - Al Gorithm on July 24, 2006 8:58:53 AM]

Share this post


Link to post
Share on other sites
I really need some help with this. I spent a ridiculously long time debugging this game and the collision is the only major thing left other than the graphics before I can release a demo--except the trivialities such as a menu system, scoring,etc. I went through every line multiple times, fixing literally DOZENS of bugs I didn't even KNOW the thing had, but the collision is the only thing that still doesn't work right. I've tried everything I can think of and I can't figure it out. I'm sure it's something obvious, but I can't see it. It works 80-90% of the time but it seems like it "picks" random times to glide through a brick as if it is not registering hits.

You can see the phenomenon for yourself in action here. . . . the only things with collision enabled are the gray bricks and white blocks at this point, and I turned off the regular paddle movement for convenience, so don't judge this aspect of it please ;) You need to load the map file (.bng) in the zip file. The ball in the upper left panel passes through a white block in the row below it after not too long for me, most times I run the program. Sometimes it passes through a different block, sooner or later, but it is inevitable that it will pass through in a fairly terrible way. The ball is not changing speed or direction other than inverting the appropriate axis so it should move the same every time.

I double checked my formula here. I see no problem at all with my method . . .


-For each block/each brick pass the x,y,width,height,and ball being tested to the collision detection function
--I get the equation of the line formed by the ball's current and last position.
--Get the high and low x and y coordinates of this line
--Test each side of the block being tested
Get the point of intersection of the two lines
For a top/bottom test, make sure the x coordinate (since we already know y is between left and right. Make sure the y is between top and bottom for a left/right test. Make sure the intersection point is between the high and low x/y coordinates of the line formed by the ball.
If the point passes these tests, meaning the point of intersection is on both line segments, get the distance from the ball's last position to the point of intersection. If it is lower than the saved closest intersection distance, overwrite the saved distance and set the position of the temporary ball variable cBall to the intersect point. The vector of cBall is set to the original ball's vector with the appropriate component inverted.
cBall is returned to the parent function. cBall is set to be equal to tBall (the ball being tested) at the beginning of the function so if no collisions occur there will be no change. Is there anything wrong with this? If someone can point a flaw in this procedure out, I will personally mail them a cookie, perhaps even deliver it in person.


Here is the entire source file with the collision funtions, as an act of desparation:

ball doCollision(ball tBall){

cBall = tBall;
calcDistance(cBall, tBall);
fltSaveDist = distclosest;
blnAnyCollision = false;

for(int i = 0; i < 3000; i++){//for each brick
if(bricks.round == 4 || bricks.round == round){//if block is in correct round
cBall = objectCollision(tBall, bricks.x, bricks.y, bricks.width, bricks.height);
}
}

for(int i = 0; i < 3000; i++){//for each block
if(blocks.round == 4 || blocks.round == round){//if block is in correct round
cBall = objectCollision(tBall, blocks.x, blocks.y, blocks.width, blocks.height);
}
}

return cBall;

}



ball objectCollision(ball tBall, float px, float py, float pwidth, float pheight){

float highx, highy, lowx,lowy = 0;
float m;
float b;
float xlol;
float ylol;
//extern float rTime;
//bool leftc;
//bool rightc;
//bool topc;
//bool bottomc;

int TOP;
int BOTTOM;
int LEFT;
int RIGHT;

int topint[2];
int bottomint[2];
int leftint[2];
int rightint[2];


float distleft = 100000;
float distright = 100000;
float disttop = 100000;
float distbottom = 100000;



if ((float)tBall.x-(float)tBall.lx == 0) {
m = ((float)tBall.y-(float)tBall.ly)/((float)tBall.x-(float)tBall.lx+1);
} else {
m = ((float)tBall.y-(float)tBall.ly)/((float)tBall.x-(float)tBall.lx);
}

b = (float)tBall.y-((float)tBall.x*m);

if(tBall.lx >= tBall.x){highx = tBall.lx; lowx = tBall.x;}
if(tBall.lx < tBall.x){highx = tBall.x; lowx = tBall.lx;}
if(tBall.ly >= tBall.y){highy = tBall.ly; lowy = tBall.y;}
if(tBall.ly < tBall.y){highy = tBall.y; lowy = tBall.ly;}


TOP = py - pheight - tBall.radius;
BOTTOM = py + pheight + tBall.radius;
LEFT = px - pwidth - tBall.radius;
RIGHT = px + pwidth + tBall.radius;

//TOP
//////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////
xlol = ((float)TOP - b) / m;
topint[0] = xlol;
topint[1] = TOP;
disttop = sqrt( (((float)tBall.lx - (float)topint[0])*((float)tBall.lx - (float)topint[0]))
+(((float)tBall.ly - (float)topint[1])*((float)tBall.ly - (float)topint[1]))
);

if(xlol >= LEFT && xlol <= RIGHT){// if(LEFT<=xlol<=RIGHT){
if(lowx <= xlol <= highx){
if( lowy <= TOP <= highy){

if (disttop<fltSaveDist){
fltSaveDist = disttop;

cBall.xVec = tBall.xVec;
cBall.yVec = -tBall.yVec;
cBall.x = topint[0];
cBall.y = topint[1]-5;
}
}
}
}
///////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
xlol = ((float)BOTTOM - b)/m;
bottomint[0] = xlol;
bottomint[1] = BOTTOM;
distbottom = sqrt( (((float)tBall.lx - (float)bottomint[0])*((float)tBall.lx - (float)bottomint[0]))
+(((float)tBall.ly - (float)bottomint[1])*((float)tBall.ly - (float)bottomint[1]))
);
if(xlol >= LEFT && xlol <= RIGHT){// if(LEFT<=xlol<=RIGHT){
if(lowx <= xlol <= highx){
if(lowy <= BOTTOM <= highy){
if (distbottom<fltSaveDist){
fltSaveDist = distbottom;

cBall.xVec = tBall.xVec;
cBall.yVec = -tBall.yVec;
cBall.x = bottomint[0];
cBall.y = bottomint[1]+5;

}

}
}
}
////////////////////////////////////////////////////////
///////////////////////////////////////////////////////
ylol = (m*(float)RIGHT) + b;
rightint[0] = RIGHT;
rightint[1] = ylol;
distright = sqrt( (((float)tBall.lx - (float)rightint[0])*((float)tBall.lx - (float)rightint[0]))
+(((float)tBall.ly - (float)rightint[1])*((float)tBall.ly - (float)rightint[1]))
);
if(ylol >= TOP && ylol <= BOTTOM){//if(TOP<=ylol<=BOTTOM){
if(lowy <= ylol <= highy){
if( lowx <= RIGHT <= highx){
if (distright<fltSaveDist){
fltSaveDist = distright;

cBall.xVec = -tBall.xVec;
cBall.yVec = tBall.yVec;

cBall.x = rightint[0]+5;
cBall.y = rightint[1];
}

}
}
}
//////////////////////////////////////////////////////
/////////////////////////////////////////////////////
ylol = (m*(float)LEFT) + b;
leftint[0] = LEFT;
leftint[1] = ylol;
distleft = sqrt((((float)tBall.lx - (float)leftint[0])*((float)tBall.lx - (float)leftint[0]))
+(((float)tBall.ly - (float)leftint[1])*((float)tBall.ly -(float)leftint[1]))
);
if(ylol >= TOP && ylol <= BOTTOM){//if(TOP<=ylol<=BOTTOM){

if(lowy <= ylol <= highy){
if( lowx <= LEFT <= highx){
if (distleft<fltSaveDist){
fltSaveDist = distleft;

cBall.xVec = -tBall.xVec;
cBall.yVec = tBall.yVec;
cBall.x = leftint[0]-5;
cBall.y = leftint[1];
}
}
}
}
return cBall;
}


void calcDistance(ball cBall, ball tBall)
{
distclosest = sqrt((((float)tBall.lx-(float)cBall.x)*((float)tBall.lx-(float)cBall.x))+
(((float)tBall.ly - (float)cBall.y)*((float)tBall.ly - (float)cBall.y))
);
}





On a positive note, I fixed the sliding issue.

Share this post


Link to post
Share on other sites
Okay, what was throwing me is that before I rewrote the function, the ball was passing through any wall, any angle, any side with no consistencies. After, in the demo program it was only the 3 moving straight up, as in x vector is equal to zero. I thought adding one to the slope in my collision would be more or less equivalent, but I guess not. So I hard coded a limitation in my update code where the ball's x velocity cannot be between 0 and one.

if( (int)balls.xVec == 0){balls.xVec = 1;}

At this point I thought I was done, but no! I set the main ball speed from 10 to 100 to make sure everything was working properly, and when I loaded the game the main ball was vibrating in place. Testing different speeds I discovered that at the ball got faster the collision was more error prone. At 10 there were a few "twitch" errors where the ball seemed to stick to the surface of the block momentarily. At about 20 it was sliding up columns of bricks. At 50 or above it had a net movement of zero. Now this would be a cool powerup, but I'm not adding a powerup at the moment. . . I rewrote the collision so I could have speeds faster than twenty or thirty without significant bugs, and now if I were to cap the ball speed I would have to make it half that. It's a line intersection test, so the speed of the ball shouldn't make a difference in the collision. .. should it?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I did not read your code, or your long post in detail.
I will say though, that a line intersection should detect collisions regardless of speed, if properly implemented.
if the line intersects more that one block, you will of course need to figure out which one came First and collide with that one first... which may mean a bounce inbetween graphics updates, and may mean doing a second line interesection for the new after-collided path...
keep this in mind... that collisions need to be chained together...

You mentioned the ball seemed to 'vibrate' and stand in place vibrating or similar odd behaviour.
This sounds to me, like the ball is going SO Fast, that you don't even get the chance to see if moving. It moves, hits the wall, bounces back to where it was, so you only see it in one spot, slightly vibrating since it didn't bounce back to the exact same pixel location...
At least that's the most Likely reason, I didnt look at it myself but its a common problem...

You also mentioned that it seems to get stuck in blocks or stuck touching a block.
This could be the same as above, or it could indicate a problem with your collision responce (bounce) method.
A common problem is that, even though you properly detect collisions, and you reflect the ball velocity for a bounce, it may still be touching or slightly touching the block; so that a second bounce is detected and it flips direction again, cancelling everything out and appearing to stick to the block.
Make sure after a collision, that you move the ball Out of the block it touched, when you do the Line intersections, are you remembering to compensate for ball radius?

Share this post


Link to post
Share on other sites
checking the intersection of a line only is not good enough, the ball has 2 dimensions (assuming its a 2d game), so you need to check a rectangle, I'll try to illustrate

Say this is your ball at t1 and t2
t1 t2
0 --------> 0

You can't just check the line from t1 to t2

-------------

You have to check the rectangular area from t1 to t2 that your ball occupies
____________
|____________|

This must be done otherwise your ball will go through the edges or corners of bricks.

As far as resolving your collisions you can either use an iterative or direct approach. In an iterative approach you find the collision by stepping through smaller and smaller time intervals until it is found, this would be a brute force method and not very efficient, but any modern computer would handle it easily. A direct approach would be to find the intersection points of the lines, then compute the exact time of collision.

No matter which method you use, you have to reverse the animation and apply the collision results before updating further, I think this may be the step you are missing.

step animation from t1 to t2
if collision found find time of collision, we'll call this tc
reverse all animation from t2 back to tc
t1 = tc
goto step 1.

OR

If you know the maximum speed of your ball you can also ensure that your update time never exceeds your smallest collidable dimensions. For example say your ball has a diameter of 32, your smallest brick a dimension of 20x10, and its maximum velocity is 100. Your update should never be more than (10+32)/100 .42 seconds otherwise you could miss the collision of a ball going through the brick height-wise. Although this appears to work it would still miss collisions where the ball would only collide with the corner of a brick. Worst case scenerio is the ball is going maximum speed and only collides with the corner pixel of brick, to catch this your maximum update time could only be 1/100 = 10ms

Share this post


Link to post
Share on other sites
Well to start with just try something like if x1=x2 and y1=y2 then



But commercial games will usualy have a few hundred points per ball with a large senario for collisions. And C or C++ what ever you are using i forgot by time i wrote this is not the easiest language for high quality collisions.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by Rasterman
You can't just check the line from t1 to t2
You have to check the rectangular area from t1 to t2 that your ball occupies


Actually, you can do the ball as just a Line.
Like I probably said earlier...
Make all the blocks invisibly fatter by an amount = ball radius.

uhh, and Yes when you intersect that line with the blocks, you do want to solve it as a system of equations to solve the Time of collision and postion...
I dunno why this guy is talking about doing 'time stepping with smaller and smaller intervals' when you can just do a direct equation and solve it a lot cheaper and more accuratly...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!