[SFML] Special Collision Detection

Sounds like a good time to read up on _collision_ detection, which is a lot more interesting than _intersection_ detection. Just moving the ball and checking for intersection with a rectangle is going to fail anyway if your ball is moving too fast.

It also depends on whether you want to treat your ball as a point (for simplicity) or an actual sphere (requiring special handling for the corners) or if you don't need perfectly precise collisions anyway.

Of course, it could also be a good time to grab some simple 2D physics engine, if you just want it working without diving into the math behind it.

There are a few ways to do collision detection.

Grids, bounding box, pixel perfect, ect...

For something like this, I would learn bounding box collision if you're new to how collision works.

Your main objective here is to get the x and y values for each object, and their current height and width to create a top, bottom, left, and right. Now, you will be checking if one box (or several) collide with another box, which means collision has been detected. I will show you a basic example.

Paddle:

Paddle_BB_Top = Paddle_Y
Paddle_BB_Left = Paddle_X
Paddle_BB_Right = Paddle_Width + Paddle_BB_Left
Paddle_BB_Bottom = Paddle_Height + Paddle_BB_Top

Ball:

Ball_BB_Top = Ball_Y
Ball_BB_Left = Ball_X
Ball_BB_Right = Ball_Width + Ball_BB_Left
Ball_BB_Bottom = Ball_Height + Ball_BB_Top

Now to detect if collision is true, you would simply have basic check seeing if anything collides.

if (Paddle_BB_Bottom > Ball_BB_Top &&
Paddle_BB_Top < Ball_BB_Bottom &&
Paddle_BB_Right > Ball_BB_Left &&
Paddle_BB_Left < Ball_BB_Right)
{
Collision = true;
}

I hope this helps, feel free to ask any additional questions.

Edit: The most important thing to never forget!!! You must update these values for each frame, or your bounding boxes will have incorrect values. So make a function to update the values before checking for collision.

There are a few ways to do collision detection.

Grids, bounding box, pixel perfect, ect...

For something like this, I would learn bounding box collision if you're new to how collision works.

Your main objective here is to get the x and y values for each object, and their current height and width to create a top, bottom, left, and right. Now, you will be checking if one box (or several) collide with another box, which means collision has been detected. I will show you a basic example.

Paddle:

Paddle_BB_Top = Paddle_Y
Paddle_BB_Left = Paddle_X
Paddle_BB_Right = Paddle_Width + Paddle_BB_Left
Paddle_BB_Bottom = Paddle_Height + Paddle_BB_Top

Ball:

Ball_BB_Top = Ball_Y
Ball_BB_Left = Ball_X
Ball_BB_Right = Ball_Width + Ball_BB_Left
Ball_BB_Bottom = Ball_Height + Ball_BB_Top

Now to detect if collision is true, you would simply have basic check seeing if anything collides.

if (Paddle_BB_Bottom > Ball_BB_Top &&
Paddle_BB_Top < Ball_BB_Bottom &&
Paddle_BB_Right > Ball_BB_Left &&
Paddle_BB_Left < Ball_BB_Right)
{
Collision = true;
}

I hope this helps, feel free to ask any additional questions.

Edit: The most important thing to never forget!!! You must update these values for each frame, or your bounding boxes will have incorrect values. So make a function to update the values before checking for collision.

This is going to be exactly the same as doing a pure intersect check, and unless it is done as a per-pixel update it isn't going to solve the problem. An intersect check, as outlined by the OP, or as done by you, checks if one object has hit another (as Trienco said, either of these is going to fail if the ball is moving too fast).

The problem that the OP is having is determining where the ball has hit an object. By using an intersect I can tell that the ball has hit a block. I can't tell that it hit the left and should reflect left, or hit the top and should reflect up.

Even just considering the previous position of the ball before the intersect doesn't work perfectly, in particular when striking near the corner of the object.



In order to get this to work perfectly you have to consider the previous position, calculate the path of the ball up until the point of collision, and then determine which side of the block the ball hit. If you can give details on how you're storing and updating your positions then I might be able to help with a bit more detail.

Maybe I'm reading the question wrong... But I would just create four collision lines, one for top, bottom, left, and right for each block. Then if the ball hits a block's left collision line, it will act in the way you want it to, the same for the block's right collision line..

Edit: Just to explain how you would do this encase you ask. You would make four "collision boxes", one for left, right, top, bottom in your block class. This is very easy to setup based on your blocks X and Y values. Then you would just make a line pretty much that outlines the block for collision checking. You can even have the ball hit the corner of the block - meaning it hit the left and bottom lines then move the in proper direction.

Maybe I'm reading the question wrong... But I would just create four collision lines, one for top, bottom, left, and right for each block. Then if the ball hits a block's left collision line, it will act in the way you want it to, the same for the block's right collision line..

This may work, but it would depend on a few things: How they want to handle corners, how often the ball's position is refreshed, how they would handle it if the ball intersected two collision objects (if the ball hit near the corner and intersected both left and top).

Answered the corner part in my edit.

"Edit: Just to explain how you would do this encase you ask. You would make four "collision boxes", one for left, right, top, bottom in your block class. This is very easy to setup based on your blocks X and Y values. Then you would just make a line pretty much that outlines the block for collision checking. You can even have the ball hit the corner of the block - meaning it hit the left and bottom lines then move the in proper direction."

He should be refreshing the balls position each frame which makes it impossible to miss a collision check. I've used this method before and it does work.

He should be refreshing the balls position each frame which makes it impossible to miss a collision check.

This isn't true. In a lot of 2D games it is probably 'Good Enough.' But unless you can guarantee a limited speed there is a chance of missing a collision detection. Even with a limited speed there's still a chance of missing collision in certain circumstances.

If we assume a game of pong running at 60FPS. The paddles are 20 pixels wide. The ball is 30 x 30 pixels. The ball takes two seconds to cross between the paddles (moving purely horizontally). There's 1000 pixels between the two paddles.

Each update the ball moves 17(ish) pixels. At this rate, it's never going to pass straight through a paddle.

If the ball is moving faster. One second between paddles, it'll move at 34 pixels per redraw. 1/2 a second and the ball moves 68 pixels, skipping straight through the paddle becomes quite likely.

If we take the smaller speed. Moving 17 pixels per redraw, but also include now a vertical motion too at the same speed, 17 pixels per redraw, there's still a chance at missing a collision detection:



The image above is drawn to scale. The two black boxes are the before and after position of the ball (moving either diagonally up left, or down right, doesn't matter), the blue box is a paddle. Now, clearly between these two positions it should collide with the top, or right of the paddle (depending on direction of movement), but based on intersect checking it won't.

Moving on to the problem of determining which side the ball hit:

"Edit: Just to explain how you would do this encase you ask. You would make four "collision boxes", one for left, right, top, bottom in your block class. This is very easy to setup based on your blocks X and Y values. Then you would just make a line pretty much that outlines the block for collision checking. You can even have the ball hit the corner of the block - meaning it hit the left and bottom lines then move the in proper direction."

Assuming:
If the ball hits the right or left, you want it to bounce back right or left, so you reverse the X motion.
If the ball hits the top or bottom, you want it to bounce back up or down, so you reverse the Y motion.
If the ball hits a corner, you want it to bounce back diagonally, so you reverse both the X and Y motion.

This is going to be another case whereby having intersect checking in the way you described may be 'Good Enough' but isn't going to be perfect.



Considering the above image. This ball is moving upwards and left, and on the update it hits the paddle. According to intersect checking with different bounding boxes per side, this is a perfect corner hit (it hit both the top and right sides) and so it reverses direction in both X & Y, and moves back down and right.

If you did a per-pixel check on the motion of the ball, then the ball actually hits the right side of the paddle and continues to bounce up and right.

You could define each action based on each corner individually, ie, "if the ball hits the top right corner make the ball travel up and right" "if the ball hits the top left corner make the ball travel up and left" to minimise this. Although this is rather cumbersome way of doing it. There is also still the problem of missing the paddle, or of hitting an incorrect side (ie, if the update is partially inside the paddle but hitting the bounding box for a different side then the direction of travel)

The way to get it to behave perfectly is either to redraw upon every pixel of movement (an obscenely intensive thing to do in most circumstances), or using vector math to determine if the path of the ball passed through an object, calculate point of impact, and react accordingly.

Now, I do agree that having bounding boxes for different sides can be good enough. It depends on the game, how often you're redrawing, how fast the ball will move. It'll depend on how the OP wants to handle it, but if he does want perfect behaviour I don't think this would be the way to do it.

Considering that this is for a breakout style game, even though the path based collision may seem more complicated, it would be simpler in the long run I think because it also reduces the need for consideration of how to react to multiple collisions. If you use intersect checking against two blocks together, then there's a high likelihood that the ball is going to intersect with (for example) the bottom left corner of one block, and the bottom right corner of another, or even intersecting with 3 (or more) blocks.

If you calculate the path and react according to point of impact, if it hits two blocks then you still know that it has hit the bottom of two blocks together, or the right, etc, and can react accordingly.

I do see your point indeed. However this is not exactly a beginner topic.

In some of my projects I do what's called back tracking for a collision check. Even though I preform standard collision checks, I also check to see if any possible collision could have happened during that given movement. I've rarely seen this discussed or explained to new game developers, but it's indeed a great thing to learn.

This would only be required if movement per frame of an object has the possibility of jumping over an object. Example a unit moves 4 pixels per frame and you intend on moving up, yet there is a bush 2x2 pixels ahead of you. You would simply jump over the object if you landed 2 pixels below and then proceeded to move up.

superman3275 could program a check which will "ghost" move the ball, check from the point of movement to where it had landed per move in the logic, then if the ball would have jumped the first block, or a left/right side, or corner, then backtrack the ball to that location of contact, other wise continue. Which is pretty much as you stated.

I can see how this will turn into a lengthy process. I hope you're able to work out a good solution.

I normally just use some basic guards so that objects don't go past each other, but that's not my question. The only thing I could think of doing is setting up four boxes, one for every side (I made pong, I know what bounding box collision is). I'm going to try to look into some more Collision Detection ideas. Also, from what I understand, all you have to do to make sure your ball doesn't go past your paddle is use a few variables and run a check every game loop, if I'm correct?

It depends on the pixel jump of each movement. You will never have to worry about the above issue unless a moveable object can move more pixels than a given width or height of another object (depending on direction), or in your case a collision check. For example, if your sprite only moves 5 pixels in any direction per frame, unless you have an object that is less than 5 pixels in size on your collision spot, you will not have to worry.

If you're looking for a perfect check, you need to program a collision check which will take the starting position, and the end position for each frame of movement of your ball to determine if collision was possible from the two points.

Unless you're willing to program a class to handle this check (which allows you to use it any project), you should look into the many physics engines out there. I personally enjoy trying to re-invent the wheel.

Black-Rook, look at his posts again. He already gave an example and explanation why this is wrong. Blocks have corners and balls aren't limited to moving purely vertical or horizontal. The width and height of a block is irrelevant, because you can always just slightly brush a corner, even moving just a single pixel (diagonally) can be too much.

  [font=courier new,courier,monospace][color=#FF8C00][]
[color=#FF0000][][][][]
  []
  [][/font]

Red is the "corner pixel" of the balls rectangle before, orange is the same pixel after. It should be obvious that during that movement, this pixel would intersect the corner of the box. No matter how many "snapshots" or "sub steps" you make, no matter how small your movement, you can _always_ miss collision if you only check for static intersections. The term "corner case" very much applies.

The simple point is this: collisions are dynamic and involve motion. If your collision detection ignores the objects motion, you're not doing collision detection. Sometimes you won't care, but usually you should.


Since break out is using neatly axis aligned boxes and is in 2D, I would highly recommend using this as a chance to learn how to "do it right", rather than waiting with it until you need to do arbitrary geometry in 3D, where some basic concepts might be the same, but their implementation will become a lot more complicated by having to handle the "generic case". "Right" in this case can either mean diving into the lovely world of collision physics (at least a simple sub set, to get the hang of it) or picking a good physics engine and just not worry about the mathy details.


The typical approach is to determine the time of (potential) intersection (t) for each potential edge, then sort by t and determine if they do in fact intersect.

This is were it becomes important to not randomly talk about "lines" when you mean "line segment". Lines are of infinite length and you typically check against a block edge's "line" first, then see if the intersection with that line is actually on the "line segment" (this is why you might want to consider treating the ball as a point, rather than a sphere, as it's making things a "lot" simpler, especially where hitting corners is involved).

To determine if the ball has any chance of hitting one edge, if it was on one side before and on the other after, you need to see if the point of intersection is on the actual edge of the box. If it was intersecting before, you probably have a bug (or are discovering why floats should never be compared with ==), if it is intersection after, treat it like being on the other side.

There are lots of things that make it easier. For example, knowing the balls velocity has positive x, you never need to check against a blocks right side. Knowing the box is convex, you never need to worry about hitting an edge at a right angle (as it is then covered by another edge), etc.

If he want's perfect collision then use pixel perfect for the ball when ghost checking 1 pixel movement at a time in that path per frame, problem solved.

I'm simply providing a simple and basic way to handle a ball hitting four sides. If he needs something more there are several physics engines out there to use.

Edit: I forgot to note down, due to the ball being able to curve, ect... You would need a formula to determine the correct path before checking against it.

I did a write up for a (ahem) quick check using bounding boxes for the Blocks and for the Ball. The same formula can also be used for a ball defined as a point, although checking for intersections for a point can be easier. Unfortunately I didn't get a chance to post it last night and I've left the text on my home computer. It'll have to wait a few hours until I get home from work.

It's not perfect, and it's not coded, just parts of it in pseudo-code. I'm only just learning C++ and I haven't had a chance to sit down and try translating it into a useable function. I also don't know enough about your game to try and translate it into code for you to apply directly.

The only thing I could think of doing is setting up four boxes, one for every side (I made pong, I know what bounding box collision is).

This purely depends on how accurate you want your collision detection to be, and how intensive. This can work, and it may be good enough for what you want it to do, but I can't decide that for you. There are flaws with doing it this way, I've noted these in more detail in my post above but I'll outline them here:

• If you only check the final ball position during any movement, then you are going to (potentially) miss collisions that should have occured. Especially if the ball is moving at speed.
  
• Need to define how corners hits are detected, and handled.
  
• Hitting an incorrect bounding box is a possibility. If the ball just misses the block on one tick, then on the next tick moves to a position inside the block, it could hit an invalid bounding box; ie, approaching from the bottom, skipping into the box and 'hitting' the box for the top of the block.
  
  
  

  
  Also, from what I understand, all you have to do to make sure your ball doesn't go past your paddle is use a few variables and run a check every game loop, if I'm correct?
  

  
  
  Doing paddles is relatively easy, because generally speaking you don't really care about directional collision detection. If the ball goes past the paddle, you lose a point, if the ball hits the paddle bounce it up (I'm assuming typical layout for Breakout).
  
  Therefore doing a simple intersect check here is good enough mostly, with an out of bounds check.
  
  This only becomes more of an issue if you actually want the ball to detect which side of the paddle it hit (ie, it hits the side of the paddle and continues to bounce down and lose a point, or there's a possibility of the ball hitting the bottom of the paddle), at which point you get the same problem as directional collision detection on your boxes.

As promised in my previous post, these are my musings on the subject:


I think I've come up with a reasonable solution, that would work to determine collisions for a ball moving at any speed without skipping through any objects.
This does rely on bounding box checks, so if you want to use something more accurate then this isn't going to be it. As FloatRects were mentioned I'm working on the assumption that using bounding boxes for collision checking is going to be good enough.
I haven't written the code because I don't know enough C++ to do so, hopefully my description is easy enough to follow. Some of the later math and theory is perhaps a bit abstract and I hope it's not too complicated (and I hope I didn't get my theory mixed up somewhere).



I use the above illustration as an example for various points. The ball starts at the position in the lower right, and travels to the top left.
Noteable Variables are:
Ball Height = 10
Ball Width = 10
Ball starting X = 100
Ball starting Y = 200
Ball finish X = 50
Ball finish Y = 100

Block Height = 10
Block Width = 20
Red Block X = 60
Red Block Y = 120
Blue Block X = 80
Blue Block Y = 130
Draw a bounding box around the extremes of the movement. Check if this box intersects with any other boxes. This is a very rough check to see if there's any chance of collision. There's no need to do a pixel perfect check if there's no blocks nearby.
If there are boxes, take note of their variables.
Red Box: Top = Y = 120, Left = X = 60, Bottom = Y + Height = 130, Right = X + Width = 80
Blue Box: Top = Y = 130, Left = X = 80, Bottom = Y + Height = 140, Right = X + Width = 100

Find the distance the ball moved horizontally and vertically:
Sqroot((BallBefore.X - BallAfter.X)^2) = Moved.X
sqroot((BallBefore.Y - BallAfter.Y)^2) = Moved.Y

From our example:

100 - 50 = 50
50^2 = 2500
Sqroot(2500) = 50

200 - 100 = 100
100^2 = 10000
Sqroot(10000) = 100

Therefore:
Moved.X = 50
Moved.Y = 100

The reason for Squaring, and then Square Rooting the variable is so that you end up with a positive result at the end. We want to find the distance moved horizontally, it doesn't matter if it's left to right or right to left.
Now determine which of these is larger:

if Moved.X > Moved.Y Then
HorizontalMovement = True
Else
HorizontalMovement = False
End if

If Both variables happen to be the same size it doesn't matter which variable we use for comparison later, so a simple if/else is fine so that one or the other gets priority.

From our example:
Moved.Y > Moved.X so HorizontalMovement = False (the ball is travelling more vertically than it is horizontally)

Now comes some of the more awkward parts:

Take the difference between the movement in the non-primary direction of travel, and divide it by the distance moved in the primary direction of travel.

if HorizontalMovement = False then
MoveRatio = (BallBefore.X - BallAfter.X) / Moved.Y
Else
MoveRatio = (BallBefore.Y - BallAfter.Y) / Moved.X
End If

This gives you the ratio for the smaller increment of travel. For each pixel moved in the primary direction (in our case, vertically) you move this amount horizontally (in our case -0.5)

Now find the actual direction of travel in the primary movement.

If HorizontalMovement = False then
if BallBefore.Y > BallAfter.Y then
Direction = MovingUp
BlockImpact = Bottom
BallImpact = Top
Else
Direction = MovingDown
BlockImpact = Top
BallImpact = Bottom
End If
Else
if BallBefore.X > BallAfter.X then
Direction = MovingLeft
BlockImpact = Right
BallImpact = Left
Else
Direction = MovingRight
BlockImpact = Left
BallImpact = Right
End If
End If

Now according to the direction of travel we want to sort the blocks in the list.

In our Case the ball is moving upwards, and so we want to start with the bottom most block and sort through the blocks going upwards as we check for collisions. This is the actual collision check you will want to repeat for each block in the list:

Now for each block in the list we want to loop through in order and check for collisions:

Find the difference between the starting BallImpact position and the BlockImpact position. In our example this means the difference between the top of the ball, and the bottom of the block.

DistanceMoved = Sqroot((Ball.Impact - Block.Impact)^2)

According to our example, for the first block (the blue block),

Ball.Impact = Top of the Ball start position = BallBefore.Y = 200
Block.Impact = Bottom of the Blue Block = 130 + Height = 140
200 - 140 = 60
sqroot(60^2) = 60

DistanceMoved = 60

Multiply this by the MoveRatio
RatioMoved = DistanceMoved x MoveRatio
DistanceMoved = 60
MoveRatio = -0.5

RatioMoved = -30

Now we use the ratio moved along with the primary direction of movement to see if a collision is true
If HorizontalMovement = False then
if (Ball.X + RatioMoved < Block.X + Block.Width) and (Ball.X + Ball.Width + RatioMoved > Block.X) Then
Collision = True
Collision.X = Ball.X + RatioMoved
Collision.Y = Block.Impact
Else
Collision = False
End if
Else
if (Ball.Y + RatioMoved < Block.Y + Block.Height) and (Ball.Y + Ball.Height + RatioMoved > Block.Y) then
Collision = True
Collision.X = Block.Impact
Collision.Y = Ball.Y + RatioMoved
Else
Collision = False
End If
End If

From our example HorizontalMovement = False

Ball.X + RatioMoved = 100 + -30 = 70
Block.X + Block.Width = 80 + 20 = 100
70 < 100 = True

Ball.X + Ball.Width + RatioMoved = 100 + 10 + -30 = 80
Block.X = 80
80 > 80 = False

Therefore, Collision = False

If Collision is false then you want to loop and check the next block in the list.

If Collision is true, then Collision.X and Collision.Y will give you the position the ball would be at, at the point of collision. What you do from there is up to you. The easiest (though technically inaccurate again) is to redraw the ball at the point of collision, and react accordingly.



Looping through the example for the Red Block:

DistanceMoved = Sqroot((Ball.Impact - Block.Impact)^2)
Ball.Impact = Top of the Ball start position = BallBefore.Y = 200
Block.Impact = Bottom of the Red Block = 120 + Height = 130
200 - 130 = 70
sqroot(60^2) = 70

DistanceMoved = 70

RatioMoved = DistanceMoved x MoveRatio
DistanceMoved = 70
MoveRatio = -0.5

RatioMoved = -35

If HorizontalMovement = False then
if (Ball.X + RatioMoved < Block.X + Block.Width) and (Ball.X + Ball.Width + RatioMoved > Block.X) Then
Collision = True
Collision.X = Ball.X + RatioMoved
Collision.Y = Block.Impact
Else
Collision = False
End if
Else
if (Ball.Y + RatioMoved < Block.Y + Block.Height) and (Ball.Y + Ball.Height + RatioMoved > Block.Y) then
Collision = True
Collision.X = Block.Impact
Collision.Y = Ball.Y + RatioMoved
Else
Collision = False
End If
End If

From our example HorizontalMovement = False

Ball.X + RatioMoved = 100 + -35 = 65
Block.X + Block.Width = 60 + 20 = 80
65 < 80 = True

Ball.X + Ball.Width + RatioMoved = 100 + 10 + -35 = 75
Block.X = 60
75 > 60 = True

Therefore, Collision = True

Collision.X = Ball.X + RatioMoved = 100 + -35 = 65
Collision.Y = Block.Impact = Bottom of Red Block = Block.Y + Block.Height = 130

The Ball collides with the Red Block when the ball is at position: 65, 130

^^^^^^ Insanely long post above me.
But, how I do it is this: I check for collision detection, move the ball, and check again. But, I also have a boolean guard that sets variables depending on if its before or after the movement. It's simple mathematics to have the class check the variables every game loop and figure out if it skipped collision. Then I just move the ball back and hope it wasn't noticed

Sorry, ^ That's kind of what you said, just simpler. Essentially I have 4 collision variables(ballx/bally at the beginning of the game loop, ballx/bally at the end) I update before and after I move the ball and check to see if collision was skipped every game loop. If collision was skipped, I move the ball back to where it should be using some basic linear algebra.

Sorry, ^ That's kind of what you said, just simpler. Essentially I have 4 collision variables(ballx/bally at the beginning of the game loop, ballx/bally at the end) I update before and after I move the ball and check to see if collision was skipped every game loop. If collision was skipped, I move the ball back to where it should be using some basic linear algebra.

Essentially that should work, yeah, basically the loop should look something like:

Take Ball Start Point.
Calculate Ball End Point
Check for Collision Along Path
If No collision, draw ball at end point
If there is a collision, calculate effect of collision.

Now, what you do when a collision occurs is going to depend on how accurate you want the ball's behaviour to be. If you redraw at the point of collision then work from there with the next loop, that's technically going to be decelerating the ball. Normally speaking this is going to be for a bare fraction of a second, but it may be something you want to consider.

If you imagine the ball is moving 100 pixels per frame. You calculate the path, then determine that it hits an object 40 pixels in front of it. If you redraw the ball at the point of impact, then the ball has only traveled 40 pixels in that frame (40% speed). It should have hit the object, adjusted its vector, and traveled another 60 pixels, which is where you should draw the ball - ie, at its new end point, not at the point of collision.

^ Exactly! When I said I move the ball to where it should be using linear algebra that's what I meant, thanks for putting that into words!