18 replies to this topic

[infectedbrain]

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

[6677]

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.

[SimonForsman]

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.

Edited by SimonForsman, 25 June 2012 - 12:47 PM.

[infectedbrain]

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?

[ApochPiQ]

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 :-)

[andrewoid]

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.

[infectedbrain]

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?

[ApochPiQ]

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.

[bimmy]

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.

Edited by bimmy, 25 June 2012 - 03:53 PM.

[6677]

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.

Edited by 6677, 25 June 2012 - 04:08 PM.

[Alpha_ProgDes]

Not to nitpick but why is this thread tagged as Functional if it is not about functional programming?

[infectedbrain]

I am new to this forum site... not sure what functional meant.. sorry

[bglanzer]

Infectedbrain to break down what ApochPiQ stated simply create a class called node that contains a pointer to a node, contains a defined space either 2d or 3d, and contains a container of collidable game objects. Set a max number of game objects allowed per node. Define a node in which its defined space covers the entire scene then begin checking the number of Objects within it. If the number exceeds the max then evenly split the space with two new nodes each with thier parent set as the original node it spawned from. Then repeat that process untill the number of collidable objects is less than the max allowed with the node and add those game objects to that nodes game object list.

Then test which node your bullet is in and only check the collidable objects within that node.

That is the basis of a quad tree. For an Oct tree split the nodes by 4 instead of 2. Here is a link utilizing quad trees for terrain rendering. Its pretty much the same concept just replace vertices with enemies. http://www.rastertek.com/tertut05.html The code is in c++ but you shouldn't have difficulties making the change to c#.

[BeerNutts]

A simpler, conceptual version, without using trees, would to simply divide your collide-able world into a grid of X rectangles. X could be something like 4, if your world is very small, like a single screen (but, in this case, spatial-hashing is probably overkill), or it could be huge, 4096, for a large world.

The idea would be to place your objects into each grids collide-list (a Vector of pointing to the objects), depending on which one it's in. Every time you move an object, check if it's passed a grid boundary, and remove from old list and place it in the proper grid list. Occasionally, an object will span 2 grids, and it will have to be in 2 lists. Then, each update, you compare only the objects with other objects in the same list.

That's kind of a conceptual way of doing it. Using trees will be much more efficient, but more difficult to implement in the beginning.

[NEXUSKill]

While the approach infectedbrain suggested is exponentially inefficient, there are a few questions that need answering before throwing him to the mess that can be a space partitioning algorithm.

How many objects would your current project have? if you know the answer, chances are you won't be needing any kind of optimization, if the answer is in the thousands or undefined, then we are in business.
As a general rule, unless you are making an educational proyect, unnecessary optimizations are undesirable. If you already have the optimization algorithm at hand you might as well use it, if you want to learn it, do it, otherwise you may be headed into one of the biggest time wastes in development.

If you need to optimize your collision detection you'll probably need to apply a couple of techniques, as others said, tree like structures are one of the most popular methods, they are different ways of applying the same technique, which is space partitioning, breaking down a large, possibly unlimited space into smaller parts where you can fit stuff in to get a certain knowledge of proximity.
If your game had rooms for example, it would be pointless to test for collision between two objects that you know are in to different rooms. That is a space partitioning, you define that rooms are separate spaces and objects cannot be in two of them at the same time.

Another good optimization is avoid checking collisions between static objects, since they usually make up for most of the population of a world. If two objects are truly static, even if they are in collision from the beginning, that is likely as designed by the level editor. If objects are subject to a physics engine, but do not move on their own, its good to flag them as being in static condition when they have found a resting spot. If your objects are mobile those are the ones you need to check all the time.

You can always dig deeper and there is no "best" optimization, they are all good for some cases and bad for others, and as I mentioned before, the cost of research and implementation HAS to be taken into consideration, even if it is the BEST optimization ever.

[infectedbrain]

Then test which node your bullet is in and only check the collidable objects within that node.

How do we know when to stop dividing and check for collision? If there is only one object in the node than nothing is colliding. Also what if an object is in more than one node at once?

[ApochPiQ]

You stop dividing when you feel like it, basically. There are different rules of thumb for how far to go depending on the type of division structure you use; kd-trees automatically calibrate themselves, for example, but are a bit more intricate than quadtrees, where you might stop at 2x-4x the size of your game's average-sized objects. This is something that can take some fine-tuning to get optimal, so design your code in such a way that you can control how far the subdivision goes.


As far as objects which overlap multiple nodes: well, you simply check all the nodes it overlaps. Ideally this is a worst-case scenario so you're still saving a lot of calculation over checking everything in the world, and your average case should still be only checking 1-2 nodes tops.

[serumas]

Some days ago I was compared quadtree and simple grid hashing techniques for dynamic objects collision in my game.
And stayed with grid, becouse of performance, simplier implementation(no recursian), much eficient space dividing (that means better collision checking filter), much faster object inserting to algoritm data list,easie getting result lists for colliding, and so on.
infectedbrain if you want i can share c++ code by email. its very simple, its not perfect and optimized, but it works for me great ...

Edited by serumas, 02 July 2012 - 02:37 AM.

[infectedbrain]

That would be great if you could send me some code to work off of.
If you just want to email it to me my email is dartosgamer@gmail.com
Thanks a lot.