[C++] Objects that delete themselves from a conatiner?

[Pixel_Outlaw]

I'm currently cobbling things together with SFML when it occurred to me that I never really had a solid foundation for objects that remove themselves from a container.

I understand how to store objects in lists, arrays, vectors ect but when it came to making a very simple particle class, I realized that I had no way for the object to delete itself when it was time. My objects need to be destroyed should they reach the edge of the screen. In blitzmax I simply made objects remove themselves from a global list when they needed to be destroyed. How would this carry over to C++? I hope I don't have to have a manager that deletes objects from their respective container types. This kind of defeats the point of having objects have their own update functions if it is to be done in a manager class.

Can somebody please help a bit?
How would you code a very simple class that deletes itself from a global container?

[Jim]

You can do that like this

Code: [Select]

list<particle*> particles;
particles.push_back(new particle);
particles.push_back(new particle);

...

particle::update()
{
  if (dead)
  {
    particles.remove(this);
    delete this;
  }
}

But that's really bad design.  Much better to have particle with a method on it that knows if it should be removed, and have it externally managed by a particlemanager.
Reason being that if anyone else has a pointer to particle, then that will now be a stale pointer. Much better if the particlemanager hides that from particle itself and encapsulates the list management away from the rest of the program.
It's also asymmetric - the particle does not create itself so it should not delete itself either.
Finally the particle object needs to know about the global list.  That doesn't sound right, it breaks encapsulation - the particle should only know about properties of itself.

Does that help?

<edit>found quite a good discussion here

Jim

[Pixel_Outlaw]

OK, I was kind of afraid of that. Looks like I have to make a bazillion classes just to do the job of what would normally take me one. I guess if that is the way it is to be done I should conform to the standard.

It just sort of rubs me the wrong way conceptually that an object can't "die" without assistance. I was under the impression that objects should know how to take care of themselves. And somehow I made the connection that taking care of themselves meant being able to "die" when necessary.


I guess maybe I could use an external function to clear away dead object also?

Thanks as always Jim.

[Jim]

C# and Java both have the concept you are maybe looking for.  In that case you'd just remove the object from the list (and any other references) and the objects would then be garbage collected.
There are libraries that let you do that in C++ (boost) too.  Or Managed C++.
It's also fairly likely that you won't need to have a bazillion classes as you envisage.  I suspect just a particle manager will do what you want, and if you have lots of things that behave the same way then templating or polymorphism will work for you instead.

Jim

[Pixel_Outlaw]

That helps quite a bit Jim.

Maybe somebody can further my understanding...

When cleaning up my objects marked for removal, how do you advise I do this?
A for loop that iterates through the length of the container? (I'm not sure how removing objects from a vector or list and changing length would affect the for loop's stability)
A While loop that continues to run deletion passes until none are found? (costs an extra iteration)

Sorry if these are basic concerns. My questions are best answered here, my professors don't make demos and games. I suspect your answers here will help others starting out too. I'm kind of winging it right now, on my own.

[Jim]

You will find that adding/removing things from a list will break the iterator (the for loop) as you suspect it will.
Edit: apparently this is true for vector, but not list.
One way around that is to create a new list as you go, eg.

Code: [Select]

list<particle *> original_list;
list<particle *> new_list;
for ... in original_list (sorry, I forget the C++ syntax for this)
{
  if (particle->is_alive())
    new_list.push_back(particle);
  else
    delete particle;
}
original_list = new_list;

Jim

[hellfire]

One way around that is to create a new list as you go

I don't see a reason for a new list.
Assuming your stuff is eg. in a std::list, you either iterate or erase:

Code: [Select]

for (std::list<Particle*>::iterator it= particles.begin(); it!= particles.end(); )
{
  Particle *particle= *it;
  if (particle->isDead())
  {
    it= particles.erase(it);
    delete particle;
  }
  else
    it++;
}


[Pixel_Outlaw]

Thanks to you both!

C++ sure is a monster when you get beyond the textbook stuff. I'm sticking with it though.

[Jim]

->hellfire - in C# you have to create a new list - modifying any enumerable type means its iterator gets broken (if you code in C# you almost certainly already know this of course).  In C++ much the same happens for std::vector types, but std::list is 'special', which I didn't know, and is why I came back to my post and crossed it out
I'm not that familiar with stl.  The spec for it is immense, comparable to the C++ standard itself, and complicated and I'm not surprised that people find it hard to understand.
http://www.sgi.com/tech/stl/table_of_contents.html

Jim

[hellfire]

In C++ much the same happens for std::vector types, but std::list is 'special'

The iterator interface works the same way for all containers, so the user can use the same code no matter which container he's actually using.
Both, vector and list, return a valid iterator when erasing an element.
std::vector is not particularly made for random insertion and deletion, though.
I'm wondering why they use a different approach in C#.

[Jim]

I searched for a good long while about that.  One reason is thread safety.  Versioning the iterator means you get thread 'safety' i.e. an exception without the overhead of locking.  I couldn't find any other reasons.

Apparently .Net4.0's concurrent collections allow it to work even with multithreading.

Jim

[relsoft]

I don't use a list as much as possible.  They have a tendency to slow your particle system down (cache misses). Same with polymorphism in general (vtable).

However, you could make things polymorphic and fast by using something like this system.
Enemy header:

Code: [Select]

/******************************************************************************
*******************************************************************************

Bubble Fight EX
relminator
http://rel.betterwebber.com


Cancer class


*******************************************************************************
******************************************************************************/

#include <nds.h>
#include <vector>

#include "EntityContainer.h"
#include "StarFighter.h"


#ifndef BLOB_H
#define BLOB_H

//------------------------------------------------------------------------------
// Blob Enemy
//------------------------------------------------------------------------------
class Blob {

public:
friend class BlobContainer;

Blob();
~Blob();
void Update();

private:
s32 x;
s32 y;
s32 Dx;
s32 Dy;
s32 Sx;
int Radius;
int Frame;
int Counter;
bool Active;

EN_DRAW_MODE DrawMode;

};

//------------------------------------------------------------------------------
// Blob Container
//------------------------------------------------------------------------------
class BlobContainer : public EntityContainer
{

public:

BlobContainer( int Palette, glImage* const Sprites );
    ~BlobContainer();
    virtual void UpdateEntities();
virtual void DrawEntities();
virtual bool Collide( StarFighter &Star );
void Spawn(  int _x, int _y, s32 speed, int _radius );

virtual int NumEntities()
{
return numEntities;
}

private:
int numEntities;

glImage *Images;
int ColorTable;

std::vector<Blob> Blobs;


};

#endif // BLOB_H


Enemy Class

Code: [Select]

/******************************************************************************
*******************************************************************************

Bubble Fight EX
relminator
http://rel.betterwebber.com


Cancer class


*******************************************************************************
******************************************************************************/

#include "Blob.h"

#define MIN_X ( -20 << 12 )
#define MIN_Y ( -18 << 12 )

#define MAX_BLOBS 16

//------------------------------------------------------------------------------
// Blob Enemy
//------------------------------------------------------------------------------
Blob::Blob()
{
Frame = 0;
Active = false;
DrawMode = EN_NORMAL;

}

Blob::~Blob()
{
}


void Blob::Update()
{
Sx += Dx;
x = Sx + sinLerp( Counter * 230 ) * Radius;
if( x < MIN_X )
Active = false;

Counter++;
// animate
if( ( Counter & 3 ) == 0 )
{
Frame = (Frame + 1) & 3;
}

}


//------------------------------------------------------------------------------
// Blob Container
//------------------------------------------------------------------------------
//--------------------------------------
// Ctor and Dtor
//--------------------------------------
BlobContainer::BlobContainer( int Palette, glImage* const Sprites )
{
ColorTable = Palette; // init needed data for drawing
Images = Sprites;
Blobs.resize( MAX_BLOBS/2 ); // 1/2 of max (speed of iteration)
Blobs.reserve( MAX_BLOBS ); // reserve max for speed.  No need to do this for enemies
}

BlobContainer::~BlobContainer()
{
Blobs.clear(); // clear the bullets
}

//--------------------------------------
// Virtual Functions
//--------------------------------------
void BlobContainer::UpdateEntities()
{

std::vector<Blob>::iterator iter;
for( iter = Blobs.begin(); iter != Blobs.end(); ++iter )
{
if( iter->Active )
iter->Update();
}

}

void BlobContainer::DrawEntities()
{

glColorTable( GL_RGB16, ColorTable );
numEntities = 0;
std::vector<Blob>::iterator iter;
for( iter = Blobs.begin(); iter != Blobs.end(); ++iter )
{
if( iter->Active )
{
numEntities++;
if( (iter->DrawMode == EN_WHITE) )
{
iter->DrawMode = EN_NORMAL;
glColorTable( GL_RGB256, Palettes::Instance()->Green() );
glSprite( (iter->x >> 12) - 19, (iter->y >> 12) - 18,
      GL_FLIP_NONE, &Images[iter->Frame]
    );
glColorTable( GL_RGB16, ColorTable );

}
else
{
glSprite( (iter->x >> 12) - 19, (iter->y >> 12) - 18,
  GL_FLIP_NONE, &Images[iter->Frame]
    );
}

}
}

}

bool BlobContainer::Collide( StarFighter &Star )
{
std::vector<Blob>::iterator iter;
for( iter = Blobs.begin(); iter != Blobs.end(); ++iter )
{
if( iter->Active )
{
int rad2 = 16 * 16;
int cx = (iter->x >> 12) - (Star.x >> 12);
int cy = (iter->y >> 12) - (Star.y >> 12);
if( ( (cx * cx) + (cy * cy) ) < (rad2 * (1+Star.IsBursting())) )
{
if( Star.IsBursting() && (iter->DrawMode == EN_NORMAL) )
{
if( (iter->Counter & 1) ) iter->DrawMode = EN_WHITE;
}
return true;
}
}
}
return false;
}


//--------------------------------------
// Non-Virtual Functions
//--------------------------------------
void BlobContainer::Spawn( int _x, int _y, s32 speed, int _radius )
{

bool SlotFull = true;      // value to check if all the slots are occupied

std::vector<Blob>::iterator iter;
for( iter = Blobs.begin(); iter != Blobs.end(); ++iter )
{
if( !iter->Active ) // insert a bullet on a free slot
{

iter->Sx = _x << 12;
iter->y = _y << 12;
iter->Dx = speed;
iter->Dy = 0;
iter->Active = true;
iter->Frame = 0;
iter->Counter = 0;
iter->Radius = _radius;
SlotFull = false; // there's a free slot so we dont execute the code below
break;

}
}

// All the slots are full
// Only push back a bullet if the slot is full and we have less than numbullets
if( SlotFull && (Blobs.size() < MAX_BLOBS) )
{
Blob Blob;
Blob.Sx = _x << 12;
Blob.y = _y << 12;
Blob.Dx = speed;
Blob.Dy = 0;
Blob.Active = true;
Blob.Frame = 0;
Blob.Counter = 0;
Blob.Radius = _radius;

Blobs.push_back(Blob);
}

}


Notice that BlobContainer is a "friend" of Blob.
Then, by containing the container in this abstract class...

Code: [Select]

/******************************************************************************
*******************************************************************************

Bubble Fight EX
relminator
http://rel.betterwebber.com


EntityContainer class


*******************************************************************************
******************************************************************************/


#include "StarFighter.h"
#include "Palettes.h"

#ifndef ENTITYCONTAINER_H
#define ENTITYCONTAINER_H

enum EN_DRAW_MODE
{
EN_NORMAL = 0,
EN_COLOR,
EN_WHITE
};

class EntityContainer
{

public:
    virtual void UpdateEntities() = 0;
virtual void DrawEntities() = 0;
virtual bool Collide( StarFighter &Star ) = 0;  // should also contain SFX and Explosion classes
virtual int NumEntities() = 0;
};

#endif // ENTITYCONTAINER_H




Updating and everything is easier.

Code: [Select]

// Enemy Containers

CancerContainer CancersC( CancerTexPal, CancerImages );
MetroidContainer MetroidsC( MetroidTexPal, MetroidImages );
BlobContainer Blobs( BlobTexPal, BlobImages );
TentakillContainer Tentakills( TentakillTexPal, TentakillImages );
CentipedeContainer Centipedes( CentipedeTexPal, CentipedeImages );
SparkyContainer Sparkies( SparkyTexPal, SparkyImages );
RotoSparkContainer RotoSparks( SparkyTexPal, SparkyImages );



std::vector<EntityContainer*> Enemies;

// order of drawing is from centipedes to tentakills
Enemies.push_back( &Centipedes );
Enemies.push_back( &Sparkies );
Enemies.push_back( &RotoSparks );
Enemies.push_back( &MetroidsC );
Enemies.push_back( &CancersC );
Enemies.push_back( &Blobs );
Enemies.push_back( &Tentakills );

       // update all enemy types
std::vector<EntityContainer*>::iterator iter;
for( iter = Enemies.begin(); iter != Enemies.end(); ++iter )
{
(*iter)->UpdateEntities();
}



This way, you limit your vtable access per enemy type rather than per enemy.  It even runs fast on the Nintendo DS.

Oh yeah, I don't "delete" but "deactivate", that way your std::vector  does not resize here and there.
Here it is in action:
http://rel.betterwebber.com/junk.php?id=119

If you need an emulator, you can google "no$gba".

The idea behind this system is to combine both OOP and DoD (Data Oriented Design)

[Pixel_Outlaw]

Thanks for the code snippits relsoft!

This is a bit closer to home to what I might implement. I'm not familiar with "virtual" functions. I'll have to look into those.
Karma + all around gents.