• 9
• 9
• 10
• 10
• 9

# Checking collisions of all entities in a 2D RPG

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

## 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 on other sites

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 on other sites

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

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

##### Share on other sites

Ahh, thanks! Gonna go try that out now!

##### 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 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 on other sites

Step 1: Get it working

Step 2: Test it

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

Step 4: Test it again

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.

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