7
\$\begingroup\$

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;
        }
    }
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ thank you for this useful improvement suggestions. I'll try to clean up the code, and take care of this things \$\endgroup\$ – T_01 Apr 4 '15 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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