Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am making a top down shooter in XNA. I have a player, a list of enemies, a list of world objects like crates, trash cans, etc. and the map which has walls. Is there a better way to check for collisions than,

for (all enemies) for (all world objects) check for collision between enemies and world objects for (all players bullets) for (all enemies) check for collisions between players bullets and enemies and so forth.

What I mean is, I have a few lists of a bunch of objects and they all need to be checked for collisions. What is the most resourceful way to do this? Thanks for your help in advance.

share|improve this question
    
Sounds like the same problem as this: gamedev.stackexchange.com/questions/45392/… –  Kylotan Jan 4 '13 at 1:27

3 Answers 3

up vote 1 down vote accepted

That all comes down to how your game is organized, currently.

BUUUT, there are some quick wins to be had with various organization systems (if you're talking about dealing with many elements, rather than, say a PONG number of collisions to test against).

For example, a quick win might be to use quadtrees/octrees to do your sorting.

Think of it like this: You know that the enemies in the top-left aren't going to be colliding with the walls in the bottom-right.

So why not do some work ahead of time, to cut those checks out?

Depending on the language you're using and the hoops you might have to jump through to have multidimensional lists which contain lists, all of which also contain your items...

...I've got a list of enemies which span the whole screen.
Instead, I'll make a list, which contains 4 lists -- each of those lists is going to represent a quadrant of the screen (NE, NW, SE, SW).
Then, I'm going to stuff the position data of each entity into one of those buckets.

Right off the bat, I've shaved a TON of superfluous collision checks.
As objects move over the bounding lines, I should take them out of one bucket and put them in the appropriate new bucket.

If there are still areas where there are lots of collisions going on, you can use recursion to break one of THOSE buckets up into 4 smaller buckets (so breaking NE into NE:NE, NE:NW, NE:SE, NE:SW), and within that quadrant, assigning all of the objects into the quadrants of the quadrant. If one object is too big to fit inside of the smaller bucket, or is now crossing over the lines, then leave it in the parent bucket, and check that one exception object against all of the objects in the smaller buckets (beats checking all of them, though).

You can recursively do this until you hit a threshold which you set for yourself (eg: "no more than 5 levels deep, but until you hit that depth, no more than 5 collisions to check per quadrant").

That said, if you DON'T have lots of collisions to check for, then this kind of optimization can actually slow things down.
For instance, you wouldn't want to do this for, say, Super Mario Bros III, because there just isn't enough stuff going on to warrant the maintenance of the quadtree.

But quadtrees and octrees are used in many, many games - even higher-end 3D games. Octrees are similar, except they also deal with height (or depth -- whichever axis you're not using in a quadtree in your game). So instead of breaking a square into 4 quadrants, you're breaking a cube into 8 octants.

Hope that helped.

share|improve this answer
    
Excellent, thanks for the detailed answer. –  Jeff Jan 4 '13 at 8:32

A Smart way is to store your object in a Spatial Structure like an octree (3D) (see this for example http://ploobs.com.br/?p=1622) or quad tree for 2D. (there are lots of others, the choice depends on the usage)

Those types of structures make the lookup complexity very smaller (queries like "what object is close to me" will be faster (not n*n like brutal force approach) ).

Try using a Physic Engine that handles this for you.

3D physic engine for xna: Bepu http://farseerphysics.codeplex.com/

2D physic engine for xna: FarSeer http://farseerphysics.codeplex.com/

Both are VERY well documented.

share|improve this answer

There are many ways to optimize your idea (it's a exponential complexity algorithm).

I think, for a 2D game, a good way to implement a collision detection system is using Quadtrees. It is simple, and easy to implement, and in the long run can be parallelizable.

I'm not going to extend in this subject, but will leave links to others SE questions about this spatial data structure ;)

http://stackoverflow.com/questions/4981866/quadtree-for-2d-collision-detection

Data Structure (or algorithm) for fast distance-based entity lookups

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.