Sign in to follow this  
RanmaruX

Lists containing different types (and determining what type an element is)

Recommended Posts

RanmaruX    122
This is sort of a number of different problems all related... 1. I'm just wondering what methods are available for storing a list of elements that can be different types. Perhaps something provided by the STL? 2. I'd also like to be able to examine an element and determine what type it is somehow. 3. Also... (and this is related) would it be possible to write code that calls a function passing different parameters depending on different cases without actually having to use if / case. Pseudocode example: Instead of: if( Element.type == "enemy" ) Element.DoStuff( enemyarg1, enemyarg2 ); else if( Element.type == "projectile" ) Element.DoStuff( projectilearg ); I would like: if( Element.type == "enemy" ) args = dunno; //some way of containing both enemyarg1 and enemyarg2// else if( Element.type == "projectile" ) args = projectilearg; Element.DoStuff( args ); where args is somehow able to contain an abstract set of arguments... I suppose what I mainly need to know is how to contain said "abstract set of arguments" and how to write a function that can take args of that type and process them. EDIT: Sorry, I'm using C++ EDIT AGAIN: I've just realised a major problem with the above :p It assumes that Element actually *has* a function called DoStuff() Ok... let's assume that my list will only contain elements that inherit from class Thing; which has a virtual DoStuff() function.

Share this post


Link to post
Share on other sites
RanmaruX    122
Sorry to overcomplicate, I think I can clarify this a bit :)

class Thing
{
virtual DoStuff( Bunchofargs Args );
}

Enemy and Projectile both inherit from Thing and are stored together in one list...

They both need different information for their implementation of the DoStuff() function...

I'd like to iterate through my list and pass in a different kind of information depending what type each element is...

I'd like some way of defining and interpreting a "Bunchofargs" type...

Share this post


Link to post
Share on other sites
jpetrie    13159
1). STL containers cannot contain objects of different (static) type. You can store base class pointers in a container, however, where the actual pointers may point to different subclasses. If that is the case you can provide a sorting metric in the base class and use the regular sorting methods.

2). RTTI; using typeid or dynamic_cast can tell you. You can also embed a getType() member in your base class.

3). If you want to call different overloads of a function based on type in the way you've described, you might have a larger design problem. What's the larger scope of the problem you are trying to solve? Manual type-switching is icky, in the general case.

Quote:

They both need different information for their implementation of the DoStuff() function...

If this is true, then they are poorly designed. Probably they should not both inherit from Thing; but also possibly DoStuff should be removed and/or made non-virtual or you should re-think why and how the subclasses get the data they need for DoStuff().

Just because you can apply an "is-a" relationship doesn't mean you should. Enemy and Projectile may both "be Things," but if their fundamental behavior is that different from eachother than the relationship is broken.

FWIW, I've rarely ever found it neccessary for projectiles and enemies to derive off a common base class like this.

Share this post


Link to post
Share on other sites
RanmaruX    122
I see, thanks for the input! I suppose for question #1 I would just use something like a vector of Thing* pointers.

The general idea is that I'd like to be able to expand my program and add different classes to it without having to change my "loop through EVERYTHING and update it" code everytime I do. At the moment I've got to loop through all the projectiles and call Update() then loop through all the enemies and call Update() and then say I add particle emitters, I'll have to go into that .cpp file again and add code to loop through all the emitters and call Update() again. It would be nice to have that .cpp file (if not just that one function) applicable to many different programs that make use of different types.

Enemies and projectiles were just an example really. The relationship might seem more obvious if I'd used something like PlayerCharacter and EnemyCharacter. The relationship between the different types (and their reason for being derived from the same parent) is that they both have to be iterated through and updated every frame. So let's say the parent class is an "Updateable" rather than a "Thing" for clarity.

Share this post


Link to post
Share on other sites
jpetrie    13159
But just because everything in your game will need updating every frame (which is, first of all, not true) doesn't mean that everything needs to be in one big master list -- that leads to problems.

One of those problems is what you've just encountered yourself: some subtypes of your base class require additional information to properly update themselves. The "solutions" to this are to type switch and call appropriate overloads (this implies you'll have to modify the type switch when you need to extend it to support a new subtype, something you are trying to avoid and something that is brittle in general); or to have the subtype provide modifiers to store off the extra data they need; their update functions will refer to the stored data. This means you'll need a seperate loop to iterate through each subtype list and set that data. Again, basically the same problem as the first solution; or something else equally crude.

Another one of the problems is locality of reference. You probably don't have fine control over the ordering of the elements in this master-list-of-stuff-to-update. When a new object is added, it'll get shoved at the end of list... it might not be near any other objects of its type, at all. Your list might look like: player, enemy, particle, missile, enemy, particle, particle, particle, power-up, enemey... et cetera. Not cool.

Since everything is in one big list, removing objects from that list (since its not ordered in any fashion) is going to be a linear operation... and the length of the list will be long. If you are trying to remove an enemy from the list, you'll potentially have to search through all of your particles and power-ups as well. If enemies weren't in the same list as particles, et cetera, you'll cut down on your search time dramatically.

Since everything is in one big list, efficiently culling objects that don't need to be rendered or processed (because they are out of the view frustum, or whatever) is more difficult, mostly for the above reasons.

In short, Just Say No to treating all objects as the same thing and updating them all in one big list. What you think you are saving in development and maintainence effort isn't really going to be a savings. Some things are fundamentally DIFFERENT and require different processing, different means of rendering, culling, handling in general.

Perhaps part of your problem is the apparent centralization of your updates. The update for the enemies should be in the management subsystem for enemies, and the one for particles should be in the one for particles. The central game itself shouldn't be manually iterating these lists and updating them, as it increasing interdependancy between the enemey management (or whatever) subsystem and the game itself. You cannot transparently alter the way that enemies are processed; you must modify external code to do so.

Share this post


Link to post
Share on other sites
snk_kid    1312
C++ isn't paritcular well suited to this however there are methods to have some form of heterogeneous containers in C++:

True heterogeneous container:

A limited form of true heterogeneous container exist via Boost.Fusion 2.0, i think it's about to go into review to be an offical part of boost. I say there limited because you can't add new types at runtime.

Another thing to relize there immutable containers there more functional-like, this is doesn't mean it's bad thing just that if you're not use to functional programming (no not procedural) you'll need to make a slight adjustment in your thought process. If you have experience with STL you should be alright with them in general. The advantage they have is it's completely type-safe and checked at compile-time.

Faking heterogeneous containers:

  • Abuse OO, erase static type information into some base type, use sub-type polymorphism and/or visitor pattern and/or casting syndrome.


  • Again abuse OO, have a container of boost::any, use the visitor pattern and/or casting syndrome


  • For a small set of types you can have a container of boost::variant, this is more type-safe than the previous two methods, the only (minor) problem is if you need to a new types to the set you'll need to add it to the pre-existing list of types and then recompile.

Share this post


Link to post
Share on other sites
Well, you don't have to abuse OO. In fact, you can still manage a lot of small lists, and implement an update manager that will update all your lists :)


#include <list>
#include <vector>
#include <algorithm>
#include <functional>

class Updater
{
public:
Updater() { }
virtual ~Updater() { }
virtual void update() = 0;
};

class UpdateManager
{
std::vector<Updater*> mUpdaters;
public:
void registerUpdater(Updater *updater)
{
mUpdaters.push_back(updater);
}
void unregisterUpdater(Updater *updater)
{
mUpdaters.erase(std::remove(mUpdaters.begin(), mUpdaters.end(), updater), mUpdaters.end());
}
void update()
{
std::for_each(mUpdaters.begin(), mUpdaters.end(), std::mem_fun(&Updater::update));
}
};

template <class container> class ListUpdater : public Updater
{
container& mContainer;
// typedef container::value_type contained;
public:
ListUpdater(container& c) : mContainer(c) { }
virtual ~ListUpdater() { }
virtual void update()
{
// for a reason I don't understand, the following line keep saying
// me "illegal call of non-static member function". Any clue?
// std::for_each(mContainer.begin(), mContainer.end(), std::mem_fun(&contained::update()));
typedef container::iterator iterator;
for( iterator it = mContainer.begin(); it != mContainer.end(); it++) {
it->update();
}
}
};

class A
{
public:
void update() { std::cout << "update A" << std::endl; }
};

class B
{
public:
void update() { std::cout << "update B" << std::endl; }
};

int _tmain(int argc, _TCHAR* argv[])
{
std::vector<A> vectA;
std::list<B> listB;
std::vector<B> vectB;

vectA.resize(5, A());
vectB.resize(3, B());
listB.resize(2, B());

ListUpdater<std::vector<A> > vaUpdater(vectA);
ListUpdater<std::list<B> > lbUpdater(listB);
ListUpdater<std::vector<B> > vbUpdater(vectB);

UpdateManager manager;

manager.registerUpdater(&vaUpdater);
manager.registerUpdater(&vbUpdater);
manager.registerUpdater(&lbUpdater);

manager.update();

std::cin.get();

return 0;
}




You just have to add the Updater specialization you want (if you need it to do some fancy stuff) and voilà.

HTH,

Share this post


Link to post
Share on other sites
RanmaruX    122
I didn't want to go into the specifics of my own program because I wanted to keep the question general but the way I've done things might be more relevant than I thought now.

What I actually have is:

- an ArrowManager class, one of which contains a list of arrows (basically a projectile) and an Update function to update all arrows in the list
- an Enemymanager class which does the same thing for enemies

Then in FrameUpdate() I'm calling the following (the arguments aren't exactly what I'm passing but the principle's the same):

ArrowManager.Update( pWalls, fElapsedTime );
EnemyManager.Update( pPaths, fElapsedTime );

However I've found with all the various managers I'm adding to the game, this list is getting quite large and messy. What I was imagining (and I think this is what Emmanuel is referring to) is having a "list of managers" (so element 0 is an ArrowInterface, element 1 is an EnemyInterface, element 2 is potentially an EmitterInterface). I could even go on to have a manager for managers... :)

Then I'd basically iterate through my list of managers calling each manager's Update() function (bear with my simplified pseudo code):

// Loop
CurrentManager.Update( args );
// Next

This whole system becomes more useful when you realise that it also applies to iterating through all my managers and calling their Init() and CleanUp() functions!

I fear jpetrie may be right about this though because every time I implement a new class, I'm going to have to change this code so that it puts different information in the args. I'll probably have to do this for every class I add... Unless when I initialise my ArrowManager, I can obtain a permanent pointer to pWalls and fElapsedTime! Then I won't have to pass any args in my Update() function at all. The plot thickens...

Share this post


Link to post
Share on other sites
jpetrie    13159
Quote:

// Loop
CurrentManager.Update( args );
// Next


Doing this would be icky, and I'll repeat that I don't think you should. Some of what I mentioned previously may be invalidated by your design, but the fact that not everything needs updating the same way still holds: Sometimes you don't actually update entire collections of things every frame. Sometimes you may want updateable lists updated more than once per frame.

Quote:

I could even go on to have a manager for managers... :)


Ew. :P
I think you are bordering on, or have reached the point of, attemping to overgeneralize things. There's precious little difference of effort in the following two means of adding something to the list of updating interfaces:


// During game startup:
UpdateManagers.push_back(playerManager);
UpdateManagers.push_back(particleManager);

// or, during game update:
playerManager.Update( args );
particleManager.Update( different args );


adding a new update management interface requires one line of code to be changed in both cases, and in both cases the lines of code are part of the "game" so neither is more encapsulated than the other.

However the latter method allows you to specify the appropriate arguments without having to muck about with polymorphism abuse or other hacks that are likely to make your code less readable.

Share this post


Link to post
Share on other sites
BTownTKD    205
I'm really really sorry in advance: this is completely off-topic from the original post.

But,

OMG!!1! jpetrie's user rating is t3h "1337"!!! Way to go. Was that on purpose?

Share this post


Link to post
Share on other sites
NotAYakk    876
I'll leave the flaws in your design to others, and see if I can get your design to work:

class GameState {
public:
virtual data_1 get_data_1() = 0;
virtual data_2 get_data_2() = 0;
// etc -- but with better function names.
};

class Thing {
public:
virtual void DoStuff( GameState* ) = 0;
};

template<class iterator>
void DoUpdates( iterator begin, iterator end, GameState* state ) {
{for(iterator i = begin; i != end; ++i) {
(*i)->DoStuff(state);
}}
}

class ThingTypeA {
struct MyArguements {
double width;
int cheese;
};
static MyArguements GetMyArguements(GameState* state);
void DoActualWork( MyArguements args );
virtual void DoStuff(GameState* state) {
DoActualWork( GetMyArguements(state) );
}
};


Note that the details of ThingTypeA are not set in stone -- but extracting out only what ThingTypeA needs from the GameState can help with keeping side effects down. Other times you'd want full access to the GameState.

Going further down the "how close can I get to what you asked for"...

Expand the interface for the Thing:

class Generic;
class StateMessages;

class Thing {
public:
virtual void ExtractArguements( GameState* state, std::vector<Generic>& args ) const = 0;
virtual void DoStuff( std::vector<Generic> const& args ) = 0;
};


where your "Generic" class is a boost variant, a pointer to a polymorphic base class, or some other many-typed item.

In effect, your Things have different code, but they get their information from the same (large) source -- the game state. You can attempt to isolate your Things from the entire game state by some of the methods above.

Share this post


Link to post
Share on other sites
jpetrie    13159
Quote:

OMG!!1! jpetrie's user rating is t3h "1337"!!! Way to go. Was that on purpose?


Not at all. And so far three people, at least, have pointed it out. The sooner it changes the happier I'll be :)

Share this post


Link to post
Share on other sites
Quote:
Original post by jpetrie
Quote:

OMG!!1! jpetrie's user rating is t3h "1337"!!! Way to go. Was that on purpose?


Not at all. And so far three people, at least, have pointed it out. The sooner it changes the happier I'll be :)


Oh! teh noes! You're no longer 1337 :'(

Wait, I may be able to give you your leet rating again if I --rate you... Er. No. It doesn't sound like a good idea [grin]

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