FRIHOST • FORUMS • FAQ • TOS • BLOGS • DIRECTORY
You are invited to Log in or Register a Frihost Account!

Programming collision detection

   Frihost Forum Index -> Scripting -> Others
 


snowboardalliance
I'm working on a breakout like game in java for class. (The pong-like paddle and ball where you try to break little rectangles by hitting them with the ball)

I wanted to try some advanced collision detection, so that if a ball hit a rectangle, it would bounce off of it correctly, like if it was moving on a path and collided through for 10 pixels, the collision detection would use these 10 pixels for moving the ball as it bounces.

Example crappy drawing in paint


I am using vectors for the ball movement. I found http://www.gamasutra.com/features/20020118/vandenhuevel_02.htm this site that shows how to do it right with a moving ball hitting a stationary ball, but I need it with rectangles. My question is, how do I apply the techniques from this site, to a ball->rectangle collision?

I thought about treating the nearest side of the rectangle as a line an the vector as a line and calculating the intersection, but I would appreciate some other advice on this.
Indi
Sometimes the best solution is not a general purpose collision detection algorithm. Honestly, most games don't use them - most games do things like align bounding boxes to axes to simplify the calculations.

In your case, some very easy simplifications can drastically ease the calculations. For starters, align your rectangles to the axes. That will solve the vast majority of the problem.

Say your ball is at position (x, y) moving with velocity (v_x, v_y), and it has radius r. (See my even crappier drawing below.)



All you have to do to detect a collision is to check the x-coordinate, because the y-coordinate is simply a matter of seeing if q ≤ y ≤ (q + b). To check x, you just have to subtract p from x, and if the result is ≤ r, you have collided.

To handle the collision is trivial. Simply set v_x = -v_x.

If you want to get sexy, you can even correct for the case where the ball actually penetrates the block between frames. For example, if in frame 1 you are 7 pixels from the block, then you move forward 10 pixels, the ball would appear to dig into the block a little bit before it bounces back. What you want to happen is to have the ball move forward 7 pixels then back 3 in that frame. No problem. Simply move the ball forward the 10 pixels, then do the collision detection. When you subtract p from x, take the result, multiply it by 2 (because you have gone 3 pixels into the block - you have to go 3 pixels back to get to the point of impact, then another 3 to get to where you want to be), and subtract it from x. Voila. That's all there is to it.

In summary, here's one easy way to do it.
  1. At the start of the frame, move the ball using the velocity (v_x, v_y) - simply set (x, y) to (x + v_x, y + v_y).
  2. Subtract (the new) x from p (and store the result).
  3. If the result is less than or equal to r, there might have been a collision - otherwise, simply skip the rest.
  4. See if q ≤ y ≤ (q + b). If so, there was a collision. If not, simply skip the rest.
  5. Set v_x to -v_x.
  6. Correct x by subtracting two times the result of p - x (that you stored).
As simple as it sounds, as long as you are using rectangular blocks and only hitting them from one side, this is all you need for perfect collision behaviour. Extending it to handle collisions from the other direction is no problem (for example, when the ball hits the back wall and ricochets to hit the back of a block) - i leave it as an exercise to the programmers here. It is also no problem to add the vertical collision detection - so you can even hit the top and bottom of the block (another exercise for the programmers here). These same collision detection algorithms will handle colliding with the sides of the playing field, and the paddle (although, if you want to be really sexy, you can test to see if the paddle is moving up or down and use its velocity to change the vertical velocity of the ball - so if the paddle was flying up quickly and the ball hits it perfectly horizontally, it will add a bit of upwards vertical motion to the recoil, simulating momentary friction of ball on paddle (and if you want to be really, really sexy, you can add some spin to the ball, and use that in calculations, or just for graphical effect)).
snowboardalliance
thanks, that's very similar to what I was working on and I like how you explained the "digging in" correction. A few questions though.

First, assuming I have a rectangle with the top right point at (x,y) that has width a and height b, would the point (p,q) just be the nearest corner? Like bottom-left when the ball is moving NE, bottom-right when the ball is going NW, etc.?

Secondly, in most breakout-like games, the ball bounces differently off of your paddle depending on where it hits. Like the far edges will significantly change the angle and speed up the ball etc.



So would it work if I just bounced it like normal (using vectors its just like 360-Θ) and then added or subtracted from the angle based on the x position relative to the center? I don't know if that's the best way

EDIT:

OK, I have a problem, the ball I'm using is bigger than the rectangle and it is not detecting collisions.
Indi
snowboardalliance wrote:
First, assuming I have a rectangle with the top right point at (x,y) that has width a and height b, would the point (p,q) just be the nearest corner? Like bottom-left when the ball is moving NE, bottom-right when the ball is going NW, etc.?

Ah, crap, my bad. i forgot to mention - (p, q) is completely arbitrary. Wherever you "anchor" your rectangle - whatever point you use to locate the rectangle's position, be it one of the corners or the centrepoint - you can calculate (p, q) from that easily. For example if point (x, y) is on the top right, (p, q) is just (x - a, y - b). If point (x, y) is the centrepoint of the rectangle, then (p, q) is (x - a/2, y - b/2), and so on.

You could easily modify the algorithm slightly to eliminate the extra calculations from putting your anchor point somewhere other than where i did. For example, if you used the top left instead of the bottom left, then instead of checking for q ≤ y ≤ (q + b), you check for (q - b) ≤ y ≤ q.

snowboardalliance wrote:
Secondly, in most breakout-like games, the ball bounces differently off of your paddle depending on where it hits. Like the far edges will significantly change the angle and speed up the ball etc.



So would it work if I just bounced it like normal (using vectors its just like 360-Θ) and then added or subtracted from the angle based on the x position relative to the center? I don't know if that's the best way

Probably the easiest way would be to handle the collision just like shown, but then take an extra step where you check for where y is relative to q + b/2 (which would be the center of the paddle in the drawing i did, using the (p, q) i did on the bottom left).

The way you handle exactly how much angle to add is really a matter of taste that will affect the "flavour" of the game play - because there's really no physical reason for the ball to deflect that way from a flat surface. Once you determine where on the paddle you hit - which you can do simply by subtracting y from q + b/2 (the more positive the result the further down you hit the paddle, zero means you hit it dead center) - how you use that to change the angle is really up to you. i suppose you could find the percentage of how far from the center to the end you hit (so you'll get finer control with a longer paddle) and use that in some way to fudge the angle. You just have to watch out for the case that you show in your diagram in the bottom right hand corner - you don't want to add so much of an angle that the ball ricochets backwards (that is, behind the paddle).

snowboardalliance wrote:
EDIT:

OK, I have a problem, the ball I'm using is bigger than the rectangle and it is not detecting collisions.

Are you using the algorithm i described? That shouldn't be a factor. The size of the ball only determines how far away from the block the center of the ball is when a collision happens. The ball could be a hundred times bigger than the block without any problems.
snowboardalliance


New problem.

I found that with blocks stacked on top of one another, I am detecting the wrong collisions.

The yellow spot is correct, and the blue line is where the ball should move.
Really, it detects the green spot, so it moves following the green line and then continues to screw up while it is inside some blocks.

Here's the code if it helps.
Basically, if I can check the collisions of several bricks near the ball, how do I determine the correct one?

// part of update code
Code:
boolean hit = false;
      do
      {
         ball.move();
         hit = map.wallCollisions(ball) ||
            map.brickCollisions(ball) ||
            paddle.checkCollision(ball);
         
         if (hit)
         {
            parent.playTink();
            // debugging
            parent.repaint();
            parent.pause(250);
         }
      } while (hit);


// pre-collision

Code:
   public boolean brickCollisions(Ball b)
   {
      // find approximate grid location
      int x = (int) (b.getX()/Constants.SCALE)-x_offset;
      int y = (int) (b.getY()/Constants.SCALE)-y_offset;
      
      ArrayList<Brick> possible = getBricks(x, y);
      
      // check all possible bricks for collisions
      for (int i = 0; i < possible.size(); i++)
      {
         Debug.print("---Begin Collision---");
         // if there is a collision, change brick and award points
         if (possible.get(i).checkCollision(b))
         {
            Debug.print("Collision Detected with " + possible.get(i));
            // get the point value, will also change/delete brick
            int points = possible.get(i).hit();
            game.addPoints(points);
            
            return true;
         }
      }
      
      return false;
   }


// collision code
Code:
public boolean checkCollision(Ball b)
   {
      // get the Vector v of the Ball b
      // changes made to v are stored in b
      Vector v = b.getVector();
      // check if next move will collide
      double new_x = v.moveX(b.getX());
      double new_y = v.moveY(b.getY());
      
      // in this case, it will never collide
      double x_diff = b.getRadius()+2, y_diff = b.getRadius()+2;
      
      // check movement direction
      // also if it is going right, it must have been on left before, etc.
      if (v.getDir().isRight() && (b.getX()+b.getRadius()) < (this.x + this.width))
      {
         x_diff = this.x - new_x;
      }
      else if (v.getDir().isLeft() && (b.getX()-b.getRadius()) > this.x)
      {
         x_diff = new_x - (this.x + this.width);
      }
      if (v.getDir().isUp() && (b.getY()-b.getRadius()) > this.y)
      {
         y_diff = new_y -(this.y + this.height);
      }
      else if (v.getDir().isDown() && (b.getY()+b.getRadius()) < (this.y + this.height))
      {
         y_diff = (this.y) - new_y;
      }
      
      Debug.print("***x_diff: "+x_diff+" y_diff: "+y_diff+
         " degrees: "+b.getDir().getDegrees()+" brick: "+this.toString());
      
      if (y_diff <= b.getRadius())
      {
         if (new_x+b.getRadius() > this.x &&
            new_x-b.getRadius() < this.x + this.width)
         {
            b.move();
            b.getDir().bounceY();
            
            Debug.print("***degrees: "+b.getDir().getDegrees());
            Debug.print("***b.x: "+b.getX()+" b.y: "+b.getY()+
               " newx: "+new_x+" newy: "+new_y);
            Debug.print("this.x: "+this.x+" this.y: "+this.y);
            Debug.print("Collision with top/bottom of brick: "+this.toString());
            
            return true;
         }
      }
      else if (x_diff <= b.getRadius())
      {
         if (new_y+b.getRadius() > this.y &&
            new_y-b.getRadius() < this.y + this.height)
         {
            b.move();
            b.getDir().bounceX();
            
            Debug.print("***degrees: "+b.getDir().getDegrees());
            Debug.print("***b.x: "+b.getX()+" b.y: "+b.getY()+
                  " newx: "+new_x+" newy: "+new_y);
               Debug.print("this.x: "+this.x+" this.y: "+this.y);
            Debug.print("Collision with side of brick: "+this.toString());
            
            return true;
         }
      }
      
      return false;
   }
Indi
It looks like your problem is handling collisions in multiple dimensions at once. When you're doing one dimensional collision detection, like collisions with vertical walls only, it's no big deal to order the vertical walls by increasing x-coordinate and check them in that order. When you add another dimension, you run into the problem you're having there - does the horizontal collision have precedence or the vertical?

What you have to do is make a note of how far into its motion the ball impacts the object. Going back to my crappy sketch and the steps i gave:
From before wrote:
  1. At the start of the frame, move the ball using the velocity (v_x, v_y) - simply set (x, y) to (x + v_x, y + v_y).
  2. Subtract (the new) x from p (and store the result).
  3. If the result is less than or equal to r, there might have been a collision - otherwise, simply skip the rest.
  4. See if q ? y ? (q + b). If so, there was a collision. If not, simply skip the rest.
  5. Set v_x to -v_x.
  6. Correct x by subtracting two times the result of p - x (that you stored).
You have to make a few modifications. Once you detect a collision, don't handle it right away. Instead, note the collision and the distance the ball has traveled before making the collision. In the image, the collision occurs when the ball's x-coordinate is p - r. That means the ball has traveled from (x, y) to (p - r, ?) along vector (v_x, v_y). Simple geometry gives the distance traveled as:
d = (p - r - x) / cos(atan(v_y / v_x)) // (of course, this can be simplified)

So now, in between steps 4 and 5:
  1. Mark this collision as the one to be calculated.
  2. Calculate the distance the ball travels before colliding.
  3. Check for other collisions (using steps 1 - 4 above as necessary).
  4. If other collisions are detected, check the distance before the collision for them, too.
  5. If the distance for the new collision is less than the distance for the collision marked, make this collision the new marked collision.
  6. Repeat for all detected collisions.
  7. For the final marked collision, do the last steps to handle the collision (5 and 6 above, and anything else that needs doing like disappearing blocks and so on).
Here's an example of what i mean in rough code. i don't do Java if i can avoid it, but this shouldn't be too hard to translate.

First, i would make an abstract base collision event class something like this:
Code:
abstract class CollisionEvent
{
   private float time_of_impact_;   // This is a measure of how far into the
                                    // ball's movement it is when the
                                    // collision occurs. If it is 0, the
                                    // collision happens right at the start
                                    // of the fram. If it is 1, it happens
                                    // right at the end. A collision at 2.4
                                    // will happen before a collision at 3.2
   
   final float getTimeOfImpact() { return time_of_impact_; }
   final void setTimeOfImpact(float t) { time_of_impact_ = t; }
   
   final void calculateVerticalTimeOfImpact(
      Point starting_position,
      Vector velocity,
      int x_coordinate_of_impact)
   {
      time_of_impact_ = (x_coordinate_of_impact - position.x) /
         Math.cos(Math.atan(velocity.y / velocity.x));
      normalizeTimeOfImpact(velocity)
   }
   
   final void calculateHorizontalTimeOfImpact(
      Point starting_position,
      Vector velocity,
      int y_coordinate_of_impact)
   {
      time_of_impact_ = (y_coordinate_of_impact - position.y) /
         Math.sin(Math.atan(velocity.y / velocity.x));
      normalizeTimeOfImpact(velocity);
   }
   
   private final normalizeTimeOfImpact(Vector velocity)
   {
      time_of_impact /=
         Math.sqrt(velocity.x * velocity.x + velocity.y * velocity.y);
     
      // Optimization idea: work with time of impact squared to avoid sqrt
      // and sign problems
   }
   
   abstract void process();
}

Then, for example, a collision with the wall becomes something like:
Code:
class WallCollisionEvent extends CollisionEvent
{
   static final int HORIZONTAL   = 0;
   static final int VERTICAL     = 1;
   
   private Ball ball_;
   private int type_;
   private int coordinate_;
   
   WallCollisionEvent(Ball b, int type, int coordinate)
   {
      ball_ = b;
      type_ = type;
      coordinate_ = coordinate;
     
      if (type == HORIZONTAL)
         calculateHorizontalTimeOfImpact(
            ball_.getPosition(), ball_.getVector(), coordinate);
      else // (type == VERTICAL)
         calculateVerticalTimeOfImpact(
            ball_.getPosition(), ball_.getVector(), coordinate);
   }
   
   void play_sound()
   {
      GameSounds.play(GameSounds.WALL_BOUNCE_SOUND);
   }
   
   void process()
   {
      if (type_ == HORIZONTAL)
         // process a bounce off a horizontal wall
      else // you get the idea
     
      play_sound();
      // If this were a block, you could remove the block here,
      // change the score, anything.
   }
}

// Or, you know, you could make this class abstract, too and have a
// HorizontalWallCollisionEvent and so on, depending how OO you wanted to
// get. All this class would do in this case is play the sound.

Then your collision testing code would be:
Code:
List<CollisionEvent> getCollisions()
{
   List<CollisionEvent> collisions;
   
   checkForWallCollisions(collisions); // Add any potential wall collisions
                                       // to the collision list
   checkForBlockCollisions(collisions); // Add any potential block collisions
   checkForPaddleCollisions(collisions); // Same for the paddle
   // checkForBallCollisions(collisions); // You can even add more collision
                                          // types later, like when you have
                                          // multiple balls in play, they can
                                          // collide with each other.
   
   return collisions;
}

void handleCollisions()
{
   List<CollisionEvent> collisions = getCollisions();
   
   while (!collisions.empty())
   {
      CollisionEvent collision = collisions.get(0);
     
      // Find the collision with the lowest time to impact
      for (int n = 1; n < collisions.size(); ++n)
      {
         CollisionEvent c = collisions.get(n);
         
         if (c.getTimeOfImpact() < collision.getTimeOfImpact())
            collision = c;
      }
     
      // Process that collision
      collision.process();
     
      // Check for any new collisions
      collisions = getCollisions();
   }
}

By doing it this way, adding new types of collisions is trivial - just inherit a new type of CollisionEvent and add a line in getCollisions() to test for that type of collision. Also, changing the behaviour of collisions is also a snap. Suppose you have activated a power-up that makes the ball burrow through blocks it hits when it destroys them instead of bouncing off. Or instead of bouncing off the wall you want to travel through it and come out on the other side of the field. Or you want the ball to stick to the paddle until a button is pressed to launch it. Either way, just use a different collision event, and it will be processed automatically.
snowboardalliance
Thanks for that explanation

Unfortunately, my program was due for class before I read this and I simply corrected the error by checking if 2 collisions occur (only 0, 1, or 2 are possible now) and if so, I try to combine them into one larger brick. Not the most elegant, but it worked.

I might try your way if I continue to work on this game on my own though, so thanks.
Indi
Ah, sorry, i didn't realize you had a deadline. >_< i wouldn't have spent so much time doing the code if i did.
Reply to topic    Frihost Forum Index -> Scripting -> Others

FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP
© 2005-2007 Frihost, forums powered by phpBB.