Jump to content
  • Advertisement
Sign in to follow this  

[.net] Collion Detection for Game Objects

This topic is 4349 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

Question: I know that BSP/Octrees can be used to detect collisions between the player and the world, but are there any standard algorithms for detecting collisions between moving game objects? Eg.) Suppose there are 1000 players in a MMORGP. What's the best way to detect a collision between one player and the 999 others? The collision bounding area type (box/sphere) doesn't matter in this situation. I'm just looking for a quick way avoid testing collisions with characters that may be on the other side of the map.

Share this post


Link to post
Share on other sites
Advertisement
Octree is the best implementation out. It works fine for moving objects as long as the objects' containing node is updated correctly when the object moves. There is also the problem with which node to contain your object in:
a) Keep multiple instances of each object (one in each node that it "touches"). I.E. keep all objects in leaf nodes.
b) Keep each game object in the smallest node that completely contains it.

I'm not sure which of those is the best. I would presume (a), but it does seem a bit more complicated, and you can't use the octree to traverse data because it has multiple copies of each object.

If you don't want to use a space partition, the next best collision detection is bounding sphere and/or bounding boxes (axis aligned or not). The most important part is using a lot of trivial rejection. I always use the following 2: velocity - if the objects are not getting closer, there is not need to detect collision; and bounding sphere - simple distance test to determine if 2 objects are close enough to collide.

I'm using only bounding spheres right now, a hierarchy of spheres. Most objects just have a bounding sphere to check and we can get thousands of objects on the screen.

Laterz

Share this post


Link to post
Share on other sites
Thanks!

I anticipated updating the nodes everytime an object moves, but I wasn't sure if there was a work around for it. As for keeping large objects in smaller leafs, I suspect there is a lot of space overhead in keeping a copy in each leaf that it touches, especially if the object is very large and the max leaf volume is very small. If I understand correctly, the drawback of keeping large objects in nodes is that it results in more uneccessary surface checks because the partition it occupies is larger and therefore its node is more likely to be 'hit' when traversing the Octree.

I think I'll go with storing my large objects in a single node because they vary greatly in size.

Thanks again.

Share this post


Link to post
Share on other sites
Quote:
Original post by ivquatch
I suspect there is a lot of space overhead in keeping a copy in each leaf that it touches, especially if the object is very large and the max leaf volume is very small.


Well, by "store a copy", I meant keep a pointer in each node. Its not really a memory problem, just a more complex algorithm for moving game objects around.

When storing objects in just the leafes that it touches, the hard part is if the object moves, you have to know all the nodes its stored in to move all of the pointers :( I'm not sure what the best way for that is... maybe keep a list of nodes inside each game object. And the easiest part is the collision detection, you need to only test collision with all objects in each leaf node.

When storing objects in the smallest node that contains them, the downside is that its a little tricky determining which node to store the object in. Its also a little weird if your octree is symmetrical about the origin, any object at the origin will be contained by the ROOT node and checked against all other nodes... because it touches the biggest 8 nodes (all children of the root). And the collision detection is a little trickier, you just have to test against all objects in nodes above and below the object, not just the leaves.

I think the "storing in leaves only" is the best option, but I can't say that I've done it before. I did, however, make an octree that dynamically subdivided sections that had clusters of objects... and quickly realized that it had virtually NO application in the real world :(
Anyways, I suggest not taking my word too much, do some research. I've seen a few papers online. Make sure you search for octree and octtree. I wish someone would tell me the correct spelling.
Haha.

Cheers.

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!