Collision Detection

Summary:

Any suggestions appreciated!

Collision Detection

ff8jake 11 Oct 2011 07:48

Well, it's been a few days since any new posts, so I'll go ahead and ask two in a row… :D

I've been getting into this a bit more during the night, and decided I would try my hand at a pong clone, but got bored and it has now turned into a slightly more fast paced Arkanoid clone. I figured the first steps would be to get the ball bouncing around the screen like I wanted and the paddle/slider bouncing the ball as it gets hit. Keeping the ball inside the screen bounds wasn't too hard (I had balls go missing or get stuck several times), but I finally just started resetting the ball's X or Y value if it landed outside. Not the prettiest fix, but it seemed like it would be fast to process and absolutely ensure the ball doesn't get "lost".

As for the paddle meeting a ball, I was using Rectangle.Intersects(). It seems the faster the ball moves the more flaky the collision detection becomes, eventually at high speeds it can even go through the paddle (i.e., the ball's velocity was high enough to cause it to be drawn before, then after the paddle without making a connection). It had to be run at a very high speed to do this, but it still bugs me.

So I guess my question is twofold,
1) Is Rectangle.Intersects() the best collision detection method for a simple (but fast) arcade game like this, and
2) is there a good way to guarantee a reliable collision?

I've read a bit about preemptive collision checking, but most of the examples were very advanced. I hope I haven't jumped in over my head. :)

Thanks!

Re: Collision Detection

WindwalkerDM 11 Oct 2011 23:52

Hello.

I am working on a simple shoot-em-up so I didn't need that fast of collision detection anytime, however now I added upgrades into my game and one of them speeds up the players bullets. With other things in mind I was searching overall and stumbled upon this, so I have the same fear…

I can't post a direct link here, but search "metanetsoftware" over google and read about their "technique"

The concept looks extremely advanced, but bear with it and read through it. Their method for collision detection (and what happens after it) was very exciting for me. Yet, their concepts are beyond my application skills… but maybe you will get it better?

ff8jake (guest) 12 Oct 2011 01:21

Well, I read it up to the point where they were checking collisions between non AABB objects (as I am currently just working with rectangle intersection), and while I don't fully understand it yet, it was very helpful. Especially the part about determining which axis to use for calculating rebound. I've just started creating the bricks in this brick breaker game, and I was really wondering how to figure out which side of the brick was being hit by the ball (and thus, multiply the appropriate axis by -1);

As for my original question regarding the ball going through my paddle, I did find a 'solution' but I'm not yet sure I really like it, or rather I don't think it would work in many places (for instance, bullets in a shooter). My paddle is only around 25px tall and 200px wide, so I decided to make the bounding box extend further down out of sight (even out of window). Like this:

skipperccDOTcom/paddleRect.png

While this fixed any potential ball passthrough, it also extended my paddle's point of center much lower. I found I could make a new Vector2 by subtracting the Vector2 of the ball's center from the Vector2 of the paddle's new center, then call Vector2.Normalize() so I could then use that vector in my position update calculations without messing with the usual "speed" the ball traveled. The effect is if you hit the ball with the middle of the paddle it flies straight up, if you hit it with the side it goes sideways, giving a small degree of control (which could be adjusted more or less by adjusting my paddle's bounding box height). But beware, I may be completely retarded doing it this way, and if you have any suggestions I'd be happy to hear. I already plan on updating it a bit with the info from the article you suggested.

Re: Collision Detection

rbwhitaker 12 Oct 2011 13:27

I've had the problem you're describing myself, before. I can think of two things that might be of use to you.

So it sounds like you've got the code already in place to update the ball and paddle, and bounce the ball back up when it hits the paddle. Everything's fine until the ball is traveling really fast, and the ball's position gets updated beyond the location of the paddle. There's an easy fix: more frequent but smaller updates. For instance, move the ball 1/5 as far and check for collisions (or whatever else you're doing to update), and repeat that 5 times. Basically, you're doing five mini-updates per "real" update, giving you the opportunity to check for collisions at 5 different locations. The ball would have to be travelling 5 times faster to skip the paddle. And of course, you're not just limited to 5. You could make it 3 or 500 if you really wanted.

Honestly, that's the approach I'd probably take.

Short of that, though, rather than doing collision detection with a point and a rectangle, you can determine a line segment from the previous ball location to the current ball location, and do collision detection with a line segment and a rectangle. This way, even if the final position of the ball is past the paddle, the line segment will still go through the paddle's rectangle, and you can still catch it in the collision detection.

The math for that is a bit trickier, and as far as I know, there's no built-in XNA code to do line segent/rectangle collision detection. But it is definitely possible, and if you're willing to write the collision detection code for it, it is a good solution too.

I'd still go with the multiple smaller updates though.

ff8jake (guest) 13 Oct 2011 06:20

You're my hero RB. For some reason it didn't occur to me that I could perform my position updates (or any updates for that matter) across several small steps in a single Update() call, and it completely changes how I look at Update() now; in fact, I think I might even speed my ball up a little bit more. :)

I ended up combining the SAT collision mentioned in WindwalkerDM's post with the finer/faster/multi collision checks you mentioned. Since I'm not a super math wiz and I am only dealing with bounding boxes (and don't have a need for projecting my object onto an axis besides X or Y), I came up with the following:

    static public void CollisionCheck(CollidingObject collidingObjectA, CollidingObject collidingObjectB)
        {

            int aMinX = collidingObjectA.Rectangle.Left;
            int aMaxX = collidingObjectA.Rectangle.Right;
            int bMinX = collidingObjectB.Rectangle.Left;
            int bMaxX = collidingObjectB.Rectangle.Right;
            int aMinY = collidingObjectA.Rectangle.Top;
            int aMaxY = collidingObjectA.Rectangle.Bottom;
            int bMinY = collidingObjectB.Rectangle.Top;
            int bMaxY = collidingObjectB.Rectangle.Bottom;
            int xOverlap;
            int yOverlap;

            // Check for X axis overlap
            if ((aMinX < bMaxX) && (bMinX < aMaxX))
            {
                // Check for Y axis overlap
                if ((aMinY < bMaxY) && (bMinY < aMaxY))
                {
                    // We have a bounding box collision
                    // Perform neccessary actions

                    // Figure out how to calculate our X overlap
                    if (collidingObjectA.Rectangle.Center.X < collidingObjectB.Rectangle.Center.X)
                    {
                        xOverlap = aMaxX - bMinX;
                    }
                    else
                    {
                        xOverlap = bMaxX - aMinX;
                    }

                    // Figure out how to calculate our Y overlap
                    if (collidingObjectA.Rectangle.Center.Y < collidingObjectB.Rectangle.Center.Y)
                    {
                        yOverlap = aMaxY - bMinY;
                    }
                    else
                    {
                        yOverlap = bMaxY - aMinY;
                    }

                    // Perform action based on axis with smallest overlap
                    if (xOverlap < yOverlap)
                    {
                        doSomething();
                    }
                    else
                    {
                        doSomething();
                    }
                }
            }
        }

It's a bit savage, but it has the ball bouncing very nicely off the sides of my bricks before they disappear.

WindwalkerDM 13 Oct 2011 11:05

That's wonderful :D You seem to have succeeded implementing it very efficiently, at least the basic version. Ain't this programming thing wonderful and this site is the best ever?