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'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.
share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

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;
  coll1.Colliders.Add(obj2);
  Collision coll2= new Collision();      
  coll2.Victim = obj2;
  coll2.Colliders.Add(obj1);

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.

share|improve this answer
    
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? –  Djentleman Jul 11 '12 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. –  Marton Jul 11 '12 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! –  Djentleman Jul 11 '12 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. –  Marton Jul 11 '12 at 12:24
add comment

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:

  • Put your environment in a static quadtree. This can be built when loading or defined in the level.

  • Put everything else in a dynamic quadtree.

  • For each object, check for collision with the environment quadtree, then check for collision with the dynamic quadtree. Respond accordingly.

share|improve this answer
    
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. –  Djentleman Jul 11 '12 at 11:42
    
That isn't very clear from your question. It looked to me like you were comparing each object type with each object type, which is the wrong way to approach this. If you want to make the actual collision checking efficient, you need to have a broad phase and a narrow phase. –  knight666 Jul 11 '12 at 11:45
    
I have mentioned my broad phase (quadtree) and my narrow phase (bounding shapes and possibly even pixel-perfect). My question is, given my scenarios, should I use multiple quadtrees and compare them against each other (e.g., one will contain the "Enemy" objects as they are inserted), or a single quadtree with conditionals (e.g., if this object is of type "player" and the other object is of type "enemy", proceed with collision)? I know I'm oversimplifying, but you can safely assume I understand collision. –  Djentleman Jul 11 '12 at 11:59
add comment

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.