自更新QuadTree

Question

我正在制作一个简单的2D游戏引擎，为了使碰撞检测更加有效，我尝试了一个QuadTree类。我不知道这是否管用，但这没那么重要。您不必浪费时间来测试它，但是我想知道这在逻辑方面是否是一个有效的设计，特别是我做的update()方法，所以这个方法只有在至少一个对象被移动时才会被调用。

这个类不需要类Handler、CollideableObject和GameObject，但为了上下文起见，我将它们放在这里。

我很高兴听到任何oppinion和任何修改，所以请随意使用这段代码和/或以任何方式修改它。

对不起，如果我的英文描述和我的代码很难理解，我仍然是一个初学者。

守则：

import java.awt.Rectangle;
import java.util.LinkedList;

/**
 * 
 * This class is not independent, the minimum requirements to use it are the classes {@link Handler}, {@link GameObject} and {@link CollideableObject}. 
 * <br> <br>
 * This class is optional, and is only adviced to use when the amount of collision detections reach an inefficient number.
 * The class increases performacne by placing each object in the parameter handler by sorting them into a hierachical system in wich specific nodes can hold an added amount of objects.
 * These nodes automatically split if the amount reaches the chosen amount.
 * <br> <br>
 * Keep in mind that this class supports objects with 2D qualities
 * 
 * @see {@link Handler}, {@link GameObject}, {@link CollideableObject}, {@link ObservableList}
 * @version 1.0 
 * @author Kristóf Bácskai
 *
 */

public class QuadTree {

    private class QuadTreeNode extends QuadTree {

        private final QuadTree parent;

        public QuadTreeNode(QuadTree parent, int objectCap, double x, double y) {
            super(parent.getHandler(), objectCap, x, y, parent.getWidth() / 2, parent.getHeight() / 2);

            this.parent = parent;

        }

        public final QuadTree getParent() {
            return parent;
        }

    }

    private final Handler handler; //This object is not important for this 
    class, but as you can see in later on it contains a list of all the 
    objects in the game.

    private int objectCap;

    private final QuadTreeNode[] nodes;

    protected final LinkedList<CollideableObject> objects; // The type 
    ColliedeableObject has an x, y value and a java.awt.Shape object as a 
    hitbox

    protected final double x, y, width, height;

    private boolean isSplit;

    /**
     * @param handler used as source of processable objects 
     * @param objectCap the amount of objects in a single node before 
     splitting it
     * @param width of node
     * @param height height of node
     * 
     * @author Bácskai Kristóf
     * 
     */

    public QuadTree(Handler handler, int objectCap, double width, double height) {

        if (handler.equals(null)) throw new IllegalArgumentException("Handler can't be null");

        if (objectCap < 2) throw new IllegalArgumentException("Object cap has to be above 1");

        if (width < 1 || height < 1) throw new IllegalArgumentException("Width and height values have to be greater than 1");

        this.handler = handler;
        this.objectCap = objectCap;

        x = 0;
        y = 0;

        this.width = width;
        this.height = height;

        isSplit = false;

        nodes = new QuadTreeNode[4];

        objects = new LinkedList<CollideableObject>();

    }

    protected QuadTree(Handler handler, int objectCap, double x, double y, double width, double height) {

        if (handler.equals(null)) throw new IllegalArgumentException("Handler can't be null");

        if (objectCap < 2) throw new IllegalArgumentException("Object cap has to be above 1");

        if (width < 1 || height < 1) throw new IllegalArgumentException("Width and height values have to be greater than 1");

        this.handler = handler;
        this.objectCap = objectCap;

        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;

        nodes = new QuadTreeNode[4];

        objects = new LinkedList<CollideableObject>();

    }

    public final void update() {

        for (CollideableObject object : objects) if (!handler.getObjects().contains(object)) remove(object);

        for (QuadTreeNode node : nodes) {

            for (CollideableObject object : objects) {

                if (!handler.getObjects().contains(object)) remove(object);

                if (node.getObjects().contains(object) && !object.getHitbox().intersects(node.getBounds())) node.remove(object);

            }

            if (node.getObjects().size() >= node.getObjectCap()) node.split();

            if (node.getObjects().size() < node.getObjectCap()) node.mergeChildren();

        }

        if (!isSplit) return;

        for (QuadTreeNode node : nodes) {

            node.update();

        }

    }

    public final void insert(CollideableObject object) {

        objects.add(object);

        for (QuadTreeNode node : nodes) {

            if (object.getHitbox().intersects(node.getBounds())) node.insert(object);

        }

    }

    public final void remove(CollideableObject object) {

        objects.remove(object);

        for (QuadTreeNode node : nodes) {

            if (node.objects.remove(object)) node.remove(object);

        }

    }

    protected final void split() {

        nodes[0] = new QuadTreeNode(this, getObjectCap(), 0, 0);
        nodes[1] = new QuadTreeNode(this, getObjectCap(), getWidth() / 2, 0);
        nodes[2] = new QuadTreeNode(this, getObjectCap(), 0, getHeight() / 2);
        nodes[3] = new QuadTreeNode(this, getObjectCap(), getWidth() / 2, getHeight() / 2);

        for (QuadTreeNode node : nodes) {

            for (CollideableObject object : objects)
                if (object.getHitbox().intersects(node.getBounds())) node.insert(object);

        }

        isSplit = true;

    }

    protected final void mergeChildren() {

        for (int i = 0; i < nodes.length; i++) nodes[i] = null;

        isSplit = false;

    }

    public final LinkedList<CollideableObject> getObjects() {
        return (LinkedList<CollideableObject>) objects.clone();
    }

    public final Handler getHandler() {
        return handler;
    }

    public final int getObjectCap() {
        return objectCap;
    }

    public final void setObjectCap(int objectCap) {
        this.objectCap = objectCap;
    }

    public final double getWidth() {
        return width;
    }

    public final double getHeight() {
        return height;
    }

    public Rectangle.Double getBounds() {
        return new Rectangle.Double(0, 0, width, height);
    }

    public boolean isSplit() {
        return isSplit;
    }

}

CollideableObject.java：

import static com.bacskai.game_engine.tools.Tools.areIntersecting;

import java.awt.Point;
import java.awt.Shape;
import java.util.LinkedList;

public abstract class CollideableObject extends GameObject {

    private Shape hitbox;

    public CollideableObject(int x, int y, Shape hitbox) {
        super(x, y);

        this.hitbox = hitbox;

    }

    public CollideableObject(int x, int y, int velX, int velY, Shape hitbox) {
        super(x, y, velX, velY);

        this.hitbox = hitbox;

    }

    public final void basicTick() {
        super.basicTick();

        if (checkCollisions()) eventsInLastTick.add(ObjectEvent.Collided);

    }

    public abstract void collide(CollideableObject objects);

    protected boolean checkCollisions() {

        boolean collided = false;

        LinkedList<CollideableObject> likelyCollisions = new LinkedList<CollideableObject>();

        likelyCollisions.remove(this);

        for (CollideableObject object : likelyCollisions) {

            if (areIntersecting(object.getHitbox(), getHitbox())) {

    /*
    The areIntersecting(Shape hitbox1, Shape hitbox2) method:

        public static boolean areIntersecting(Shape shape, Shape shape2) {
            Area area = new Area(shape);
            area.intersect(new Area(shape2));
            return !area.isEmpty();
        }

    */
                collide(object);

                collided = true;

            }

        }

        return collided;

    }

    public Point getLocation() {
        return new Point(getX(), getY());
    }

    public Shape getHitbox() {
        return hitbox;
    }

    public final void setHitbox(Shape value) {
        hitbox = value;
    }

}

GameObject.java：

import java.awt.Graphics;
import java.util.LinkedList;

public abstract class GameObject {

    private Handler handler;

    private int x, y, velX, velY;

    protected final LinkedList<ObjectEvent> eventsInLastTick;

    public GameObject(int x, int y) {

        this.x = x;
        this.y = y;

        eventsInLastTick = new LinkedList<ObjectEvent>();

    }

    public GameObject(int x, int y, int velX, int velY) {

        this.x = x;
        this.y = y;
        this.velX = velX;
        this.velY = velY;

        eventsInLastTick = new LinkedList<ObjectEvent>();

    }

    protected void basicTick() {

        x += velX;
        y += velY;

        if (velX != 0 || velY != 0) eventsInLastTick.add(ObjectEvent.Moved);

    }

    public abstract void tick();

    public void render(Graphics g) {}

    public Handler getHandler() {
        return handler;
    }

    public void setHandler(Handler handler) {
        this.handler = handler;
    }

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }

    public int getVelX() {
        return velX;
    }

    public void setVelX(int velX) {
        this.velX = velX;
    }

    public int getVelY() {
        return velY;
    }

    public void setVelY(int velY) {
        this.velY = velY;
    }

    public final LinkedList<ObjectEvent> getEventsInLastTick() {
        return eventsInLastTick;
    }

    protected final void clearEvents() {
        eventsInLastTick.clear();
    }

}

Handler.java：

import java.awt.Graphics;
import java.awt.image.BufferedImage;
import java.util.LinkedList;

public abstract class Handler {

    private final LinkedList<GameObject> objects;

    private QuadTree quadTree;

    public Handler() {

        objects = new LinkedList<GameObject>();

    }

    public Handler(QuadTree quadTree) {

        objects = new LinkedList<GameObject>();

        this.quadTree = quadTree;

    }

    public abstract void handleEvent(GameObject object, ObjectEvent events);

    private final void handleEvents(GameObject object) {

        for (ObjectEvent event : object.getEventsInLastTick()) {

            if (object.getClass().isInstance(event.getObjectType())) handleEvent(object, event);
            else throw new ClassCastException("Event" + event.name() + " is undefinded for the type " + object.getClass());

        }

    }

    public final void tickAll() {

        for (GameObject object : objects) {

            object.tick();

            handleEvents(object);

            object.clearEvents();

        }

    }

    public final void renderAll(Graphics g) {

        for (GameObject object : objects) {

            object.render(g);

        }

    }

    public final BufferedImage renderAll(BufferedImage image) {

        BufferedImage dest = image;

        Graphics g = dest.getGraphics();

        for (GameObject object : objects) {

            object.render(g);

        }

        g.dispose();

        return dest;

    }

    public final void addObject(GameObject object) {

        if (objects.contains(object)) throw new IllegalArgumentException("This object is already added to this handler");

        object.setHandler(this);

        objects.add(object);

        if (!quadTree.equals(null) && object instanceof CollideableObject) quadTree.insert((CollideableObject) object);

    }

    public final void removeObject(GameObject object) {

        object.setHandler(null);

        objects.remove(object);

        if (!quadTree.equals(null) && object instanceof CollideableObject) quadTree.remove((CollideableObject) object);

    }

    public final LinkedList<GameObject> getObjects() {
        return (LinkedList<GameObject>) objects.clone();
    }

    public final QuadTree getQuadTree() {
        return quadTree;
    }

    public final void setQuadTree(QuadTree quadTree) {

        if (!(quadTree.equals(null) && quadTree.getHandler().equals(this))) throw new IllegalArgumentException("The parameter QuadTree must have it's handler set to this");

        this.quadTree = quadTree;

    }

}

ObjectEvent.java：

public enum ObjectEvent {

    Moved(GameObject.class),
    Collided(CollideableObject.class);

    private Class<?> objType;

    private ObjectEvent(Class<?> objType) {

        this.objType = objType;

    }

    public Class<?> getObjectType() {
        return objType;
    }

}

耽误您时间，实在对不起!

Answer 1

在查看代码时，我立即建议您不要在代码中添加随机空格。无论何时，当您分配随机部分时，您都应该确保这样做是有充分理由的--比如拆分代码库中的各个逻辑部分。

此外，您还希望避免编写这样的代码

for (CollideableObject object : objects) if (!handler.getObjects().contains(object)) remove(object);

在一行中有太多的字符使得很难理解特定的代码行在做什么。

如果使用空格和大括号，则可以使查看的人更容易准确地知道for循环中具体发生了什么，而不必从左到右滚动以更清楚地看到代码。

如果你还有其他问题，请告诉我。谢谢。