Return to Answer

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 will work better. To make things faster maybe your zones are only xZones. 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.

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.

*** 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 will work better. To make things faster maybe your zones are only xZones. 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.

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 Andon said.

By I add to that - sort the objects. Give each zone a number. In my example below: zoneNum = xZone * 20 + yZone.

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.

int x=CheckFirstBlueIndex
Do while done==false
    if blue[x].zoneNum > CheckLastZone then done=true;
    checkBlueCollisionForIndex(x);
    x++;
end do loop

The above would check everything from 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.

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

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.

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.

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.

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.