How to optimize collision detection

Question

I am developing a 2D Java Game with LibGDX. This is what it kinda looks like (simplified):

The big black circle is the player, which you can move by tilting the smartphone. The red circles and blue rectangles are enemies, which will move from the right of the screen to the left. The player has to avoid crashing into them.

Right now I am checking in the Game Loop every enemy against the player, whether they collide or not. This seems kinda inefficient to me, but I don't know how to improve it.

I have tried the Quadtree approach, but it did not really work. The player could easily glitch through enemies and the collision was not detected. Unfortunately, I have destroyed the Quadtree implementation. I used this tutorial/blog as my Quadtree implementation.

Answer 1

Andon's answer is really good. Here's another way to approach it. Which includes his method and mine.

Sorting.

For there to be a collision your black dot has to be within a range both in the x and y axis. Both. So you could have an algorithm that puts each of your red and blue dots in an xZone and a yZone. Let's say you're using coordinates of -200 to +200 on x and y. If your objects are 20 pixels wide, they have to be within so many pixels of each other in order to collide. So make your zones the size of that range. Then you know that you only have to check within 3 zones horizontally and 3 zones vertically. That's basically what And on said - although his was velocity based and mine is just zone based.

Then I add to that: sort the objects. Give each zone a number. In my example below: zoneNum = xZone * 20 + yZone. It will be different for you depending on how many zones tall and wide you decide you need. Also figuring out the xZone and yZone is a formula based on your coordinate scale and the number of zones you decide to have.

The black dot is in zone 62. Therefore you only need to check dots that are in zones 41-43, 61-63, and 81-83. When the black dot moves, create a checkFirstZone and a checkLastZone.

Then sort the array of red and blue objects by zoneNum. Or sort each category individually if they're in different arrays. You only have to do this when they move. If they don't move in your game it's only once. As you sort them though create a checkFirstBlueIndex.

When checking collisions, start at checkFirstBlueIndex and check until you're past the last zone, skipping zones that aren't needed to be checked.

int x=checkFirstBlueIndex
do while done==false
    if blue[x].zoneNum > checkLastZone or x>numberOfBlues then done=true;
    checkBlueCollisionForIndex(x);
    x++;
 end do loop

The above would check all indexes from zone 41 to 83. Which is still 48 more zones than you need to check. So based on how much speed increase you need, you could also limit it to only check those 9 zones. Math. There are simple formulas for knowing if a zone needs to be checked or not.

You could add that part to your checkBlueCollisionForIndex() function - first check if it's in a hot zone, but you'd have to test the speed on that.

One other way would be to check the 3 zones in each of the 3 lines. So you could have a zoneLineEnd which you'd set to 'checkFirstZone' plus 3. When you pass that skip to the next line. Something like this:

zoneLineEnd = checkFirstZone + 3;
x = checkFirstBlueIndex;
do while done==false;
    if blue[x].zoneNum > zoneLineEnd then done=true;
    checkBlueCollisionForIndex(x);
    x++;
end do loop
// then skip ahead until the next line start
do while blue[x].zoneNum < zoneLineEnd+18 or x>numberOfBlues
   x++;
end do loop
zoneLineEnd+=3;
// then repeat the check for the 3 zones on that line.
// then repeat the skip again and the next check.

When your black dot moves zones you do have to reset checkFirstZone, checkLastZone'. And skip ahead to find 'checkFirstBlueIndex. Add something like this before the above pseudo code.

if blackDotMoved {
    done=false;
    x=0;
    do while done==false
        if blue[x].zoneNum==checkFirstZone
            checkFirstBlueIndex = x;
            done=true;
        end if
    end do
end if

Of course when you're on the edge of the screen the zone math might wrap around and check collisions on the other side of the screen. This might not be a big deal since your collision detection will already handle that. You probably don't need to worry about checking 3 extra zones. At some level it's faster to check them than to check to see if you need to check them.

In the end though, you have to check and weigh if sorting and checking zones takes less time than just checking each dot. With a handful of dots like this, sorting probably takes longer. But with 500 dots sorting and skipping will be a big help.

In my game my ship only moves forward and my terrain is presorted by xUnit. So no matter how long my terrain is I only have to check collisions on a small set at a time. I split the world into zones and my startZoneIndex moves forward as the ship moves forward. And I only check collisions for the 3 zones ahead of that.

* UPDATE *

I just noticed that you said your enemies only move left to right. In that case you might want to make your zones go left to right instead of top to bottom. Then your sorting could work better. To make things faster I might only do xZones and then you're just checking 3 zones, but more objects since the zones are the full height. It always depends on the details of your game. But maybe once a colored dot has moved beyond the black dot you never have to check it again. Unless the black dot can zip over there. Depends on your game.

Answer 2

The easiest thing to do would be to cluster these points into a 2D grid (my brain is already hardwired to do that when I see colored squares and circles).

Determine the largest number of grid lines your player can cross in each dimension given its current velocity and then throw out any enemies that are not within +/- n-many grid lines of the player. You can do all of that with a few integer comparisons and reserve complicated tests involving floating-point arithmetic, euclidean distance, etc. for points that actually need to be tested.

Imagine drawing a bunch of evenly spaced grid lines (horizontal and vertical) through the diagram you already showed. Whenever an enemy moves, have it place itself into the appropriate grid cell; this is trivial, just divide its x,y coordinate by the distance between each grid line and throw out the fractional part. There are more sophisticated data structures you can use to further accelerate this process (e.g. kD trees, quadtrees, etc.), but what it boils down to in the end is partitioning (clustering) the enemies into groups for broad-phase rejection.

Answer 3

I was in a very similar situation not long ago and what I did was to stick to your original approach. It's far easier, but you know your needs and situation better. You do have to check collisions between the player and each obstacle, but to improve the performance you can implement a broad phase check before the actual collision check. First, you find the distance between the enemy and the character. If it's "close enough" (up to you to define what that means") then perform a collision check. Otherwise, carry on to the next enemy.

Also, you said in the comments that you set your enemies to null once they're out of the "game field". I assume you then create a new instance of an enemy when you need a new one. That's definitely going to waste a lot of time and could temporarily freeze your application during garbage collection. But you already received a suggestion to use an object pool instead. That's also what I ended up using. :)