Jump to content
  • Advertisement
Sign in to follow this  
Multiverse

Collision efficiency question

This topic is 4847 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
If I'm wrong, someone please correct me :-)

I believe it doesn't make a difference either way because the same work is being done, just in a different order.

If you want to improve efficiency in such an algorithm, you need to find ways to do less work because the ways you mention will not scale to high volume (ie. it's basically brute force).

One approach to take would be to someone partition your game area into some sort of tree structure. That way, you can avoid collision tests on enemys that don't even have a bullet near them.

edit: quick google search found this article ... didn't read it so I don't know if it's any good, but the description sounded good:
http://www.heroicvirtuecreations.com/QuadTree.html

Share this post


Link to post
Share on other sites
Its just a guess, but I think the only differences would come from cache performance. I think in option A you would have more cache hits with the 5 enemies.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Well, 5 * 100 == 100 * 5, so if you were just checking integers, it wouldn't make a difference. However, if an enemy is going to be killed after a few bullet hits, then you can remove him from consideration (unless corpses stop bullets) if you deal the damage as you go, and remove bullets and targets as you go, you can make it a bit faster. If an enemy gets killed after the first 5 bullets, you don't need to test the other 95, unless his corpse stops them.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!