In my previous post, I mentioned about 2 approaches to solve the problem of choosing the right function at run time depending on the type of object. They were:

  1. Virtual functions and RTTI
  2. Virtual Functions only

In this post, I intend to discuss the next approach: Emulating Virtual function tables (using RTTI without that messy if-else construct). It builds off of the advantages of each of the approaches mentioned earlier. Here it goes:

The title pretty much says it all.. Compiler implements virtual functions by creating an array of function pointers (vtable) and simply indexing into that array whenever a function is called. This approach does pretty much the same thing. Here is a snapshot of some of the code:

class GameObject
{
 virtual void Collide(GameObject& otherObject) = 0;
 ...
};

class SpaceShip : public GameObject
{
 void Collide(GameObject& otherObject);

 void hitSpaceShip(SpaceShip& sShip);
 void hitAsteroid(Asteroid& asteroid);
}

Intuitively, we have the main collide function which serves as an arbitrator which maps the run time request to the appropriate hitObject(…) function. To facilitate this mapping, we create an associative array or a lookup table with the help of STL map (our own sweet version of vtable, yeehaw!). We can directly access the associative array(will be referred to as function map from now on) in the collide function, but its preferred to do it via an intervening function; LookupFn(…); which would take GameObject as the argument and return the appropriate (from the mappign) function pointer:

class SpaceShip : public GameObject
{
//...
typedef void (SpaceShip::*HitFunctionPtr)(GameObject&);
HitFunctionPtr LookupFn(const GameObject& otherObject) const;
//...
}

Assuming that LookupFn(…) works automagically and yields the right function for the given object, its trivial to write the Collide function.

void SpaceShip::collide(GameObject& otherObj)
{
 HitFunctionPtr hfp = LookupFn(otherObj);

 (this->*hfp)(otherObject);
//this would invoke hitAsteroid(otherObject) or hitSpaceShip(otherObject) depending on otherObject
}

All thats left now is LookupFn(…). Lets do some magic *evil laughter echoes*::

HitFunctionPtr SpaceShip:: LookupFn(const GameObject& otherObject) const
{
static HitMap collisionMap = initializeCollisionMap(); //where HitMap is typedef'd as:
// typedef map<string, HitFunctionPtr> HitMap;

HitMap::iterator mapEntry = collisionMap.find(typeid(otherObject).name() );

return mapEntry->second;
}

Since the mapping is needed to be made one time only, we can initialize it and make it static. I won’t get into these details. The book More Effective C++ provides good explanation of all of this too. Assuming, we covered all the type of object combinations, iterator will definitely return the apt function pointer. That was easy! ;)
For the sake of completeness, here is the listing for initializeCollisionMap():

HitMap& SpaceShip:: initializeCollisionMap()
{
HitMap* hMap = new HitMap;

(*hMap)["Asteroid"] = &hitAsteroid;
(*hMap)["SpaceShip"] = &hitSpaceShip;

return *hMap;
}

PS: There is no if-else hierarchy. This is what I call clean!
Voila, we’re done. Seriously, we’re done..(Psst..the above code won’t compile) >> Oooo, Noooooooooo! :(

The problem stated is more of a semantic problem rather than the idea behind this concept. At this point, the approach has been explained and what follows is just an explanation of what is the problem..

HitMap&amp; SpaceShip:: initializeCollisionMap()
class SpaceShip : public GameObject
{
//...
typedef void (SpaceShip::*HitFunctionPtr)(GameObject&);
HitFunctionPtr LookupFn(const GameObject& otherObject) const;
//...
}

The prototype for the HitFunctionPtr takes GameObject& as an argument, but as you’d have noticed..the:

void hitSpaceShip(SpaceShip& sShip);
void hitAsteroid(Asteroid& asteroid);

takes in an argument of type Asteroid/Spaceship. This does not match the function pointer prototype and thus the compiler does not like what you are asking it to do. The workaround is to change the above HitObject(…) functions to:

void hitSpaceShip(GameObject& sShip);
void hitAsteroid(GameObject& asteroid);

void SpaceShip:: hitAsteroid(GameObject& otherObj)
{
Asteroid& asteroid = dynamic_cast<Asteroid&>(otherObj);

//process SpaceShip - Asteroid
}

With this in place, it should make the compiler happy and it should compile fine. Thats about it!

Pros:
- It makes the RTTI code more efficient (indexing into an array vs if-else statements).
- It also isolates usage of RTTI in one single place.

Cons:

- If we need to add new type of GameObjects, we still need to access the original library and implement collision methods for the new objects, and recompile it. This brings us back to the original problem we faced earlier. But, there is hope, for the last approach takes care of that. It utilizes all the concepts discussed so far and yields a practical solution.

Its been a long post already, so I won’t get into the last approach now. I should be posting that soon, along with some code to see all of this in action ;) .

PS: I recommend going through the Item 31 of Modern Effective C++ to understand some of the gory details. I have just covered the essence of the approach.

If you have any questions or suggestions, please feel free to contact me. Also, if this post helped you any bit, I’d appreciate if you could leave me an encouraging comment.