I'm currently developing a 2D sidescrolling shooter game for PC (think metroidvania but with a lot more happening at once). Using XNA.

I'm utilising quadtrees for my spatial partitioning system.

All objects will be encompassed by standard bounding geometry (box or sphere) with possible pixel-perfect collision detection implemented after geometry collision (depends on how optimised I can get it).

These are my collision scenarios, with <> representing object overlap (multiplayer co-op is the reason for the player<>player scenario):

Collision scenarios (true = collision occurs):
Player              <>      Player          =   false
Enemy               <>      Enemy           =   false
Player              <>      Enemy           =   true
PlayerBullet        <>      Enemy           =   true
PlayerBullet        <>      Player          =   false
PlayerBullet        <>      EnemyBullet     =   true
PlayerBullet        <>      PlayerBullet    =   false
EnemyBullet         <>      Player          =   true
EnemyBullet         <>      Enemy           =   false
EnemyBullet         <>      EnemyBullet     =   false
Player              <>      Environment     =   true
Enemy               <>      Environment     =   true
PlayerBullet        <>      Environment     =   true
EnemyBullet         <>      Environment     =   true


Going off this information and the fact that were will likely be several hundred objects rendering on-screen at any given time, my question is as follows:

Which method is likely to be the most efficient/optimised and why:

1. Using a single quadtree with boolean checks for collision between the different types of objects.
2. Using three quadtrees at once (player, enemy, environment), only testing the player and enemy trees against each other while testing both the player and enemy trees against the environment tree.

I have recently implemented a similar scenario in my game. I have the same principles (e.g. no friendly fire etc.), and this is how I've done it:

1 . All objects (even Environment) have a PlayerID property. In your game, for example: Environment.PlayerID = 0, Player.PlayerID = 1, Enemy.PlayerID = 2 etc. If a bullet is fired by the player: Bullet.PlayerID = 1, and so on.

2 . The first step in my collision detection is to check if the two objects I test for collision are actually the same. The second step is to see if their PlayerID's are the same:

    if (obj1.PlayerID != obj2.PlayerID){ ... }
else { continue; }


This already narrows down the cases, but I added some further optimizations:

3 . I have a Collision class:

  public class Collision{
public Object Victim;
public List<Object> Colliders = new List<Object>();
}


In my collision detection loop, I make a new Collision instance for each object in my scene that happen to participate in a collision. For example, if obj1 collides with obj2, I will create two new Collisions so:

  Collision coll1= new Collision();
coll1.Victim = obj1;
Collision coll2= new Collision();
coll2.Victim = obj2;


If I detect another collision for obj1 in the same Update cycle (with obj3 for example), I just add the obj3 to the coll1.Colliders list, and create a new Collision for obj3 (unless one already exists).

4 . Once I went through all the objects in the scene, I have a nice list of Collisions. Now I can go through that list, and apply the collision effects to their "Victims".

5 . I handle the collision effects in the Player, Bullet etc. classes. For example:

  public class Player{
...
public void OnCollision(Object collider){
if (collider is Player){...}
if (collider is Bullet){...}
...
}
...
}


This way I can customize the collision effects only when necessary. For example, in my game bullets simply disappear (with an explosion effect) when they collide with anything, so I don't have any 'if' blocks in the Bullet.OnCollision method.

• I like this solution, having a Collision class is clever. But it is really efficient? Having a wide variety of characters moving around the environment alone would generate a significant amount of collisions every frame, wouldn't it? Would it perhaps be better to have a separate case for objects colliding with the environment, one that doesn't create classes? Jul 11, 2012 at 11:51
• You don't have to worry about this unless you have millions of objects. This is a really lightweight class, it won't have any visible impact on the performance of your application. I need to mention though, that I've also defined an ICollidable interface, and all collidable objects implement this. So in practice, the Victim property is of ICollidable type, and the Colliders property is of List<ICollidable> type. This means, I don't have to do as many casting operations. Jul 11, 2012 at 12:11
• Yeah, I've been working on using interfaces for polymorphism (I use ISpatialNode for my quadtree lists), so that makes sense to me. This is a great solution and means I'll only need one quadtree, so thanks! Jul 11, 2012 at 12:19
• You're welcome! Sorry I couldn't post the loop from my actual collision management code, I'm at work right now :-) I'm pretty sure you can fit it to your own needs though. Jul 11, 2012 at 12:24

It seems to me that you must not think of it as "player check with enemybullet" but of the collision objects themselves.

Seeing as you already know what types of collision objects you want to support:

All objects will be encompassed by standard bounding geometry (box or sphere)

It's easy to make a table of the collision you might have.

Box     <>   Box
Box     <>   Sphere
Sphere  <>   Box
Sphere  <>   Sphere


Personally, here's how I do it in my game. Which, granted, doesn't have very advanced collision detection yet.

• Update all objects in the Scene. An update only affects an object's velocity (direction * speed), not its position. Position + velocity then becomes the future position.

• Clear dead collision objects. For each ModuleCollision, check if it's dead and remove it from the list if so.

• Collision checking. Check every ModuleCollision with every other ModuleCollision and act accordingly if a collision has occurred. A collision might affect an object's velocity.

• Finalize position. Run the UpdatePost function for each object, which adds the (perhaps altered) velocity to the position.

Here's what my collision checking looks like:

// collision checking using the handshake problem

for (size_t i = 0; i < m_ModulesCollision.size(); i++)
{
ModuleCollision* coll_left = m_ModulesCollision[i];

for (size_t j = 0; j < m_ModulesCollision.size(); j++)
{
ModuleCollision* coll_right = m_ModulesCollision[j];

if (coll_left->CheckCollision(coll_right))
{
GameObject* obj_left = coll_left->GetOwner();
GameObject* obj_right = coll_right->GetOwner();

// this also affects coll_right
coll_left->CollisionResponse(coll_right);

obj_left->OnCollision(obj_right);
obj_right->OnCollision(obj_left);
}
}
}


I only care about the ModuleCollision's, not the objects themselves. This way you can easily make a list of active objects and only do collision checking on those objects.

What I would suggest if speed is really becoming a problem:

• While this is informative, it doesn't really answer my question. I already know how I'm going to do the actual collisions, I'm just wanting to know what the most efficient approach would be in terms of indexing the objects. Say I already know about the ModuleCollision object and I'm already using it. I now need to know how to make this section efficient given my conceptual design: Collision checking. Check every ModuleCollision with every other ModuleCollision and act accordingly if a collision has occurred. A collision might affect an object's velocity. Jul 11, 2012 at 11:42