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

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#.

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.

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.

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.

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.
[color=#284b72]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 ...