0
\$\begingroup\$

I am developping a spaceinvader-like game. There comes the problem of how to handle collision detection.

At first I was doing like that :

forEach(fireBall : fireBalls) {
    forEach(stormTrooper : stormTroopers) {
        if (collides(fireBall, stormTrooper)) {
             // Explode

But then when playing I had the feeling the game was slowing down at some point, and I tought it had something to do with the multiple elements and the double loop.

So I tried to break the loops whenever I had the chance, changing the forEach loops to for loops at the same time :

for (var i = 0; i < fireBalls.length; i++) {
     if (stormTroopers.length > 0 && fireBalls[i].y > stormTroopers[0].y) {
          break;
     }
     for (var j = 0; j < stormTroopers.length; j++) {
         if (fireBalls[i].y > (stormTroopers[j].y + 31)) {
             break;
         }

If the fireball isn't on the same "y" as any stormtrooper, the fireballs following are not going to be either, so no need to check. Same for the stormtroopers loop. This works only if the list is ordered, meaning the first stormTrooper of the list has the highest "y" value.

The problem in my game is that all stormTroopers don't have the same speed, so I need to sort the list each time.

This leads to my question : in order to enhance the performance, I tried to break the loops, but for that I had to add a new operation : sort the list of the stormTrooper. Is it worth it?

\$\endgroup\$
2
  • \$\begingroup\$ I would recommend using a quadtree instead. Check this wiki page for more info: en.m.wikipedia.org/wiki/Quadtree \$\endgroup\$
    – Anton D
    Dec 21, 2014 at 17:46
  • \$\begingroup\$ 'I tought it had something to do with' ... Use a profiler (In Chrome you have one), so you'll know for sure who's the culprit. \$\endgroup\$ Dec 22, 2014 at 10:51

2 Answers 2

1
\$\begingroup\$

To know if its worth it profile the collision loop and see if its faster after your changes.

For sorting, a bubble or insertion sort will be faster than a quick sort if you reuse the same mostly-sorted array every frames.

Quick sort is only faster if the list is completely random, for mostly-sorted lists you're better off with an improved bubble (insertion) sort as most of the time your stormTroopers will still be in the proper order the next frame.

You can probably keep your fireballs sorted as well in reverse order, especially if they all move at the same speed. You'll only have to check the overlap.

Because everything moves at roughly the same speed in roughly the same direction full blown quadtrees might be overkill. The quadtree maintenance itself could become more intensive than the cost of plain Y-ranged, Y-sorted collision.

You can also do a pseudo-binary search (warmer - colder) in your sorted arrays on the Ys as the next fireball will be close to the previous one it can help skipping to a relevant stormTroopers, then scan forward AND backward in the stormTroopers array until you're outside the Y range in both directions, start scanning stormtroopers from the range's proper extremity for the next fireball.

By sorting both fireballs and stormtroopers, checking only the overlap, and ranged scanning on every iteration it can end up faster than maintaining a quadtree.

With this you can also try sorting them in X, the sorted & ranged scanning will cause your two inner loops (backward and forward scan) to do very few iterations as it will resume the inner-scan from the values found in the previous outer iteration.

\$\endgroup\$
2
  • \$\begingroup\$ I second this approach. Also you should probably profile first to determine if the slowdown is actually caused by collision detection. In a simple game such as invaders, it is likely even a naive brute force n^2 strategy would be fast enough. \$\endgroup\$
    – user55564
    Dec 22, 2014 at 0:39
  • \$\begingroup\$ Thank you for actually answering the question and not just redirect me towards QuadTree :) I also thought QuadTree was overkill as the game is mainly axed on the y-axis. I will look into profiling. \$\endgroup\$ Dec 22, 2014 at 11:13
2
\$\begingroup\$

You've inadvertently come across a form of broad-phase collision culling. Specifically, sort and sweep!

Why not go all the way and use a QuadTree instead? Quadtrees recursively subdivide the space into quadrants, and only check collisions between entities which occupy the same quadrant. You can speed up your collision detections exponentially this way, with just a bit of mental overhead.

\$\endgroup\$
1
  • \$\begingroup\$ To be honnest I saw this QuadTree while browsing the forum for similar problem, but I didn't really get into it. I will have another look :) \$\endgroup\$ Dec 21, 2014 at 19:12

You must log in to answer this question.

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