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.
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. \$\endgroup\$ – Gustavo Maciel Jun 5 '14 at 16:14