# What is the best way to check lists of objects that collide

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.

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.

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.