Orginizing/Optimising my collision detection setup

Question

I'm creating a 2D tile based platformer with AABB (Axis aligned bounding boxes), and it works, I just want to organize and optimize my setup. Here are methods in my player class and entity class that are relevant to the collision. How could I make this better? I'm harshly looking at that public boolean[] method, but I cant figure out another way without using state.

AbstractEntity.java

public boolean[] getCornersAreSolid(double x, double y) {
    int leftTile = (int)(x / Tile.SIZE);
    int rightTile = (int)((x + this.collisionBox.getWidth()) / Tile.SIZE);
    int topTile = (int)(y / Tile.SIZE);
    int bottomTile = (int)((y + this.collisionBox.getHeight()) / Tile.SIZE);

    boolean topLeft;
    boolean topRight;
    boolean bottomLeft;
    boolean bottomRight;

    if(leftTile < 0 || leftTile >= map.getWidth() || topTile < 0 || topTile >= map.getHeight())
        topLeft = false;
    else
        topLeft = map.getTileAt(leftTile, topTile).getAttribute(Attribute.SOLID);
    if(rightTile < 0 || rightTile >= map.getWidth() || topTile < 0 || topTile >= map.getHeight())
        topRight = false;
    else
        topRight = map.getTileAt(rightTile, topTile).getAttribute(Attribute.SOLID);
    if(leftTile < 0 || leftTile >= map.getWidth() || bottomTile < 0 || bottomTile >= map.getHeight())
        bottomLeft = false;
    else
        bottomLeft  = map.getTileAt(leftTile, bottomTile).getAttribute(Attribute.SOLID);
    if(rightTile < 0 || rightTile >= map.getWidth() || bottomTile < 0 || bottomTile >= map.getHeight())
        bottomRight = false;
    else
        bottomRight = map.getTileAt(rightTile, bottomTile).getAttribute(Attribute.SOLID);

    return new boolean[]{topLeft, topRight, bottomLeft, bottomRight};
}
/*
 * @return next position
 */
public Vec2D getNextPosition() {

    int currCol = (int)getX() / Tile.SIZE;
    int currRow = (int)getY() / Tile.SIZE;

    double xdest = getX() + this.velocity.x;
    double ydest = getY() + this.velocity.y;

    double xtemp = getX();
    double ytemp = getY();

    boolean[] corners = getCornersAreSolid(getX(), ydest);
    boolean topLeft = corners[0];
    boolean topRight = corners[1];
    boolean bottomLeft = corners[2];
    boolean bottomRight = corners[3];

    if(this.velocity.y < 0) {
        if(topLeft || topRight) {
            this.velocity.y = 0;
            ytemp = currRow * Tile.SIZE;
        }
        else {
            ytemp += this.velocity.y;
        }
    }
    else if(this.velocity.y > 0) {
        if(bottomLeft || bottomRight) {
            this.velocity.y = 0;
            ytemp = (currRow + 1) * Tile.SIZE - this.collisionBox.getHeight() % Tile.SIZE - 1 ;
        }
        else {
            ytemp += this.velocity.y;
        }
    }

    corners = getCornersAreSolid(xdest, getY());
    topLeft = corners[0];
    topRight = corners[1];
    bottomLeft = corners[2];
    bottomRight = corners[3];
    if(this.velocity.x < 0) {
        if(topLeft || bottomLeft) {
            this.velocity.x = 0;
            xtemp = currCol * Tile.SIZE;
        }
        else {
            xtemp += this.velocity.x;
        }
    }
    if(this.velocity.x > 0) {
        if(topRight || bottomRight) {
            this.velocity.x = 0;
            xtemp = (currCol + 1) * Tile.SIZE - this.collisionBox.getWidth() % Tile.SIZE -1 ;
        }
        else {
            xtemp += this.velocity.x;
        }
    }
    return new Vec2D(xtemp, ytemp);
}

PlayerEntity.java extends Abstract Entity

@Override
public void update() {
    this.setPosition(this.getNextPosition());
    if(this.movingLeft)
        this.velocity.x = -WALK_SPEED;
    if(!this.movingLeft && this.velocity.x < 0)
        this.velocity.x *= COEF_FRIC;

    if(this.movingRight)
        this.velocity.x = WALK_SPEED;
    if(!this.movingRight && this.velocity.x > 0)
        this.velocity.x *= COEF_FRIC;

    animations.update();
}
@Override
public void keyPressed(KeyEvent e) {
    switch(e.getKeyCode()){
        case KeyEvent.VK_A:
            this.movingLeft = true;
            break;
        case KeyEvent.VK_D:
            this.movingRight = true;
            break;
        case KeyEvent.VK_W:
            this.velocity.y = -5;
            break;
    }
}

@Override
public void keyReleased(KeyEvent e) {
    switch(e.getKeyCode()){
        case KeyEvent.VK_A:
            this.movingLeft = false;
            break;
        case KeyEvent.VK_D:
            this.movingRight = false;
            break;
    }
}

Answer 1

You play around with different ordering (depending on you data) it may be faster to check absolutes first, or last.

if(leftTile < 0 || leftTile >= map.getWidth() || topTile < 0 ||....

can become

if(leftTile < 0 || topTile < 0 || leftTile >= map.getWidth()...

Also, notice that you throw away half your answers after a fast check, plenty of room for improvement.

 if(this.velocity.y < 0) { ...

Depending on how many objects versus tiles you have or if the collision map is static, consider rendering the collision map to a array to eliminate lookup overhead

You are creating a new Vec2d at the end of each test, you can reuse a object or just set the result where it belongs.

This is just suggestions, always benchmark. Always.

Answer 2

I bet you could cut your code in half here, since you do a lot of things twice, just in a slightly modified way. That's a a good indication that you're not writing things as modular as you could. There's also a lot of code duplication static analysis tools out there that can help you out because you're only causing yourself more work in these cases. Especially when you decide to change just one tiny thing...

getCornersAreSolid()

I immediately question why you're returning a boolean array. My fear that you're storing the result of the four corners in it soon realizes itself. In my own personal opinion, there are few uses for raw arrays anymore, since they just open the door to a world of index out of bounds exceptions. Consider a new small class that communicates all of this in a semantic way. corners[0] means nothing unless you trace through all the code. solidCorners.isSolid(Direction.TOP_LEFT) is clear without any further explanation (though I admit better variable names could be used).

int leftTile = (int)(x / Tile.SIZE);

This is just a personal point of mine, but why not add a space between (int) and the rest? When I read this, or if(leftTile < 0 ||...., I think why are you writing codewithnospacesbetweenyourwords? Again, highly personal and stylistic, so don't take too seriously.

boolean topLeft;
boolean topRight;
boolean bottomLeft;
boolean bottomRight;

These are all set by default to false, though it wouldn't be a bad idea to make it explicit:

boolean topLeft = false;
boolean topRight = false;
boolean bottomLeft = false;
boolean bottomRight = false;

so that when you see

if(leftTile < 0 || leftTile >= map.getWidth() || topTile < 0 || topTile >= map.getHeight())
    topLeft = false;
else
    topLeft = map.getTileAt(leftTile, topTile).getAttribute(Attribute.SOLID);

you ask yourself why you might be setting these variables to false twice.

This can be replaced with

if(leftTile >= 0 && leftTile < map.getWidth() && topTile >= 0 && topTile < map.getHeight()) {
    topLeft = map.getTileAt(leftTile, topTile).getAttribute(Attribute.SOLID);
}

Here, I removed the first condition, since that is covered by the default boolean variable initialization value, and applied DeMorgan's law to the inverse of it to check only the else case.

Also note the use of curly braces. There's no reason to ever write a control statement without them. That is,

if(leftTile < 0 || leftTile >= map.getWidth() || topTile < 0 || topTile >= map.getHeight())
    topLeft = false;
else
    topLeft = map.getTileAt(leftTile, topTile).getAttribute(Attribute.SOLID);

should always be written as

if(leftTile < 0 || leftTile >= map.getWidth() || topTile < 0 || topTile >= map.getHeight()) {
    topLeft = false;
}
else {
    topLeft = map.getTileAt(leftTile, topTile).getAttribute(Attribute.SOLID);
}

(or whatever your preference of block placement.) White space is free, so don't be frugal.

And as was alluding to at the start, you have the exact same code here repeated four times, with only the parameters changing. Why not just add a method:

private boolean hasAttribute(YourMapClass map, Attribute attribute, int tileY, int tileX) {
  boolean result = false;

  if (tileX >= 0 && tileX < map.getWidth() && tileY >= 0 && tileY < map.getHeight()) {
    result = map.getTileAt(tileX, tileY).isAttribute(attribute);
  }

  return result;
}

Notice that this method can be used for any attribute, and with this,

boolean topLeft;
boolean topRight;
boolean bottomLeft;
boolean bottomRight;

if(leftTile < 0 || leftTile >= map.getWidth() || topTile < 0 || topTile >= map.getHeight())
    topLeft = false;
else
    topLeft = map.getTileAt(leftTile, topTile).getAttribute(Attribute.SOLID);
if(rightTile < 0 || rightTile >= map.getWidth() || topTile < 0 || topTile >= map.getHeight())
    topRight = false;
else
    topRight = map.getTileAt(rightTile, topTile).getAttribute(Attribute.SOLID);
if(leftTile < 0 || leftTile >= map.getWidth() || bottomTile < 0 || bottomTile >= map.getHeight())
    bottomLeft = false;
else
    bottomLeft  = map.getTileAt(leftTile, bottomTile).getAttribute(Attribute.SOLID);
if(rightTile < 0 || rightTile >= map.getWidth() || bottomTile < 0 || bottomTile >= map.getHeight())
    bottomRight = false;
else
    bottomRight = map.getTileAt(rightTile, bottomTile).getAttribute(Attribute.SOLID);

can be simplified to

boolean topLeft = hasAttribute(map, Attribute.Solid, topTile, leftTile);
boolean topRight = hasAttribute(map, Attribute.Solid, topTile, rightTile);
boolean bottomLeft = hasAttribute(map, Attribute.Solid, bottomTile, leftTile);
boolean bottomRight = hasAttribute(map, Attribute.Solid, bottomTile, rightTile);

getNextPosition()

double xdest = getX() + this.velocity.x;

This doesn't follow stand Java camel case, and should be

double xDest = getX() + this.velocity.x;

or better

double destX = getX() + this.velocity.x;

I also wouldn't be suggest using the this qualifier here. I know IDEs will automatically put that in wherever they can, but really the only time I feel you need to is in a case like

final int bar;

public Foo(int bar) {
    this.bar = bar;
}

Couple lines down,

double xtemp = getX();
double ytemp = getY();

Same comments about the naming. More importantly though, something smells here because immediately after this you work with those terrifying arrays I mentioned at the start, and then have this:

if(this.velocity.y < 0) {
    if(topLeft || topRight) {
        this.velocity.y = 0;
        ytemp = currRow * Tile.SIZE;
    }
    else {
        ytemp += this.velocity.y;
    }
}
else if(this.velocity.y > 0) {
    if(bottomLeft || bottomRight) {
        this.velocity.y = 0;
        ytemp = (currRow + 1) * Tile.SIZE - this.collisionBox.getHeight() % Tile.SIZE - 1 ;
    }
    else {
        ytemp += this.velocity.y;
    }
}

And the fact that you do this again for the horizontal case should scream out that you should introduce a new method.

There's a a lot of things going on in this block, including the modification of public variables in another object (gasp!). You can perform all of this in a new method that you reuse again below for the horizontal case. This would be even easier if you use a new class to hold the directional boolean values as I metioned earlier.

Answer 3

Forgive me if I get the syntax wrong, I'm not really a Java programmer, but I have a suggestion that might help.

The first thing I would do to get rid of the array of booleans is create a class that represents what they are.

class SolidCorners
{
    boolean topLeft;
    boolean topRight;
    boolean bottomLeft;
    boolean bottomRight;
}

Doing this make's all of the other code simpler and more readable because it becomes self documenting. For example, getCornersAreSolid method becomes:

public SolidCorners getCornersAreSolid(double x, double y) {
    int leftTile = (int)(x / Tile.SIZE);
    int rightTile = (int)((x + this.collisionBox.getWidth()) / Tile.SIZE);
    int topTile = (int)(y / Tile.SIZE);
    int bottomTile = (int)((y + this.collisionBox.getHeight()) / Tile.SIZE);

    SolidCorners corners;

    if(leftTile < 0 || leftTile >= map.getWidth() || topTile < 0 || topTile >= map.getHeight())
        corners.topLeft = false;
    else
        corners.topLeft = map.getTileAt(leftTile, topTile).getAttribute(Attribute.SOLID);

    // and so on..

    return corners;
}

And when you use the method you don't need to know the correct index positions in the array..

corners = getCornersAreSolid(xdest, getY());
//topLeft = corners[0];
//topRight = corners[1];
//bottomLeft = corners[2];
//bottomRight = corners[3];

if(corners.topLeft || corners.bottomLeft) {

Creating an extra class up front may feel like more work, but usually it turns out to be less in the long run.