Better than item 31.
Makutaku
item 31 in the "More Effective C++" by Scott Meyers:
From the description of the problem we can see that it is symmetric: an
asteroid hitting a spaceship is the equivalent to a spaceship hitting an
asteroid.
Using nonmember functions to implement the collision he shows something like
this:
void Hit ( SpaceShip* ship, Asteroid* asteroid) { /* process collision */ }
void Hit ( Asteroid* asteroid, SpaceShip* ship )
{
Hit(ship, asteroid) // call the primary function because of the symmetry
}
Instead of going ahead and try to solve the problem emulating virtual
function tables, let's go back to the visitor pattern approach. It has a
serious problem of recompilation because of the cyclic dependency among headers
- that's why the author had abandoned this approach. I wonder if the acyclic
variation of the visitor pattern could come and help me ...
Assuming that the reader knows the structure of this pattern, we could
declare class SpaceShip like this :
>> class SpaceShip:
>> public GameObject,
>> public Collider,
>> public CollidesWith<SpaceShip>,
>> public CollidesWith<SpaceStation>,
>> public CollidesWith<Asteroid> { ... };
Since, in this problem, the visitor hierarchy is also the element hierarchy we
could merge GameObject and Collider. Let's call it GameObject too (but with a
pure virtual method like : "virtual void AcceptCollision(GameObject* obj)=0;"
The implementation of " AccptCollision" would try to (dyn)cast to the proper
Interface to handle the collision. In order to avoid repeating similar code we
make a template to implement this method.
If I decide to add a new type of object, say a Satellite, it looks like I have
to modify the header for every class in my hierarchy (assuming everything can
collide with everything else). However we DO NOT HAVE TO. Since the problem is
symmetric we can implement the AcceptCollision method above in a way that, when
it fails to cast to the proper interface, it then tries the other side. If the
other side also fails we will have an infinite loop, so we make use of a little
flag. The " AcceptCollision" would then be implemented like this:
template<typename T>
void GameObject_T<T>::acceptCollision(GameObject* obj, bool flag)
{
CollidesWith<T> *objSpec = dynamic_cast<CollidesWith<T>*>(obj);
T* real_this = dynamic_cast<T*>(this);
assert(real_this!=0); // or an exception ??
if(objSpec!=0) { objSpec->hit(real_this); } // it does implement the
interface
else if(flag) // try the other side wishing it was implemented there
{
obj->acceptCollision(real_this,false);// false avoids infinite loop
}
else // in case the colision was not implemented at all
{ /* could throw an exception or just ignore */ }
}
As far as I can see , this approach solves the problem on item31, supports
inheritance , has little code, clean and easy to understand. No recompilation
necessary. Let's see this working: Suppose, in the beginning, we just have one
type of object - SpaceShip :
>> class SpaceShip : public GameObject_T<SpaceShip>,
>> public CollidesWith<SpaceShip>{...};
Which can collide with others spaceships. We compile and play the boring game.
Later we decide to add some asteroids and make it funnier, so we add a new
type:
>> class SpaceShip; // forward declare
>> class Asteroid : public GameObject_T<Asteroid>,
>> public CollidesWith<Asteroid>,
>> public CollidesWith<SpaceShip>{...};
And we don't touch the spaceship header nor the implementation file , but treat
the collision between SpaceShip and Asteroid just in asteroid files.
Given the following code:
>> GameObject *ship = new SpaceShip;
>> GameObject *aster = new Asteroid;
when :
>> ship->AcceptCollision(aster); // asteroid implements interface
// so the trivial thing will occur
and when:
>> aster->AcceptCollision(ship); // ship does NOT implement interface
// so it tries the other side which does implement it !!!
Extrapolating this idea, we may add as many classes we want, without
recompilation and also without redundant code. Game on Item31 is solved due
it's symmetry. Let's hope Nintendo will like it ! :-)
And just to conclude the whole idea, let me repeat :
" ... the meek of heart shell inherit the earth."
Regards ....
Rob Santos.
(dry cleaners cashier)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
Sam N. Max
different, but I have been thinking about an appropriate type-safe method of
handling something like object collisions myself.
Instead of doing collisions on a container that stores base game objects,
add the game objects to other containers that have a more specialized type,
and do collisions checks between various containers. In order to visualize
this better, I'll provide an example.
Suppose you have a project containing 4 game related classes: a base
CGameObject, and three classes deriving from this: CProjectile, CSpaceShip,
CGuiControl. CSpaceShip is a space ship in the game, and CProjectile is
what it shoots. CGuiControl is just used to draw the user interface for the
program. In fact, CGuiControl is never used in collision checks, but it is
just here as an example of what you'd obviously want to skip.
The objects are defined like this:
class CGameObject { };
class CSpaceShip : public CGameObject
{
public:
void OnCollide( CSpaceShip* otherShip )
{
/* Record damage here */
}
void OnCollide( CProjectile* projectile )
{
/* Record damage here */
}
};
class CProjectile : public CGameObject
{
public:
void OnCollide( CGameObject* someObject )
{
/* Have hit something, so "destroy" myself (destruction of game
objects will be discussed later) */
}
};
Now, you could have your containers of CSpaceShips and CProjectiles like
this:
vector<CShapeShip*> enemyShips;
vector<CShapeShip*> friendlyShips;
vector<CProjectile*> enemyProjectiles;
vector<CProjectile*> friendlyProjectiles;
With our objects setup in containers like this, we could call an algorithm
which checks for collisions and calls different type-specific OnCollide
methods when appropriate. The up-shot of this is that no type-casting is
required, and objects that do not need to be checked (such as the
CGuiControls) are skipped outright by simply never doing a collision check
on a container of them. As well, in this example enemy and friendly objects
are separated into different containers, so it would be easily possible to
check for collisions without accounting for frienldy fire (or with, multiple
calls).
For our collision checking algorithm, we would like it to work with a very
general case, preferibly with iterators, like this:
CheckCollision( friendlyShips.begin(), friendlyShips.end(),
enemyProjectiles.begin(), enemyProjectiles.end() );
The function would defined something like this:
template <class ItA, class ItB>
void CheckCollision( ItA beginA, ItA endA, ItB beginB, ItB endB)
{
// Pseudo code....
for every collision between A and B found
{
A->OnCollide(B);
B->OnCollide(A);
}
}
Because CheckCollision would know the types of A and B, it would call the
appropriate version of OnCollide. Note that this algorithm needs to be
modified to check sprites from the same list, such as:
CheckCollision( friendlyShips.begin(), friendlyShips.end(),
friendlyShips.begin(), friendlyShips.end() );
This method of doing collision checking is quick, dynamic, and type-safe.
It is easy to add different kinds of collisions between not only different
kinds of objects, but different sets of the same object. It's also nice to
note that you can use the virtual versions of OnCollide only if you want to,
as well have OnCollide methods defined inline. If you define a version of
OnCollide for CGameObject* which does nothing, the object can be used with
unexpected collision checks where the other object handles the approriate
action to be taken.
----------------------------
Now I'd like to look at what I consider the most problematic part of this:
how game objects are deleted. I think this is a very important topic
because very often the collision of something will trigger its destruction
(either right away or at a later time). As well, because this object could
be in multiple containers, it's not possible to just store a single pointer
for a container in it. We need some way to make sure the object is removed
from all these containers in a controlled manner. I'll suggest two method
of doing this:
(1) Each game object will have a list of all containers it is a part of, and
remove itself from them upon deletion.
(2) The game objects will be reference counted, and it's state will change
when it is requested for it to be destroyed. Containers will dereference
them when they notice this change of state.
I'd just like to say outright that it would probably be appropriate for each
of these cases to have some sort of specialized container that would handle
the collision checks and the removal of game objects when appropriate.
Requiring a user to organize with a normal STL container would likely get
messy.
(1)
Pros:
+ Cleanup of the game object can be done exactly when needed
+ The object knows which containers it's part of (and hence, could know
whether it is "friendly" to the user)
Cons:
- Uses extra memory to store pointers to each container it's a part of
(2)
Pros:
+ Uses less memory than (1)
+ All game objects have the benefits that come with being reference counted
Cons:
- The object must be dynamic (since it's being reference counted)
- It may take a while for the sprite to actually be deleted when requested,
since it is only deleted once all containers "realize" that it's destroyed.
- The check to see if an object is "destroyed" incurs a small performance
hit.
I personally think both are very valid solutions. Here I make (2) look
worse, but I think the memory issue is an important one. Anyway, if anyone
else has any other suggestions on how this deletion could be accomplished,
I'd be happy to here about it.
- Sam N. Max
Makutaku
>different,
Actualy it is not off-topic. It depends on the point of view. My primary
intension was not to present a possible design for the problem of collision
among objects but to present a way to apply the acyclic visitor pattern to
solve problems where the hierarchy of visitor and the hierarchy of elements to
be visited are the same and symmetric. The problem of collision among objects
is just an example of this type of problems that was presented by Scott Meyers
on his book.
On the other side it also does present a way to solve collision problem among
objects and I really appreciate your comments and it look like a very good
idea.
>Anyway, if anyone
>else has any other suggestions on how this deletion could be accomplished,
I have a little suggestion but I don't know if it "fits well" :
Instead of using pointers from the containers to the CGameObjects we could
use indexes to this CGameObjects instead . Then , we could have a
CGameObjectManager to manage the creation, access and destruction of
GameObjects. This would require even less memory and no reference counting per
object - the manager would have a flag indicating wheather the index is still
valid - if not there would be no gpf and the manager itself would remove the
"dead pointer" from the container. On ffficiency issue we would have one more
access per call, however we could improve the overall performance because we
could avoid memory fragmentation better.
Regards,
Rob.
Larry Evans
>
....skipping part
>
> template<typename T>
> void GameObject_T<T>::acceptCollision(GameObject* obj, bool flag)
> {
> CollidesWith<T> *objSpec = dynamic_cast<CollidesWith<T>*>(obj);
> T* real_this = dynamic_cast<T*>(this);
> assert(real_this!=0); // or an exception ??
> if(objSpec!=0) { objSpec->hit(real_this); }
> >> class SpaceShip : public GameObject_T<SpaceShip>,
> >> public CollidesWith<SpaceShip>{...};
>
> Which can collide with others spaceships. We compile and play the boring game.
> Later we decide to add some asteroids and make it funnier, so we add a new
> type:
>
> >> class SpaceShip; // forward declare
> >> class Asteroid : public GameObject_T<Asteroid>,
> >> public CollidesWith<Asteroid>,
> >> public CollidesWith<SpaceShip>{...};
>
Dispatch: A New Approach Using Templates and RTTI" that appeared in
_C++ Report_ in June 1998. In that article, I think
F<T> is your GameObject_T<T>
Target<T> is your CollidesWith<T>
f is your acceptCollision
f_impl is your hit
A could be your SpaceShip
B could be your Asteroid
Do you think you could extend this to "triple-dispatch" as described in
http://ourworld.compuserve.com/homepages/Patrice_Gautier/visitor.pdf?
Sam N. Max
news:20000108024851...@ng-fq1.aol.com...
> >This might be a little off-topic in the sense that the type of list is
> >different,
>
> intension was not to present a possible design for the problem of
collision
> among objects but to present a way to apply the acyclic visitor pattern to
> solve problems where the hierarchy of visitor and the hierarchy of
elements to
> be visited are the same and symmetric.
Heh, I figured that the acyclic visitor pattern was what you really wanted
to cover, which is I gave the "off-topic" warning.
> >Anyway, if anyone
> >else has any other suggestions on how this deletion could be
accomplished,
>
> I have a little suggestion but I don't know if it "fits well" :
> Instead of using pointers from the containers to the CGameObjects we
could
> use indexes to this CGameObjects instead . Then , we could have a
> CGameObjectManager to manage the creation, access and destruction of
> GameObjects. This would require even less memory and no reference counting
per
> object - the manager would have a flag indicating wheather the index is
still
> valid - if not there would be no gpf and the manager itself would remove
the
> "dead pointer" from the container. On ffficiency issue we would have one
more
> access per call, however we could improve the overall performance because
we
> could avoid memory fragmentation better.
Well, I'm not sure how much this will help. The left-over index has to be
maintained by the CGameObjectManager so it can tell the containers that the
object has been destroyed. In order to know when all the containers have
had the object removed so the index can be used for something else, you'd
still need to maintain a reference count. However, the actual object itself
is removed earlier, which is a plus.
pes...@my-deja.com
Larry Evans <cpplj...@earthlink.net> wrote:
> I'm wondering if this is the same or similar to
Carlo Pescio's "Multiple
> Dispatch: A New Approach Using Templates and
RTTI" that appeared in
> _C++ Report_ in June 1998.
(thanks to Larry Evans who told me about this
thread)
Rob Santos' approach is indeed similar to mine,
but has different hypothesis and consequences.
The similarity is in the use of the Curiously
Recurring Template Pattern in the declaration of
the GameObject-derived classes, and in the
inheritance from several CollidesWith instances
(similar to "Target" in my paper).
The major differences are:
- my approach doesn't assume (and so doens't
exploit!) symmetry.
- his approach does not handle a deep hierarchy
of GameObjects (e.g. an AsteroidSmasherShip,
derived from SpaceShip, that destroys the
asteroids but wants to inherit all the remaining
collisions from the regular SpaceShip, without
adding new code).
In fact, in my implementation of acceptCollision
("f" in my paper) if "this" and "obj" does not
seem to handle the collision, I try the immediate
base class of this, and so on until I reach the
base class, in which case no handling is
possible. Instead, Rob reverses the call and
tries a collision between "obj" and "this".
The two approaches can be merged, to exploit any
symmetry in the problem and still handle a deep
hierarchy, but then you have to decide:
do you try to navigate the hierarchy first, or do
you try the reverse call first?
Depending on the hierarchy you're dealing with,
you may get different results.
This bears some resemblance with linearization in
presence of multiple inheritance, a subject of
much research from where some good ideas (e.g.
monotonicity) could be reused here.
As a side note, an updated version of my
implementation (unfortunately not the article, at
least not yet), slightly faster than the one
published in C++ Report, is available online from
http://www.eptacom.net/publications
Have fun,
Carlo
pescio@NO_SPAM_PLEASEacm.org
Sent via Deja.com http://www.deja.com/
Before you buy.
Makutaku
>Dispatch: A New Approach Using Templates and RTTI" that appeared in
>_C++ Report_ in June 1998.
Well , I hope I can answer your question as soon as I separate some time to
study this article. I am sure I haven't read it. Hopefully it will clear some
clouds I had on further problems. About triple dispatch I tried to see if it
was possible and I think it is but I couldn't find an easy (elegant) way to
implement it . This article may help a lot.
Thank you,
Regards,
Rob.
Makutaku
>maintained by the CGameObjectManager so it can tell the containers that the
>object has been destroyed. In order to know when all the containers have
>had the object removed so the index can be used for something else, you'd
>still need to maintain a reference count.
of the object deleted only after sometime has passed that gives us high
probability that every container was informed - sometimes this approach would
work well, sometimes would bring horrible results.
However, the actual object itself
>is removed earlier, which is a plus.
>
The fact that the reference count can be implemented outiside the objects could
also be an advantage in some cases.
Larry Evans
>
> Makutaku wrote:
...skipped
> Do you think you could extend this to "triple-dispatch" as described in
> http://ourworld.compuserve.com/homepages/Patrice_Gautier/visitor.pdf?
Pescio's code in http:// www.eptacom.net/ pubblicazioni/ pub_eng/
multdisp.cpp.
The classes and functions in the Pescio's code were renamed in order
to emphasize the relationship with the normal Visitor pattern. In
particular, the classes in Pescio's code are both acceptors and
visitors, unlike the normal Visitor pattern where there is a heirarchy
of acceptor classes and another of Visitor classes.
The correspondence between the class names in Pescio's code and the
following code are:
Pescio's Here
======== ====
Base AcceptorVisitor
Target Visitor
F AcceptOk
f accept
f_impl visit
DF DAcceptor
dispF dispAccept
This code compiles and runs OK with gcc2.95.2.
---------------------------- the code --------------------------------
// The following is a renamed version of Pescio's code.
#include <iostream>
#include <typeinfo>
// Shared header file
class AcceptorVisitor
{
public :
typedef AcceptorVisitor Parent ;
virtual ~AcceptorVisitor() {} ;
virtual void accept( AcceptorVisitor& b ) = 0 ;
} ;
template< class Acceptor_T >
class Visitor
{
public :
virtual void visit( Acceptor_T& ) = 0 ;
} ;
template< class P >
class DAcceptor
{
public :
template< class Acceptor_T >
static
void
dispAccept( Acceptor_T& t, AcceptorVisitor& b )
;
} ;
template<>
class DAcceptor< AcceptorVisitor >
{
public :
template< class Acceptor_T >
static
void
dispAccept( Acceptor_T& t, AcceptorVisitor& b )
{
throw bad_cast() ;
}
} ;
template< class Acceptor_T >
class AcceptOk
: virtual public AcceptorVisitor
{
public :
void accept( AcceptorVisitor& a_visitor )
{
typedef Visitor< Acceptor_T > VisitorT ;
VisitorT* visitor_t = dynamic_cast< VisitorT* >(&a_visitor) ;
Acceptor_T& me = static_cast<Acceptor_T&>(*this) ;
if( visitor_t )
visitor_t-> visit( me ) ;
else
{
typedef typename Acceptor_T::Parent TParent ;
DAcceptor< TParent >::dispAccept( me, a_visitor ) ;
}
}
} ;
class AcceptOk< AcceptorVisitor >
{
public :
void accept( AcceptorVisitor& )
{
throw bad_cast();
}
} ;
template< class P > template< class Acceptor_T >
void DAcceptor<P>::dispAccept( Acceptor_T& t, AcceptorVisitor& a_visitor
)
{
t.AcceptOk< P >::accept( a_visitor ) ;
// static bind (accept is virtual)
}
// Project-specific file
class B ; class C ;
class A : public AcceptOk< A >,
public Visitor< A >,
public Visitor< B >,
public Visitor< C >
{
public :
void visit( A& )
{ cout << "A-A" << endl ; }
void visit( B& )
{ cout << "A-B" << endl ; }
void visit( C& )
{ cout << "A-C" << endl ; }
} ;
class B : public AcceptOk< B >,
public Visitor< A >,
public Visitor< B >
{
public :
void visit( A& )
{ cout << "B-A" << endl ; }
void visit( B& )
{ cout << "B-B" << endl ; }
} ;
class C : public AcceptOk< C >, public A
{
public :
typedef A Parent ;
void accept( AcceptorVisitor& b )
{ AcceptOk<C>::accept(b) ; }
void visit( A& )
{ cout << "C-A" << endl ; }
void visit( C& )
{ cout << "C-C" << endl ; }
} ;
//
// The following used for N-dispatch
//
template
< unsigned NARG
>
struct Visitor_N
//Specializations contain visit methods taking NARG arguments.
;
template
<
>
struct Visitor_N
< 3
>
{
AcceptorVisitor*
m_args[3]
;
void
print3
( AcceptorVisitor& x
, AcceptorVisitor& y
, AcceptorVisitor& z
)
{ cout
<<"visit( "
<<typeid(x).name()
<<", "
<<typeid(y).name()
<<", "
<<typeid(z).name()
<<" )"<<endl
;}
virtual
void
visit(A& x,A& y,A& z)
{ print3(x,y,z)
;}
//You can also include any visit with any permutation of arg types
//here.
virtual
void
visit(AcceptorVisitor& x,AcceptorVisitor& y,AcceptorVisitor& z)
{ print3(x,y,z)
;}
};//end Visitor_N<3>
struct ArgTypes_0
{
static
unsigned const
NARGS=0
;
};
template
< typename ARG_TYPES
, typename LAST_TYPE
>
struct ArgTypes_N
: public ARG_TYPES
{
static
unsigned const
NARGS=ARG_TYPES::NARGS+1
;
typedef
ARG_TYPES
ArgTypes
;
typedef
LAST_TYPE
LastType
;
};
template
< unsigned NARGS
, typename ARG_TYPES
, unsigned NUNKNOWN=NARGS
>
struct VisitorArgs
;
template
< typename ARG_TYPES
, unsigned NUNKNOWN
>
struct VisitorArgs
< 3
, ARG_TYPES
, NUNKNOWN
>
: public AcceptorVisitor
, public Visitor<A>
, public Visitor<B>
, public Visitor<C>
{
static
unsigned const
NARGS=3
;
Visitor_N<NARGS>&
m_visitor_N
;
VisitorArgs
( Visitor_N<NARGS>&a_visitor_N
)
: m_visitor_N(a_visitor_N)
{
; unsigned nargs=ARG_TYPES::NARGS
; m_visitor_N.m_args[nargs]->accept(*this)
;}
void
accept(AcceptorVisitor&av)
{ cerr
<<typeid(this).name()
<<"::accept(AcceptorVisitor) does nothing"
<<endl
;}
void
visit(A&y)
{
; typedef ArgTypes_N<ARG_TYPES,A> ArgTypes_arg
; VisitorArgs<NARGS,ArgTypes_arg,NARGS-ArgTypes_arg::NARGS>
visitor(m_visitor_N)
;}
void
visit(B&y)
{
; typedef ArgTypes_N<ARG_TYPES,C> ArgTypes_arg
; VisitorArgs<NARGS,ArgTypes_arg,NARGS-ArgTypes_arg::NARGS>
visitor(m_visitor_N)
;}
void
visit(C&y)
{
; typedef ArgTypes_N<ARG_TYPES,C> ArgTypes_arg
; VisitorArgs<NARGS,ArgTypes_arg,NARGS-ArgTypes_arg::NARGS>
visitor(m_visitor_N)
;}
};//end VisitorArgs<3,,NUNKNOWN>
template
< typename ARG_TYPES
>
struct VisitorArgs
< 3
, ARG_TYPES
, 0
>
{
static
unsigned const
NARGS=3
;
VisitorArgs
( Visitor_N<NARGS>&a_visitor_N
)
{
; typedef typename ARG_TYPES::ArgTypes::ArgTypes::LastType T0
; typedef typename ARG_TYPES::ArgTypes::LastType T1
; typedef typename ARG_TYPES::LastType T2
; T0&a0=dynamic_cast<T0&>(*a_visitor_N.m_args[0])
; T1&a1=dynamic_cast<T1&>(*a_visitor_N.m_args[1])
; T2&a2=dynamic_cast<T2&>(*a_visitor_N.m_args[2])
; a_visitor_N.visit(a0,a1,a2)
;}
};//end VisitorArgs<3,,0>
int main()
{
A a ;
Visitor_N<3> v3 ;
v3.m_args[0]=&a ;
v3.m_args[1]=&a ;
v3.m_args[2]=&a ;
VisitorArgs<3,ArgTypes_0> va3(v3) ;
return( 0 ) ;