Collision detection using boolean arrays?

Question

I'm currently trying to write a collision detection method for a 2D game and I'm stuck.

The intersects() method is called by the player passing the enemy, and the coordinates of the player and enemy. An ImageMask object has a 2 dimentional boolean array corresponding to the mask of the sprite. The masks are scaled 4 times because the sprites are 16x16 and scaled up to 64x64 in the game.

public boolean intersects(ImageMask other, int tx, int ty, int ox, int oy) {
    boolean[][] otherMask = other.getMask();
    if ((tx+mask.length*4<ox)         // This checks if the sprites
            || ty+mask[0].length*4<oy // aren't close to each other.
            || ox+otherMask.length*4<tx
            || oy+otherMask[0].length*4<ty)
        return false;

    //This stuff isn't working.
    for (int i=0;i<mask.length;i++) {
        for (int j=0;j<mask[i].length;j++) {
            for (int k=0;k<otherMask.length;k++) {
                for (int l=0;l<otherMask[k].length;l++) {
                    if ((tx+i*4)<=(ox+k*4) && (tx+i*4+4)>=(ox+k*4)
                            && (ty+j*4)<=(oy+l*4) && (ty+j*4+4)>=(oy+l*4+2)
                            && mask[i][j] && otherMask[k][l]) {
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

This isn't working very well; sometimes it works as expected, but sometimes it reports collisions when the entities aren't touching, or fails to do so when the entities are on top of each other. How should I fix this to make collision detection work?

I'm not entirely sure what's going on here, but the quadruple nested for loops are most likely going to be a problem. — Madison May
I optimized it, but then it didn't work so I simplified it. The for loops iterate through each boolean in both of the arrays xD. — Anubian Noob
@MadisonMay I don't think the nested loops are a problem. They might look intimidating, but really, it's quite easy to look at them and see that they are correct. The only real alternative is to use a recursive function, but that has its own complexity that makes it hard to read. The problem likely lies in the complicated IF statement, not the loops. Either that or he's passing in bad values to begin with. — torbinsky
@AnubianNoob I would suggest verifying your IF statement logic using some unit tests. Draw out a bunch of overlap scenarios and then set up unit tests for each one, ignoring the looping part. Just statically define your tx, ox, etc... variables to match a specific boundary condition and make sure they give you the answer you expect. In fact, I would suggest refactoring your "intersects" method into one or two more methods. Especially that if statement. Break it out into its own static function or method so that you can simplify the variables for readability. — torbinsky

Anubian Noob Anubian Noob · Accepted Answer · 2014-01-02T01:39:47

The if statement should read

if ((tx+i*4)<=(ox+k*4+4) && (tx+i*4+4)>=(ox+k*4)
        && (ty+j*4)<=(oy+l*4+4) && (ty+j*4+4)>=(oy+l*4+2)
        && mask[i][j] && otherMask[k][l])

Also, looking at the rest of the project, you messed up x and y when initializing the ImageMask.

Collision detection using boolean arrays?

1 Answers