0

I have all my objects in one vector, but I don't know how to check collisions between each object.

At first, I tried doing a nested for-loop. However, since colliding objects would sometimes destroy each other, it was a really icky way of doing it and is a very rigid architecture.

According to this, Iterator invalidation rules and C++ nested iterators

I shouldn't use nested for loops to check for collision.

Than by what method should I do it? Everything is already in the vector, the collision code is done, as well as the response. I just need a way to move through the entire vector and check collision with everything, and still lets me erase and change things.

Edit: I don't want to break out of the loop either.

Edit 2: The objects that are colliding is namely bullets with other objects such as walls. The bullets are really just quads that fire off. Using a bounding box empirical method, I detect when the bullet is inside the wall, and just delete the bullet. Once the wall hits a certain limit of hp, it too will be deleted. The main problem I have with dealing with this is that my nested for loop would fail upon hitting the parent loop once something is erased. It would throw an iterator not increment able error, but using a break point, I can clearly see that the iterator can be identified.

Community
  • 1
  • 1
user2418426
  • 105
  • 1
  • 12
  • 1
    Nested loops should work if either you don't use iterators and take care of handling index increase, or if you push objects to erase to a temporary container and use that container to know what objects to remove once you checked for collisions. – Some programmer dude Sep 02 '14 at 14:45
  • Use another container like `set` to help with collision checking? – Landys Sep 02 '14 at 14:45
  • This is a tricky thing because order of can also matter (if bomb A, bomproof B, and C all collide, what happens?). You have to clearly define that before you figure out what happens. but in general, I'd do a loop, detect all the collisions, then a DIFFERENT loop to process all the collisions. – IdeaHat Sep 02 '14 at 14:45
  • Can you share some more context what your objects are and what is viewed as a collision? This will help you get a better answer, like building a hash table based on the object properties and then probing for collisions. – Tim Child Sep 02 '14 at 14:49
  • @JoachimPileborg How? The only way I can think of is for(int i = 0; i < Array.size(); i++). I'm concerned whether the condition Array.size() changes every rerun of the loop or not. – user2418426 Sep 02 '14 at 14:50
  • If you don't remove an object, you increase the counter variable. If you remove an object, you don't increase the counter. Of course, it depends on which object you remove. – Some programmer dude Sep 02 '14 at 14:52
  • @MadScienceDreams Well I'm not so picky about the order of collisions. Just getting the collision to work right now would be fine. How would you process the collision without destroying the loop? – user2418426 Sep 02 '14 at 14:57
  • @user2418426 Well if you don't care about the order, then the most efficient way is a double-loop that builds up a list (vector) of indices that you want to destroy (it can process the other collisions in line as well), then a second loop that removes all those elements. You really don't want to delete them in line as it is a O(n) operation to remove (changing your O(n^2) collision loop into a O(n^3)) – IdeaHat Sep 02 '14 at 15:01
  • @MadScienceDreams So its the answer Meesa provided below right? In the first nested loop, I mark which ones to delete. Than I make a second loop and use std::remove_if and destroy the object. – user2418426 Sep 02 '14 at 15:04
  • @user2418426 yah I shoulda guessed that there was a stl thingy for this. std::remove_if wouldn't require a second loop. I don't like the memory and initialization requirement for this, but it certainly simpler than writing your own. – IdeaHat Sep 02 '14 at 15:14

1 Answers1

0

If I understood it correctly, this is how I would do it:

  1. Create a bit array/mask (std::vector<bool>) to mark which elements should be removed.

  2. After you are done with the outer loop, remove the elements that were marked (in the bit array) to be removed.

    You can do it by constructing new vector and swapping its contents with the original one or use std::remove_if.

Messa
  • 24,321
  • 6
  • 68
  • 92
  • How do I use remove if? I've looked on http://www.cplusplus.com/reference/algorithm/remove_if/, and it seems like I have to pass in a function to use it. Are there more examples I can refer to to do this? – user2418426 Sep 02 '14 at 15:02