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