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

### Show differencesHistory of post edits

### #1PyroDragn

Posted 09 October 2012 - 04:48 PM

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

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