0
\$\begingroup\$

I'm making a simple 2D game engine, and to make collision detection more effective I tried making a QuadTree class. I don't know if this will work, but that's not that important. You don't have to waste Your time testing it, but I would like to know if this is an efficient design in terms of logic, especially the update() method altough I made it so this method is only called when at least one of the objects is moved.

The classes Handler, CollideableObject and GameObject are not necessary for this class, but I put them here for context's sake.

I'm happy to hear any oppinion and see any modification, so feel free to use this code and / or modify it in any way.

Sorry if my english description and my code is hard to understand, I'm still a beginner.

The code:

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;
    }

}

Thanks for Your time!

\$\endgroup\$
1
\$\begingroup\$

Something I would immediately recommend from looking at your code is that you should not put random whitespace in your code. Whenever you space out random parts, you should ensure you do so with good reason - such as splitting up various logical parts of your codebase.

Also, you want to avoid writing code like this

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

Having too many characters in one line makes it hard to decipher what a particular line of code is doing.

If you instead used whitespace and braces, you could make it easier for someone viewing to be able to tell exactly what is happening specifically inside the for loop without having to scroll from left to right to see the code more clearly.

Please let me know if you have any other questions. Thank you.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.