java - 矩形的递归碰撞检测不太有效

Question

我有一堆大小可变的矩形，它们随机放置在一个区域中。

我正在尝试进行(递归)碰撞检测，通过移动它们的位置来确保它们不会发生碰撞。

但是，仍然有问题(一些矩形仍然发生碰撞)，我不知道是什么......可能是我无法正确进行递归。如果有人检查一下，我将不胜感激。

这是代码，只需复制并粘贴并运行它，您就会立即看到结果。需要 JavaFx:

import javafx.application.Application;
import javafx.geometry.Point2D;
import javafx.geometry.Rectangle2D;
import javafx.scene.Scene;
import javafx.scene.layout.Pane;
import javafx.scene.paint.Color;
import javafx.scene.shape.Rectangle;
import javafx.stage.Stage;

import java.util.*;

public class Example extends Application {

    public static void main(String[] args) {
        launch(args);
    }

    private Pane root = new Pane();

    @Override
    public void start(Stage stage) throws Exception {

        Scene scene = new Scene(root, 800, 600);

        stage.setTitle("Collision Problem");
        stage.setScene(scene);
        stage.setOnCloseRequest(e -> System.exit(0));
        stage.show();

        run();
    }

    private static class Node2D {

        private double x, y, w, h;

        public Node2D() {
            w = randInt(40, 80);
            h = randInt(20, 40);
        }

        public void setPosition(double x, double y) {
            this.x = x;
            this.y = y;
        }

        public double getWidth() {
            return w;
        }

        public double getHeight() {
            return h;
        }
    }

    private static class LayoutEntity {

        private Node2D obj = new Node2D();

        private double x, y;

        public void setLocationInLayout(double x, double y) {
            this.x = x;
            this.y = y;
        }

        public double getXInLayout() {
            return x;
        }

        public double getYInLayout() {
            return y;
        }
    }

    public void run() {

        LayoutEntity[] entitiesToLayout = new LayoutEntity[100];
        for (int i = 0; i < entitiesToLayout.length; i++)
            entitiesToLayout[i] = new LayoutEntity();

        randomizePositions(entitiesToLayout);

        collisionDetection(entitiesToLayout);

        for (LayoutEntity entity : entitiesToLayout) {
            Node2D node = entity.obj;
            node.setPosition(entity.getXInLayout(), entity.getYInLayout());
        }

        // Print possible collisions
        displayNodes(entitiesToLayout);
    }

    private void displayNodes(LayoutEntity[] all) {
        for (LayoutEntity entity : all) {
            Node2D node = entity.obj;

            Rectangle rect = new Rectangle(node.x, node.y, node.w, node.h);
            rect.setStroke(Color.BLACK);
            rect.setFill(null);

            root.getChildren().add(rect);
        }
    }

    private void randomizePositions(LayoutEntity[] entities) {
        for (LayoutEntity entity : entities) {
            entity.setLocationInLayout(randInt(0, 512), randInt(0, 512));
        }
    }

    private void collisionDetection(LayoutEntity[] entities) {
        collisionDetection(Arrays.asList(entities));
    }

    private void collisionDetection(Collection<LayoutEntity> c) {

        List<LayoutEntity> collisions = new ArrayList<>();

        for (LayoutEntity e1 : c) {
            for (LayoutEntity e2 : c) {
                if (e1 == e2)
                    continue;
                boolean collides = checkAndResolveCollision(e1, e2);
                if (collides)
                    collisions.add(e1);
            }
        }

        checkRecursively(collisions, c);
    }

    private void checkRecursively(List<LayoutEntity> collisions,
            Collection<LayoutEntity> all) {

        if (collisions.isEmpty())
            return;

        for (LayoutEntity e1 : all) {

            for (int i = 0; i < collisions.size(); i++) {

                LayoutEntity e2 = collisions.get(i);

                if (e2 == e1)
                    continue;

                boolean collides = checkAndResolveCollision(e1, e2);
                if (collides) {

                    if (collisions.contains(e1))
                        continue;

                    collisions.add(e1);

                    checkRecursively(collisions, all);
                }
            }
        }
    }

    private boolean checkAndResolveCollision(LayoutEntity e1, LayoutEntity e2) {

        Node2D n1 = e1.obj;

        // Ideally, I also want to add a gap around the boxes
        double extraSpace = 0;

        double w1 = n1.getWidth() + extraSpace * 2;
        double h1 = n1.getHeight() + extraSpace * 2;

        Rectangle2D b1 = new Rectangle2D(e1.getXInLayout() - extraSpace,
                e1.getYInLayout() - extraSpace, w1, h1);

        Node2D n2 = e2.obj;

        double w2 = n2.getWidth() + extraSpace * 2;
        double h2 = n2.getHeight() + extraSpace * 2;

        Rectangle2D b2 = new Rectangle2D(e2.getXInLayout() - extraSpace,
                e2.getYInLayout() - extraSpace, w2, h2);

        if (b1.intersects(b2)) {

            Point2D trans = getMinimumTranslation(b1, b2);

            double x = e1.getXInLayout() + trans.getX();
            double y = e1.getYInLayout() + trans.getY();

            e1.setLocationInLayout(x, y);

            return true;
        }
        return false;
    }

    private Point2D getMinimumTranslation(Rectangle2D source, Rectangle2D target) {

        double mtdx, mtdy;

        Point2D amin = new Point2D(source.getMinX(), source.getMinY());
        Point2D amax = new Point2D(source.getMaxX(), source.getMaxY());
        Point2D bmin = new Point2D(target.getMinX(), target.getMinY());
        Point2D bmax = new Point2D(target.getMaxX(), target.getMaxY());

        double left = (bmin.getX() - amax.getX());
        double right = (bmax.getX() - amin.getX());
        double top = (bmin.getY() - amax.getY());
        double bottom = (bmax.getY() - amin.getY());

        if (left > 0 || right < 0)
            return Point2D.ZERO;

        if (top > 0 || bottom < 0)
            return Point2D.ZERO;

        if (Math.abs(left) < right)
            mtdx = left;
        else
            mtdx = right;

        if (Math.abs(top) < bottom)
            mtdy = top;
        else
            mtdy = bottom;

        // zero the axis with the largest mtd value.
        if (Math.abs(mtdx) < Math.abs(mtdy))
            mtdy = 0;
        else
            mtdx = 0;

        return new Point2D(mtdx, mtdy);
    }

    private static Random rand = new Random();

    public static int randInt(int min, int max) {
        return rand.nextInt((max - min) + 1) + min;
    }
}

Answer 1

通过阅读你的代码，我可以预测的是，问题出在逻辑上。在 checkAndResolveCollision() 内，当您使用

为 Node 分配新坐标时

e1.setLocationInLayout(x, y);

您错过了检查分配给该节点的新坐标是否与我们已经针对该节点检查过的任何其他节点重叠。

您必须生成逻辑，无论何时更改节点的坐标，都必须再次针对每个其他节点进行检查

希望有帮助