3

在我编写碰撞检测算法时,我遇到了这个问题。这是一件很奇怪的事情,超出了我的理解。

这里的问题是,如果在我的算法中,在 function 中提出,tryMove()我添加并在减去所有单元占用的区域后检测(由甚至没有靠近,移动单元所在的位置,它正在移动到。potentialAreamoveLineAreaspaceTestAreamoveLineAreax=280,y=120x=1880,y=120x=1914,y=126

我想知道这个问题的原因可能是什么,以及为了将来避免它该怎么做。

我必须说我有一个临时解决方案 ( tryMove2()) 但请不要让它影响你的想法,即我不喜欢这个解决方案,我坚信第一个解决方案 ( tryMove()) 应该有效,而且一定是我忘记了一些事情。

请参阅下面出现问题的代码。

import java.awt.Point;
import java.awt.Polygon;
import java.awt.geom.Area;
import java.awt.geom.Ellipse2D;
import java.util.ArrayList;
import java.util.List;

/**
 * Test showing some unexpected and weird behaviour of area subtraction.
 * @author Konrad Borowiecki
 */
public class TestTryMove {
    private static final List<Point> unitCenterPoints = new ArrayList<Point>();
    static{
        unitCenterPoints.add(new Point(1720, 120));
        unitCenterPoints.add(new Point(1880, 120));
        unitCenterPoints.add(new Point(1800, 200));
        unitCenterPoints.add(new Point(1720, 280));
        unitCenterPoints.add(new Point(1880, 280));
        unitCenterPoints.add(new Point(120, 120));
        unitCenterPoints.add(new Point(280, 120));
        unitCenterPoints.add(new Point(200, 200));
        unitCenterPoints.add(new Point(120, 280));
        unitCenterPoints.add(new Point(280, 280));
        unitCenterPoints.add(new Point(120, 1720));
        unitCenterPoints.add(new Point(280, 1720));
        unitCenterPoints.add(new Point(200, 1800));
        unitCenterPoints.add(new Point(120, 1880));
        unitCenterPoints.add(new Point(280, 1880));
    }
    public static void main(String[] args) {
        int[] xpointsOK = new int[]{1876, 1884, 1918, 1910};//for Move OK
        int[] ypointsOK = new int[]{139, 101, 108, 146};//for Move OK
        Polygon lineOK = new Polygon(xpointsOK, ypointsOK, xpointsOK.length);

        int[] xpointsFAIL = new int[]{1877, 1883, 1917, 1911};//for problem no move
        int[] ypointsFAIL = new int[]{139, 101, 107, 145};//for problem no move
        Polygon lineFAIL = new Polygon(xpointsFAIL, ypointsFAIL, xpointsFAIL.length);

        Point endPointCPOK = new Point(1914, 127);//Move OK
        Point endPointCPFAIL = new Point(1914, 126);//problem no move
        //where in both cases it should be move OK              
        System.out.println("******TEST for method tryMove()******");            
        System.out.println("TEST 1: this will FAIL");
        System.out.println("Result="+tryMove(endPointCPFAIL, lineFAIL)); 
        System.out.println("\nTEST 2: this will be OK");
        System.out.println("Result="+tryMove(endPointCPOK, lineOK));


        System.out.println("******TEST for method tryMove2()******");   
        System.out.println("TEST 1: this will be OK");
        System.out.println("Result="+tryMove2(endPointCPFAIL, lineFAIL)); 
        System.out.println("\nTEST 2: this will be OK");
        System.out.println("Result="+tryMove2(endPointCPOK, lineOK));
    }
    /**
     * Tests if a unit represented by point of index 1 in the list of 
     * unitCenterPoints (i.e. [1880, 120]) can make a move to the given endPointCP.
     * (Please notice we are ignoring this unit in the algorithm 
     * i.e. if(i != movingUnitIndexInTheArray)).
     * @param endPointCP the point where the unit moves to.
     * @param line the line of the move of the thickness equal to units width (mod=40), 
     * drawn between the current unit's center point and the endPointCP, 
     * represented as a polygon object.
     * @return true if move possible; false otherwise. 
     */
    private static boolean tryMove(Point endPointCP, Polygon line){
        Area potentialArea = getArea(endPointCP);
        Area moveLineArea = new Area(line);
        moveLineArea.add(potentialArea);
        //this area is used for testing if nothing stays on the way of the move
        Area spaceTestArea = new Area(moveLineArea);
        //the index of the unit making the move in the unitCenterPoints list
        int movingUnitIndexInTheArray = 1;
        //we are subtracting from spaceTestArea all areas of units
        for(int i = 0; i < unitCenterPoints.size(); i++)
            if(i != movingUnitIndexInTheArray) {
                Point p = unitCenterPoints.get(i);
                Area uArea = getArea(p);
                spaceTestArea.subtract(uArea);
                //we have intersection then return false, we cannot make this move  
                if(spaceTestArea.isEmpty() || !spaceTestArea.equals(moveLineArea)) {
                    System.out.println("No move --- a unit is on the way. "
                            + "Conflicting point is="+p +"; for i="+i);
                    return false;
                }
            }
        System.out.println("Move OK.");
        return true;
    }

    private static boolean tryMove2(Point endPointCP, Polygon line){
        Area potentialArea = getArea(endPointCP);
        Area moveLineArea = new Area(line);
        //test if unit can move to the new position
        Area potentialTestArea = new Area(potentialArea);
        //this area is used for testing if nothing stays on the way of the move
        Area spaceTestArea = new Area(moveLineArea);
        //the index of the unit making the move in the unitCenterPoints list
        int movingUnitIndexInTheArray = 1;
        //we are subtracting from spaceTestArea all areas of units
        for(int i = 0; i < unitCenterPoints.size(); i++)
            if(i != movingUnitIndexInTheArray) {
                Point p = unitCenterPoints.get(i);
                Area uArea = getArea(p);
                spaceTestArea.subtract(uArea);
                potentialTestArea.subtract(uArea);
                //we have intersection then return false, we cannot make this move  
                if(spaceTestArea.isEmpty() || !spaceTestArea.equals(moveLineArea)
                        || potentialTestArea.isEmpty() || !potentialTestArea.equals(potentialArea)) {
                    System.out.println("No move --- a unit is on the way. "
                            + "Conflicting point is="+p +"; for i="+i);
                    return false;
                }
            }
        System.out.println("Move OK.");
        return true;
    }
    /**
     * Gets the area taken by a unit given the unit's center point.
     * @param p the center point of a unit.
     * @return circle area.
     */ 
    private static Area getArea(Point p) {
        int mod = 40;//this is width and height of a unit
        Ellipse2D circle = new Ellipse2D.Double(p.x - mod / 2, p.y - mod / 2, mod, mod);
        return new Area(circle);
    }
}

这是它产生的输出:

******TEST for method tryMove()******
TEST 1: this will FAIL
No move --- a unit is on the way. Conflicting point is=java.awt.Point[x=280,y=120]; for i=6; where moving unit point is=java.awt.Point[x=1880,y=120]; the unit is moving to=java.awt.Point[x=1914,y=126]
Result=false

TEST 2: this will be OK
Move OK.
Result=true
******TEST for method tryMove2()******
TEST 1: this will be OK
Move OK.
Result=true

TEST 2: this will be OK
Move OK.
Result=true

为了让您更好地看到问题,我有两个图像为两个端点呈现它,第一个1914, 126是方法失败时,第二个1914, 127是正常时。

这就是我们的问题。

这里一切正常。

如果需要更多描述,我会尽快回答。谢谢大家。

EDIT1: 正如@trashgod 所建议的,我确实尝试并实现了一个使用intersect()方法的解决方案。我不喜欢每次测试都必须创建一个新对象。你能为这个算法提出一些优化建议吗?

private static boolean tryMove3(Point endPointCP, Polygon line){
    Area potentialArea = getArea(endPointCP);
    Area moveLineArea = new Area(line);
    moveLineArea.add(potentialArea);
    //this area is used for testing if nothing stays on the way of the move
    //the index of the unit making the move in the unitCenterPoints list
    int movingUnitIndexInTheArray = 1;
    //we are subtracting from spaceTestArea all areas of units
    for(int i = 0; i < unitCenterPoints.size(); i++)
        if(i != movingUnitIndexInTheArray) {
            Point p = unitCenterPoints.get(i);
            Area uArea = getArea(p);
            Area spaceTestArea = new Area(moveLineArea);
            spaceTestArea.intersect(uArea);
            //we have intersection then return false, we cannot make this move  
            if(!spaceTestArea.isEmpty()) {
                System.out.println("No move --- a unit is on the way. "
                        + "Conflicting point is="+p +"; for i="+i
                        + "; where moving unit point is="
                        +unitCenterPoints.get(movingUnitIndexInTheArray)
                        +"; the unit is moving to="+endPointCP
                        +"; spaceTestArea.isEmpty()="+spaceTestArea.isEmpty());
                return false;
            }
        }
    System.out.println("Move OK.");
    return true;
}
4

2 回答 2

3

我猜你正在与其中一种方式发生冲突,java.awt.geom.Area可能会变空。如果有帮助,我在下面拍了一张照片。或者,您可以使用createTransformedShape()andcontains()吗?

附录:tryMove3()看起来是正确的。如果它真的更糟,我看到了几种可能性:

  • 缓存任何 static Area,也许是与每个中心点相关的那些。

  • 基于getBounds()四叉树进行粗略的附近检查并跳过远程对。

在此处输入图像描述

JFrame f = new JFrame();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.add(new JPanel(){

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2d = (Graphics2D) g;
        g2d.scale(10, 10);
        g2d.translate(-1875, -100);
        g2d.setColor(Color.green);
        g2d.draw(lineOK);
        g2d.setColor(Color.green.darker());
        g2d.drawRect(endPointCPOK.x, endPointCPOK.y, 1, 1);
        g2d.setColor(Color.red);
        g2d.draw(lineFAIL);
        g2d.setColor(Color.red.darker());
        g2d.drawRect(endPointCPFAIL.x, endPointCPFAIL.y, 1, 1);
    }
});
f.pack();
f.setSize(450, 500);
f.setLocationRelativeTo(null);
f.setVisible(true);
于 2011-07-01T20:09:47.110 回答
2

不知何故,第 6 次减法正在改变 spaceTestArea 的几何形状,使其不等于 moveLineArea,这可以通过对两者进行异或操作来直观地看到。面积 API 仅声明 equals 测试两个几何是否相等,但遗憾的是没有进一步详细说明。例如,如果您将调试代码添加到您的程序中,您会看到这个 ExclusiveOr 区域仅在第 6 次减法中弹出。我还没有弄清楚为什么,但也许如果你创建一个 excluxiveOr 图像的图像,你会看到。

您的代码与我的调试语句(有些多余,抱歉):

import java.awt.*;
import java.awt.geom.*;
import java.util.ArrayList;
import java.util.Formatter;
import java.util.List;

public class TestTryMove {
   private static final List<Point> unitCenterPoints = new ArrayList<Point>();
   static {
      unitCenterPoints.add(new Point(1720, 120));
      unitCenterPoints.add(new Point(1880, 120));
      unitCenterPoints.add(new Point(1800, 200));
      unitCenterPoints.add(new Point(1720, 280));
      unitCenterPoints.add(new Point(1880, 280));
      unitCenterPoints.add(new Point(120, 120));
      unitCenterPoints.add(new Point(280, 120));
      unitCenterPoints.add(new Point(200, 200));
      unitCenterPoints.add(new Point(120, 280));
      unitCenterPoints.add(new Point(280, 280));
      unitCenterPoints.add(new Point(120, 1720));
      unitCenterPoints.add(new Point(280, 1720));
      unitCenterPoints.add(new Point(200, 1800));
      unitCenterPoints.add(new Point(120, 1880));
      unitCenterPoints.add(new Point(280, 1880));
   }

   public static void main(String[] args) {
      int[] xpointsOK = new int[]{1876, 1884, 1918, 1910};// for Move OK
      int[] ypointsOK = new int[]{139, 101, 108, 146};// for Move OK
      Polygon lineOK = new Polygon(xpointsOK, ypointsOK, xpointsOK.length);

      int[] xpointsFAIL = new int[]{1877, 1883, 1917, 1911};// for problem no
                                                            // move
      int[] ypointsFAIL = new int[]{139, 101, 107, 145};// for problem no move
      Polygon lineFAIL = new Polygon(xpointsFAIL, ypointsFAIL,
               xpointsFAIL.length);

      Point endPointCPOK = new Point(1914, 127);// Move OK
      Point endPointCPFAIL = new Point(1914, 126);// problem no move
      // where in both cases it should be move OK
      System.out.println("******TEST for method tryMove()******");
      System.out.println("TEST 1: this will FAIL");
      System.out.println("Result=" + tryMove(endPointCPFAIL, lineFAIL));
      System.out.println("\nTEST 2: this will be OK");
      System.out.println("Result=" + tryMove(endPointCPOK, lineOK));

      System.out.println("******TEST for method tryMove2()******");
      System.out.println("TEST 1: this will be OK");
      System.out.println("Result=" + tryMove2(endPointCPFAIL, lineFAIL));
      System.out.println("\nTEST 2: this will be OK");
      System.out.println("Result=" + tryMove2(endPointCPOK, lineOK));
   }

   private static boolean tryMove(Point endPointCP, Polygon line) {
      Area potentialArea = getArea(endPointCP);
      Area moveLineArea = new Area(line);
      System.out.println(showBounds("moveLine before add", moveLineArea));
      moveLineArea.add(potentialArea);
      System.out.println(showBounds("moveLine after add ", moveLineArea));
      // this area is used for testing if nothing stays on the way of the move
      Area spaceTestArea = new Area(moveLineArea);
      System.out.println(showBounds("spaceTest", spaceTestArea));
      Area xOr = (Area)spaceTestArea.clone();
      xOr.exclusiveOr(moveLineArea);
      System.out.printf("Pre   %s  %s  %s%n", showBounds("STA", spaceTestArea), showBounds("MLA", moveLineArea), 
               showBounds("xOr", xOr)); 

      // the index of the unit making the move in the unitCenterPoints list
      int movingUnitIndexInTheArray = 1;
      // we are subtracting from spaceTestArea all areas of units
      for (int i = 0; i < unitCenterPoints.size(); i++) {
         if (i != movingUnitIndexInTheArray) {
            Point p = unitCenterPoints.get(i);
            Area uArea = getArea(p);
            spaceTestArea.subtract(uArea);
            xOr = (Area)spaceTestArea.clone();
            xOr.exclusiveOr(moveLineArea);
            System.out.printf("i: %02d %s  %s  %s  %s%n", i, 
                     showBounds("STA", spaceTestArea), 
                     showBounds("MLA", moveLineArea), 
                     showBounds("uA", uArea),
                     showBounds("xOr", xOr));         
            // we have intersection then return false, we cannot make this move
            if (spaceTestArea.isEmpty() || !spaceTestArea.equals(moveLineArea)) {
               System.out.println("spaceTestArea.isEmpty()? " + spaceTestArea.isEmpty());
               System.out.println("!spaceTestArea.equals(moveLineArea)? " + !spaceTestArea.equals(moveLineArea));
               System.out.println("moveLineArea bounds: " + moveLineArea.getBounds());
               System.out.println("No move --- a unit is on the way. "
                        + "Conflicting point is=" + p + "; for i=" + i);

               return false;
            }
         }
      }
      System.out.println("Move OK.");
      return true;
   }

   public static String showBounds(String name, Area area) {
      Rectangle rect = area.getBounds();
      StringBuilder resultSB = new StringBuilder();
      Formatter formatter = new Formatter(resultSB);
      formatter.format("%5s [%04d, %04d, %04d, %04d]", name, rect.x, rect.y, rect.width, rect.height);

      return resultSB.toString();
   }

   private static boolean tryMove2(Point endPointCP, Polygon line) {
      Area potentialArea = getArea(endPointCP);
      Area moveLineArea = new Area(line);
      // test if unit can move to the new position
      Area potentialTestArea = new Area(potentialArea);
      // this area is used for testing if nothing stays on the way of the move
      Area spaceTestArea = new Area(moveLineArea);
      // the index of the unit making the move in the unitCenterPoints list
      int movingUnitIndexInTheArray = 1;
      // we are subtracting from spaceTestArea all areas of units
      for (int i = 0; i < unitCenterPoints.size(); i++)
         if (i != movingUnitIndexInTheArray) {
            Point p = unitCenterPoints.get(i);
            Area uArea = getArea(p);
            spaceTestArea.subtract(uArea);
            potentialTestArea.subtract(uArea);
            // we have intersection then return false, we cannot make this move
            if (spaceTestArea.isEmpty() || !spaceTestArea.equals(moveLineArea)
                     || potentialTestArea.isEmpty()
                     || !potentialTestArea.equals(potentialArea)) {
               System.out.println("No move --- a unit is on the way. "
                        + "Conflicting point is=" + p + "; for i=" + i);
               return false;
            }
         }
      System.out.println("Move OK.");
      return true;
   }

   /**
    * Gets the area taken by a unit given the unit's center point.
    * 
    * @param p
    *           the center point of a unit.
    * @return circle area.
    */
   private static Area getArea(Point p) {
      int mod = 40;// this is width and height of a unit
      Ellipse2D circle = new Ellipse2D.Double(p.x - mod / 2, p.y - mod / 2,
               mod, mod);
      return new Area(circle);
   }
}
于 2011-07-01T20:03:41.943 回答