Sign in to follow this  
Sean_Seanston

Traversing 2 vectors and deleting from both

Recommended Posts

The actual purpose of this is for a game but what I mean is, say you have 2 vectors and you need to check each object of the first against each object of the second. If a condition is met, both objects should be destroyed. How do you go about this? The invalidation of the iterators is what makes it confusing for me. So I have:
	for ( itEn = enemies.begin(); itEn != enemies.end(); )
	{
		for( itProj = playerProjectiles.begin(); itProj != playerProjectiles.end(); )
		{
			if( collision( (*itEn)->getEntity(), &(*itProj) ) )
			{
                          <DESTROY OBJECTS>
			}
			else
				itProj++;
		}
		itEn++;
        }

Just to confirm my suspicions I indulged my curiosity and tried this messy goto just to see if it would actually work as desired and indeed it seems to work:
loop:
	for ( itEn = enemies.begin(); itEn != enemies.end(); )
	{
		for( itProj = playerProjectiles.begin(); itProj != playerProjectiles.end(); )
		{
			if( collision( (*itEn)->getEntity(), &(*itProj) ) )
			{
				enemies.erase( itEn );
				playerProjectiles.erase( itProj );
				goto loop;
			}
			else
				itProj++;
		}
		itEn++;
	}
}

Of course then apart from the unforgivable sin of using goto, we're not being very efficient since it's moving the iterators back to the start every time there's a collision but it was just a means of getting it clear in my head and confirming why it wasn't working. So after erasing, the iterators need to be made valid again. I tried using:
			itEn = enemies.erase( itEn );
			itProj = playerProjectiles.erase( itProj );

Without the goto instead but that errors after getting rid of a few objects. I suspect it's something fairly minor in the layout that's causing it but I'm not very advanced on the minutiae of how iterators work. Perhaps I'm advancing an iterator when I shouldn't?

Share this post


Link to post
Share on other sites
For me, I store pointers in a vector...for example...



std::vector<Enemy *> theEnemyList;

//Then when I want to traverse the list I do the following (this might not be a //good way, but it works-for-me.com)

for ( int i = 0; i < theEnemyList.size(); i++ )
{
if ( theEnemyList[ i ] )
{
do_something_with_Enemy_Pointer( theEnemyList[ i ] );

if ( theEnemyList[ i ]->isKilled )
{
theEnemyList[ i ] = NULL;
}
}
}

//then when I need a new enemy....just find the first NULL enemy pointer...

for ( int i = 0; i < theEnemyList.size(); i ++ )
{
if ( theEnemyList[ i ] == NULL )
{
use_this_enemy_slot( theEnemyList[ i ] );
break;
}
}





Ok, so this is probably fine for fairly small lists...and would probably be inefficient for large lists, say a particle system.

But it's simple...and works.com

Share this post


Link to post
Share on other sites
Something like this (names and or types need changing).

typedef std::container<Entity*> EntityList;
typedef std::container<Projectile> ProjectileList;

EntityList::iterator handleCollision(EntityList &list, EntityList::iterator entity, ProjectileList &projectiles)
{
for( ProjectileList::iterator projectile = projectiles.begin(); projectile != projectiles.end(); )
{
if( collision( (*entity)->getEntity(), &(*projectile) ) )
{
projectiles.erase( projectile );
return enemies.erase( entity );
}
else
{
++projectile;
}
}

return ++entity;
}

void caller()
{
for ( EntityList::iterator entity = enemies.begin(); entity != enemies.end(); )
{
entity = handleCollision(enemies, entity, playerProjectiles);
}
}

Share this post


Link to post
Share on other sites
How about flagging the dead elements somehow, instead of removing them one by one? Then sort the dead ones to the end of the vector and snip off the end. That would be constant time op without need for any reallocs. Plus you don't need to worry about obsolete iterators. One n^2 pass for flagging then std::unique maybe? If you don't care about the ordering after the cleanup.

Share this post


Link to post
Share on other sites
How I would do it would depend on a lot of factors. For example, is the order of the elements in enemies and playerProjectiles important? What types are held in the two containers and how expensive are they to copy? How big do you expect these containers to be and how big relative to each other? How many collisions do you expect every time you check for collisions? However, if you just wanted to take your existing code and make it work, you could do this:

for ( itEn = enemies.begin(); itEn != enemies.end(); ) {
bool matched = false;
for( itProj = playerProjectiles.begin(); !matched && itProj != playerProjectiles.end(); ) {
if( collision( (*itEn)->getEntity(), &(*itProj) ) ) {
itEn = enemies.erase( itEn );
playerProjectiles.erase( itProj );
matched = true;
} else {
++itProj;
}
}
if (!matched) ++itEn;
}

Share this post


Link to post
Share on other sites
Quote:
Original post by GregMichael
For me, I store pointers in a vector...for example...


Hmmm... I suppose it would work if you always checked before doing anything with a pointer if it was NULL or not. Still, maybe seems less clean that it could be.

However...

Quote:
Original post by darkelf2k5
How about flagging the dead elements somehow, instead of removing them one by one? Then sort the dead ones to the end of the vector and snip off the end.


This had entered my mind though I decided to see if there was a better and/or cleaner solution. But combining both, I can imagine that maybe you could set the pointers to NULL and then move the NULL pointers to the end and pop the vector... hmmm.

Quote:
Original post by rip-off
Something like this (names and or types need changing).


Looks pretty good... it does more or less what the goto did but cleanly. Nice.

Quote:
Original post by SiCrane
For example, is the order of the elements in enemies and playerProjectiles important?


No, I'm pretty sure it's not.

As for the rest... I think it probably won't matter for my purposes, I'd imagine they'd be quite small in the grand scheme of things and absolute efficiency would probably not be necessary.

That seems a pretty nice looking solution. Nice and simple.

Thanks everyone, I think I should be able to make something suitable now.

Share this post


Link to post
Share on other sites
If order isn't important you should consider not using erase() to get rid of your elements. Either swap the element you want to remove with the last element in the vector or copy the last element over the element you want to remove and then call pop_back().

Share this post


Link to post
Share on other sites
0) Why are you passing '&(*itProj)' to your collision function? Use references.

1) Why do you have to "getEntity()" from an enemy in order to do collision testing? I could understand if you were getting some kind of bounding box object from the enemy, but then why aren't you also getting it from the projectile, and why is it called "getEntity"? In what sense is an enemy not already an "entity"? What does "entity" even mean in your program?

2) Why are your enemies stored by pointer in the vector? Don't do that; if you need polymorphism then use a polymorphic pImpl wrapper or store them in a boost::ptr_container; if you need to "share" the instances somehow, then store smart pointers such as boost::shared_ptr.

3) What if there is a more complex collision than one enemy with one projectile? If a projectile is simultaneously colliding with two enemies, do you really want to remove it when the first collision is detected and thus miss the second? How about two projectiles into the same enemy? Or the general case?

Warning! Code not tested! :)
In particular, the operator overloading in the CollisionTester depends on the types in the two containers being different, and the logic depends on the containers themselves being different. So this won't work for enemy-enemy or projectile-projectile collisions, should you care about them :)

If you want everything involved in a complex collision to be removed, then your best bet is to just mark everything that needs to be removed in one pass, and then do another pass over each vector to remove the marked objects:


template <typename Container, typename Predicate>
bool any(Container& c, Predicate func) {
for (typename Container::iterator it = c.begin(), end = c.end(); it != end; ++it) {
if (func(*it)) { return true; }
}
return false;
}

template <typename Killable>
bool is_dead(const Killable& k) { return k.dead; }

template <typename Container, typename Predicate>
void erase_all_where(Container& c, Predicate p) {
c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
}

template <typename Target, typename Colliders>
struct CollisionTester {
const Colliders* c_ptr;
Target* t_ptr;

CollisionTester(const Colliders& c): c_ptr(&c) {}

bool operator()(typename Colliders::reference c) {
return collision(*t_ptr, c);
}

void operator()(Target& t) {
t_ptr = &t;
if (any(*c_ptr, *this)) { t.dead = true; }
}
};

std::for_each(enemies.begin(), enemies.end(), CollisionTester(projectiles));
std::for_each(projectiles.begin(), projectiles.end(), CollisionTester(enemies));
erase_all_where(enemies, is_dead);
erase_all_where(projectiles, is_dead);




If you want things to be removed as the collisions are detected, you can still make use of standard library algorithms, but we'll need to be a little trickier:


// any, is_dead as before.

// Slight modification in erase_all_where to report if anything was erased:
template <typename Container, typename Predicate>
bool erase_all_where(Container& c, Predicate p) {
typename c::iterator end = c.end();
typename c::iterator garbage = std::remove_if(c.begin(), end, p);
c.erase(garbage, end);
return garbage != end;
}

// Slight modification in CollisionTester to erase as collisions are found
// and report if any were found:
template <typename Target, typename Colliders>
struct CollisionTester {
const Colliders* c_ptr;
Target* t_ptr;

CollisionTester(const Colliders& c): c_ptr(&c) {}

bool operator()(typename Colliders::reference c) {
return collision(*t_ptr, c);
}

void operator()(Target& t) {
t_ptr = &t;
return erase_all_where(*c_ptr, *this);
}
};

// For each enemy, the collision tester sets the enemy as the "target", tests
// and removes all projectiles. Then it reports whether there was a collision,
// so that the enemy can in turn be removed by the outer erase_all_where().
erase_all_where(enemies, CollisionTester(projectiles));


Share this post


Link to post
Share on other sites
[quote]Original post by Zahlman
0) Why are you passing '&(*itProj)' to your collision function? Use references.

What do you mean exactly? I'm not completely following. The function takes 2 Entity* which is also because other non-projectile classes derived from Entity may be using it.

Quote:
Original post by Zahlman1) Why do you have to "getEntity()" from an enemy in order to do collision testing? I could understand if you were getting some kind of bounding box object from the enemy, but then why aren't you also getting it from the projectile, and why is it called "getEntity"? In what sense is an enemy not already an "entity"? What does "entity" even mean in your program?


An enemy has AI and is in control of a class derived from Entity, which represents interactive objects that move or collide etc. such as in this case a Plane. This way a player or AI can use the same Plane objects. The Projectiles on the other hand just travel forward when they're spawned and are represented as just a class derived from Entity.

Quote:
Original post by Zahlman2) Why are your enemies stored by pointer in the vector? Don't do that; if you need polymorphism then use a polymorphic pImpl wrapper or store them in a boost::ptr_container; if you need to "share" the instances somehow, then store smart pointers such as boost::shared_ptr.


Well they were mostly stored as pointers because storing them as objects was causing problems since pointers to the objects in the vector ended up pointing to garbage.

I'll have to look at boost::shared_ptr sometime... people often talk about them. Right now though I'm running out of time so I'll have to avoid any refactoring unless completely necessary.

Quote:
Original post by Zahlman3) What if there is a more complex collision than one enemy with one projectile? If a projectile is simultaneously colliding with two enemies, do you really want to remove it when the first collision is detected and thus miss the second? How about two projectiles into the same enemy? Or the general case?


Well I was trying to figure out the basic way of having 2 objects that collide both be destroyed first and then was going to tackle the inevitable greater complexity involved in actually making it work like a game should. Damage for example will have to be involved rather than just both disappearing on collision.

Good point on colliding with 2 enemies though. What would you suggest there? Some kind of flag system that detects what hit what and then a separate function to deal with the results of that later?

Ah, reading ahead I see that's exactly what you mean ^_^. Yeah. that seems like probably the best way to go.

Quote:
Original post by Zahlman
In particular, the operator overloading in the CollisionTester depends on the types in the two containers being different, and the logic depends on the containers themselves being different. So this won't work for enemy-enemy or projectile-projectile collisions, should you care about them :)


So would it involve a lot of changes to make it work for objects of the same type? Projectile-projectile collisions might be nice but then I suppose they're not necessary.

UPDATE: I wrote that last bit before the forums went down (for most of the day... bah) but since then I've come to a realization. The fact that the planes etc. have health can work pretty obviously as a flag mechanism to tell whether or not something should be destroyed. So, based on that I've come up with the following that appears to work so far, what do you think? In semi-pseudocode to spare the unnecessary details...


//Check for enemy-player projectile collisions
for ( itEn = enemies.begin(); itEn != enemies.end(); itEn++ )
{
for( itProj = playerProjectiles.begin(); itProj != playerProjectiles.end(); itProj++ )
{
if( collision( enemy, projectile) ) )
{
enemy.causeDamage( damage );
projectile.causeDamage( damage );
}
}
}

//Check for enemy-player collisions
for ( itEn = enemies.begin(); itEn != enemies.end(); itEn++ )
{
for( itPlay = players.begin(); itPlay != players.end(); itPlay++ )
{
if( collision( enemy, player )
{
enemy.causeDamage( damage );
player.causeDamage( damage );
}
}
}

//Remove dead enemies
for ( itEn = enemies.begin(); itEn != enemies.end(); )
{
if( enemy.health <= 0 )
{
itEn = enemies.erase( itEn );
}
else
itEn++;
}

//Remove destroyed player projectiles
for ( itProj = playerProjectiles.begin(); itProj != playerProjectiles.end(); )
{
if( projectile.health <= 0 )
{
itProj = playerProjectiles.erase( itProj );
}
else
itProj++;
}



Does that look ok? As far as I can tell, it should mean that 1 projectile touching 2 enemies at the same time will work as you'd expect; 2 enemies and the projectile taking damage.

Share this post


Link to post
Share on other sites
[quote]Original post by Sean_Seanston
Quote:
Original post by Zahlman
0) Why are you passing '&(*itProj)' to your collision function? Use references.

What do you mean exactly?


I mean, you currently pass a pointer to your function. There is no reason why your function should accept a pointer. Instead, it should accept a reference.

This is a reference, in case that's the point you're missing.

Quote:
The function takes 2 Entity* which is also because other non-projectile classes derived from Entity may be using it.


Yes; references handle that.

Quote:
An enemy has AI and is in control of a class derived from Entity, which represents interactive objects that move or collide etc. such as in this case a Plane. This way a player or AI can use the same Plane objects. The Projectiles on the other hand just travel forward when they're spawned and are represented as just a class derived from Entity.


That still doesn't tell me what an Entity is.

Quote:
Well they were mostly stored as pointers because storing them as objects was causing problems since pointers to the objects in the vector ended up pointing to garbage.


So, because of sharing, then. (More generally, "aliasing"; i.e. having other parts of code refer to the same logical data.)

boost::shared_ptr is probably what you want, then.

Quote:
Well I was trying to figure out the basic way of having 2 objects that collide both be destroyed first and then was going to tackle the inevitable greater complexity involved in actually making it work like a game should. Damage for example will have to be involved rather than just both disappearing on collision.


Then you will definitely want to be thinking in terms of two passes. "Damage" the objects in the first pass, and remove anything that's damaged enough to be destroyed in the second.

Quote:
Good point on colliding with 2 enemies though. What would you suggest there?


I don't know; it's your game. You have to decide logically what should happen before you can think about how to make it happen. Try thinking of a few test cases first and sketching out on paper (or in a text document) what should happen.

Quote:
The fact that the planes etc. have health can work pretty obviously as a flag mechanism to tell whether or not something should be destroyed.


Now you're getting it. :)

Quote:
Does that look ok?


Sure, but you should still consider using the erase-remove idiom (see for example the erase_all_where helper function in my code) to do the removal.

Quote:
As far as I can tell, it should mean that 1 projectile touching 2 enemies at the same time will work as you'd expect; 2 enemies and the projectile taking damage.


Sure. And if you want a projectile to only be able to damage one enemy, you can make that work, too, by doing full damage to the projectile on any collision, and not allowing such projectiles to damage enemies (you might still test the collision, and then check the projectile's status and skip the causeDamage call, for example).

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Quote:
Original post by Sean_Seanston
Does that look ok?


Sure, but you should still consider using the erase-remove idiom (see for example the erase_all_where helper function in my code) to do the removal.

Or partition/erase since order doesn't matter.

Share this post


Link to post
Share on other sites
I don't know if anyone has already posted this, but erase() returns "A bidirectional iterator pointing to the new location of the element that followed the last element erased by the function call, which is the list end if the operation erased the last element in the sequence."

Using this knowledge, you can quite simply erase elements from a container without invalidating the iterators, eg

for(std::list<float>::iterator it = list.begin(); it != list.end(); it)  //Don't increment here!
{
if(*it == someVal)
{
it = erase(it);
}
else
{
++it;
}
}

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this