Quad Tree and Collision Detection Implementation

Question

I have an implementation of a quad tree and abstract collision detection classes. The code works but looks very ugly, but I don't know what I could change to make it better.

The reason I used two interfaces instead of just extending an abstract class is because the classes which will use this are render objects and have to extend RenderObject. This is a thing I don't want to change because RenderObject doesn't have to be a collision instance every time.

The Quad Tree:

package de.skysoldier.headsoccer.physics2d;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;
import org.lwjgl.util.vector.Vector2f;
import de.skysoldier.headsoccer.CollisionInstance;
public class QuadTree {
 public static final int MAX_DEPTH = 4;
 public static final int MIN_ITEMS = 2;
 public static final int MAX_ITEMS = 10;
 private int depth;
 private int objectCount;
 private Vector2f minCorner;
 private Vector2f maxCorner;
 private Vector2f center;
 private QuadTree parent;
 private ArrayList<QuadTree> children;
 private ArrayList<CollisionInstance> collisionInstanceList;
 public QuadTree(Vector2f minCorner, Vector2f maxCorner){
 this(0, minCorner, maxCorner, null); 
 }
 public QuadTree(int depth, Vector2f minCorner, Vector2f maxCorner, QuadTree parent){
 this.minCorner = minCorner;
 this.maxCorner = maxCorner;
 this.center = new Vector2f(minCorner.x + 0.5f * (maxCorner.x - minCorner.x), minCorner.y + 0.5f * (maxCorner.y - minCorner.y));
 this.depth = depth;
 this.parent = parent;
 collisionInstanceList = new ArrayList<>();
 }
 public QuadTree(int depth, float minx, float miny, float maxx, float maxy, QuadTree parent){
 this(depth, new Vector2f(minx, miny), new Vector2f(maxx, maxy), parent);
 }
 private int getQuadrandIndex(CollisionInstance collisionInstance){
 AABB aabb = collisionInstance.getCollideable().getAabb();
 int quadrandPositionX = aabb.getMinCorner().x > center.x ? 1 : (aabb.getMaxCorner().x < center.x ? 0 : -1); //1: right | 0: left
 int quadrandPositionY = aabb.getMinCorner().y > center.y ? 1 : (aabb.getMaxCorner().y < center.y ? 0 : -1); //1: top | 0: bottom
 return quadrandPositionX < 0 || quadrandPositionY < 0 ? -1 : 2 * quadrandPositionX + quadrandPositionY;
 }
 public void add(CollisionInstance CollisionInstance){
 objectCount++;
 if(objectCount > MAX_ITEMS && !hasChildren() && depth < MAX_DEPTH) createChildren();
 int quadrandIndex = -1;
 if(hasChildren() && (quadrandIndex = getQuadrandIndex(CollisionInstance)) >= 0){
 children.get(quadrandIndex).add(CollisionInstance);
 }
 else collisionInstanceList.add(CollisionInstance);
 }
 public void remove(CollisionInstance CollisionInstance){
 objectCount--;
 if(objectCount < MIN_ITEMS && hasChildren()) releaseChildren();
 int quadrandIndex = -1;
 if(hasChildren() && (quadrandIndex = getQuadrandIndex(CollisionInstance)) >= 0){
 children.get(quadrandIndex).remove(CollisionInstance);
 }
 else collisionInstanceList.remove(CollisionInstance);
 }
 public boolean hasChildren(){
 return children != null;
 }
 private void createChildren(){
 children = new ArrayList<>();
 children.add(new QuadTree(depth + 1, minCorner.x, minCorner.y, center.x, center.y, this)); //bottom left
 children.add(new QuadTree(depth + 1, minCorner.x, center.y, center.x, maxCorner.y, this)); //top left
 children.add(new QuadTree(depth + 1, center.x, minCorner.y, maxCorner.x, center.y, this)); //bottom right
 children.add(new QuadTree(depth + 1, center.x, center.y, maxCorner.x, maxCorner.y, this)); //top right
 ArrayList<CollisionInstance> collisionInstanceCopys = new ArrayList<>();
 collisionInstanceCopys.addAll(collisionInstanceList);
 collisionInstanceList.clear();
 objectCount -= collisionInstanceCopys.size();
 Iterator<CollisionInstance> iterator = collisionInstanceCopys.iterator();
 while(iterator.hasNext()){
 add(iterator.next());
 }
 }
 private void releaseChildren(){
 collisionInstanceList.addAll(collectCollisionInstances(false));
 children = null;
 }
 public String toString(){
 StringBuilder builder = new StringBuilder();
 builder.append(tabString(depth, "[QT depth: " + depth + ", num: " + objectCount + "] " + collisionInstanceList));
 builder.append("\n");
 if(hasChildren()){
 for(QuadTree qt : children) builder.append(qt);
 }
 return builder.toString();
 }
 public Vector2f getMinCorner(){
 return minCorner;
 }
 public Vector2f getMaxCorner(){
 return maxCorner;
 }
 public static String tabString(int depth, String appendix){
 StringBuilder builder = new StringBuilder();
 for(int i = 0; i < depth; i++) builder.append(" ");
 if(appendix != null) builder.append(appendix);
 return builder.toString();
 }
 public QuadTree getParent(){
 return parent;
 }
 private ArrayList<CollisionInstance> getPossibleCollisions(ArrayList<CollisionInstance> collisions){
 ArrayList<CollisionInstance> subList = collectCollisionInstances(false);
 ListIterator<CollisionInstance> iterator1 = collisionInstanceList.listIterator();
 while(iterator1.hasNext()){
 CollisionInstance collisionInstance1 = iterator1.next();
 ListIterator<CollisionInstance> iterator2 = collisionInstanceList.listIterator(iterator1.nextIndex());
 while(iterator2.hasNext()){
 collisions.add(collisionInstance1);
 collisions.add(iterator2.next());
 }
 for(CollisionInstance collisionInstance2 : subList){
 collisions.add(collisionInstance1);
 collisions.add(collisionInstance2);
 }
 }
 if(hasChildren()){
 for(QuadTree tree : children){
 tree.getPossibleCollisions(collisions);
 }
 }
 return collisions;
 }
 public ArrayList<CollisionInstance> getPossibleCollisions(){
 ArrayList<CollisionInstance> collisions = new ArrayList<>();
 getPossibleCollisions(collisions);
 return collisions;
 }
 private ArrayList<CollisionInstance> collectCollisionInstances(boolean addSelf){
 ArrayList<CollisionInstance> collisionInstances = new ArrayList<>();
 collectCollisionInstances(addSelf, collisionInstances);
 return collisionInstances;
 }
 private void collectCollisionInstances(boolean addSelf, ArrayList<CollisionInstance> collisionInstances){
 if(addSelf) collisionInstances.addAll(collisionInstanceList);
 if(hasChildren()){
 for(QuadTree tree : children){
 tree.collectCollisionInstances(true, collisionInstances);
 }
 }
 }
}

The AABB class:

package de.skysoldier.headsoccer.physics2d;
import org.lwjgl.util.vector.Vector2f;
import org.lwjgl.util.vector.Vector3f;
public class AABB {
 private Vector3f minCorner;
 private Vector3f maxCorner;
 private Vector3f center;
 public AABB(){
 this(new Vector3f(), new Vector3f());
 }
 public AABB(Vector2f minCorner, Vector2f maxCorner){
 this(new Vector3f(minCorner.x, minCorner.y, 0), new Vector3f(maxCorner.x, maxCorner.y, 0));
 }
 public AABB(Vector3f minCorner, Vector3f maxCorner){
 this.minCorner = minCorner;
 this.maxCorner = maxCorner;
 calcCenter();
 }
 public void calcCenter(){
 center = new Vector3f(
 minCorner.x + 0.5f * (maxCorner.x - minCorner.x), 
 minCorner.y + 0.5f * (maxCorner.y - minCorner.y), 
 minCorner.z + 0.5f * (maxCorner.z - minCorner.z));
 }
 public Vector3f getMinCorner(){
 return minCorner;
 }
 public Vector3f getMaxCorner(){
 return maxCorner;
 }
 public Vector3f getCenter(){
 return center;
 }
 public String toString(){
 return "[AABB: min(" + minCorner.x + "|" + minCorner.y + "), ctr(" + center.x + "|" + center.y + "), max(" + maxCorner.x + "|" + maxCorner.y + ")]";
 }
}

Collision Instance:

package de.skysoldier.headsoccer;
import de.skysoldier.headsoccer.physics2d.Collideable;
import de.skysoldier.headsoccer.physics2d.CollisionListener;
public interface CollisionInstance {
 Collideable getCollideable();
 CollisionListener getCollisionListener();
}

Collideable:

package de.skysoldier.headsoccer.physics2d;
import org.lwjgl.util.vector.Vector3f;
public interface Collideable {
 AABB getAabb();
 boolean basicCollision(Collideable collideable);
 boolean collision(Collideable collideable);
 boolean contains(Vector3f point);
}

Abstract implementation of collideable:

package de.skysoldier.headsoccer.physics2d;
public abstract class AbstractCollideable implements Collideable {
 private AABB aabb;
 public AbstractCollideable(AABB aabb){
 this.aabb = aabb;
 }
 public AABB getAabb(){
 return aabb;
 }
 public boolean basicCollision(Collideable collideable){
 AABB aabb1 = getAabb();
 AABB aabb2 = collideable.getAabb();
 return !(aabb2.getMinCorner().y > aabb1.getMaxCorner().y || aabb2.getMaxCorner().y < aabb1.getMinCorner().y || aabb2.getMaxCorner().x < aabb1.getMinCorner().x || aabb2.getMinCorner().x > aabb1.getMaxCorner().x);
 }
 public abstract boolean collision(Collideable collisionInstance);
}

cubical collideable:

package de.skysoldier.headsoccer.physics2d;
import org.lwjgl.util.vector.Vector3f;
public class CubicalCollideable extends AbstractCollideable {
 public CubicalCollideable(AABB aabb){
 super(aabb);
 }
 public boolean collision(Collideable collideable){
 if(collideable instanceof CircularCollideable) return collideable.collision(this);
 return basicCollision(collideable);
 }
 public boolean contains(Vector3f point){
 AABB aabb = getAabb();
 return point.x >= aabb.getMinCorner().x && point.x <= aabb.getMaxCorner().x && point.y >= aabb.getMinCorner().y && point.y <= aabb.getMaxCorner().y;
 }
}

circular collideable:

package de.skysoldier.headsoccer.physics2d;
import org.lwjgl.util.vector.Vector3f;
public class CircularCollideable extends AbstractCollideable {
 private float radius;
 public CircularCollideable(float radius){
 super(new AABB(new Vector3f(), new Vector3f()));
 this.radius = radius;
 }
 public float getRadius(){
 return radius;
 }
 public boolean collision(Collideable collideable){
 if(collideable instanceof CircularCollideable){
 Vector3f center2 = collideable.getAabb().getCenter();
 Vector3f center1 = getAabb().getCenter();
 float a = Math.abs(center2.x - center1.x);
 float b = Math.abs(center2.y - center1.y);
 float maxDistance = getRadius() + ((CircularCollideable) collideable).getRadius();
 return a * a + b * b < maxDistance * maxDistance;
 }
 else if(collideable instanceof CubicalCollideable){
 CubicalCollideable cubical = (CubicalCollideable) collideable;
 if(cubical.basicCollision(this)){
 return true;
 }
 else {
 Vector3f v1 = cubical.getAabb().getMinCorner();
 Vector3f v2 = cubical.getAabb().getMaxCorner();
 Vector3f v3 = new Vector3f(v1.x, v2.y, 0);
 Vector3f v4 = new Vector3f(v1.y, v2.x, 0);
 float radiusSquared = radius * radius;
 return distanceSquared(v1) <= radiusSquared || 
 distanceSquared(v2) <= radiusSquared ||
 distanceSquared(v3) <= radiusSquared ||
 distanceSquared(v4) <= radiusSquared;
 }
 }
 return false;
 }
 public float distanceSquared(Vector3f point){
 float dx = Math.abs(point.x - getAabb().getCenter().x);
 float dy = Math.abs(point.y - getAabb().getCenter().y);
 return dx * dx + dy * dy;
 }
 public boolean contains(Vector3f point){
 return false;
 }
}

Example usage class:

class TestObject extends AGLRenderObject implements CollisionInstance, CollisionListener {
 private Collideable collideable;
 public TestObject(){
 //super constructor and stuff
 //collideable = ...;
 }
 @Override
 public void collisionResponse(CollisionInstance collisionInstance){
 // TODO Auto-generated method stub
 }
 @Override
 public Collideable getCollideable(){
 // TODO Auto-generated method stub
 return collideable;
 }
 @Override
 public CollisionListener getCollisionListener(){
 // TODO Auto-generated method stub
 return this;
 }
 }

Answer 1

I suggest the following changes to make the code more readable:

Avoid long expressions in return statements

E.g., instead of this: return !(aabb2.getMinCorner().y > aabb1.getMaxCorner().y || aabb2.getMaxCorner().y < aabb1.getMinCorner().y || aabb2.getMaxCorner().x < aabb1.getMinCorner().x || aabb2.getMinCorner().x > aabb1.getMaxCorner().x);

You could write something like this:

boolean outsideY1 = aabb2.getMinCorner().y > aabb1.getMaxCorner().y;
boolean outsideY2 = aabb2.getMaxCorner().y < aabb1.getMinCorner().y;
boolean outsideX1 = aabb2.getMaxCorner().x < aabb1.getMinCorner().x;
boolean outsideX2 = aabb2.getMinCorner().x > aabb1.getMaxCorner().x;
return !(outsideY1 || outsideY2 || outsideX1 || outsideX2);

Note, that by choosing descriptive names (I'm not sure if I got the intent right, feel free to change them), the code becomes easier to understand. Besides, it is also easier to debug: you can see which component returns true/false. There are another few places, where return expression could be split up in a similar way.

Capitalizing

Follow the Java conventions, and start variable names with small letter, instead of capital letter. E.g. change this: public void add(CollisionInstance CollisionInstance) to this: public void add(CollisionInstance collisionInstance)

Single return point in functions

E.g. in CircularCollideable.collision, you could store the return value in a variable, and return it at the end of the function, instead of having more return points, i.e. something like this:

public boolean collision(Collideable collideable){
 boolean ret = false;
 if(collideable instanceof CircularCollideable){
 // ... snip
 ret = a * a + b * b < maxDistance * maxDistance;
 }
 else if(collideable instanceof CubicalCollideable){
 CubicalCollideable cubical = (CubicalCollideable) collideable;
 if(cubical.basicCollision(this)){
 ret = true;
 }
 else {
 // ... snip
 // also consider splitting the expression :)
 ret = distanceSquared(v1) <= radiusSquared || 
 distanceSquared(v2) <= radiusSquared ||
 distanceSquared(v3) <= radiusSquared ||
 distanceSquared(v4) <= radiusSquared;
 }
 }
 return ret;
}

While there are varying opinions, on whether single return point is a good pattern or not (see e.g. this question), in your case, it would be a good choice, since the function is already split up into more if/else branches. The advantage of this change is, that it makes the code easier to debug (you can set one single break point, and check the return value there).

On a side note: you might want to refactor your code in a way, that large if/else constructs with instanceof's are avoided (especially if you will have many types of collideables). While I can't suggest any better example, you could have a look at the Visitor Pattern for a starting point.

Make methods private

I'm referring to CircularCollideable.distanceSquared(). This method is only used within its class, so it would be better to make it private. This also helps a lot in understandability of the code, especially if you are developing with an IDE, that will visually mark private/public methods in a different way.

• T_01: thank you for this useful improvement suggestions. I'll try to clean up the code, and take care of this things