Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualPyroDragn

Posted 09 October 2012 - 04:55 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).

Posted Image

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

#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

PARTNERS