Tuesday, May 30, 2017

optimization - Does it matter who does the collision detection?


I gave an answer to How to decide which GameObject should handle the collision?, and received a lot of negative feedback on it, claiming that it does not matter who does the collision detection. I am not understanding that stance.


For example:


There are 100 bullets and 1 player on the screen. Let's assume brute force collision detection and no optimization such as layers or references.


If the collision detection is done by the bullet, each bullet must detect for collision on 100 different objects. That's 100 x 100 detections, for 10000 detections total.


If the player does the detection, that's 100 detections total, one for each bullet.



Am I mistaken? If so, what am I missing?



Answer



It does not matter in general.


Your examples aren't exactly fair. Your "player does collision" check looks like this:


for each player:
for each bullet:
if player.intersects(bullet), report it

Your "bullet does collision" check looks like this:


for each bullet:

for each other object in the world:
if bullet.intersects(object), report it

Yes, in that case, the first example is definitely better. It will execute 100 times, whereas the second example executes 10,000 times. A more fair example would be for each bullet, for each player for the second case, which will also loop 100 times. If the first example is allowed to take advantage of the fact that system has individual lists of types and that bullets don't need to test against other bullets, why is the second not?


Most general-purpose collision systems don't operate like that because they don't have the foreknowledge of the system required by your first example, and because to build it out could be expensive in terms of memory, and not always a computational win. Doing so means you need to store collision properties in separate arrays for each type of object that can interact, or otherwise similarly manage and configure different blocks of collision data and iterate them possibly several times at different times in the update loop and it can quickly become a cumbersome and potentially cache-unfriendly mess. There are scenarios where such a specialized collision handling structure could be advantageous over other methods. But they are specialized scenarios.


In general collision handling works by looking at N objects and (modulo various optimizations for spatial organization, preventing duplicate checks in a given frame, et cetera), tests them all against each other, blindly firing out notifications to any interested party that "these two things hit each other, do something about it if you want."


No comments:

Post a Comment

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...