Sign in to follow this  
MadMax1992

Getting rid of nasty typeid()

Recommended Posts

I got a basic physics engine working. It's a 2D physics engine, currently only supporting AABBs and Spheres. Let me get to the point: I have the following classes: Entity: Controls forces and position. Has the following important functions:
void HandleCollision(Entity* pEntity, ShtrVector2 *pCollisionPoint, ShtrVector2 *pCollisionNormal)
This function only changes forces and position on itself, not on the entity passed through the function, the other entity is just used for retrieving mass/bounciness variables
virtual Update(float fTimeFactor)
Update position and acceleration through forces Collidable: Is a collidable object. Important functions:
virtual bool DoesCollide(ShtrCollidable *pCollideable)
simple virtual functions, when called directly through a collidable object, returns false, to prevent errors.
virtual void CreateBoundingSphere
when called on collidable object, destroys the current bounding sphere and sets it to NULL to prevent errors. CollidableAABB (public Collidable, public Entity): Implements DoesCollide and CalculateBoundingSphere further. Also implements update function so it also moves it's AABB CollidableSphere (public Collidable, public Entity): Same as CollidableAABB, just with a sphere My problem Inside the DoesCollide function, I have some very nasty typeid's. This is the code (this is the one for the AABB):
bool ShtrCollidableAABB::DoesCollide(ShtrCollidable *pCollidable)
{
	if (GetBoundingSphere()->Intersect(*pCollidable->GetBoundingSphere())) {
		if (typeid(*pCollidable) == typeid(ShtrCollidableAABB)) {
			ShtrCollidableAABB *pDummy = dynamic_cast<ShtrCollidableAABB*> (pCollidable);

			if (this->GetAABB()->Intersect(*pDummy->GetAABB())) {
				return true;
			}
		} else if (typeid(*pCollidable) == typeid(ShtrCollidableSphere)) {
			ShtrCollidableSphere *pDummy = dynamic_cast<ShtrCollidableSphere*> (pCollidable);

			if (this->GetAABB()->Intersect(*pDummy->GetSphere())) {
				return true;
			}
		}
	}

	return false;
}
Is there a way to get rid of these typeid's with polymorphism and good base classes (I haven't got a clue how to do this)? Or is this the only way to go? Thanks in advance, Max Henger

Share this post


Link to post
Share on other sites
Why not just give the base class an enum Type variable that you can test instead of the typeid() / dynamic_cast, and have the derived classes constructor set that type (Or better, pass it as a parameter to the constructor of the base class)

Share this post


Link to post
Share on other sites
This doesn't really belong in Math and Physics. Moved to General Programming.

In any case, as long as you're doing the dynamic_casts you don't need the typeids. Just check the result of the cast for nullness.

Share this post


Link to post
Share on other sites
Quote:
Original post by Evil Steve
Why not just give the base class an enum Type variable that you can test instead of the typeid() / dynamic_cast, and have the derived classes constructor set that type (Or better, pass it as a parameter to the constructor of the base class)


This is quite literally a textbook example of what not to do. First off, you've just replicated functionality provided by the language: you've reimplemented typeid. Secondly, even if you have a good reason for rolling your own RTTI facilities, adding a member variable to keep track of things is a waste of space and processing power. If you have to do this, make the type code come from a virtual function. This means that the type code is bound to the type of the object rather than the state of the object. Thirdly, that still won't eliminate the dynamic_cast, since the action that occurs is dependent on the concrete type of the object.

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
This is quite literally a textbook example of what not to do. First off, you've just replicated functionality provided by the language: you've reimplemented typeid. Secondly, even if you have a good reason for rolling your own RTTI facilities, adding a member variable to keep track of things is a waste of space and processing power. If you have to do this, make the type code come from a virtual function. This means that the type code is bound to the type of the object rather than the state of the object. Thirdly, that still won't eliminate the dynamic_cast, since the action that occurs is dependent on the concrete type of the object.
My reasoning for not using a virtual function was to avoid the overhead (Admittedly, it's a tiny cost compared to the actual collision test). The dynamic_cast could be turned into a reinterpret_cast, since the type is then known (Assuming the type is correct of course).

If this is the only place that RTTI is used, then I'd see my method as a perfectly acceptable solution, since RTTI can be disabled which can reduce code size (As I believe every struct and class in the application has RTTI information generated for it). The extra 4 bytes (Assuming the enum is 4 bytes) per instance is unlikely to be a significant memory increase.

EDIT: Hmm, too many brackets in this post [smile]

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
Quote:
Original post by Evil Steve
Why not just give the base class an enum Type variable that you can test instead of the typeid() / dynamic_cast, and have the derived classes constructor set that type (Or better, pass it as a parameter to the constructor of the base class)


This is quite literally a textbook example of what not to do. First off, you've just replicated functionality provided by the language: you've reimplemented typeid. Secondly, even if you have a good reason for rolling your own RTTI facilities, adding a member variable to keep track of things is a waste of space and processing power. If you have to do this, make the type code come from a virtual function. This means that the type code is bound to the type of the object rather than the state of the object. Thirdly, that still won't eliminate the dynamic_cast, since the action that occurs is dependent on the concrete type of the object.



@SiCrane: RTTI isn't free... the compiler must generate code to keep track of the concrete type also, so I'm not sure why you said "adding a member variable to keep track of things is a waste of space and processing power". Further, the virtual function (which is basically how RTTI works anyway) requires a vtable entry and at least one call-through-a-pointer to operate. This requires even *more* processing power and storage.

What we usually do is:

1. Disable language RTTI in the compiler settings (which means we don't use dynamic_cast or typeid() at all).

2. When needed, add a type member variable that is initialized in constructors to the derived concrete type.


Now, having said all of that:

@OP:

You're ultimately trying to intersect the AABB of "this" with either the sphere or AABB of pCollidable. May I suggest a wrapper class that can contain the AABB and/or the sphere? Then you wouldn't have to check the type of the collider at all; instead you could inspect the contents of the wrapper inside the Intersect() function. That's one way... there are others. You're not stuck with the factoring you came up with.

Share this post


Link to post
Share on other sites
Quote:
Original post by Evil Steve
The dynamic_cast could be turned into a reinterpret_cast, since the type is then known (Assuming the type is correct of course).

Also a bad idea. A reinterpret_cast would reinterpret the bit pattern of the pointer as the cast type. However, that would not necessarily do the correct thing under multiple or virtual inheritance. If you must do this without a dynamic_cast at least use a static_cast which will at least give you some sort of warning if your type hierarchy would give you those kinds of problems. Or better yet, a boost::checked_cast which will use a dynamic_cast in debug and a static_cast in release.

Share this post


Link to post
Share on other sites
Quote:
Original post by mumblyjoe
@SiCrane: RTTI isn't free... the compiler must generate code to keep track of the concrete type also, so I'm not sure why you said "adding a member variable to keep track of things is a waste of space and processing power". Further, the virtual function (which is basically how RTTI works anyway) requires a vtable entry and at least one call-through-a-pointer to operate. This requires even *more* processing power and storage.

The compiler doesn't generate code to keep track of the concrete type, at least not any additional code over what it already does: the concrete type is implicit in the value of the pointer to the vtable, which is automatically assigned in the constructor. If you put a member variable that tracks a type into a class you've added an additional member to every instance of that class. This information is completely redundant with the pointer to the vtable. Setting this member variable is a waste of processing power because this action duplicates the action the constructor already does when it assigns that vtable pointer. Using a virtual function allows you to forgo this duplication of effort. Yes, using a virtual function is more expensive than reading a simple variable. However, by increasing the size of an object you decrease spatial locality for all uses of that object. Therefore, unless you are attempting to optimize the extremely unusual situation that you're doing type look ups more frequently than actually using the object, a virtual function lookup would win out in terms of actual overall program performance. (With some compilers you can even go an extra step and compare the vtable pointer directly against the vtable address and get your type information just as fast but without needing to bloat your class size.)

So again: adding a member variable to track the concrete type of an object is a bad idea because you're duplicating work that the compiler will be more than happy to do for you. This means that you're now in charge of maintaining that type information without help from the compiler. There will be no warning if you do something like assign two classes the same type id by accident or screw up by using the wrong kind of pointer cast to get your pointer.

Sometimes this headache will be worth it. Then you can disable RTTI and introduce your type code. However, using a member variable for that type code is a bad idea, since you've now duplicated the effort from the only place that the compiler can help you with your custom RTTI: assigning the vtable pointer. Not only is this duplication of effort apparent in the extra work you have to do, but also literally duplicates code and storage that the compiler uses anyways to do its work for non-RTTI purposes.

Share this post


Link to post
Share on other sites
Sounds like you want to do double dispatch, which is pretty tricky to do in Cpp. The wikipedia article linked has one example of how it can be done (and it's even about collision!), but I suspect it doesn't quite fit the architecture you have in mind.

Share this post


Link to post
Share on other sites
double dispatch, or explicit types. For the second case, I'd advocate a table of function pointers. Double Dispatch is nice, but the code can bloat very quickly.

Share this post


Link to post
Share on other sites

enum
{
COLLIDABLE_TYPE_SPHERE,
COLLIDABLE_TYPE_RECTANGLE,
COLLIDABLE_TYPE_CONVEXPOLYGON,
COLLIDABLE_TYPE_COUNT,
};

struct Collidable
{
const int m_typeId;
Collidable(int typeId) : m_typeId(typeId) {}
};

struct CollidableSphere: public Collidable
{
CollidableSphere() : Collidable(COLLIDABLE_TYPE_SPHERE) {}
};

struct CollidableRectangle: public Collidable
{
CollidableRectangle() : Collidable(COLLIDABLE_TYPE_RECTANGLE) {}
};

struct CollidableConvexPolygon: public Collidable
{
CollidableConvexPolygon() : Collidable(COLLIDABLE_TYPE_CONVEXPOLYGON) {}
};

struct CollidableTable
{
bool Collide(Collidable* A, Collidable* B)
{
static bool (*CollideFunc)(Collidable* A, Collidable* B) funcTable[COLLIDABLE_TYPE_COUNT][COLLIDABLE_TYPE_COUNT] =
{
{ CollideSphereSphere, CollideSphereRect, CollideSpherePoly },
{ NULL , CollideRectRect, CollideRectPoly },
{ NULL , NULL , CollidePolyPoly },

if(A->m_typeId > B->m_typeId)
swap(A, B);

return funcTable[A->m_typeId][B->m_typeId](A, B);
};

static bool CollideSphereSphere(Collidable* A, Collidable* B);
static bool CollideSphereRect(Collidable* A, Collidable* B);
static bool CollideSpherePoly(Collidable* A, Collidable* B);
static bool CollideRectRect(Collidable* A, Collidable* B);
static bool CollideRectPoly(Collidable* A, Collidable* B);
static bool CollidePolyPoly(Collidable* A, Collidable* B);
}
};

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
Quote:
Original post by mumblyjoe
@SiCrane: RTTI isn't free... the compiler must generate code to keep track of the concrete type also, so I'm not sure why you said "adding a member variable to keep track of things is a waste of space and processing power". Further, the virtual function (which is basically how RTTI works anyway) requires a vtable entry and at least one call-through-a-pointer to operate. This requires even *more* processing power and storage.

The compiler doesn't generate code to keep track of the concrete type, at least not any additional code over what it already does: the concrete type is implicit in the value of the pointer to the vtable, which is automatically assigned in the constructor. If you put a member variable that tracks a type into a class you've added an additional member to every instance of that class. This information is completely redundant with the pointer to the vtable. Setting this member variable is a waste of processing power because this action duplicates the action the constructor already does when it assigns that vtable pointer. Using a virtual function allows you to forgo this duplication of effort. Yes, using a virtual function is more expensive than reading a simple variable. However, by increasing the size of an object you decrease spatial locality for all uses of that object. Therefore, unless you are attempting to optimize the extremely unusual situation that you're doing type look ups more frequently than actually using the object, a virtual function lookup would win out in terms of actual overall program performance. (With some compilers you can even go an extra step and compare the vtable pointer directly against the vtable address and get your type information just as fast but without needing to bloat your class size.)

So again: adding a member variable to track the concrete type of an object is a bad idea because you're duplicating work that the compiler will be more than happy to do for you. This means that you're now in charge of maintaining that type information without help from the compiler. There will be no warning if you do something like assign two classes the same type id by accident or screw up by using the wrong kind of pointer cast to get your pointer.

Sometimes this headache will be worth it. Then you can disable RTTI and introduce your type code. However, using a member variable for that type code is a bad idea, since you've now duplicated the effort from the only place that the compiler can help you with your custom RTTI: assigning the vtable pointer. Not only is this duplication of effort apparent in the extra work you have to do, but also literally duplicates code and storage that the compiler uses anyways to do its work for non-RTTI purposes.


OK, you win. :) I didn't realize the vtable pointer was used for RTTI... now your entire argument makes sense.

Share this post


Link to post
Share on other sites
I would make the typeid implicit in the GetSphere/GetAABB (returning null if it is not the right typeid):

struct Collidable {
bool DoesCollide(const Collidable& pCollideable) const
{
if (GetAABB()) {
if (pCollideable.GetAABB()) {
return GetAABB()->Intersect(*pCollideable.GetAABB());
}
else if (pCollideable.GetBoundingSphere()) {
return GetAABB()->Intersect(*pCollideable.GetBoundingSphere());
}
}
else if (GetBoundingSphere()) {
if (pCollideable.GetAABB()) {
return GetBoundingSphere()->Intersect(*pCollideable.GetAABB());
}
else if (pCollideable.GetBoundingSphere()) {
return GetBoundingSphere()->Intersect(*pCollideable.GetBoundingSphere());
}
}
return false;
}

virtual AABB* GetAABB() const { return 0; };
virtual Sphere* GetBoundingSphere() const { return 0; };

};

struct CollidableAABB : public Collidable {
virtual AABB* GetAABB() const { return &m_AABB; };
private:
AABB m_AABB;
};

struct CollidableSphere : public Collidable {
virtual Sphere* GetBoundingSphere() const { return &m_boundingSphere; };
private:
Sphere m_boundingSphere;
};



This way you don't need dynamic_casts, and the derived classes are very easy and short to implement (you still could make DoesCollide be virtual if you need some particular behavior).
If you add another CollidableSubType you have sadly to modify your base class (smaller changes would be required using the Evil-Steve-"enum"-method), but you can let the other deriveds unchanged.

Share this post


Link to post
Share on other sites
And what's so evil about enums... However, you just need to expand your types to say, 10, and see the evilness of your implementation.

Share this post


Link to post
Share on other sites
Well, I will have to implement a 10-cases-if inside a one 10-cases-if... which makes around 210 lines (not counting "}" alones), in addition to 10 single-line virtual functions defined in the base class.

Horrible, I fully agree, but this still doesn't make your approach look better: You will have a 10*10 table, and 45 collision functions.
And how are these functions expected to be implemented? I hope I am wrong, but this is how I think they should be:

static bool CollideSphereSphere(Collidable* A, Collidable* B)
{
CollidableSphere* dA = dinamic_cast<CollidableSphere*>(A);
CollidableSphere* dB = dinamic_cast<CollidableSphere*>(B);
if (dA && dB) {
return dA->GetSphere()->Intersect(dB->GetSphere());
}
return false;
}

Remember, you have 45 of them, and therefore 270 lines of additional code!


Beside, I think your m_typeId should be of type COLLIDABLE_TYPE (assuming you give that name to the unnamed enum), declaring it as "int" isn't dangerous?

Share this post


Link to post
Share on other sites
This is not just about line counting, but also efficiency, maintenance and flexibility.

My example is just a crude implementation of the function table idea. Ideally, you'd want to use functors instead, and for example a hash map, keying in the object types to give you the corresponding function to call. The object id can be anything, as long as two of them can be combined to make a key for the hash map.

One advantage is to hide the code away from the collision objects themselves. All the collision routines would be implemented outside, so there will be no dependencies.

The second advantage is the implementation of custom collision types, or basically, extending your library to new collision objects. These new collision objects could be part of an external library, that would supply the functors, and insert them into the map.

The overhead being, the table lookup, and the functor call.

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
The compiler doesn't generate code to keep track of the concrete type, at least not any additional code over what it already does: the concrete type is implicit in the value of the pointer to the vtable, which is automatically assigned in the constructor. If you put a member variable that tracks a type into a class you've added an additional member to every instance of that class. This information is completely redundant with the pointer to the vtable. Setting this member variable is a waste of processing power because this action duplicates the action the constructor already does when it assigns that vtable pointer. Using a virtual function allows you to forgo this duplication of effort. Yes, using a virtual function is more expensive than reading a simple variable. However, by increasing the size of an object you decrease spatial locality for all uses of that object. Therefore, unless you are attempting to optimize the extremely unusual situation that you're doing type look ups more frequently than actually using the object, a virtual function lookup would win out in terms of actual overall program performance. (With some compilers you can even go an extra step and compare the vtable pointer directly against the vtable address and get your type information just as fast but without needing to bloat your class size.)

So again: adding a member variable to track the concrete type of an object is a bad idea because you're duplicating work that the compiler will be more than happy to do for you. This means that you're now in charge of maintaining that type information without help from the compiler. There will be no warning if you do something like assign two classes the same type id by accident or screw up by using the wrong kind of pointer cast to get your pointer.

Sometimes this headache will be worth it. Then you can disable RTTI and introduce your type code. However, using a member variable for that type code is a bad idea, since you've now duplicated the effort from the only place that the compiler can help you with your custom RTTI: assigning the vtable pointer. Not only is this duplication of effort apparent in the extra work you have to do, but also literally duplicates code and storage that the compiler uses anyways to do its work for non-RTTI purposes.


I understand your points about not reimplementing the work that the compiler does, but I would hesitate to recommend the use of typeid for something like the inner loop of a collision detection algorithm. Many people might not be aware that (at least for Visual Studio) the typeid equality operator actually performs a strcmp under the hood. Which is slow. There's more about it here.

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
And that would be the point behind the third paragraph in the post you just quoted.


I understand that. It's just that from your post it isn't clear exactly why you'd want to roll your own RTTI in the first place. You don't mention that comparing type_info classes is significantly slower in many implementations than comparing an enum. This isn't common knowledge in my experience, so I just wanted to point that out for people who might not know.

Share this post


Link to post
Share on other sites
Well I'm reading this topic and I still don't clearly understand how it should be done [looksaround]
If I store objects as pointers to base classes and want to check what type it is I can use the type stored in the class like :

unsigned int getType()const{return m_Type;}

or put a pure virtual function in the base class :
virtual unsigned int getType()const=0;

and implement it in each derived class and return the type there,for example in NPC derived class :
class NPC : public Entity
{
..
..
unsigned int getType()const{return EntityTypes::NPC;}
..
..
};

What would be the way to use dynamic_cast?

For example there are 4 different derived classes from entity base class and you dont know the type you either use typeid to check the type or you use dynamic_cast and check the result

NPC* npc = dynamic_cast<NPC*>(entity);
Building* building = dynamic_cast<Building*>(entity);
if(npc){
//dostuff
}
else if(building){
//dostuff
}
etc.
So my question is what would be the best way to check class type and do specific stuff to that class without storing type as member? [smile]

Share this post


Link to post
Share on other sites
What's this about the vtable pointer? I haven't done much work with type comparison, is it valid to compare vtable pointers to determine if two objects have the same type?

Share this post


Link to post
Share on other sites
Quote:
Original post by Valere
What's this about the vtable pointer? I haven't done much work with type comparison, is it valid to compare vtable pointers to determine if two objects have the same type?

Certainly. Oh, no, not directly, since there is no such thing as a vtable pointer in C++. It's spelled "typeid" or "dynamic_cast", depending on how you want to use the information. That's what the above discussion is all about: whether it's the perfect solution to leverage the type information already present in the runtime or to reinvent your own.

Share this post


Link to post
Share on other sites
Haha, that's the great thing about GameDev, you ask one question you don't know shit about... And you get three almost equally good solutions...

I think it'll be more easy to embed an enum into my classes with a GetType() function in the base class, since I'll only use 2 types of intersection objects (maybe a third in the future).

I don't want to have a nasty strcmp in my (even more nastier) typeid functions ;-)

Thank you guys again!
-Max Henger

Share this post


Link to post
Share on other sites
Quote:
Original post by Bregma
Quote:
Original post by Valere
What's this about the vtable pointer? I haven't done much work with type comparison, is it valid to compare vtable pointers to determine if two objects have the same type?

Certainly. Oh, no, not directly, since there is no such thing as a vtable pointer in C++. It's spelled "typeid" or "dynamic_cast", depending on how you want to use the information. That's what the above discussion is all about: whether it's the perfect solution to leverage the type information already present in the runtime or to reinvent your own.


Thanks Bregma, that makes the discussion much clearer, and brings it back into the world that I'm used to thinking about. I was beginning to wonder if there *was* a way to read the vtable pointer that I had simply never run across.

Share this post


Link to post
Share on other sites
Quote:
Original post by SaltyGoodness
You don't mention that comparing type_info classes is significantly slower in many implementations than comparing an enum. This isn't common knowledge in my experience, so I just wanted to point that out for people who might not know.


What do you mean for significantly? With a very short test my pc needs around 2 milliseconds for 1'000'000 enum comparisons and 20 milliseconds for the same amount of strcmp (two equal strings of size 7). It's 10 times slower, but still negligible...

I am definately against the enum trick because it needs, soon or later, a dynamic cast. I believe that a dynamic cast is too powerfull (exposes all the public member functions of the derived class), and I am sure it will be abused more than used. There is no relation between the enum and the proper way to use it (dynamic cast to the proper derived class, and call the right collision function only (?)). How can one see that without reading an accurate documentation? IMO, this is a very bad design; polymorphism is not for that. If you can't get rid of a dynamic_cast, you might think to use templates everywere instead of polymorphic classes (executable size is no longer a valid argument today).

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