Testing an object in a vector against all other objects in the vector?

[wh1t3crayon]

Hi there, I'm working on collision detection for a game in SFML. I succesfully designed a Spatial Partition grid to speed up the collision test, in the following of this tutorial: http://maryrosecook.com/blog/post/how-to-do-2d-collision-detection
But now I have an issue with one aspect of it: Going through a vector of objects and testing all the OTHER objects in the vector against said object. The author puts it into psueudocode here:

For each tick of the clock

For every object in the game

Get all the other objects in the same grid square

For each other object in the same grid square

I have trouble with the last line, because in iterating through a vector I am not sure how to skip over the current object.
Here is my own code (a couple of sysntax errors but this is a c++ question not an SFML question):

//for every moveable object
		for(int i = 0; i < rects_.size(); i++){
			std::vector<sf::RectangleShape> posibleObjects_; //this will be a vector of WorldObjects in a real game
			//for every object in that object's gridsquare
			for(int j = 0; j < rects_.size(); j++){
				if(rects_[i].intersects(rects_[j])){
					//collision
				}
			}
		}

The problem is, a collision will always be reported because somewhere in the vector the object will eventually check against itself which is always a true collision. What is the correct way to do this?

[Computergeek01]

The problem is, a collision will always be reported because somewhere in the vector the object will eventually check against itself which is always a true collision. What is the correct way to do this?

Give each object a Unique ID. If the object that you are testing against has the same ID has the object you are testing, skip it.

[wh1t3crayon]

So that would require an extra check each time right? Like

//for every moveable object
		for(int i = 0; i < rects_.size(); i++){
			std::vector<sf::RectangleShape> posibleObjects_; //this will be a vector of WorldObjects in a real game
			//for every object in that object's gridsquare
			for(int j = 0; j < rects_.size(); j++){
                                //check for ID's
                                if(rects_[j].ID != rects_[i].ID){
				    if(rects_[i].intersects(rects_[j])){
					//collision
                                     }
				}
			}
		}

Is that what you mean?

If so, how would I make sure that duplicate objects of the same class receive a different ID?

[Computergeek01]

TBH? I'm usually lazy about it. I give the top level class a static data member that gets incremented and copied to a UUID local to the instance. There are probably more efficient ways, but I don't usually have performance issues. Yes, you would have an extra check.

[wh1t3crayon]

Would a regular static int work just as well in place of a UUID?

[Computergeek01]

Yes, sorry that's what I meant. I was using that as an acronym for "Universally Unique Identifier", I forgot that it is also an MS data type.

[wh1t3crayon]

Haha oh okay, that was a rather intimidating google result. Anyways, just for brainstorming, are there any other ways for objects to skip over themselves in vectors?

[Computergeek01]

If 'i' == 'j' in your example it should mean the same thing.

[ne555]

for(int K=0; K<size; ++K)
   for(int L=0; L<size; ++L)
      if( K not_eq L and collision(K,L) )

iirc that's what you've got, but given that collision is reflexive, you could

for(int K=0; K<size; ++K)
   for(int L=K+1; L<size; ++L)
      if( collision(K,L) )

If I misunderstood and the second loop traverse another container, you may use the memory address of the objects.

[wh1t3crayon]

for(int L=K+1; L<size; ++L) So that also ensures that no object checks against itself?
Also, you mentioned that collision is reflexive which is exactly another issue I have. If A and B test against each other and collide, how do I ensure that I don't check for B and A, which has already been confirmed true but because of the nested for loop is being checked again?

[ne555]

> If A and B test against each other and collide, how do I ensure that I don't check for B and A
that gets solved too. If your second loop starts from `K+1' then the collision checks are performed always from the element with the lesser index (K<L)
That ensures that you would not test the object with itself (K=L) or repeat a pair (L<K)

[wh1t3crayon]

If I misunderstood and the second loop traverse another container, you may use the memory address of the objects.

Yes, the top loop is a container of all moveable objects while the bottom is a container of all objects, so they're different. How would I use the memory adresses of the objects here?