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!
