[SFML] Special Collision Detection

Started by
17 comments, last by superman3275 11 years, 7 months ago
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. laugh.png
GameDev Journal: http://www.gamedev.n...-rooks-journal/

OpenChess - 1.0 done!

Classic RPG #1 - Task 9 -> January 1st 2013
Advertisement
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.
f@dzhttp://festini.device-zero.de
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.
GameDev Journal: http://www.gamedev.n...-rooks-journal/

OpenChess - 1.0 done!

Classic RPG #1 - Task 9 -> January 1st 2013
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).

collision.png

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 :)

I'm a game programmer and computer science ninja !

Here's my 2D RPG-Ish Platformer Programmed in Python + Pygame, with a Custom Level Editor and Rendering System!

Here's my Custom IDE / Debugger Programmed in Pure Python and Designed from the Ground Up for Programming Education!

Want to ask about Python, Flask, wxPython, Pygame, C++, HTML5, CSS3, Javascript, jQuery, C++, Vimscript, SFML 1.6 / 2.0, or anything else? Recruiting for a game development team and need a passionate programmer? Just want to talk about programming? Email me here:

hobohm.business@gmail.com

or Personal-Message me on here !

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.

I'm a game programmer and computer science ninja !

Here's my 2D RPG-Ish Platformer Programmed in Python + Pygame, with a Custom Level Editor and Rendering System!

Here's my Custom IDE / Debugger Programmed in Pure Python and Designed from the Ground Up for Programming Education!

Want to ask about Python, Flask, wxPython, Pygame, C++, HTML5, CSS3, Javascript, jQuery, C++, Vimscript, SFML 1.6 / 2.0, or anything else? Recruiting for a game development team and need a passionate programmer? Just want to talk about programming? Email me here:

hobohm.business@gmail.com

or Personal-Message me on here !


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!

I'm a game programmer and computer science ninja !

Here's my 2D RPG-Ish Platformer Programmed in Python + Pygame, with a Custom Level Editor and Rendering System!

Here's my Custom IDE / Debugger Programmed in Pure Python and Designed from the Ground Up for Programming Education!

Want to ask about Python, Flask, wxPython, Pygame, C++, HTML5, CSS3, Javascript, jQuery, C++, Vimscript, SFML 1.6 / 2.0, or anything else? Recruiting for a game development team and need a passionate programmer? Just want to talk about programming? Email me here:

hobohm.business@gmail.com

or Personal-Message me on here !

This topic is closed to new replies.

Advertisement