I am trying to write a collision detection system for my game and the only way I can see this working is if I check every object in a scene for a collision every time I call the update function. I don't really want to do this because it seem inefficient to me. Is this really that bad of an Idea? Is there a better way? Am I just stupid?
I am using XNA 4.0
thanks in advance,
Dartos
Is it wise to check all objects in a given state for collision every cycle?
I'm also coming up on this problem soon.
Only way I can think of doing it is declaring a counter variable. Each update increment the counter by 1 until it hits lets say 5 where we rest it back to 0. Certain objects absolutely required to be updated such as player and bullets you update every time the update function is called. Other objects such as crates only update if count = 1, enemies might only be updates on counts 2 and 4. Backgrounds on count 0.
I've not put this into practise yet so someone with more XNA experience than me might want to say yay or nay to that plan.
Only way I can think of doing it is declaring a counter variable. Each update increment the counter by 1 until it hits lets say 5 where we rest it back to 0. Certain objects absolutely required to be updated such as player and bullets you update every time the update function is called. Other objects such as crates only update if count = 1, enemies might only be updates on counts 2 and 4. Backgrounds on count 0.
I've not put this into practise yet so someone with more XNA experience than me might want to say yay or nay to that plan.
All moving objects have to check for collisions against nearby objects.
Store your objects in a tree structure based on location and you can avoid even looking at objects that are far away.
For 2D games a quadtree tends to be fairly efficient (it also works well for 3D games if the world is reasonably flat) , you could also look at octrees or bsp trees.
Store your objects in a tree structure based on location and you can avoid even looking at objects that are far away.
For 2D games a quadtree tends to be fairly efficient (it also works well for 3D games if the world is reasonably flat) , you could also look at octrees or bsp trees.
Author
Store your objects in a tree structure based on location and you can avoid even looking at objects that are far away.
I am not that familiar with tree structures. Can you provide some explanation or direct me toward some documentation?
You've got three types of tree structures (more correctly, spatial partitioning structures) to go look up:
- Quadtrees
- Octrees
- BSP trees
There are also KD-trees which might be useful depending on your game. Wikipedia has in-depth explanations of all of them :-)
- Quadtrees
- Octrees
- BSP trees
There are also KD-trees which might be useful depending on your game. Wikipedia has in-depth explanations of all of them :-)
Im not too sure about implementing trees to prioritise collision detection, but what I will say is on an update, first check if the triggering object is moving or has moved. If true, then do a collision detection. This should cut down processing for stationary objects like barells, while constantly checking things like bullets. However if the barrel is moved at some point, then you would do collision detection for it to make sure it doesnt clip a wall for example.
6677's suggestion to check for collision on every Nth update is very risky. If you check for a collision on a bullet on every 5th update for example, then the bullet could have passed through a very thin wall in the time between every 5th update.
6677's suggestion to check for collision on every Nth update is very risky. If you check for a collision on a bullet on every 5th update for example, then the bullet could have passed through a very thin wall in the time between every 5th update.
Author
Andrewoid, I think im going to use trees. I have heard about trees but I have no knowlage of their implementation.
Which brings me to this, I looked up those tree types on google but I can't find a good explination on how they can be applied to collision detection. Can anyone give me an example?
Which brings me to this, I looked up those tree types on google but I can't find a good explination on how they can be applied to collision detection. Can anyone give me an example?
It's a simple concept.
You divide the world up into chunks, based on whatever tree type you select. Then you look at which "chunk" each object is inside of. If you have a bullet in chunk A and a player in chunk B, and you know (based on the tree's properties) that chunks A and B can never overlap, then you don't have to do collision detection between the bullet and the player.
You divide the world up into chunks, based on whatever tree type you select. Then you look at which "chunk" each object is inside of. If you have a bullet in chunk A and a player in chunk B, and you know (based on the tree's properties) that chunks A and B can never overlap, then you don't have to do collision detection between the bullet and the player.
I think partition trees are pretty much the archetypal method of filtering collisions in large engines, but in a more general sense, all you are trying to achieve is to filter down (or cull) pairs of potentially colliding objects. There are actually many ways to do this, so if you are uncomfortable with data structures you could certainly try a simpler method first. For instance, if use events to respond to collisions (i.e. collidable objects have an onCollide event or something) then one very easy optimization is to only check pairs where one or the other object has an event listener set. If neither object cares (as is often the case for level geometry) then don't bother checking them.
A slightly more complex optimization is to deactivate (Bullet library calls this sleeping IIRC) objects which haven't collided with anything for some time. This technique has some subtleties, because you need to be able to detect when to wake an object (if, say, a character is approaching a stack of sleeping boxes).
Another method of culling collisions is to cull based on dynamic bounding regions. For example, say I have a flock of birds that always tend to be close together, rather than check an airplane against each bird, I will check the airplane against a bounding sphere that contains all the birds, and only if it passes I'll check individual collisions.
Collision libraries (like Bullet) generally use all of these methods together. Basically, though, I'm just saying there are many valid methods to skip certain collision checks (sometimes called broad phase collision checking) so don't settle on one that is going to give you fits unless you're sure it's necessary.
A slightly more complex optimization is to deactivate (Bullet library calls this sleeping IIRC) objects which haven't collided with anything for some time. This technique has some subtleties, because you need to be able to detect when to wake an object (if, say, a character is approaching a stack of sleeping boxes).
Another method of culling collisions is to cull based on dynamic bounding regions. For example, say I have a flock of birds that always tend to be close together, rather than check an airplane against each bird, I will check the airplane against a bounding sphere that contains all the birds, and only if it passes I'll check individual collisions.
Collision libraries (like Bullet) generally use all of these methods together. Basically, though, I'm just saying there are many valid methods to skip certain collision checks (sometimes called broad phase collision checking) so don't settle on one that is going to give you fits unless you're sure it's necessary.
6677's suggestion to check for collision on every Nth update is very risky. If you check for a collision on a bullet on every 5th update for example, then the bullet could have passed through a very thin wall in the time between every 5th update.
Thanks, I won't be using that then.
Might be somewhere else its handy but not here then and not somewhere I can think yet.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
