两个形状对象之间的Java碰撞检测?

17

我想知道判断Shape对象是否与另一个形状相交的最佳方法。 目前,只要涉及到Shape与Rectangle相交或反过来,我的游戏就已经解决了碰撞检测问题。我遇到的问题是Shape类中的intersects()方法只能使用Rectangle或Point作为参数,而不能使用另一个Shape。有没有一种有效的方法来测试两个Shape对象是否有任何重叠?

我尝试的一种方法是使用for循环生成一组点区域,以测试它们是否在形状内,然后构建一个Point对象数组发送到另一个形状进行测试,但这会由于所有不必要的比较而显著降低我的帧率。

我搜索了很多,但在这里没有找到类似的东西。如果这是一个重复问题,请提前谅解。


1
仅考虑形状的边界框对于复杂形状是否足够?如果是,那就简单了。如果不是,那我认为会有些棘手... - souldzin
不,边界框不起作用。必须是形状的实际周长。我尝试使用getBounds()方法,但如果您尝试将角色对角线移动到墙壁之外,它们会被卡住,即使精灵没有撞到墙壁。 - Monkeybro10
4个回答

21

虽然没有经过测试,但为什么不试一试呢:

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实现了Shape接口,但添加了一些有用的方法


1
这难道不会产生很多垃圾吗? - user3011902
1
@TastyLemons 我怀疑一个Area实例不会占用太多堆空间,而且由于“intersect”操作会改变Area,因此尝试重复使用它并没有太大的好处。无论如何,JVM的GC策略都是为处理短寿命对象而设计的,比长寿命对象更好:http://programmers.stackexchange.com/questions/149563/should-we-avoid-object-creation-in-java - user2221343
1
我认为如果你在多个对象上每一帧都运行这个方法,可能会导致一些问题。 - user3011902
@TastyLemons 这是一个很好的观点,在低延迟场景下,GC暂停对程序可能会非常有害,因此值得对此代码进行分析并尝试确定内存的使用情况。JVM可能会或可能不会聪明地优化这个问题;如果存在问题,可以考虑Java的各种垃圾回收策略或构建一个完全避开Area的解决方案。 - user2221343

10

你也可以使用形状本身的边界来进行比较:

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

这看起来更加舒适。


2
这将产生边界框碰撞,而不是询问者所需的形状交集。然而,值得注意的是,这很可能比我的答案性能更好。首先,没有必要进行防御性复制,因为此“intersect”方法不会改变形状。此外,此“intersect”的合同规定可以在性能上降低精度:http://docs.oracle.com/javase/7/docs/api/java/awt/geom/RectangularShape.html#intersects(java.awt.geom.Rectangle2D) - user2221343

1
尽管用户2221343已经回答了Monkeybro10的问题,但在某些情况下,知道形状的轮廓可能会对使用他描述的技术起作用,我认为这可能有所帮助:
例如,如果您绘制两个多边形,则仅当多边形轮廓内包含的区域重叠时才检测到它们之间的碰撞,如果仅在多边形的准确轮廓上发生碰撞,则不会检测到它们之间的碰撞。如果您填充两个多边形,但不绘制它们,则即使在可见区域的轮廓上也会检测到碰撞。
我写了一个小例子来说明我的意思。取消注释绘制或填充命令,并通过取消给定行的第二个多边形垂直上升一个像素。运行代码并在JFrame中查看结果。如果上升第二个多边形,且两个多边形仅通过“fill”命令可见,则它们与其轮廓相交且检测到碰撞。如果未上升第二个多边形,并且两个多边形通过“draw”命令可见,则它们与其轮廓相交,但不会检测到碰撞:
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");
        }
    }

}

0
如果您认为区域相交太昂贵,可以先进行边界检查: shapeA.getBounds().intersects(shapeB.getBounds())
如果通过了边界检查,则进行区域相交检查。
if( myShape.getBounds().intersects(otherShape.getBounds()) ){
    Area a = new Area(myShape);
    a.intersect(new Area(otherShape));
    if(!a.isEmpty()){
        // do something
    }
}

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接