how fast is collision detection? faster than you may think!

Hey everyone,

Lets say you have a player object and 10,000 enemies. The player is red. All but one enemy is red. If the enemy is red it can hurt the player.

If an enemy is red and overlaps the player, then the player dies.

But in what order should you check? You could first compare variables, or you could compare collisions.

If you compare colors first, you narrow the sellected enemies down to 1. That means you only run around 60 collision checks per second. Not bad right?

If you compare is ghost overlapping player first, you have to have thousands of collision checks... and then check the few that returned if they are the right color. That sounds bad right?

Well, as it turns out, testing for collisions first in this case is the most efficient thing to do. It is twice as efficient as doing it the other way. It's always a good idea to make little tests and compare the results side by side if you are having performance problems. The simple order of conditions can change alot, and often times our initial assumptions can be wrong. When you compare collisions first you have an advantage in that most of the work is occurring at a lower, very optimized level. Collision detection in construct has been optimized in significant ways including a broad phase check that eliminates most objects before even getting to the actual overlap test. However, comparing the variables at the event level has the additional overhead of the event system, and is more or less brute forcing its way to victory.

Most games of course, wouldn't need 10,000 enemies at once. and of course there are things you could do quite easilly to reduce the variable check and collision check, simply by replacing the red ghost with a different object when it turns red and then checking against that object instead of all the ghosts...

Anyway, I thought it was an interesting test and shared.

Anyone else have any surprising results, or oh duh moments in the realm of c2 development?

We need to go deeper.

You tried enemy overlaps player, but did you try player overlaps enemy?

Then how about on collision?

Could we get an official explanation as to why this is the case? Is it simply an outlier based on scalability? Optimising is already hard enough without being forced to consider methods that seem illogical - it hurts my poor non-programmer brain

newt - The condition Is "player overlapping enemy", is 400% faster than "is Enemy Overlapping player "

Good call on bringing that one up. I just tested using the same conditions and all (10,000 enemies). The results make sense, I think. In the case of the "is Enemy overlapping player", I believe the collision detection runs out and fetches the objects within the grid the enemy is occupying. For each enemy object, which increases overhead. In the case of the player overlapping enemy case, Since there is only one player, it only has to go through this process once. Keep in mind, my explanation is complete conjecture as I don't have access to how broad and narrow phase collision detection works in construct. I'm just going of what I know about collision detection in general.

The cool thing is that the SOL is the same regardless of the order of operations.

My conclusion is that when testing overlaps, use the object that you believe to be fewer of... IE is player overlapping bullets, rather than the other way around.

Could we get an official explanation as to why this is the case? Is it simply an outlier based on scalability? Optimising is already hard enough without being forced to consider methods that seem illogical - it hurts my poor non-programmer brain

I think the biggest moral of the story is to:

1. Never optimize unless there is a reason. Code should be reasonable and readable. If you find you are not meeting your performance goals and benchmarks, then identify areas of performance bottle necking.

2. When optimizing, never make assumptions. In many cases, for whatever reason, an certain way of coding may seem easier to humans but slows the computer down. Most tests like the one I made can be set up in a blank project in a few minutes. At that point, it's setting up an experiment. make sure you follow good science.

Most of the time you really needn't worry about this sort of thing though, and it can become a productivity bottleneck pretty quickly. Remember, part of making a game efficient is doing so efficiently and optimizing can be a waste of time where it is not needed.

You could, in theory, do a .count < or > to determine which way to do the picking I guess.

Luckily logic is a pretty good indicator of how to proceed, I do suggest more experimentation however.

Is overlapping at offset for example.

newt - The run-time function to test an overlap between two polygons always gets passed offset parameters for x and y. When you test overlap it just sends 0 and 0 for offset x and y. Those offsets get added to the quads points regardless of whether they are 0 or not. Basically an offset test is the same as a regular test as far as the runtime goes.