Archived

This topic is now archived and is closed to further replies.

Perfect collision for breakout-style game

This topic is 5584 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''m working hard on my new breakout style game (2D), and I''m trying to get perfect collisions. There are two problems: 1) When a ball hits a block, it has to bounce depending on where it hit the block. I can check if the bounding box of the block and the ball collide, that''s simple, but then figuring out what directions need to change for the ball is a bit trickier. Bottom line is this: given a ball''s x/y velocities and a collission occurs, you have to determine if the x-velocity gets negated, or the y-vel (I prefer not to have corner hits where both get negated, let it determine it it one way or the other, maybe even randomly on perfect corner hits) This is a little harder than I thought it would be. I pretty much have it down but its not very perfect, and it has a big flaw explained next: 2) Now this problem is the RELA problem that I have no idea how to fix except with a LOT of long and slow code. Sometimes the ball can speed up, and sometimes the framerate may get choppy, either way sometimes the position change of a ball over one frame might be enough to jump it over and entire block, or a corner of a block. Either way, it causes a collision that was supposed to occur somewhere in between frames to be missed. I was thinking of throwing out rays and checking for collisions with every block, but then I''d have to figure out which way the ray has to bounce on the collision (like problem 1), and then keep following the ray for the vector magnitutde it has, and check for more collisions, cause maybe it was a REALLY big lag and in a flawless model the ball was supposed to hit one block and then another. Hopefully you get my point. Now bear in mind the board is a 20x15 grid and the balls can get trippled, so say there can be up to 50 balls at an extreme, don''t want to deal wtih al the raycasting math i think it would be too slow. Whew, im tired, hope that made sense and people reply - Rob ByteMe95::~ByteMe95() My S(h)ite

Share this post


Link to post
Share on other sites
Hehe
I remember having this problem - unfortunately (as I often do) I didnt finish the game

I never fully solved the problem actually, but one very bad way is to move the ball incrementally, and check each position.
eg. To move the ball 18 units, move it 5+5+5+3, each time checking the position.

This still doesnt completely solve the problem, but like I said I never actually finished anyway
(I think I got disapointed at myself for the crap work in it

I will be very interested to see other game developer''s ideas on this one - because ray casting is the only decent idea that comes to mind for me.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Assuming you have the perfect collision point at the surface of the bbox: if the bounce is detected when ball.y>box.miny && bally<box.maxy then you got a side hit (ball.x = -ball.x) otherwise you''re on the front or back of the tile (ball.y = -ball.y) of course your detection algorithm better deal at least with a line~box intersection if you intend to get the exact colission location.
Now it seems like you really need a raycasting if you deal with frame drop and stuff. But sure altought it may run realtime on moderns machines I believe there''s a more clever approach than the Brute Force one. If your tiles are fixed width and height you can consider your tile map as a ''screen'' (where tiles would stand as pixels) and then trace the line from old position to new position using an algorithm wich will ''hit'' all the ''pixels'' the line cross, I''m not sure if Bresenham can do that... you get the first tile hit using this technique then you refine using some stupid if () then () algorithm to find the exact collision point. That''s similar to the first step in raytracing an octree.

Share this post


Link to post
Share on other sites
anon: problem with that is that I dont always get the EXACT point of collision because of the jumpiness of the ball. Which leads us again to ray tracing. Of course the ball is 16x16 in pixels, so what ray do i trace? I figure i should trace the ray from the cetner of the ball and extend the box lines out by 8 pixels on each side when checking against them.
Your idea sounds interesting with treating the blocks as pixels, but once I find all the intersections, i gotta determine the exact point of contact again.
I thnk the ball should really be thought of as a 16x16 BLOCK, might be easier to envision

ByteMe95::~ByteMe95()
My S(h)ite

Share this post


Link to post
Share on other sites
As for the detection of a hit in between frames...

One quick way you could do this rather than moving incrementally one pixel at a time (yuck!) is create an axis-aligned bounding box of the vector of the ball''s movement from its last position to the next position, then comparing this AABB to the AABB''s of your blocks. AABB compares are very fast and should quickly reject most of the blocks. Then you could do your more careful collision checking. Honestly if all of your blocks are axis aligned boxes of some sort, you will probably be able to come up with some really quick collision detection for it.

I''m not sure if this was your question but I only had a minute while my program was linking.

Share this post


Link to post
Share on other sites
hmm, I have no idea how to make the ball''s vector axis aligned

I also have to check, as i said, 300 blocks (well i skip inactive/dead blocks) per ball, which i established as max 50. Will these axis aligned collisions run fine wtih all that?
Also, Once i do find a collision using that, I have to compensate for it, if you lok at problem 2 what is the ball is supposed to bounce of a collision and then is suupposed to collide with another block? Another round of collision detecting tests.

ByteMe95::~ByteMe95()
My S(h)ite

Share this post


Link to post
Share on other sites
Get starting and ending position of your ball.
Just get all the blocks inside this box, that should be pretty straightforward and if the game is fast enough, you will end up with only 1 to 9 blocks.

On those blocks, you can already skip all empty spots and you end up calculating two line-line collision per filled block depending on the ball's direction. Usually this will be 2 to 6 line-line collision per ball per frame and these aren't slow at all.

EDIT : Corrected a logic error


[edited by - Coincoin on August 29, 2002 6:07:36 PM]

Share this post


Link to post
Share on other sites
Just saw your last post.

Well yes doing it in several pass is your best bet. Each pass should go straight. If it rebounds, you use the collision pos as a new starting pos for another collision pass. However, those cases are going to be very rare, especially if your game is fast, so it won''t significantly slow down the game.

Share this post


Link to post
Share on other sites
Isn't that basically the same way a billiards game would be handled? Parse for the first collision, move up to that point, affect all velocities in the earliest collision, then do another parse using the new velocities, and repeat, until the time elasped since the last frame is used up?

I can't think of any other way to do that. So coding for a perfect collision might set you up well for additional collision challenges in the future.

[edited by - Waverider on August 29, 2002 6:31:32 PM]

Share this post


Link to post
Share on other sites
coincoin: sounds interseting, I may try that.
A few questions: How would i know which blocks to check based on the balls starting and ending positions? I can see how I could get the cell of the starting and ending pos, say they come out to be 4,4 and 5,3 (ball going up and right), but then which blocks do i check? it wont always be a perfect 9 block squasre from the beginning to ending pos.

Also, from what I can understand and the way i do it now (for another part of the game, i also do line intersect tests between the ball and the blocks), for each block there are 4 intersect tests per ball since I have to check every wall of every block (4) to get the proper intersection, why did u say it would take 2 line-line collision tests per block?

thanks for all the help guys

ByteMe95::~ByteMe95()
My S(h)ite

Share this post


Link to post
Share on other sites
If you know the starting block (3,5) and ending block (5,6) just take all blocks in the X range 3..5 and Y range 5..6, that is, 6 blocks. Most of the time (unless the game is really slow, your ball will be in 1 2 or 4 blocks).

As for the line collision, you only have to check for two lines since its impossible to collide an edge from behind. See what I mean?

If the ball is coming from top right, it''s impossible to collide with bottom or left sides. Even more, if your vertical displacement is smaller than one block, you don''t have to test for top and bottom edges. Same for horizontal displacement and left-right edges. If the total ball movement is constrained in only ONE block, you don''t have to test at all!

Never forget to take the ball size into account.

Share this post


Link to post
Share on other sites
(Long post - the bottom paragraph may be all you care about)

No good replies yet (sorry everyone who posted before me - you''re all stupid!!!, jk)

Anyways. First, inorder for what I''m about to say you need to have your blocks mapped on the level such that every block is the same number of pixels high and wide. Basically this will allow you to find what block a pixel is in using a simple divide.

i.e. running and 800 by 600 every block is 40px wide(20 blocks across) and 15px high(# of blocks up and down depend on how much of the screen you decide to use) starting at 0,0. That means a pixel at 201, 48 would be the 5th block on the X axis and the 3rd block down.

Also, the blocks should be stored in a 2 dimensional array (or if 1d, have a macro to access blocks based on 2 dimensions). After you have this, its quite simple.

The ball has TWO leading edges, an X and Y. If the ball is going to the top right of the screen the two leading edged are the top and right. Check the top middle pixel of the ball bitmap, and the right middle pixel of the ball bitmap for collisions. It should be as simple as getting the coordinate, dividing it to find what block its in. THEN use the modulus operator to find out wether to the coordinate is closer to the top or bottom of the block, or left or right.

In psuedo algorithm here is what you do:

-Get leading X coordinate based ball''s velocity.
-Divide to find out what block row and col the block is in.
-If there is a block there, negate the X velocity of the ball.
-Repeat steps with Y axis collision.

Share this post


Link to post
Share on other sites
Ebony:
your suggestion is very itneresting as well, and I do have everything set up as you said (800x600, each block is 32x16 I believe).
Your solution is definately doable, BUT you completely neglected the second part of my problem.

Coin: Now I see what you''re saying, good call.
I have yet to decide waht t go with that wont be a CPU hogf or many balls, though coin your solution does sound most efficient

ByteMe95::~ByteMe95()
My S(h)ite

Share this post


Link to post
Share on other sites
You are making the problem more complicated that you have to. You already have a ray cast for you between frames. The ray is the velocity of the ball. Plus you already know the positions of the blocks. If the blocks are static, it is simple. If the blocks are moving, then it is complicated.

If your ball is 5 pixels by 5 pixels, and its current position is 200,200(on center). If the ball is moving at xv=5 and yv=-25 then you could possibly jump a block. If you have a block at 170,180(top left corner) then the ball could jump this block. The bottom right corner of this block is 202,196. Now you do a bounding box type of check. The four corners of the ball are:

198,198 ball_corner[1]
202,198 ball_corner[2]
202,202 ball_corner[3]
198,202 ball_corner[4]

The four corners of the block are:

170,180 block_corner[1]
202,180 block_corner[2]
202,196 block_corner[3]
170,196 block_corner[4]

Now you check the blocks corners against the starting and ending corners of the ball to see if there is a collision. If a velocity is positive, then the ball start corner should be greater than the blocks and the ending corner should be less:

  
for(int i=1;i<=4;i++) {
for(int j=1;j<=4;j++) {
if(xv>0) {
if(ball_corner[j].x < block_corner[i].x && ball_corner[j].x+xv > block_corner[i].x) {
if(yv>0) {
if(ball_corner[j].y < block_corner[i].y && ball_corner[j].y+yv > block_corner[i].y) {
return true;
}
}
else if(yv<0) {
if(ball_corner[j].y > block_corner[i].y && ball_corner[j].y+yv < block_corner[i].y) {
return true;
}
}
}
}
else if(xv<0) {
if(ball_corner[j].x > block_corner[i].x && ball_corner[j].x+xv < block_corner[i].x) {
if(yv>0) {
if(ball_corner[j].y < block_corner[i].y && ball_corner[j].y+yv > block_corner[i].y) {
return true;
}
}
else if(yv<0) {
if(ball_corner[j].y > block_corner[i].y && ball_corner[j].y+yv < block_corner[i].y) {
return true;
}
}
}
}
}
}
return false;


Worst case, this could be slow. But you get the point and you could optimize it from here.

This is set up as a function call to make it easy to exit the loop. You might even be able to make the compiler inline it.

---
Make it work.
Make it fast.

"I’m happy to share what I can, because I’m in it for the love of programming. The Ferraris are just gravy, honest!" --John Carmack: Forward to Graphics Programming Black Book

Share this post


Link to post
Share on other sites
captain that is very basic bounding box collision detection which I already have implemented.

You didnt address my real problem which is which way to make the ball bounce (which is becoming less and less of an issue) and more importantly problem #2

coin: if i do raycasting adn follow the ray through X possible colisions until i reach the magnitutde of the velocity vector of the ball (say in a perfect world, but slow running game, it was supposed to collide with 3 blocks in one frame), I actually have to move the position of the ball in addition to it''s x/y velocities correct? As of right now i never touch the ball''s coordinates frmo the collision detection, it just adjusts the balls velocities based on a collision, but that has the problems I started this thread with of course.

ByteMe95::~ByteMe95()
My S(h)ite

Share this post


Link to post
Share on other sites