1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
-2
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Could you expand on that? One-line answers tend to be deleted because they don't bring anything tangible to the table. \$\endgroup\$ – Vaillancourt Jun 22 '16 at 11:16
  • \$\begingroup\$ The OP asked for more solutions to his spatial partitioning problem. Not to explain them. \$\endgroup\$ – tym0r Jun 23 '16 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.