Java collision detection between two Shape objects?
Asked Answered
F

4

17

I would like to know the best way to tell if a Shape object intersects another shape. Currently I have collision detection in my game sorted out as long as it involves a Shape intersecting a Rectangle or vice versa. The problem I'm having is that the intersects() method in the Shape class can only take a Rectangle or a Point as a parameter, not another Shape. Is there an efficient way to test if two Shape objects are overlapping in any way? One way I tried was using a for loop to generate an area of points to test if they were in the shape, and then building an array of Point objects to send to the other shape to test, but this significantly dropped my framerate because of all of the unnecessary comparisons.

I looked and looked for something similar on here but didn't find anything really. Sorry in advance if this is a repeat.

Flunkey answered 28/3, 2013 at 19:48 Comment(2)
Is considering only the bounding box of the shape sufficient for complex shapes? If so, then its simple. If not, then I think it gets a little tricky...Anamariaanamnesis
No, the bounding box will not work. It has to be the actual perimeter of the shape. I tried using the getBounds() method, but if you try to move your character diagonally past a wall they get stuck even though the sprite isn't hitting it.Flunkey
C
22

Not tested, but why not:

import java.awt.geom.Area;

...

public static boolean testIntersection(Shape shapeA, Shape shapeB) {
   Area areaA = new Area(shapeA);
   areaA.intersect(new Area(shapeB));
   return !areaA.isEmpty();
}

Area implements Shape, but adds some potentially useful methods

Citified answered 28/3, 2013 at 20:25 Comment(4)
Does this not create a lot of Garbage?Pickwickian
@TastyLemons I doubt an Area instance uses very much heap space, and since the "intersect" operation mutates the Area, there would not be much benefit in trying to re-use it. Either way, JVM's GC strategies are designed to handle short-lived objects better than long-lived objects: programmers.stackexchange.com/questions/149563/…Citified
I just thought if you run this method every tick. for several objects, this could lead to some issues.Pickwickian
@TastyLemons it's a good point, in a low-latency scenario where GC pauses can be very detrimental to your program, it would be worthwhile to profile this code and try to determine how memory is being used. The JVM may or may not be clever enough to optimize this somehow; if it is problematic, it could be worth looking into Java's various garbage collection strategies or building a solution that eschews Area entirelyCitified
P
10

You can also use the bounds of the shape itself and then compare the bounds:

public boolean collidesWith(Shape other) {
    return shape.getBounds2D().intersects(other.getBounds2D());
}

This is a bit nicer on the eyes.

Pickwickian answered 28/7, 2015 at 0:37 Comment(1)
This will give a bounding-box collision rather than the shape intersection that the asker wants. However, it is worth nothing that this is very likely much more performant than my answer. For one, there's no need to make defensive copies, since this intersect method doesn't mutate the shape. Also, the contract for this intersect specifies that accuracy can be reduced in favor of performance: docs.oracle.com/javase/7/docs/api/java/awt/geom/…Citified
L
1

Even though user2221343 already answered Monkeybro10's question, I thought it might be helpful in some cases to know, that the outline of a shape might play a role if you use his described technique:

For example, if you draw two polygons, the collision of them won't be detected if it occurs only on the exact outline of the polygons. Only, if the areas that are included inside the polygons' outlines will overlap, the collision is detected. If you fill two polygons, but don't draw them, the collision will be detected even on the outline of the visible area.

I wrote a small example to show what I mean. Either uncomment the draw or fill command, and rise the second polygon vertically by one pixel by uncommenting the given line. Run the code and watch the result in the JFrame. If the second Polygon is risen, and both polygons are only visible by the "fill" command, they intersect with their outlines and collision is detected. If the second polygon is not risen, and both polygons are visible by the "draw" command, they intersect with their outlines but collision is not detected:

import java.awt.Color;
import java.awt.EventQueue;
import java.awt.Graphics;
import java.awt.Polygon;
import java.awt.geom.Area;

import javax.swing.JFrame;

public class Test {

    private JFrame frame;
    private Polygon polygon1;
    private Polygon polygon2;

    /**
     * Launch the application.
     */
    public static void main(String[] args) {
        EventQueue.invokeLater(new Runnable() {
            public void run() {
                try {
                    Test window = new Test();
                    window.frame.setVisible(true);
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        });
    }

    /**
     * Create the application.
     */
    public Test() {
        initialize();
    }

    /**
     * Initialize the contents of the frame.
     */
    private void initialize() {
        frame = new JFrame(){
            private static final long serialVersionUID = 1L;

            @Override
            public void paint(Graphics g){

                super.paint(g);

                doDrawing(g);

            }
        };
        frame.setBounds(100, 100, 450, 300);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        int nShape1 = 4;
        int xPoly1[] = {30,50,50,30};
        int yPoly1[] = {30,30,50,50};
        polygon1 = new Polygon(xPoly1,yPoly1,nShape1);

        int nShape2 = 4;
        int xPoly2[] = {35,55,55,35};
        int yPoly2[] = {50,50,70,70};

        // uncomment next line to rise second polygon vertically by one pixel
        //yPoly2[] = {49,49,69,69};

        polygon2 = new Polygon(xPoly2,yPoly2,nShape2);
    }
    public synchronized void doDrawing(Graphics g){
        g.setColor(new Color(255,0,0));

        // if you draw the polygon, collision on the exact outline won't be detected.
        // uncomment draw or fill command to see what I mean.
        g.drawPolygon(polygon1);
        g.fillPolygon(polygon1);

        g.setColor(new Color(0,0,255));

        // if you draw the polygon, collision on the exact outline won't be detected.
        // uncomment draw or fill command to see what I mean.
        g.drawPolygon(polygon2);
        g.fillPolygon(polygon2);

        Area area = new Area(polygon1);
        area.intersect(new Area(polygon2));
        if(!area.isEmpty()){
            System.out.println("intersects: yes");
        }
        else{
            System.out.println("intersects: no");
        }
    }

}
Lineal answered 6/11, 2014 at 19:39 Comment(0)
U
0

If you think the area intersect is too expensive, you could first do a bounds check: shapeA.getBounds().intersects(shapeB.getBounds())

If this passes, then do the area intersect check.

if( myShape.getBounds().intersects(otherShape.getBounds()) ){
    Area a = new Area(myShape);
    a.intersect(new Area(otherShape));
    if(!a.isEmpty()){
        // do something
    }
}
Utta answered 24/5, 2018 at 20:39 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.