I'm working on an Arkanoid/Breakout clone and in creating collision detection I've come up against the hurdle of tunnelling due to the fast moving ball.

I've heard of numerous solutions for doing so but I've currently implemented the idea of having a line go out from the ball in the direction it's moving at the correct magnitude to see if there should be some collisions happen along the path of the next move cycle.
However this doesn't solve the problem of the predictive line itself tunnelling into the bounding box of the blocks and thus making the block think it's been hit multiple times (so destroying the block instantly even if it had many hit-points) and also firing the ball's bounce method more than once so if I continue with this predictive collision detection solution I need something to make the block's hit-point decrease method and the bounce method to fire only once even if the bounding boxes overlap for more than one update cycle.

My problem is I can't figure out how to do this? Or if this simply isn't the most ideal collision detection method for this particular kind of game?

I found this article which sounds like the ideal solution but the solution provided seems especially complex and I feel I shouldn't need anything this in depth and I'm unsure how to adapt the principle algorithm to code, does anyone know any other more simple examples of this method?

Here's a link to my current code on SkyDrive too if you'd like to take a look through what I have currently.

Thanks.

It sounds like you're suggesting there would be multiple hits to the same block with this method but I don't see why.

However, I do see how you could trigger a collision with multiple blocks; there might be two that would have been within the range of movement if it didn't bounce. However, it's not hard to pick which collision happened first and only process that one.

Here's some pseudocode (Disclaimer: This is completely untested!):

bool collided = false;
double nearestHit = double.MaxValue;
BlockEdge nearestHitEdge;

foreach block in blocks {
   foreach edge in block {
      Vector2 intersection = lineIntersection(ballVelocityVector, edge);
      double distance = distanceBetween(ballCoords, interesection);
      if (distance < ballRadius + length(ballVelocityVector) && distance < nearestHit) {
         collided = true;
         nearestHitEdge = edge;
         nearestHit = distance;
      }
   }
}

if (collided) {
   nearestHitEdge.parentBlock.hit();
   ball.bounceOff(nearestHitEdge);
}

/* End of pseudocode */

Also, for your convenience here's some actual C# code for finding the intersection of two lines given two points on the lines. It expects "points" to be a 4x2 multidimensional array where the first index specifies which point and the second index indicates X (0) or Y (1). The first two points define one line and the other two define the other line.


            double nx, ny;

            if (points[0, 0] == points[1, 0])
            {
                if (points[2, 0] == points[3, 0])
                {
                    nx = double.MaxValue;
                    ny = double.MaxValue;
                }
                else
                {
                    double slope2 =(points[3, 1] - points[2, 1]) / (points[3, 0] - points[2, 0]);
                    double b2 = points[2, 0] * -slope2 + points[2, 1];
                    nx = points[0, 0];
                    ny = slope2 * nx + b2;
                }
            }
            else if (points[2, 0] == points[3, 0])
            {
                double slope1 = (points[1, 1] - points[0, 1]) / (points[1, 0] - points[0, 0]);
                double b1 = points[0, 0] * -slope1 + points[0, 1];
                nx = points[1, 0];
                ny = slope1 * nx + b1;
            }
            else
            {
                double slope1 = (points[1, 1] - points[0, 1]) / (points[1, 0] - points[0, 0]);
                double slope2 = (points[3, 1] - points[2, 1]) / (points[3, 0] - points[2, 0]);
                double b1 = points[0, 0] * -slope1 + points[0, 1];
                double b2 = points[2, 0] * -slope2 + points[2, 1];
                nx = (b2 - b1) / (slope1 - slope2);
                ny = slope1 * nx + b1;
            }

You could give every block a bounding box and then do a ray cast from where the ball is before you move it, to where the ball will be after you move it, and then check the ray for collisions.

@Stathgar:
The block's Hit() method fires multiple times 'cause the collision detection checks are made every update cycle and when the bounding boxes tunnel into one another that makes them overlap and collide for more than one update cycle, thus decrease the block's hit-points by more than one with each collision.

@Lord Ikon:
That is what I'm doing currently only using BoundingBoxes as opposed to Rays. This helps with detecting the specific edge of the block which is hit as Rays would confuse this as - if I understand them right - Rays are of indefinite length.

zanders:

Why don't you move the ball position so that it no longer collides with the current block?

I was considering this and I noticed that Contains() has an overload that seems to return the amount by which the two boxes overlap and was wondering if that could somehow be used to make moving the ball back a distance easier and more accurate?
I'm not entirely sure how to use an enumerator like this so if so a pointer towards an example article would be especially helpful?

zanders:

Another idea to prevent multiple calls to block.Damage() would be to add a boolean value that tells you if the ball was still colliding with a bounding box last update; meaning Damage() doesn't need to be called if you're still colliding with the same box.

Rays do have infinite length, however, you grab all collisions, and then sort the closest collision to the ball to the front and use only it.

You could use a swept circle vs. rectangle/aabb/line/plane query. It would tell you exactly where the ball will first touch the paddle, even if the ball is moving so fast it would skip behind the paddle in a single update.

That way you could handle the collision and let the ball move in the opposite direction by the remaining distance it would have moved if the paddle wasn't in the way.

Here is an article describing the algorithm: Sweep test for circle vs line segment