Collision

Newbie & Debugging Questions
#1

My first post here, so Hello to everyone. I’ve already read through a lot of posts here for help and its been great.

I’m working my way through making a breakout(ball bouncing, hitting box’s etc…) style game to learn a bit more about how to program in Java.

I went though Kev’s tutorial for space invaders in Java 2d. For collision he used a method he described as “brute force”. As far as I understand this just tells my game “entities” to do something when they overlap, but for my game I need my ball to know if its hit the sides, top or bottom of the box’s and to do something depending on which.

What collision detection method do you think would work best for this? And a brief description of how its implemented would be great. Or a Link to some source/tutorial would be sweet.

#2

I am assuming that you are keeping track of the balls position and boundaries using a Point (as the center) and a radius and that you are keeping track of your blocks using a Rectangle (where x and y are the top left corner). A collision test could work like this. What you need to do is compare the x and y coordinates to determine where the ball is in relation to the blocks. (if ball.x < block.x ball is to the left etc.) then you need to determine if the ball is moving in such a way as it will hit the block (ball is left of the block and is moving right etc.) then do your collision test. Based on the location of the ball and the direction it is moving you where it hit.

Example:

 ball is lower than the top of the block but is higher than the bottom of the block
   ball is left of block
     ball is moving right    //we now know that the ball is left of the block, in a position that it might hit it, and is moving right
       if ball hits block
         do ball hits the left of the block function
    ball is right of block
      ball is moving left
        if ball hits block
          do ball hits right of the block function

Too determine if it hits top or bottom it is mostly the same, if the ball is between the x of the block and the value of x + width, then determine if it is above or below, the direction it is going, and then do your hit test.

It is almost the same as your standard collision you just need to calculate where your ball is in relation to the block and have something that stores the balls velocity. If this is too confusing I can up with some code for you.

#3

In terms of actual collision just use Java’s built in geometry functions.

Instantiate some java.awt.geom.Ellipse2D and java.awt.geom.Rectangle2D objects. Then simply use ellipse.intersects(rextangle) in order to see if there is collision. If there is, you can compare ellipse.getX() and ellipse.getY() versus rectangle.getX() and rectangle.getY() in order to know how to deflect the object (using hit normals).

#4

Understand, though, that Kev’s point about using “brute force” means that he was checking every moving object against every object, which becomes an O(N^2) operation if all objects are moving. This can be a huge bottleneck in action packed games.

If collision detection causes speed issues for you (in a breakout clone, it probably won’t as long as you do it in a reasonable way), there are two ways out:

  1. Early-exit optimizations (use bounding box check to quit the test early)
  2. Never-enter optimizations (be clever and make sure you never check for shape overlap without a bounding box overlap)

In 1) you use methods to quickly decide that two objects don’t overlap, for instance you might notice that the left edge of one is to the right of the right edge of the other (usually you’d check for possible bounding box overlap, and break out before a detailed test if no overlap exists).

But that doesn’t remove the O(N^2) behavior, it just speeds it up a bit. To get rid of the O(N^2), you need to store away some data to make sure you aren’t checking each pair. The two common ways to do this are a) use a grid (place each object in a grid cell, and only check collisions for objects in the same or neighboring grid cells - easy to implement, but you have to choose the cell size carefully), and b) incremental sweep and prune (search Google for the details - essentially, this method maintains a sorted list of bounding box edges and you only check collisions for overlapping pairs; this can be tough to implement well, and suffers from somewhat poor insertion times if you do a lot of insertions).

#5

DragonsRage - That is similar to how I would have worked it out, just I didn’t think to use the direction of the ball until after I had determined which side of the box it hits, and then it would have been just to change the direction. The way you describe should work much better.

Demonpants - I’ll look into those functions.

ewjordan - I thought “brute force” collision wouldn’t work for more advanced games, but as I’m new to this, it was the easy option just to get my program started and get some graphics and movements and collisions happening.
I will look into using a grid when I move onto something more advanced. I had seen grids on some of my google results, but they way you explained it, I can see how much better it would work in a lot of 2d games.

Thank you all for your time.

edit - oh yeah, i’ll let ya know how it works out, just kinda late now.

#6

Quad tree is a good method of speeding up collision and it’s very easy to grasp.

Basically, just divide your world into four sections over and over again. Check which section the ball collides with, then remove everything else not in that section from the possibilities. Keep going until you’re down to a useful level of precision.

#7

You’ll be surprised just how many objects you can brute force on a current computer without it even breaking a sweat - I’ve had several thousand objects all moving and colliding without having to do any optimisation at all. Just brute force it and optimise it later if it’s causing a problem.

#8

I’m having problems getting anything to work right now. I’m using :

    public boolean collidesWith(BBEntity other) {
        me.setBounds((int) x,(int) y,sprite.getWidth(),sprite.getHeight());
        him.setBounds((int) other.x,(int) other.y,other.sprite.getWidth(),other.sprite.getHeight());

        return me.intersects(him);
}

// Notification that this entity collided with another.
    public abstract void collidedWith(BBEntity other);

from Kev’s program

and have been trying things like

 public void collidedWith(BBEntity other) {

       if (other instanceof BrickEntity){
              otherX = other.getX();
              otherY = other.getY();
    
             if (BallXposition > otherX({
                 if (BallXpositon < (otherx + 100){  // I've tried add getWith() function with no luck :S
                        if (BallYposition > otherY+50){ //  ^^^^^^^ getHeight() ^^^^^^^^^^^^^
                        
                               dy = -dy;
                             
                       }

                  }
              }

      }

  }

which I thought should get it to bounce off the bottom of the brick, but it just does random stuff

any help would be apreciated

#9

The first thing you should do is create two blocks that you know collide and see if your collidesWith method works.

#10

I know the collidesWith method works, I used it for my paddle in the game, the ball is traveling down, it hits the paddle and heads back up.
Just when it comes to the blocks(and at some point the paddle too so that will have to be changed),
there is the possibility that is hits the sides also, the collideswith method is still called but dosent know to do different actions dependant on the top, bottom or either side.

What I did so far is use Kev’s space invader tutorial source, take out the bits that I wouldn’t need for my program, and then add bits so my program would do stuff I wanted it to. That might be why I’m having problems implementing something similar to my last post.

I will write a smaller program, with just shapes rather than images/sprites. It will be good practice and hopefully I will work out what I’m doing wrong.

Thank you for your time.

#11

Ok, so…

I made a new program. Its basically a window with a buffered graphics content.
It has 2 squares, one stays in the center, one moves around the screen. I made collision detection for the moving square like

    if (square2y == squareY+squareH){
        if (square2x > squareX){
           if (square2x< squareX+squareW){
                dy= -dy;
           }
        }
    }
    if (square2x == squareX+squareW){
        if (square2y > squareY){
            if (square2y < squareY+squareH){
                dx= -dx;
            }
        }
    }

etc…

Worked great, also found out 1 probable cause of my other program not working, I was using if more than, rather than if equals to.

then I added

me.setBounds(squareX+10, squareY+10, squareW+10, squareH+10);
him.setBounds(square2x+10, square2y+10, square2W+10, square2H+10);

and and if statement to my first collision detection to see if collidesWith method works
and it does, another thing i found out is that i had to make the bounds slightly larger than my squares or else my first collision detection wouldn’t work out right.

I think where I’m having problems mainly with my original program is after collidesWith is called,
in my collidedWith function, I’m not getting the right data, like collided with brick, I’m not getting the right values for the bricks x,y,width, height. If you look at my earlier post it shows how I tried to get this data eg. other.getY() might be returning something else’s X coordinate.

I’m sure this is down to the way my program is set out.

But any thoughts on this would be great

And is this normal for a beginner to have problems like this? I know that might not be a simple yes or no answer.

Thanks again

#12

I’d definitely make sure those methods work before doing anything else. If getX() is wrong, then you’re never going to have a working part of your program!

#13

I think I will play around with my second program. Its all done on one page. So I’ll try to split it up into different class’s and work on transferring data around.

My original question is answered I think, I just need to work on my actual Java/programming skills.

#14

Practice makes perfect!

It’s very good that you were able to fix this on your own - you’ll definitely have less trouble in the future.

#15

I just worked out why my getX() was wrong, now I just have to tinker with my collision bounds to get it to look right, should be no problem.

100% solved :slight_smile:

Thank you all for your posts, really appreciated.