checking for collisions between a single sprite and a vector of sprites

[martinw30]

Hey all,

I am attempting to write a function that will return true if the sprite I pass in the first argument collides with any sprite that may reside with the vector that is passed to the second argument yet I am having some trouble deciding:

a) If a vector is the best way to store my sprites once that are bound to a texture
b) how to check the vector if ANY element collides with the sprite without having to iterate through the entire vector each time a collision check is called.

bool windowInit::bounceCheck(const sf::Sprite &Sprite, vector<sf::Sprite> vect)
{      
        for (int i=0; i<vect.size(); i++)
                return (Sprite.getGlobalBounds().intersects(vect[i].getGlobalBounds()));

        return false;
}

I think my logic isnt quite right and also I have seperated the sprite in the first argument from the vector in the second so I dont need to check if there is a match.

Thanks in advance

Martin

[binary1248]

a) That's what STL containers are for. You could think about passing it around by reference though. Passing it with your code creates a copy of it each time you call that method if you are not compiling with C++11 support yet. Also make sure to pick a container that best suits your needs. Each of them have their advantages and disadvantages.

b) This is why physics engine CPU usage scales with the amount of objects they have to handle. There are a few tricks they employ though. You could also store a global collision domain for all the sf::Sprites in the vector. This could be a simple box that contains all the bounds of the sf::Sprites. That way you would test to see if the sf::Sprite you pass collides with that global box before doing the more expensive checks. Depending on how much area the sf::Sprites in the vector cover it can save you a bit.

[thePyro_13]

...Passing it with your code creates a copy of it each time you call that method if you are not compiling with C++11 support yet...

Sorry to lead this off into a tangent, but could you elaborate on this? How would this code behave under C++11, I would have assumed it still passed by value and was identical to it's old behaviour.

[binary1248]

In C++11 the standards committee made it easier (or more forgiving) to pass stuff around without using references. All STL containers must be move capable in C++11. See this for more info on move semantics.

[martinw30]

Thank you for your hasty replies.

I'm gathering from the global domain you mean iterating thorugh the array/vector/etc and creating a new IntRect/FloatRect or calling the member's getGlobalBound() function?

Maybe if you can give me an example of this to make it clearer

Thanks again

Martin

[binary1248]

Blue are the sf::Sprites in your vector. Red is the collision domain you need to check first. Green is the sf::Sprite to check against.

[martinw30]

Wow thanks for the diagram, its helped to visualise it at least

I'll try and get my head around a "collision domain" and how to create that from the vector im using

Thanks again!

Martin

[martinw30]

Hey again,

So I ended up adding my vector of sprites to another vector and attempting to check if it collided. Im guessing thats what you meant by a container for my vector....

otherwise I completely misinterpreted you :/

Martin

[kurasu1415]

Maybe I can help clarify a bit. think of splitting the screen into a grid of lets say... 4x4 squares. Those squares represent regions to handle collision. So, first you check collision of a sprite on those regions. If you are in region 1,1 then you only need to check collision against other things in the same region as you. Remember to allow objects to be in multiple regions, in case they are on the border. This is a good way of breaking up a complex physical scene into general groups. Its like saying, "this guy is in the top left corner, so why check collision against this guy in the bottom right?".

Please let me know if that makes sense.

[binary1248]

Umm I didn't really mean that, if I did I would have already mentioned BSPs. They are also an option, but until you know you really need them, they are a lot of work to implement properly.

What I meant was: instead of simply saving a std::vector<sf::Sprite> you save a:

class CollisionDomain {
        std::vector<sf::Sprite> sprites;
        sf::FloatRect bounds;

        void AddSprite( const sf::Sprite& sprite );
        void RemoveSprite(...);
        ...
};

bool windowInit::bounceCheck( const sf::Sprite& Sprite, const CollisionDomain& domain ) {
        if( !Sprite.getGlobalBounds().intersects( domain.bounds ) ) {
                return false;
        }
       
        for( int i=0; i < domain.sprites.size(); i++ ) {
                if( Sprite.getGlobalBounds().intersects( domain.sprites[i].getGlobalBounds() ) ) {
                        return true;
                }
        }

        return false;
}
 

bounds is the sf::FloatRect containing ALL sf::Sprites in your vector so you save time if the sf::Sprite you check against the domain isn't even in it. You only have to do the full comparison with all sf::Sprites if the sf::Sprite you are checking is really in bounds (the sf::FloatRect). When you add a sf::Sprite to the vector obviously you will have to update the bounds. When you remove a sf::Sprite vice versa. If you don't add or remove stuff too often it isn't that much of a disadvantage.

[martinw30]

Ok I understand now....but how do I add several global bounds to one rect item? It's only supposed to hold the position of one sprite at a time. My code is just overwriting the rect or cumalatively adding to it.

void AddSprite(const sf::Sprite& sprite){
                // add the current sprites bounds to the rect then ann that sprite to the vector
                bounds = sprite.getGlobalBounds();
                sprites.push_back(sprite);
                cout << sprites.size() << " " << bounds.width << endl;
        }

Thanks again for your help.

I just finished a 3 year Games Development degree and Im amazed still at how much I dont fully understand :/

Martin

p.s Ive added a screenshot. Its my main menu (NF) that the balls will bounce around bouncing off the menu items (Logo, menu choices etc). The ball isnt in the vector but every other item is.


[attachment deleted by admin]

[binary1248]

You just expand the sf::FloatRect every time you add a sf::Sprite to the vector. std::max and std::min might help you with that.

[martinw30]

OK so Ive been playing with this function and changed it to accept a map instead.

I want the function to check if the shape collides with ANY element that lives within the map I send it, yet it only returns true if the shape collides with the first element of my map and none other so I'm guessing my logic is out:

static bool bounceCheck(const sf::CircleShape& shape, std::map<string, sf::Sprite>& Sprite){
                // returns true if a ball collides with any element of the map
                for (map<string, sf::Sprite>::iterator it = Sprite.begin(); it!=Sprite.end();it++)
                {
                        return (it->second.getGlobalBounds().intersects(shape.getGlobalBounds()));
                }
                return false;
        }

how do i get it to say "Well yes you are part of the map so return true"

Thanks again

Martin

p.s Also having just tested my code and outputting the it->first element at collision point the console is informing me that when the shape collides with an element of the map (sprite) it returns more than one file it collides with. As it waits until it collides with the first element then passes true that it collides with the others for as long as the shape collides with the first. Do I need to also check for a match with filename, map key etc?