Checking collisions of all entities in a 2D RPG

[Ex0Matter 111]

I recently started working on a 2D game engine using SFML/C++, and I'm stuck now on trying to check collisions of any moving entities. Right now, my code is structured into Maps, which contain a simple manager of Entities. This manager just contains an array of Entity pointers, and is Map-specific. I've seen mentions of Quadtrees but I'm not sure if that would be effective for this type of project.

 

Feel free to check out my source code (https://bitbucket.org/Ex0Repos/sfml_2d/src) if you want to look at how I've done things, but remember that the design is probably not the best, and I have a ton of things I know I need to change.

 

Thanks!

Edited May 24, 2016 by Ex0Matter

[TheCanadianVendingMachine 693]

Do you know if brute-forcing it will lag the game? If it does, take a look into quadtrees. If not, brute force it! An obvious way to brute force it is to collide all entities with all other entities, and manage from there. Maybe even perform a check to see if they are within range. Sure, this isn't the fastest you can be; but if it works, and works well, don't worry about implementing a quad-tree like structure.

[Ex0Matter 111]

Sorry if this sounds a little stupid, but how would I go about implementing this?

[TheCanadianVendingMachine 693]

std::vector<sf::Sprite> objects;
for (auto &obj : objects)
{
  for (auto &collisionObject : objects)
  {
    if (obj.getGlobalBounds().intersects(collisionObject.getGlobalBounds()))
    {
      // collision!
    }
  }
}

That would be the most basic way of implementing a collision-like system. Only problems that the code above has is that you can collide with the same object you are testing with, and that with huge amount of objects (greater than 100), it will slow down.

 

Note: This will not resolve collisions. Only detect them

Edited May 24, 2016 by TheCanadianVendingMachine

[Ex0Matter 111]

Ahh, thanks! Gonna go try that out now!

[jHaskell 1856]

...

That would be the most basic way of implementing a collision-like system. Only problems that the code above has is that you can collide with the same object you are testing with, and that with huge amount of objects (greater than 100), it will slow down.

 

Note: This will not resolve collisions. Only detect them

 

 

I would prefer the following slight variation, which avoids the following problems:

 

Testing an object against itself.

Testing object 0 against object 1, and later testing object 1 against object 0.

std::vector<sf::Sprite> objects;
size_t num_sprites = objects.size();
for (int i = 0; i < num_sprites; i++){
  for (int j = i + 1; j < num_sprites; j++){
    if (objects[i].getGlobalBounds().intersects(objects[j].getGlobalBounds())){
      // collision!
    }
  }
}

[Infinisearch 3044]

Instead of a full on quadtree you can use a simpler grid to accelerate collision.  Split your map up into equally sized rectangles.  Place objects in each rectangle.  Only check for collisions for object in the same rectangle.  A simple way to reduce the amount of collision checks you need to run.

[Daniel Ricci 844]

Step 1: Get it working

Step 2: Test it

Step 3: if necessary, get it working faster (after profiling)

Step 4: Test it again

 

Don't know if you're using STL and/or boost, these might help you out in your journey.

 

Im unsure if Quadtrees are as effective in 2D space as they are in 3D space, like BSP trees, so I don't want to give potentially falsey information.

[vstrakh 2456]

Im unsure if Quadtrees are as effective in 2D space as they are in 3D space, like BSP trees

Quadtree works on 2D plane. It's octree that works in 3D space.

[Infinisearch 3044]

While I agree with the sentiment of profiling/benching and then optimizing if necessary, I also feel that for a beginner its good to introduce oneself to more advanced things.  As a bonus since its not mission critical at the time there's less pressure.  So if I were the OP I would implement brute force first make sure its working correctly then implement grid or quadtree acceleration for "fun".