CODEWITHSUNDEEP
javagame-physicsgraphics2djava-2d
user1104028
user1104028

Reputation: 397

Fast Java Image Collision Detection Algorithm

I am working on a Java 2D video game, and I am looking for a faster Collision Detection algorithm than what you see below. I am trying to detect a collision between a torpedo and a ship. The algorithm I am using seriously impacts the performance of my main Graphics 2D dispatch loop, slowing down my screen repaints. Was wondering if anyone could recommend a better algorithm for how to handle this, that was quicker to detect a collision? Pointers to sample code would be great!

Here is the slow algorithm that I am using that goes Pixel by Pixel..

    private boolean isPixelCollide(double x1, double y1, VolatileImage image1,
                double x2, double y2, VolatileImage image2) {   

        double width1 = x1 + image1.getWidth() -1,
                 height1 = y1 + image1.getHeight() -1,
                 width2 = x2 + image2.getWidth() -1,
                 height2 = y2 + image2.getHeight() -1;

          int xstart = (int) Math.max(x1, x2),
              ystart = (int) Math.max(y1, y2),
              xend   = (int) Math.min(width1, width2),
              yend   = (int) Math.min(height1, height2);

          // intersection rect
          int toty = Math.abs(yend - ystart);
          int totx = Math.abs(xend - xstart);

          for (int y=1;y < toty-1;y++){
            int ny = Math.abs(ystart - (int) y1) + y;
            int ny1 = Math.abs(ystart - (int) y2) + y;

            for (int x=1;x < totx-1;x++) {
              int nx = Math.abs(xstart - (int) x1) + x;
              int nx1 = Math.abs(xstart - (int) x2) + x;
              try {
                if (((image1.getSnapshot().getRGB(nx,ny) & 0xFF000000) != 0x00) &&
                    ((image2.getSnapshot().getRGB(nx1,ny1) & 0xFF000000) != 0x00)) {
                   // collide!!
               return true;
            }
              } catch (Exception e) {
//            System.out.println("s1 = "+nx+","+ny+"  -  s2 = "+nx1+","+ny1);
              }
            }
          }

          return false;

}

Upvotes: 2

Views: 152

Answers (2)

MaKri
MaKri

Reputation: 200

You can define bounds of each object on your scene with Rectangle class and then use Rectangle#intersect(Rectangle rect) method. So your intersect method can look like this:

private boolean intersect(double x1, double y1, VolatileImage image1, double x2, double y2, VolatileImage image2) {
    return (new Rectangle(x1, y1, image1.getWidth(), image1.getHeight()).intersect(new Rectangle(x2, y2, image2.getWidth(), image2.getHeight()));
}

Upvotes: 1

sgtHale
sgtHale

Reputation: 1547

That's a lot of getRGB(). Have you considered representing the torpedo and a ship as boxes first and use it for some early reject mechanism?

Also try dividing the pixel tests by 2. Test half the resolution by skipping along every other pixel. Half resolution shouldn't be much of a problem depending on your picture.

Upvotes: 0

Related Questions