Java Slick 2D Collision Detection Methodology

Question

I have a collision detection for terrain setup (non-terrain is handled with a quadtree I implemented apart from this) and I was wondering how others have done it compared to mine and what I could learn from people's critiques here.

My map is stored in a 2D array of "GameSquare"s

public class GameSquare extends GameObject {
    private char tileLetter = 'W';
    private int row, col;
}
public boolean isPassable() {
    return tileLetter != 'W';
}

The row and col are the index in the 2D array.

The char corresponds to the graphic, my render checks the char and draws a Wall(W), Floor(O), or Door(X)

The Player
My player class gets track of the player in pixels. The speed and X,Y positions are all in exact pixels. I divide those measures by the width or height of the tile graphics I use and truncate it; in order to find the corresponding array cell that the player is in. In order to do collision detection I wrote a method that takes a cardinal direction, the players current collision box, and a distance which is usually their speed.
The cardinal direction is an enum that has methods for the adjX and adjY.
For example; East would return adjX() = 1 and adjY() = 0 whereas
SouthEast would return adjX() = 1 and adjY() = 1 <-- Positive because this is the movement in a 2D array.

The Collision Check

public int canMove(Direction dir, Rectangle collisionBox, int distance) {       
    int goodToGo = 0;
    // Check each 'step' of our attempted movement from 1 - distance(ie speed)
    for(int i = 1; i <= distance; i++) {
        // Assemble suggested new position bounds to check, ie corners of suggested movement    
        HashSet<Vector2f> cornerPoints = new HashSet<Vector2f>();
        cornerPoints.add( new Vector2f(collisionBox.getMinX()+dir.adjX()*i, collisionBox.getMinY()+dir.adjY()*i) );
        cornerPoints.add( new Vector2f(collisionBox.getMaxX()+dir.adjX()*i, collisionBox.getMinY()+dir.adjY()*i) );
        cornerPoints.add( new Vector2f(collisionBox.getMinX()+dir.adjX()*i, collisionBox.getMaxY()+dir.adjY()*i) );
        cornerPoints.add( new Vector2f(collisionBox.getMaxX()+dir.adjX()*i, collisionBox.getMaxY()+dir.adjY()*i) );

        // Check each corner of this step
        for( Vector2f point : cornerPoints ) {
            // Out of bounds check
            if( point.y < 0 || point.y > this.dungeonHeight*ratioRow ||
                    point.x < 0 || point.x > this.dungeonWidth*ratioCol ) {
                return goodToGo;
            }

            // Figure out what map square this point falls on
            int checkX = (int) (point.x / ratioCol);
            int checkY = (int) (point.y / ratioRow);

            // If that's a wall square... no go, we're done here, return the number of steps that
            // were OKed so far
            if( this.dungeon[checkY][checkX].getTileLetter('W') ) {
                return goodToGo;
            }
        }
        // If this step, i, didn't have any conflicts on any of the proposed new corners, then
        // increment our ongoing count of how many steps are OK to take
        goodToGo++;
    }
    return goodToGo;
}

I know blocks of code are kind of a bitch but any feedback or just shared attempts at 2D collision detection in Slick/Java are very appreciated.

Answer 1

That really looks quite slow.

First of, don't use HashSet in these situations. A HashSet is a HashMap with "blind" values - like using the key as a value, too. They guarantee uniqueness and fast access (as everyone knows!), but for a set of four objects in a tight and often called loop, you are really hurting performance - the creation overhead is far too high and lookup speed isn't that great.

Next, you should probably change your usage pattern. Don't store distances in int if everything else is float. Same goes the other way around - the conversion between int and float is not free and you should avoid it in code that has to be really fast.

It looks like you never use fractional values and always integers - even in your floats - so you probaly think you can get away with them. They are used as painting positions for the tiles anyway.

Still, even for pixel-precise games, as soon as you change to float, everything starts to get smoother. Because you get sub-pixel movements, which wouldn't be possible for int. You can't display them, but they still affect percieved smoothness. I'd go for float, always keep positional data as floats and only convert to int when I need it to draw stuff.

Next, you can use a vastly better collision check method.

Vastly better in most cases as least. If every object is rectangular, you'd be ok with your way - but there's a lot of conditionals involved and you end up with code like this:

if (!(a.maxY < b.minY || a.minY > b.maxY)) blocked = true; ....

The other (better) way:

Use bounding circles. For each object, you store float x, y, boundsRadius; - the center and the distance to the entities point with the largest distance from the center.

Then... pythagoras (a*a + b*b = c*c)! For entities e1 and e2:

public static boolean maybeCollision(Entity e1, Entity e2) {
    float xDistance = e1.x - e2.x,
          yDistance = e1.y - e2.y,
          rSum      = e1.boundsRadius + e2.boundsRadius
    ;
    return xDistance * xDistance + yDistance * yDistance < rSum * rSum;
}

It's like calculating the distance - Math.sqrt(dx * dx + dy * dy) - but we don't use square root (which is on the slow side) and square the sum of the radius instead. You can use float or int - it doesn't matter as long as there is no overflow. Just change the local variables.

I really love how it's totally independend of the orientation of the objects towards each other - you don't need any ifs, the square of the distance automatically makes the result positive and it just works.

Here, I call the method maybeCollision (and that's a bad name, as it's not a verb. Still fits!) because you still have to check per pixel - it sees anything inside of the circle as a collision. But it's lightning fast and you have to check with bounding boxes, too (as long as you don't write Tetris or a round-based Minecraft)...