# How to optimize collision detection

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.

• There's no other way AFAIK. Or you have a tree and check only enemies that the tree specify as near enemies, or you check for every entity. By any means, it doesn't seem like your app will suffer for performance. Bother with this only if extremely necessary. – Gustavo Maciel Jun 5 '14 at 16:14
• When you only have to check the player against all enemies, this should not be sooo much of a problem (assuming that the number of enemies is in the order of that displayed in the image). It's a simple linear search. (The situation would be different if you also wanted to detect collisions among enemies - this would be quadratic, and could become an issue). That said, considering the effort for updating data structures like quadtrees, I assume that using these will make the check slower than the simple linear search. – Marco13 Jun 5 '14 at 16:16
• @GustavoMaciel well since there can be up to 200-300 enemies, it sometimes lags. – Niklas Jun 5 '14 at 16:23
• If your game lags with 200 enemies, then your collision check is probably inefficient? Are you performing a quick broad-phase (eg. circle vs. circle test)? I think you should profile your application to figure out what portion of your code creates the lag (could be something entirely different than collision detection, like memory-allocation). – bummzack Jun 5 '14 at 18:00
• @Niklas Yes, exactly. There should be an implementation for this in libgdx called "Pool". – bummzack Jun 5 '14 at 20:06

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.

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.

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. :)