[C++] Store objects of different type in the same vector (of other container)

4cb4fbeb06e93e1ebb4982174b9fa8a2
0
Ph_nyx 101 Sep 21, 2005 at 13:29

Hi !

I plan to make a simple 2D “Zelda-Like” RPG in C++. The main idea of the game engine is to use C++ objects and just code some basic member functions to make them interact together. Those objects can be some world elements, or some monsters, items etc.

All those objects will be hard-coded (I thought about creating a script language to create / program them but it seems to be a little bit too complicated for a first game). All the objects will have the same member functions. For example, for monster interactions we would have stuff like that :

monster1->attack(monster2); // monster1 attacks monster2

In this case, monster1 and monster2 would be 2 objects instanciated from 2 different classes, but inherited from one super class (Entity) :

Class Entity (the superclass)
Class Orc inherited from Entity
Class Troll inherited from Entity
Class Goblin inherited from Entity
etc.

monster1 and monster2 could be Orc, Troll, or Goblin.

In the game, I want a big container with all the game objects inherited from Entity (a vector for example). Of course, I would like the class member functions can deal with all Entity types (as well Orc, Troll and Goblin) and have a very clear and generic code.

I’ve seen stuff about “dynamic binding” and “virtual functions” that allows to deal with different classes inherited from a superclass, such as this FAQ (http://www.parashift.com/c++-faq-lite/virtual-functions.html#faq-20.8 I’ll have a look on it later ;)) but I really don’t know how to mix all that and make it works.

Any idea ? :)

10 Replies

Please log in or register to post a reply.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Sep 21, 2005 at 13:38

I suggest you have a look at that article right now (or better yet, even before you opened this thread, but it’s too late for that now :)). Why are you using inheritance if you’re not using virtual functions?

The idea is you make a std::vector<Entity*> in which you place pointers of all your instances.

22b3033832c5c699c856814b0cf80cb1
0
bladder 101 Sep 21, 2005 at 13:43

I suggest you read it now :). And not just section 20.8, but the entire thing:

http://www.parashift.com/c++-faq-lite/virtual-functions.html

But either way, to do what you want youd have your base class “Entity” that has a virtual attack function. You’d derive Troll Orc and what not from Entity. Then you’d create an std::vector of Entiry pointers. Then you can just manipulate them how you expect to.

vector[0]->attack(vector[1]) // etc…

[edit]
apparently posted a bit too late…
[/edit]

6aa952514ff4e5439df1e9e6d337b864
0
roel 101 Sep 21, 2005 at 15:20

You are on the right way, and as my predecessors said: read the article. welcome to the beautiful world of polymorphism ;)

25bbd22b0b17f557748f601922880554
0
bramz 101 Sep 21, 2005 at 16:52

Very carefully i’m going to say that you’ll probably also need the “double dispatching pattern”. What on Earth is that monster (no pun intended)?

Well, probably you’re going to want to do different things when an Orc is attacking a Troll or a Goblin. The problem is, how is that attack function going to know whether it is attacking Troll or Goblin?

If you know about function overloading, you might think that’s going to solve your problem because you say “hey, i just overload attack for trolls and goblins”. Unfortunately, it’s not going to work.

// overloading looks usefull, but it's not going to work.
void Orc::attack(Troll* victim) {}
void Orc::attack(Goblin* victim) {}

The problem is that when the actual attack happens, you’ll only have Entity pointers (remember? you wanted to store all those monsters in one big container). Take the following as an example. We’ll have two monsters: one Orc and one Troll.

// our test case
Entity* monster1 = new Orc;
Entity* monster2 = new Troll;
// ... blablabla ...

// the actual attack:
monster1->attack(monster2);

OK, test case is settled, now we have to get it work. How do we know what attack function to use? Orc’s? Troll’s? Goblin’s? Simple, attack will be a virtual function (read the FAQ :) ), and since monster1 is an Orc, we’ll get in Orc’s attack function. Huray, now the other one.

How does Orc’s attack function know wether it’s attacking a Troll or Goblin? Simple, we’ve overloaded it for both … oh wait … We’re not passing a Troll or Goblin pointer to attack but an Entity pointer! The overloading mechanism is never going to know what function to choose! Even worse, it will not compile, because there isn’t a single attack function that accepts an Entity pointer!

It turns out, we must have an attack function that accepts an Entity pointer. Easily done, but problem now is that we’ll end up in that function regardless if the Orc is attacking a Troll or Goblin. How does the attack function know which one it is?

void Orc::attack(Entity* victim)
{
    // am i attacking a Troll or Goblin?  or maybe another Orc?
}

There are various ways to solve this. One way is to use typeid or dynamic_casts to make a typeswitch and do what to do per type. Like following:

void Orc::attack(Entity* victim)
{
    if (Troll* troll = dynamic_cast<Troll*>(victim))
    {
        // victim is troll (oh dear)
    }
    else if (Goblin* goblin = dynamic_cast<Goblin*>(victim))
    {
        // victim is goblin (too easy!)
    }
    else
    {
        // i dunno what it is ... run!
    }
}

While it works, this is plain ugly but more importan, dynamic_casts are slow, and the complexity is even linear in the number of kind of monsters. Don’t want that.

Another, more interesting, sollution comes from the observation that Orc’s attack function doesn’t know of what type the victim is, but it does know that the aggressor is an Orc! So, you reverse the logic and you let the victim be attacked by an Orc! And then you can use overloading to determine by what kind of monster the victim is attacked. Moreover, since this “be_attacked” function is again a virtual function, the real idenity of the victim will be finally revealed!

All together:

class Orc;
class Troll;
class Goblin;

class Entity
{
public:
    virtual void attack(Entity* victim) = 0;
    virtual void be_attacked(Orc* aggressor) = 0;
    virtual void be_attacked(Troll* aggressor) = 0;
    virtual void be_attacked(Goblin* aggressor) = 0;
};

class Orc: public Entity
{
public:
    virtual void attack(Entity* victim) { victim->be_attacked(this); }
    virtual void be_attacked(Orc* aggressor) { // oh no, my brother is attacking me }
    virtual void be_attacked(Troll* aggressor) { // oh dear }
    virtual void be_attacked(Goblin* aggressor) { // too easy! }
};

class Troll: public Entity
{
public:
    virtual void attack(Entity* victim) { victim->be_attacked(this); }
    virtual void be_attacked(Orc* aggressor) { // oh no, not again! }
    virtual void be_attacked(Troll* aggressor) { // Troll fight! }
    virtual void be_attacked(Goblin* aggressor) { // pff! }
};

class Goblin: public Entity
{
   // ... you get the idea :)
};

// SHOWCASE!

Entity* monster1 = new Orc;
Entity* monster2 = new Troll;

monster1->attack(monster2) // calls void Orc::attack(Entity*) which in turns calls Troll::be_attacked(Orc*)
}

Now the ugly typeswitches are replaced by two virtual function calls (hence double dispatcher :) ) which are both fast and O(1).

However, as you can see, the number of be_attacked functions grows N² with N being the number of monstertypes. So, if you have 10 kind of monsters, you have 100 be_attacked functions. This is getting a maintainance hell, but without the double dispatcher thingy it would have been worse.

There are ways to get around that, but they use nifty template metaprogramming tricks like typelists and things like that. Very nice, but a bit tricky to explain :)

Hope this helps :)

Bramz

25bbd22b0b17f557748f601922880554
0
bramz 101 Sep 21, 2005 at 16:53

this threading is kind of annoying me, because i always tend to reply to another message, never to the main thread :/

25bbd22b0b17f557748f601922880554
0
bramz 101 Sep 21, 2005 at 16:54

mmmh, now I did? i’m confused

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Sep 21, 2005 at 18:12

I just have it in flat view. lol

And bramz, do you think you could point me to one of those nifty template metaprogramming hacks? I’ve been trying to find a way to make the visitor pattern nicer looking for awhile, but with no success.

4cb4fbeb06e93e1ebb4982174b9fa8a2
0
Ph_nyx 101 Sep 22, 2005 at 10:41

@bramz

How does Orc’s attack function know wether it’s attacking a Troll or Goblin? Simple, we’ve overloaded it for both … oh wait … We’re not passing a Troll or Goblin pointer to attack but an Entity pointer! The overloading mechanism is never going to know what function to choose! Even worse, it will not compile, because there isn’t a single attack function that accepts an Entity pointer!

This is the problem..

Another, more interesting, sollution comes from the observation that Orc’s attack function doesn’t know of what type the victim is, but it does know that the aggressor is an Orc! So, you reverse the logic and you let the victim be attacked by an Orc! And then you can use overloading to determine by what kind of monster the victim is attacked. Moreover, since this “be_attacked” function is again a virtual function, the real idenity of the victim will be finally revealed!

I gave 3 monster types here, but there will be lots of entities (maybe 200) so I can’t overload like that for every monster.

However, as you can see, the number of be_attacked functions grows N² with N being the number of monstertypes. So, if you have 10 kind of monsters, you have 100 be_attacked functions. This is getting a maintainance hell, but without the double dispatcher thingy it would have been worse.

I thought about that problem. Ideally, I want to be able to add a new monster easily, by just creating 1 new .cpp and .h files and add a few lines in one other file, and don’t have to edit all my other monster class !

Maybe I could just add a class variable to Entity (such as int ent_type) and proceed according to this value in the membre functions using a plain switch.
Of course, as there will be lots of monsters, I won’t add a case statement for every monster. I plan to use “cascading” inheritence, to make categories of entities, because monsters won’t attack themselves, but they may attack the player :)

Class EvilGuy inherits from Entity
Class GoodGuy inherits from Entity
Class Projectile inherits from Entity

and then
Class Orc inherits from EvilGuy

Class Elf inherits from GoodGuy
Class Player inherits from GoodGuy

Class Missile inherits from Projectile

and then order entities with sub-categories so that all EvilGuys would attack GoodGuys the same way (using the same member function), and so on.

There are ways to get around that, but they use nifty template metaprogramming tricks like typelists and things like that. Very nice, but a bit tricky to explain :)

Sounds good ;)
All I want is not to waste time maintaining the source code. I prefer to “waste” it learning clean and efficient programming ways.

Thanks for your help. I’ll have a look in the doc now :)

25bbd22b0b17f557748f601922880554
0
bramz 101 Sep 22, 2005 at 16:48

Damn, I was hoping not having to answer that question. But then I shouldn’t have started about it, should I? :) I’ll have to think about it. But this should be a good start: http://www.codeproject.com/cpp/mmcppfcs.asp

065f0635a4c94d685583c20132a4559d
0
Ed_Mack 101 Sep 23, 2005 at 04:48

For creating new classes without maintainence pain, I’m using a small perl script that writes a factory function and an include file. It’s really simple and a nice solution (my previous solution used statically declared variables’ initialisation to trigger the entities being added to a factory, but that really was a hack).