Hi everyone, i was just wondering if there is a performance difference between testing a few objects against many, or testing many objects against a few, in terms of performance. for example: say i have a game, there are 100 bullets, and only 5 enemies. would it be better to: A: starting with the first bullet, iterate through the 5 enemies to see if there is a hit, then move onto the next bullet. B: starting with the first enemy, iterate trough the 100 bullets and then move onto the next enemy. I have a feeling it would be better to test a few against the many (option B), but that is just an (un)educated guess. Could somebody enlighten me a little on the subject. More specifically: would there be any difference? if so, which one is best? if so again, how much of a difference would it make? and for bonus points, a brief explanation of why it does/doesn't make the difference. thanks for your time guys and gals! :D

thanks for the reply Joel.

I know the example i used was pretty basic. I was just using it to set the scene. :D

The issue doesnt really have anything to do with my project or anything i'm coding at the moment, it was just something my brain stumbled upon while thinking about something. I am aware that there are many better ways to improve the efficiency of the scenario, its just something i was interested in finding out about.

I'd test bullets to enemies.

To me, it's a matter of data encapsulation.

A common issue with games is having fast moving objects such as bullets move "through" the things they're supposed to hit. Imagine your enemy has a bounding box of 5x5pixels, and your bullet's is 1x1 pixel. If the bullet was moving 20pixels each frame, it could potentially pass right over an enemy and its bounding box completely. If the bullet moves fast enough it's possible it could pass over multiple enemies. It is therefore important for the bullet to know if it is "close" to an enemy or enemies. And, if the bullet determines it will "pass over" multiple enemies, it must determine which one gets hit first.

It should be up to the bullet to determine which enemy it hits. The bullet should do the math and figure out which entity will get hit first.

If enemies were in charge of collision, the enemy would first have to figure out if a bullet is going to hit it, then it would have to talk to other enemies and figure out if others could get hit. THEN the enemy would have to figure out which one gets hit first.

very good points from everyone, thanks for all your replies. I'm not trying to code this, or use it in a game scenario, its just a trivial curiosity I found myself thinking about.

i suspect if there was any difference between 'many against few' and 'few against many' it would be a very small difference anyway. (perhaps the difference would scale with the amount of tests being done, e.g. 5 enemies and 1 million bullets would be more noticeable)

thanks again everyone, if anyone else has any nuggets of wisdom please feel free to fuel my thirst for seemingly useless information! :D

Doing it the brute force way you need to do (NumberOfBullets * NumberOfPlayer / 2) tests, regardless of the order.
For a small number of objects this is fine, for many more objects some sort of culling is needed.

I'm using a lazy Aabb-tree in my engine.
Here are some test exe's.
Be aware that the fps is quite bad, mostly thanks to the slow/bad drawing of my debug objects.
The interseting numbers are the "Update took" and "Query took" counter, they are all in micro seconds (10e-6).

Press and hold the right mouse button to activate mouse look. W/A/S/D to move around (or arrows).
Press space to start/pause animation.
Press T to toggle tree hierarchy view on/off.

* FrustumTest_10000.exe, shows 10000 aabb's that moves around (Update took), aabb's that are within one of the three "frustums" are solid (Query took).
Tetrahedral frustums performs similar (just to lazy to draw them :)

* OverlapTest_2500.exe, shows 2500 aabb's that moves around (Update took), aabb's that overlaps ANY other aabb are solid (Query took).
Using bruteforce this would require over 3 million aabb vs aabb tests.
The tests takes about 12ms on my machine = 60+ fps.

* SimpleFrustumTest_16.exe, shows 16 aabb's that moves around (Update took), aabb's that overlaps the frustum (cube) are solid (Query took).
This sample is basicly where you'd like to hit T to see how the tree is created/modified.

I don't remember the hardware requirements for these demos, it's DX9 and uses SSE anyway.

Also note that the code isn't super optimized, but a rather flexible templated class.
You could probably optimize it a bit more by removing some templating stuff.

Your question is a good one, particularly because its nature eliminates spatial partitioning as a viable 'algorithmic' advantage (100 bullets dynamically traversing huge distances are hard to partition efficiently!)

Generally I design my algorithms as if, eventually, I will write them in assembly (many times I don't, but often enough I do). That means thinking ahead about doing many things at the same time, where many means 4 or 8 or 12, etc. Therefore, I would choose to test many bullets at a time against one object.

It probably wouldn't make much difference in C code, but with SIMD it makes all the difference in the world. And an O(mn) collision algorithm is probably a good one to convert to SIMD, but maybe not. The profiler knows best :)

I'd have to have the problem domain phrased more precisely to give you a better answer (probably the answer would be the same, but the justification would be better).

thanks ajas95, i think you understood what i was trying to find out about. Its a theoretical sort of "who would win in a fight between Batman and Spiderman" kind of question, i think some other people missed that.

silverphyre673, i tend to disagree. sure, 5*100 == 100*5 but thats sort of missing the point. In the inner working of the compiler, language and CPU, it could make a bit difference. I say it 'could' make a difference, since that is what im trying to find out. Good point about enemies being damaged/killed etc, and therefore removed from the test, but I'm kind of assuming the conditions of the iterations will remain constant.

And finally eq, despite being quite far from what i was expecting, your reply will probably come in very handy. I'll be sure to check out your little demo test thing.

Thanks again everyone! :D