1
\$\begingroup\$

I am optimizing my "little" Java (LibGDX) shooter game, and perhaps unsurprisingly, collision detection is a "bottleneck"; I've kind of reached my performance goals already, but I want to tweak the game anyways.

Every monster in the game can collide with every other monster + friendly bullets. The game is a single-screen shooter. I am using a QuadTree.

In my Sprite/Entity-class, I have a method:

public boolean canCollideWith(Sprite s) {
    return true;
}

This method is called twice in a loop within a loop, meaning that when enough Sprites are added, it gets called a lot. It shows up as a high HotSpot in VisualVM.

I override the method in various sub-classes, e.g. in the Bullet-class:

@Override
public boolean canCollideWith(Entity e) {
    if (friendly) {
        return (e instanceof Monster && !(e instanceof Player))
                        || e instanceof Missile;
    }
    else
        return e instanceof Player || e instanceof Warp;
}

...and in the Monster-class:

public boolean canCollideWith(Entity e) {
    return e instanceof Bullet && ((Bullet) e).isFriendly() || e instanceof Monster || e instanceof Tagger || e instanceof Flower || e instanceof Shockwave;
}

I don't really like these instanceof's in the first place... what would be an elegant and a fast solution to optimize this (hopefully both :)?

Excluding the QuadTree part, here's my whole collision detection method:

public static void collisionDetection(Array<? extends Sprite> sprites) {
        for (int i = 0; i < sprites.size; i++) {

            Sprite s1 = sprites.get(i);

            if (!s1.isCollidable()) continue;

            for (int k = i + 1; k < sprites.size; k++) {

                Sprite s2 = sprites.get(k);

                if (s1 == s2) continue;

                if (!s2.isCollidable()) continue;

                if (!s1.canCollideWith(s2)) continue;
                if (!s2.canCollideWith(s1)) continue;

                boolean intersects = s1.intersects(s2);

                if (intersects) {
                    s1.fireIntersectionEvent(s2);
                    s2.fireIntersectionEvent(s1);

                    s1.intersectsWith(s2);
                    s2.intersectsWith(s1);
                }
            }
        }
    }

Thanks for any ideas.

\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

The most effective way to improve collision check speed is to decrease the number of entities that needs to be checked against. Spatial partitioning such as octree helps but you can make further improvements.

Suppose if currently you have one big list of collidables contains objects and bullets and in each collision check step you are looping through all the objects (ignore spatial partitioning for now) and you are interested in finding out whether objects and bullets collide. Bullets and bullets do not collide. If that is the case, then there is no need for bullets to be included in the collidables list. Applying this strategy, you would create 2 object groups, bullets and objects.

In each step for objects:

- update new position
- add to collidables list
- check for collisions
- resolve

In each step for bullets:

- update new position
- check for collisions
- resolve

Assuming you have equal number of bullets to objects ( most games have far more bullets than objects ) then you would have decreased the neccesary check by a factor of 4!

Keep applying this strategy and re organize objects into groups and you should probably see a large improvement in performance.

\$\endgroup\$
1
  • \$\begingroup\$ Great answer, I believe this is the 'ultimate' way to improve the performance, I shall definitely do this. By the way, I also got a big boost simply by replacing the instanceof's with a BitSet (and not using polymorphism at all in canCollideWith()). \$\endgroup\$ Dec 16, 2014 at 10:48
1
\$\begingroup\$

Your canCollideWith method should be so that s1.canCollideWith(s2) == s2.canCollideWith(s1)I think. If not it means that collision will differ according to your array order. And if both return the same results you can test that only once.

Then in your code, you give two differents definitions of your canCollideWith method canCollideWith(Sprite) and canCollideWith(Entity), so when you call your canCollideWith method with a sprite, I think it won't call the method with an entity passed and it will always return true.

\$\endgroup\$
1
  • \$\begingroup\$ I actually ended up removing the second canCollideWith() from the collisionDetection() altogether, and it now checks a "BitSet" this way: public boolean canCollideWith(Entity e) { return ((rawCollisionBits & (1L << e.type)) != 0) || ((e.rawCollisionBits & (1L << type)) != 0); } I can see that the code I posted earlier could be a little misleading.. I have an Entity-class which extends Sprite, and in it, I override the canCollideWith(Sprite s) - to call canCollideWith(Entity e) simply by casting the Sprite to Entity. \$\endgroup\$ Dec 16, 2014 at 11:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .