Jump to content
  • Advertisement
Sign in to follow this  
Ex0Matter

Checking collisions of all entities in a 2D RPG

This topic is 784 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 by Ex0Matter

Share this post


Link to post
Share on other sites
Advertisement

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.

Share this post


Link to post
Share on other sites
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 by TheCanadianVendingMachine

Share this post


Link to post
Share on other sites
...

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!
    }
  }
}

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!