   design issue: entities in multiple lists
  Hi,I'm currently working on a simple 2d arcade shooter named the towship. It uses clanlib and will be released under the GPL. I'm not only trying to make a nice game, but I'm especially trying to learn from creating the game.Although I've visited these forums quite often now, I never posted anything before really. But now I've got something I'm kinda stuck at and I figured you guys (and girls?) might have suggestions.I've got alot of entities (ships, missiles, particle-systems etc etc) that need to be stored at different locations. There's a list of entities that can collide with others, lists of entities determening the draworder, lists for AI-related stuff and a Level class that's got all entities.It should be noted that some, or even most, entities reside in more  lists at the same time. For example an enemy ship needs to be in a drawlist, collision list, AI list and 'level' list.How would you handle entity-object creation, adding them to the lists and especially how would you make sure deleted objects get removed from all lists.I've considered things like reference counting, visitor pattern, etc. But everything I've made or designed until now somehow seemed incomplete or over-designed (especially the latter actually).I'm not afraid of anything, code-wise that is, so hit me!Thanks   
  This isn't a suggestion really, as I imagine having a bunch of lists all over the place is a design problem that could be avoided by doing things slightly differently.Alas, I am not a good designer, so I have lists all over the place as well. The way I've dealt with it is that each class [or object (ship, missile, etc) if you think that way] should know about all of the lists it is/will/can reside in. The object on destruction sould remove itself from all of the lists [or ask via an event, or some similar mechanism].For example in my current project, the unit objects are kept within two lists, one for the empire they belong to, and one for the tile they occupy. In unit::unit() the created unit is added to both lists. It changes lists as it moves from tile to tile and in the case of a control change. When the unit dies, it knows which empire owns it, and while tile it occupies, so it removes itself from each list on death.This generally works fine for me. It's a little... heavy handed I guess, but I've only run across two gothchas. One was that certain times a parent object is being deleted, causing all of its children to be deleted. If the child wants to remove itself from the parent's list badness can happen [because the parent no longer exists...]. The other was interdependancy issues when loading/network-transmitting game info. If two objects require a reference to one another [and have that reference because they're generally created in pairs] they require some trickery when serialized for network communication or save games. This requires an object to be partially created and for the other half of the pair to "fill in the gaps" once the client recieves both parts. Messy. Functional though.;  Multiple lists at once is not necessarily bad IMHO. That's how i process things now and also in my previous project. It really isn't that hard to manage as long as you set some policies from the start about who can delete what and stick to it. The trick i will suggest is this:class Example {public:   Example { registry.push_back(this); }   ~Example { registry.erase( registry.find(this) ); }   // you can do the following or use some fancy kind of iterator   unsigned int GetNumExamples() { return registry.size(); }   GetExample( unsigned int index ) { return registry.at(index); } }private:   // static list that keeps track of all Examples in existance:   // also consider using a std::list   static std::vector<Example*> registry   }You can do this trick for all of your classes, even inherited classes since the list if private. That way a class Thing: public OtherThing, public Whatever {}will be in three lists, one for each class.   ;  hey, just recently i ran into a similar problem and used a factory class that contains "proto-typical" instances. basically the factory class has the stl map container in it, and when it is contructed it adds keys to objects withen the map.std::map < std::string, baseObject * > objects;and i have another class which manages all instances of all objects, originally i wanted all objects to be stored in the same list (via base class pointers) however this confused the render order, so i decided to split the objects up instead so rendering would be eiaser (probably faster since i dont have to sort the lists) so adding a game object would go like this ...manager->addObject(factory->getObject("Ship01"));and by ussing RTTI / dynamic_cast i determine what kind of object and store it in the correct list ...so i only have 1 list for each kind of object. and these objects are stored by value and only passed as const pointers.you probably have something similar im not sure. i would suggest though that you never store the same objects by value more than once. i dont think using multiple lists is bad, but for me i think i would find it confusing. maybe you could make sure you only pass your objects as const pointers, making sure they dont get accidently deleted modified ... so objects that are suposed to be the same stay the same. maybe something like this ...class entityManager {std::list < object * > objectList;std::list < object ** > renderList;std::list < object ** > collisionList;public:// ...};hope this helped in someway.   ;  The problem you describe is a classic case of the Observer pattern. You have an instance of an object which is known by other unrelated (but dependent) objects.Your problem is that you would like the other objects, called Observers, to be notified whenever the first object, called the Subject, changes in a meaningful way. One example you mentioned was the object being deleted; this would obviously be a good time to notify the Observers.You could have the objects you describe inherit from a new interface called, say, ISubject; each of the observer objects could inherit from a new interface called IObserver. In C#, this would look something like this:public abstract class Subject{  #region Members  private ArrayList m_ObserverList = new ArrayList();  #endregion  #region Methods  public void Attach(Observer o)  {    this.m_Observers.Add(o);  }  public void Detach(Observer o)  {    this.m_Observers.Remove(o);  }  public void NotifyAllDeleted()  {    foreach(Observer o in observers) o.NotifyDeleted();  }  #endregion}// ...public abstract class Observer{  #region Methods  public abstract void NotifyDeleted();  #endregion}This is a simple example that only handles the object being deleted. You could easily change the NotifyAllDeleted to be a generic handler that tells the Observer to check the object's new state and receive an update. In C#, this problem crops up so frequently that two programming constructs were built just for it; called delegates and events. This would be an even better way to handle it, though events are a more difficult topic to understand, and I was trying to keep it simple for the post.Good luck!   ;  [Edit]Crap, I just noticed that it is pretty much the same way that ekrax does it.Except for the factory design.[/Edit]I'm not sure if the way I do it is a good way.You decide. Maybe others can warn you and me if it isn't.I'd be interested in knowing that too.I store the pointers to entities, resources, triggers/events and tasks in their own managers in std::map members.Example: typedef std::map< std::string, CEntities* > m_mapEntities;m_mapEntities::iterator m_itEntities;m_mapEntities mEntities;Other Managers like ai manager, render manager(Gui, SceneGraph) just store the identifiers of interesting objects as strings in a list.I don't use a factory design any more because I didn't like that the engine had to know all the resource, entity, ... (and so on) types.So now for example when the gui manager uses an entity it request a pointer to the entity from the entity manager. All the managers need:void BeginFrame();void Idle();void EndFrame();In there other managers can go through the list and ask the entity manager if there have been changes.For example:// for each EntityIdentifier in the listif( false == pResourceManager->EntityExists( strIdentifier ) ){    // remove Identifier from list};  So long as you do not have cycles (A points to B points to C ... points to A), you can use reference counting smart pointers to manage the lifetime of your objects.That is, instead of directly using pointers, you use objects which behave like pointers - such as boost::shared_ptr - it makes things really painless.class Foo {};typedef boost::shared_ptr<Foo> spFoo;std::list<spFoo> l;std::vector<spFoo> v;v.push_back( spFoo(new Foo) ); // v[0]v.push_back( spFoo(new Foo) ); // v[1]v.push_back( spFoo(new Foo) ); // v[2]l.push_back( v[0] );spFoo ptr = v[2];v.clear();When you clear the vector, the Foo pointed to by the spFoo at v[1] will get destroyed, but not the other two, since they are still some spFoo referencing them. Only when those are gone will the corresponding Foo be destroyed.Note that you should avoid manipulating naked Foo* as much as possible, and never create multiple spFoo from a single Foo* (as they would be tracked separately, likely leading to a double-delete problem). Weak references are fun, too. They don't increment the reference count and automatically get notified if the object 'dies'. So you could stick a boost::shared_ptr in some main object list, and boost::weak_ptr everywhere else, periodically filtering dead weak_ptr from those secondary lists.Boost's license is compatible with the GPL.   ;  Thanks for the reactions,Telastyn: Although I would be interested in a method that doesn't use lists, I believe it is dificult to do that. Especially when performance is an issue, because then you'll have different types of requests that can be handled much faster when you sort your entities with different keys. When drawing, for example, I'll need the entities sorted in their draworder, this list doesn't change every frame so storing it somewhere would be a good optimization possibility. But maybe I'm mistaken. Fruny: The main reason I didn't use reference counting is that it doesn't handle a major problem: when objects are deleted it should be removed from all lists. It does however prevent memory leaks, which is a good thing as well.I thought of using reference counting in combination with a 'delete_this' member boolean. If delete_this is set, a list should remove the entity from the list and decrease the reference counting. This can be done, but I don't really like this solution.ekrax: Using pointer pointers seems a possible solution, I could change the pointer in the main list to some generic deleted_entity when the original entity is removed. But I don't like pointer pointers, I'm afraid it could render my code unreadable.kSquared: This indeed seems to be a classic example of the observer pattern. Originally I designed it as such, but when I started coding I thought having the entities renember all observers would be overkill. But maybe I was mistaken.I think I'll look into the observer pattern once more, thanks for the advice... I'm still open to other suggestions though.   ;  Well, here's a bruteish and weird method:struct ientity;struct isound_entity;struct irender_entity;template < typename EntityT > struct entity_pool{    static std::list< EntityT * > items;    template < typename FunctorT > void apply( FunctorT functor )    {   foreach( items.begin() , items.end() , functor );    }};template < typename EntityT > std::list< EntityT * > entity_pool::items;struct ientity{    ientity( void ) { entity_pool< ientity * >::items.push_back( this ); }    virtual ~ientity( void ) { entity_pool< ientity * >::items.remove( this ); }};struct isound_entity : public ientity{    isound_entity( void ) { entity_pool< isound_entity * >::items.push_back( this ); }    virtual ~ientity( void ) { entity_pool< isound_entity * >::items.remove( this ); }};struct irender_entity : public ientity{    irender_entity( void ) { entity_pool< irender_entity * >::items.push_back( this ); }    virtual ~irender_entity( void ) { entity_pool< irender_entity * >::items.remove( this ); }};struct some_entity : public irender_entity , isound_entity //yes, voodoo magic... I will probably die a horrible death{    //...};struct make_sound_functor{    //...};struct render_functor{    void operator()( irender_entity * entity ) { entity->render(); }};void mainloop( void ){   //...   entity_pool< isound_entity * >::apply( make_sound_functor() );   entity_pool< irender_entity * >::apply( render_opengl_functor() );   //...};  What about using std::maps, std::lists and Identifiers?You wouldn't need pointer pointers.I guess you stopped reading my post because I wrote that my solution is similar to ekrax's?   