LibGDX - Collision detection between all bullets and all enemies

Question

I'm trying to make a collision detection system between the player's bullets and all the enemies on screen.

So far I had something like this:

for (Bullet bullet : hero.getPistols().getAllShotBullets()) {
        for (Enemy enemy : enemies) {
            if (!enemy.isDead()) {
                if (bullet.overlaps(bullet.getBounds(), enemy.getBounds())) {
                    enemy.die();
                }
            }
        }
    }

But after a while, the frame rate drastically drops - making the game unplayable, almost (which is understandable, as the nested for loop looks terrible for performance...). I've been looking around and found out that a common solution is to use Quad-Trees, but at the same time, I'm worried that the overhead brought by the use of that data structure will make it a bit of an overkill, if that makes sense.

Are there any more solutions? Or should I use the Quad-Tree?

Thanks in advance.

Answer 1

The algorithm you are using right now has a runtime of O( n^2 ). A tree structures can help you get that runtime lowered. Quadtrees have O( log(n) ) From that you can calculate if you will benefit from a quadtree.

Answer 2

A grid. Implementation is more simple and often times superior in performance.

Edit: Hu, why the downvotes? This was more of a follow up info to the accepted answer. The OP asked for alternatives. You can find grid vs. quadtree discussions everywhere. Bottom line is a quadtree doesn't deliver a better performance (often times it's slower) than a simple grid unless you have many objects of varying size.