# Keeping a list of objects in a game

## Recommended Posts

Eralp    142
Hello, I am a little bit confused about what should I do.
Here is what I am trying to do;
I'll have renderable and physObject base classes. For example grass on my terrain will be inherited only from renderable and a bullet or a player will be inherited from both renderable and physObject. This way I guess it will be easier to check collusions between physics objects.

But I don't know how to store them, I can keep a list of renderable pointers which may point to just renderables OR both renderable and physObjects and put ALL of my game-objects in it. will I be able to check upper-classes from just a pointer to renderable base class?

If not, I'll have to keep renderables and physObjects in a two different lists. But I don't much what to store in a physObject class.. I'll keep a collusion-rectangle for sure. But suppose two physObjects intersected how should I check if one is a player or both are bullets? I may keep an ID in base class for different upper-classes and then if ID == 0 cast the object to player and hurt him if the other is ID == 1 which means its a bullet

Thanks

I reread my post, some parts are not that clear but I guess you'll understand =)

##### Share on other sites
Buckeye    10747
If you store pointers to objects (which is more common), you can have as many lists as you want. The overhead for a "duplicated" object is the size of a pointer.

##### Share on other sites
xibo    110
EDIT: *xibo pull all out...

If you have your struct phyObject in a C++ context, and there is _any_ kind of oop related to it, the C++ compiler will generate so called RunTime Type Information ( RTTI ). You can force most compilers to generate them even without OOP. So a struct
struct physObject{  long position[2];  physObject(); ~physObject();  int collidesWith( physObject const* rval ) const;};

will become the following in non object oriented C:
/* your class */struct physObject{  static const void *vtable;  long position[2];};/* helper structure used for oop purposes */struct physObject_vtable{  static const size_t number_of_parent_classes;  static const void *parent_classes;  static const void (*constructor)(struct physObject *this);  static const void (*destructor)(struct physObject *this);  static const int  (*collidesWith)(struct physObject const* this, physObject const* rval);};void physObject_constructor(struct physObject *this);void physObject_destructor(struct physObject *this);void physObject_collidesWith(struct physObject const*this, struct physObject const*rval);

The physObject_vtable struct ( which is not called like that, and in fact has it's name hidden and compiler implementation dependent ) gets its function pointers as well as vtable pointer array (the void* at my example) initialized to the corresponding vtables/functions. Also, this vtable is equal for all instances of physObject ( but not for child classes of it ), i.e. physObject::vtable is equal for all physObjects ( implied by static const ).

Now, if you call a function of an physObject instance from a C++ context:
physObject a, b;/*...*/a.collidesWith(&b);

the call transforms to vanilla C:
((struct vtable*)(a::vtable))->collidesWith(&a,&b);

While calling a function of physObject that is inherited from one of it's parent classes will instead recursively ( again this is compiler dependend ) traverse the inheritance tree(called parent_classes in my example) and call the closes function found ( virtual functions are in the vtables of children ).

Now, if you want to determine whether an instance of a structure is of type physObject or of type renderable, the fastest way to do that is to check whether the vtable of physObject (or renderable) appears in the vtable of the instance's inheritance tree, or, in the trival case, IS the vtable of the instance. The vtables are compared by comparing the memory addresses they are stored in, and that can be done in one proccessor cycle per address on todays (IBM) PCs.

However there is one problem, namely the name of the vtable is compiler dependend, hard to lookup in literature, and "hidden" from the contexts. But for this purpose, C++ offers a mechanism which does exactly this comparisations, called dynamic_cast<typename Type>(Type). The dynamic_cast operator returns a casted instance to the requested type of a given memory address, or zero/"null" if the type of the pointed structure is not a child of the requested type or the type itself.

So if you want to traverse the list for rendering, just make a list of renderables (actually you _most_probably_want_ pointers to them instead of instances, especially if sizeof(physObject) is not sizeof(renderable) ), and run it in your favorite loop. Then, when doing the collision detection, run something the likes of
for( List<renderables*>::const_iterator i=list.begin(),e=list.end(); i!=e; ++i ){  physObject const* collidable = dynamic_cast<physObject const*>(*i);  if( !collidable ) /// not physObject or a child    continue;  /* handle collisions */}

Hope this helped.

Also, compilers might not emit the vtables of "normal" structs, especially when using optimization. For this purpose it is common to define a dummy destructor (or declare the present destructor to be virtual) which forces the compiler to extract the vtable and eventually gets optimized out anyway. You can check whether a vtable pointer is present by checking whether sizeof(yourStruct) is equal to the sum of the sizes of all member instances or it somehow seems to be larger by the size of a pointer.

[Edited by - xibo on November 13, 2010 3:35:41 PM]

##### Share on other sites
xytor    136
Ok, let's not get overly complex here.
In game development, large or complicated inheritance trees are not the solution.
Consider using composition instead: your player HAS a physObj inside, and also a renderable.
This is the basis for many component based engines.

class Player{  physObj* myPhysics;  renderable* myGraphics;  //other stuff relevant to the player};

##### Share on other sites
xibo    110
Quote:
 Original post by xytorOk, let's not get overly complex here.In game development, large or complicated inheritance trees are not the solution.Consider using composition instead: your player HAS a physObj inside, and also a renderable.This is the basis for many component based engines.*** Source Snippet Removed ***

However if he wants to store a LIST of all renderables/physobjects, keeping structs like that is counterproductive as you'll have to remove the pointers to your struct's members from the list at the struct's destruction ( can happen quite often with bullets or grasses ), which is expensive as you have to traverse the whole list just to remove one pointer in worst case, and it is required to have the list visible to the destructor.
It could be optimized by having the list get sorted by the memory addresses reinterpreted to size_t, however the stl::set won't do this so you'll either have to write your own list type or use stl::set<size_t> where the size_t are actually pointers, which is IMO ugly and can easily lead to confusion if forgotten/not told which again leads to bugs.

The alternative would be to use a struct like you proposed for ANY object, and store a list of those structs, where all non-renderable objects have the renderable pointer set to some symbolic value ( i.e. null ), but then he can also just multi-inherit and save those unneeded pointers (you'll "pay" the vtables and the indirect member function invocation anyway when grasses becomes the child of renderables, not just when there's multiple inheritance )...

##### Share on other sites
Hodgman    51229
Quote:
 Original post by xytorlarge or complicated inheritance trees are not the solution.
I agree with this sentiment. Composition is almost always preferable to inheritance.

Also, sorting objects by type is often preferable to branching on type (and dynamic_cast is never preferable).

To expand on xytor's example:
class PhysObj;typedef boost::function<void(const PhysObj&)> OnHitCallback;class PhysSystem{public:  void Update()  {    for( int i=0, s=m_Objects.size(); i!=s; ++i )    {      PhysObj& obj = *m_Objects[i];      PhysObj* collidesWith = CheckForCollisions(obj);      if( collidesWith && obj.m_OnHit )        obj.m_OnHit( *collidesWith );    }  }private:  friend class PhysObj;  //{  void AddObj( PhysObj& o ) { m_Objects.push_back(&o); }  void RemObj( PhysObj& o )   {    tyepdef std::vector<PhysObj*>::reverse_iterator iterator;    iterator itLast = container.rbegin();    iterator itEnd  = container.rend();    iterator itFind = std::find( itLast, itEnd, &o );    *itFind = *itLast;    container.resize( container.size()-1 );  }  //}  std::vector<PhysObj*> m_Objects;};class PhysObj{public:   PhysObj( PhysSystem& s ) : m_Sys(s) { m_Sys.AddObj(*this); }  ~PhysObj()                           { m_Sys.RemObj(*this); }  OnHitCallback m_OnHit;private:  PhysSystem& m_Sys;  //noncopyable  PhysObj( const PhysObj& );  PhysObj& operator=( const PhysObj& );};class Player{public:  Player( GfxSystem& g, PhysSystem& p ) : myPhysics(p), myGraphics(g)  {    myPhysics.m_OnHit = boost::bind( &Player::OnCollide, this, _1 );  }private:  void OnCollide( PhysObj& other )  {  //...  }  PhysObj myPhysics;  GfxObj  myGraphics;  //other stuff relevant to the player};

Quote:
 Original post by xiboas you'll have to remove the pointers ... from the list at the struct's destruction, which is expensive as you have to traverse the whole list just to remove one pointer in worst case
Doesn't this happen whether you have a list of 'objects' or separate lists of 'physObjects' and 'graphicsObjects'? The only difference is you have to remove the object from two lists.
Quote:
 It could be optimized by having the list get sorted by the memory addresses reinterpreted to size_t, however the stl::set won't do this so you'll either have to write your own list type or use stl::set where the size_t are actually pointers, which is IMO ugly and can easily lead to confusion if forgotten/not told which again leads to bugs.
You could just use a vector of pointers. If you want a sorted vector, you can just use std::sort each update if the list has been modified. If the list only has a few hundred elements, then std::sort will be pretty damn fast. If it's got thousands, you can use a radix sort instead.

If you want to optimise the removal, you can batch up remove commands and process them all at once. If both the list of pointers and the remove-queue are sorted, then you've only got to traverse the list once per batch (of any size), instead of once per removal.
Quote:
 The alternative would be to use a struct like you proposed for ANY object, and store a list of those structs, where all non-renderable objects have the renderable pointer set to some symbolic value
This falls apart when you start having lots of components (e.g. more than just 'physics' and 'renderable').
Quote:
 can also just multi-inherit and save those unneeded pointers (you'll "pay" the vtables and the indirect member function invocation anyway when grasses becomes the child of renderables, not just when there's multiple inheritance )...
High level things like "grass" shouldn't inherit from renderable, they should be composed out of renderables.
e.g. Grass has one or more draw calls that allow it to be displayed, but grass is not a draw call.