Archived

This topic is now archived and is closed to further replies.

Collision Detection: Excluding Objects (in a nice OOP kind of way)

This topic is 5011 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So i''m constructing a collision detections system ("another one, eh?"). However, i''m having a hard time getting it to work in a nice OOP kind of model without breaking rules and making things ugly. So how would you do it? Here''s the theoretical game: Game objects include: - player - enemies - enemy bullets - player bullets - world objects (walls and whatnot) Now the *stupid* way would be to check every object against every other object. The smarter way is to only check objects in the local area. In addition, not all objects need to react with other objects (enemy bullets do not hit other enemies, etc.). This is nothing new to most of you. But how to structure such a thing? Let''s say i build a CollisionObject class. It provides basic functionality for checking collisions. What i want to do is build an engine that only checks collisions between objects for which they make sense. If i put the above into a check / do not check table, it would look like this (X = check for collision) :
		PLAYER		ENEMY		E.BULLET	P.BULLET	WALL
PLAYER				X		X				X
ENEMY		X						X		X
E.BULLET	X						X		X
P.BULLET			X						X
WALL		X		X		X		X
 
So, right away, half of the checks do not apply to each other. The only way i can think to do it is to give each inherited CollisionObject class a type field, like:
enum collision_type {
	PLAYER,
	PLAYER_BULLET,
	ENEMY,
	ENEMY_BULLET,
	WALL
	}

/* A collision object that represents the player */
class CollsionObjectPlayer{
	collision_type type = PLAYER;
	// etc
	}
 
Then check the type when i check for collisions:
bool CheckForCollision( CollisionObject* co ) {
	// Consult above table:
	// If i don''t need to perform this collision, return false
	// Otherwise, check
	}
 
Type fields are a *really* kludgy way to solve this problem. It''s old-school and doesn''t follow OOP very well, in addition to being hard to upgrade in case i add new objects in the future. SO, how could this be structured nicely? I run into this problem a lot in other situations too, so advice is greatly appreciated. thanks all!

Share this post


Link to post
Share on other sites
well, to be OOP,



class CWall: public CCollObject
{
virtual bool CollidableWith(const CCollbject& xCollObject) const { return CCollObject.CollidableWith(*this);

virtual bool CollidableWith(const CPlayer& xPlayer) const { return true; }
virtual bool CollidableWith(const CEnemy& xEnemy) const { return true; }
virtual bool CollidableWith(const CEBullet& xEbullet) const { return true; }
virtual bool CollidableWith(const CPbullet& xPBullet) const { return true; }
virtual bool CollidableWith(const CWall& xWall) const { return false; }

};



class CPlayer: public CCollObject
{
virtual bool CollidableWith(const CCollbject& xCollObject) const { return CCollObject.CollidableWith(*this);

virtual bool CollidableWith(const CPlayer& xPlayer) const { return true; }
virtual bool CollidableWith(const CEnemy& xEnemy) const { return true; }
virtual bool CollidableWith(const CEBullet& xEbullet) const { return true; }
virtual bool CollidableWith(const CPbullet& xPBullet) const { return false; }
virtual bool CollidableWith(const CWall& xWall) const { return true; }

};


class CEnemy: public CCollObject
{
virtual bool CollidableWith(const CCollbject& xCollObject) const { return CCollObject.CollidableWith(*this);

virtual bool CollidableWith(const CPlayer& xPlayer) const { return true; }
virtual bool CollidableWith(const CEnemy& xEnemy) const { return true; }
virtual bool CollidableWith(const CEBullet& xEbullet) const { return false; }
virtual bool CollidableWith(const CPbullet& xPBullet) const { return true; }
virtual bool CollidableWith(const CWall& xWall) const { return true; }

};



note the visit interface (bool CollidableWith(const CCollbject& xCollObject) const.


but I''d rather do




enum
{
COLL_OBJECT_NONE = 0,
COLL_OBJECT_PLAYER = (1 << 0),
COLL_OBJECT_ENEMY = (1 << 1),
COLL_OBJECT_EBULLET = (1 << 2),
COLL_OBJECT_PBULLET = (1 << 3),
COLL_OBJECT_WALL = (1 << 4),
COLL_OBJECT_ALL = 0xFFFFFFFF,
};


class CCollObject
{
private:
u_int m_uRejectMask;
u_int m_uAcceptMask;
u_int m_uClass;

bool CollidableWith(const CCollObject& Obj) const
{
u_int uAccept = (m_uAcceptMask & Obj.m_uClass) | (Obj.m_uAcceptMask & m_uClass);
u_int uReject = (m_uRejectMask & Obj.m_uClass) | (Obj.m_uRejectMask & m_uClass);

// by default, when not rejected nor accepted, returns true

return (uAccept || !uReject);
}
};



the second solution is faster, and allows for collision filtering on a per-object basis. also, the collision object can have multiple classes (like a Pbullet and a EBullet at the same time). The accept mask is not necessary, but it kind of overrides what the rejects filters out, so you can enforce collision detection for objects with multi classes. Well, you can play with the logic which ever way you want anyway.

Share this post


Link to post
Share on other sites
personally, i like the second method, but it still uses type fields. The first method is more OOP but doesn''t make any less work for me should i ever go and add additional types. I would have to update every other class to factor in checking for the new type. Thanks for the suggestions though. I''ll have to think about it some more.

Share this post


Link to post
Share on other sites
Doing collision detection is inherently inelegant by using OOP in C++. You will have to implement some kind of double dispatch design, which will cause your coupling between all your game objects (ie, every object has to know about every other kind) which will cause the necessary but painful recompilations every time you add something new to the mix. Plus, you will be writing twice as much code because in double dispatch, a collision player vs. enemy is different than enemy vs. player, even though they are conceptually the same and should be moved into a single method somehow.
Procedural programming to the rescue. By implementing your own pseudo-vtable (fairly painless) you can get rid of all those problems. Now this method has a few kinks, but all in all its much more robust. Here it goes (inspired by More Effective C++)

File containing your game object classes (GameObject.h):


#ifndef GAMEOBJECTS_H_
#define GAMEOBJECTS_H_

class Object
{
public:
virtual ~Object() { }
};

class Asteroid : public Object
{
};

class SpaceShip : public Object
{
};

class SpaceStation : public Object
{
};

#endif


The interface header to access your collision detection code (CollisionProcessor.h):


#ifndef COLLISIONPROCESSOR_H_
#define COLLISIONPROCESSOR_H_

#include <stdexcept>
#include <string>

class Object;

class UnknownCollision : public std::invalid_argument
{
public:
UnknownCollision(const std::string& str) : invalid_argument(str)
{
}
};

void process_collision(Object* first, Object* second);

#endif


The beating heart of your program (CollisionProcessor.cpp):


#include "GameObjects.h"
#include "CollisionProcessor.h"
#include <memory>
#include <map>
#include <typeinfo>
#include <utility>
#include <iostream>
using namespace std;

namespace
{
void asteroid_ship(Object* asteroid, Object* ship)
{
cout << "Asteroid vs. Ship" << endl;
}

void asteroid_station(Object* asteroid, Object* station)
{
cout << "Asteroid vs. Station" << endl;
}

void ship_station(Object* ship, Object* station)
{
cout << "Ship vs. Station" << endl;
}

void asteroid_asteroid(Object* asteroid1, Object* asteroid2)
{
cout << "asteroid vs. asteroid" << endl;
}

void ship_ship(Object* ship1, Object* ship2)
{
cout << "ship vs. ship" << endl;
}

void station_station(Object* station1, Object* station2)
{
cout << "station vs. station" << endl;
}

typedef void (*HitFunctionPtr)(Object*, Object*);
typedef map<pair<const type_info*, const type_info*>, HitFunctionPtr> HitMap;

HitMap* init_hit_map()
{
HitMap* hmap = new HitMap;

(*hmap)[HitMap::key_type(&typeid(Asteroid), &typeid(SpaceShip))] = asteroid_ship;
(*hmap)[HitMap::key_type(&typeid(Asteroid), &typeid(SpaceStation))] = asteroid_station;
(*hmap)[HitMap::key_type(&typeid(SpaceShip), &typeid(SpaceStation))] = ship_station;
(*hmap)[HitMap::key_type(&typeid(Asteroid), &typeid(Asteroid))] = asteroid_asteroid;
(*hmap)[HitMap::key_type(&typeid(SpaceShip), &typeid(SpaceShip))] = ship_ship;
(*hmap)[HitMap::key_type(&typeid(SpaceStation), &typeid(SpaceStation))] = station_station;
(*hmap)[HitMap::key_type(&typeid(SpaceShip), &typeid(Asteroid))] = asteroid_ship;
(*hmap)[HitMap::key_type(&typeid(SpaceStation), &typeid(Asteroid))] = asteroid_station;
(*hmap)[HitMap::key_type(&typeid(SpaceStation), &typeid(SpaceShip))] = ship_station;

return hmap;
}

HitFunctionPtr lookup(const type_info* first, const type_info* second)
{
static HitMap* hmap = init_hit_map();

HitMap::iterator it = hmap->find(HitMap::key_type(first, second));
if (it != hmap->end())
return it->second;
else
return 0;
}

} // end anonymous namespace


void process_collision(Object* first, Object* second)
{
HitFunctionPtr hfp = lookup(&typeid(*first), &typeid(*second));

if (hfp)
hfp(first, second);
else
throw UnknownCollision(static_cast<string>("Unknown collision between") + typeid(first).name() + " and " + typeid(second).name());
}


And main.cpp to pull all of this together for a short demonstration:


#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
#include "GameObjects.h"
#include "CollisionProcessor.h"

typedef pair<Object*, Object*> ObjectPair;

class ObjectGen
{
public:
ObjectPair operator ()() const
{
Object* ary[2];
for (int i = 0; i < 2; i++)
{
switch(rand() % 3)
{
default:
case 0:
ary[i] = new Asteroid;
break;
case 1:
ary[i] = new SpaceShip;
break;
case 2:
ary[i] = new SpaceStation;
break;
}
}
return ObjectPair(ary[0], ary[1]);
}
};

void collide(const ObjectPair& p)
{
process_collision(p.first, p.second);
}

int main()
{
srand((unsigned int)time(0));
const int sz = 10;
vector<pair<Object*, Object*> > items(sz);
generate(items.begin(), items.end(), ObjectGen());
for_each(items.begin(), items.end(), collide);
}

Share this post


Link to post
Share on other sites
Hey, that looks good. to recap:

1) check all collisions
2) get the function required to process these two objects
3) compute the function.

right? I like this model because most of the checking code is centralized and not spread out over several inherited objects. I think i will use this if you don''t mind.

But still, what we''re saying here is that there is no squeeky-clean way to do this, correct?

I would still like to get an "engine" approach that actually does not check other objects that don''t need to be checked... at all. That would be the ideal solution. Failing that, the specialized object<->object kind of code listed above will be used. Thanks for sharing that.

Share this post


Link to post
Share on other sites
quote:
Original post by fallenang3l
Doing collision detection is inherently inelegant by using OOP in C++.


Well, I do not agree with you on that.

You can have a "CCollider" base class with all the common properties for different "figures" (sphere, box, etc), including a property that tells what kind of "figure" it is.

Then you inherit your CSphere, CElipsoid, CBox, CEtc clases from that one, setting the type_of_figure property and you write the proper collision detection there for all the other types of "figures".

Then you inherit from any of those you need in your game objects and you complete your collision response there (if having it all in the parent class doesn''t help).

That way you can have arrays or lists of CColliders and interact with them in the way you need, with the collision detection ready and only tweaking the kind of response you need.

Share this post


Link to post
Share on other sites
@owl:

that''s how i was going to do it. My only complaint is that every subclass at some point needs to know about every other subclass and every subclass also requires some kind of type field to identify itself. Personally i like this approach better, since you can then stuff all the object into a list and work with them like that. What i don''t like is all the type-specific collison checking code being spread all over the place. What i''m hearing is that it will be spread all over regardless of how i structure everything.

For instance. Let''s say i have a CollisionObjectWall object. It''s just a wall. You run into it, you stop. Later on in the process, i think it might be cool to have a CollisionObjectSpikedWall. It''s like a wall, but if you run into it, it hurts you. Now i have to go back through all the code and add to their rather ugly switch ( object->GetType() ) statements and add case SPIKED_WALL: to each one. This is the ugly part, the cross checking. So i guess we are not choosing ugly vs. not ugly, but rather, what flavor of uglyness suits the architecture of the current project :-)

For that, i would vote for your idea. Although i also liked that functionality of fallenang3l''s program (which also compiles nice thanks ;-)

Share this post


Link to post
Share on other sites
You only have to add the apropiate response for the SpikedWall in your "CHuman" class (the base class for all human-kind of objects in your game). That''s not much of a problem.

Share this post


Link to post
Share on other sites

well, you can use the Visit method, which removes needs for type identifiers.


class CCollObject
{
bool Intersect(const CCollObject& xObject) const=0;
bool Intersect(const CCollSphere& xObject) const=0;
bool Intersect(const CCollBox& xObject) const=0;
};


class CCollSphere: public CCollObject
{
bool Intersect(const CCollObject& xObject) const
{
return xObject.Collide(this);
}

bool Intersect(const CCollSphere& xObject) const
{
//....

//....

//....

}
bool Intersect(const CCollBox& xObject) const
{
return xObject.Intersect(*this);
}
};

class CCollBox: public CCollObject
{
bool Intersect(const CCollObject& xObject) const
{
return xObject.Collide(this);
}

bool Intersect(const CCollSphere& xObject) const
{
//....

//....

//....

}
bool Intersect(const CCollBox& xObject) const
{
//....

//....

//....

}
}


and you have dependencies that you don't need, ect....


Instead, It would be great if you could do



class CCollObject
{
static bool Intersect(const CCollObject& xObjectA, const CCollObject& xObjectB);
static bool Intersect(const CCollSphere& xSphereA, const CCollSphere& xSphereB);
static bool Intersect(const CCollSphere& xSphere, const CCollBox& xBox);
static bool Intersect(const CCollBox& xBoxA, const CCollBox& xBoxB);
};



so you move the intersect code away from the objects, and do the test in the CollObject class, or any other class. but then the problem is, how to deal with the type in a efficient and clean manner. But you only need to do the switch statement into the Intersect(CCollObject, CCollObject) function.

another way to do it is to have a 2D function table.



enum COLL_OBJECT_CLASS
{
COLL_OBJECT_CLASS_UNKNOWN=-1,
COLL_OBJECT_CLASS_SPHERE=0,
COLL_OBJECT_CLASS_BOX,
//--------------------------

COLL_OBJECT_NUM_CLASSES,
};

class CCollObject
{
public:
CCollObject(COLL_OBJECT_CLASS eClass)
: m_eClass(eClass)
{}

COLL_OBJECT_CLASS GetClass() const { return m_eClass; }

private:
const COLL_OBJECT_CLASS m_eClass; // unmodifiable class identifier

};


//---------------------------------------------------------

// Intersect Functions

//---------------------------------------------------------

class CCollTestManager
{
public:
static bool Intersect(const CCollObject* pxObjectA, const CCollObject* pxObjectB);

private:
static bool SphereSphereIntersect(const CCollObject* pxObjectA, const CCollObject* pxObjectB);
static bool SphereBoxIntersect(const CCollObject* pxObjectA, const CCollObject* pxObjectB);
static bool BoxBoxIntersect(const CCollObject* pxObjectA, const CCollObject* pxObjectB);

static bool (*s_pfnIntersectTable)(const CCollObject* pxObjectA, const CCollObject* pxObjectB)[COLL_OBJECT_NUM_CLASSES][COLL_OBJECT_NUM_CLASSES];
};


bool (*CCollTestManager::s_pfnIntersectTable)(const CCollObject* pxObjectA, const CCollObject* pxObjectB)[COLL_OBJECT_NUM_CLASSES][COLL_OBJECT_NUM_CLASSES] =
{ { CCollTestManager::SphereSphereIntersect, CCollTestManager::SphereBoxIntersect },
{ NULL , CCollTestManager::BoxBoxIntersect } };


bool CCollTestManager::Intersect(const CCollObject* pxObjectA, const CCollObject* pxObjectB)
{
// swap objects in case

if (pxObjectB->GetClass() < pxObjectA->GetClass())
{
const CCollObject* pxObjectC = pxObjectA;
pxObjectA = pxObjectB;
pxObjectB = pxObjectC;
}

return s_pfnIntersectTable(pxObjectA, pxObjectB);
}


[edited by - oliii on March 25, 2004 3:59:53 AM]

Share this post


Link to post
Share on other sites
The main problem here is decoupling all the different object types so that adding new objects is not a geometric process (i.e. for each new object, the amount of code to update isn''t increasing exponentially). Most of the solutions posted have a many-to-many relationship. Ideally, you want a many-to-one relationship.

So, instead of making each object aware of all other objects and responsible for determining the collision test/no test, create a new base class which is responsible for doing this:

class CollisionType
{
protected:
typedef enum
{
ObjectType1,
ObjectType2,
etc...
} CollisionTypeID;

virtual CollisionTypeID GetCollisionTypeID (void) const = 0;
bool DoCollisionTest (CollisionType &other_object);
};

Now, add the CollisionType class as a base class to all collision object classes and implement the GetCollisionTypeID function for each one. Add new IDs to the CollisionTypeID enumeration.

Next up is the DoCollisionTest function:

bool CollisionType::DoCollisionTest (CollisionType &other_object)
{
return m_do_test [GetCollisionTypeID ()] [other_object.GetCollisionTypeID ()];
}

This introduces the m_do_test array, a two dimensional bool array. There''s only one of these required for the whole application, so it can be made a static member of CollisionType.

Lastly, the m_do_test array need to be initialised. A static member function can do this, called during the loading phase:

class CollisionType
{
public:
static void LoadCollisionLookup (const char *const filename);
};

void CollisionType::LoadCollisionLookup (const char *const filename)
{
open file
load data and parse
close file
}

The data file can be a simple text file along the lines of:

ObjectType1: ObjectType2
ObjectType2: ObjectType1, ObjectType2, ObjectType3
Player: Enemy, EnemyBullet, World
Enemy: Player, PlayerBullet, World

You''ll need to have a lookup table from the string form of the ID and the enumeration value.

What we''ve now have is a system that is easy to add new types to: updating one class; and easy to modify the interactions: change the text file (doesn''t need any recompilation!).

Skizz

Share this post


Link to post
Share on other sites
@skizz. that''s good. You''ve solved the original problem of checking for which collisions need to happen (basically) using my original table, only from a file. very good.

However, the bigger problem remains: now that we know if the collision happens, we still need to know what happens and to whome.

For instance. I come up with my new class CollisionObjectSpikedWall. Its just like a regular wall, only it hurts if you touch it. However, you don''t won''t it to hurt bullets (yours or theirs), or the AI enemies (they are too stupid to avoid it). So the spiked wall object still needs to know about relationships to other objects so it can react properly. Somewhere along the line, that relationship needs to be coded. So we go back to a many-to-many strategy. there may not be any other for this situation.

Share this post


Link to post
Share on other sites
quote:
Original post by leiavoia
For instance. I come up with my new class CollisionObjectSpikedWall. Its just like a regular wall, only it hurts if you touch it. However, you don't won't it to hurt bullets (yours or theirs), or the AI enemies (they are too stupid to avoid it).

Derive SpikedWall from RegularWall, and only overload the DoCollisionTest(Player) and DoCollisionTest(Enemy) functions?

edit: or am i missing the whole point here Another possibility is that each object have a set of Properties, and a particular collision alters those Property objects (if they exist for that object). dunno if that'd work out :|

[edited by - Tim Cowley on March 25, 2004 10:03:17 PM]

Share this post


Link to post
Share on other sites
@tim:

yes for that example, that would work, just overloading the necessary functions or having them virtual in the first place. Perhaps SpikedWall was not a good example since it''s only a small difference. Instead, consider "Explosion": it hurts you and enemies, it also vaporizes any bullets passing through it. Now you have to redefine all the other collidable objects to work with Explosion, and Explosion to work with all the other objects. This gets more and more complicated the more collidable classes there are.

Share this post


Link to post
Share on other sites
Not necesarily. You search for collision from "explosion" against all other objects and, if "explosion" knows them, then, it alters them accordingly. Just like it would be in real life. A bullet doesn't have to know about explosion. Is the explosion the event accessing its surroundings.

[edited by - owl on March 25, 2004 11:19:33 PM]

Share this post


Link to post
Share on other sites
Okay, so here is my plan. Basically, it''s alot of inherited objects with a spartan virtual interface at the top. It does not avoid switch statements or typefields, but the fact that not all objects act upon other objects makes it a bit easier. Also, if there are new objects that come into being that inherit from these game objects, they can keep the same basic action() functions for acting on other collision objects, only changing the ones that apply specifically to them. That does not take out the complication, but does reduce code

As for choosing which collision *detection* function to use, so far i like fallenang3l''s concept since the disk-disk or vector-box and whatnot collisions are just straight-up math, he is right: precedural programming makes a bit of sense there.

So, here''s the mockup so far. I should point out that i did not show a swath of CollisionObjects that represent bounding geometry (for simplicity here). But eventually, Game Objects (like Player, Bullet, Enemy, Wall) will inherit from some kind of geometry class, and the geometry class with inherit from the base CollisionObject class:


#ifdef COLLISIONOBJECTS_H
#define COLLISIONOBJECTS_H


enum collision_obj_type {
COLLISION_OBJ_PLAYER =1,
COLLISION_OBJ_PLAYER_WEAPON,
COLLISION_OBJ_ENEMY,
COLLISION_OBJ_ENEMY_WEAPON,
COLLISION_OBJ_UNOWNED,
COLLISION_OBJ_UNOWNED_WEAPON,
COLLISION_OBJ_WORLD,
};



class CollisionObject {
public:

/** Constructor */
CollisionObject( collision_obj_type t );

/** Destructor */
virtual ~CollisionObject;

/** Returns FALSE if "obj" intercepts me on it''s next update */
virtual bool Collides( CollisionObject obj ) = 0;

/** Assuming there is a collision, causes me to act upon ("collide with") the other object provided.
I only act upon other objects I know about. Otherwise I default to doing nothing. */

virtual void Act( CollisionObject obj ) {;;}

/** Object''s base collision game-object type (not bounding geometry type) */
const collision_obj_type type;

};




class CollisionObjectPlayer: public CollisionObject {
public:
/** Constructor */
CollisionObjectPlayer();

/** Destructor */
virtual ~CollisionObjectPlayer();

/** Returns FALSE if "obj" intercepts me on it''s next update */
virtual bool Collides( CollisionObject obj );

/** Assuming there is a collision, causes me to act upon ("collide with") the other object provided.
I only act upon other objects I know about. Otherwise I default to doing nothing. */

virtual void Act( CollisionObject obj );
}





bool CollisionObjectPlayer::Collides( CollisionObject obj ) {
// using some slick math function, return whether or not i collided.

// picking which function is a whole ''nuther story not discussed here.

}




void CollisionObjectPlayer::Act( CollisionObject obj ) {
switch ( obj.type ) {
// don''t check against other players.

// don''t check against my own weapons

case COLLISION_OBJ_ENEMY: {
// get hurt.

break;
}
case COLLISION_OBJ_ENEMY_WEAPON: {
// get hurt

break;
}
case COLLISION_OBJ_UNOWNED: {
// get hurt

break;
}
case COLLISION_OBJ_UNOWNED_WEAPON: {
// get hurt

break;
}
case COLLISION_OBJ_WORLD: {
// stop!

break;
}
default: ;;
}
}

#endif

Share this post


Link to post
Share on other sites
Interesting topic!

I am interested in the method that uses the typeid-operator. How cheap is that one performance vise? Is it really suited for that purpose?

Thanks

Share this post


Link to post
Share on other sites
a table of function pointers is probably the fastest way to do it. I mean, it requires no virtual tables, as it shortcuts it with a 2D table. Either use std maps, or your own home-brewed function pointer table, and you only require to extend the table as new types are added, and obviously add the collision solving function. It can be extended to other things, like collision response depending on different physics types as well, and culling physical objects types prior to collision detection. It just looks unclean, but that can be improved, by uses of typedefs and structures to structure the code better.

here''s an example


#include <iostream.h>


//------------------------------------------------------------------------------------------------

// function pointer aliases

//------------------------------------------------------------------------------------------------

typedef bool (*fnIntersectType)(class CCollObject* A, class CCollObject* B);
typedef bool (*fnResponseType )(class CPhysicsObject* A, class CPhysicsObject* B, class CContactObject* pxContact);

//------------------------------------------------------------------------------------------------

// table of function pointers

//------------------------------------------------------------------------------------------------

template < typename FUNC, int NUMTYPES>
struct CFunctionTable
{
public:
CFunctionTable()
{
memset(m_xTable, 0, sizeof(m_xTable));
}

void SetFunction(int iTypeA, int iTypeB, FUNC fnFunction)
{
m_xTable[iTypeA][iTypeB] = fnFunction;
}

FUNC operator()(int iTypeA, int iTypeB) { return m_xTable[iTypeA][iTypeB]; }

private:
FUNC m_xTable[NUMTYPES][NUMTYPES];
};



//------------------------------------------------------------------------------------------------

// CCOllObject

//------------------------------------------------------------------------------------------------

enum COLL_OBJECT_TYPE { COLL_SPHERE, COLL_BOX, COLL_NUM_TYPES };

typedef CFunctionTable<fnIntersectType, COLL_NUM_TYPES> CIntersectTable;
typedef CFunctionTable<fnResponseType, COLL_NUM_TYPES> CResponseTable;

class CCollObject
{
public:
virtual ~CCollObject() {}

virtual const char* strName() const = 0;

COLL_OBJECT_TYPE GetType() const { return m_eType; }

protected:
CCollObject(COLL_OBJECT_TYPE eType) : m_eType(eType) {}

private:
const COLL_OBJECT_TYPE m_eType;
};

//------------------------------------------------------------------------------------------------

// CCOllBox

//------------------------------------------------------------------------------------------------

class CCollBox: public CCollObject
{
public:
CCollBox(): CCollObject(COLL_BOX){}

virtual const char* strName() const { return "Box"; }
};

//------------------------------------------------------------------------------------------------

// CCOllSphere

//------------------------------------------------------------------------------------------------

class CCollSphere: public CCollObject
{
public:
CCollSphere(): CCollObject(COLL_SPHERE) {}

virtual const char* strName() const { return "Sphere"; }
};


//------------------------------------------------------------------------------------------------

// test intersections and calls the right function from the function table pointer

//------------------------------------------------------------------------------------------------

class CIntersectTestManager
{
public:
CIntersectTestManager()
{
m_xIntersectTable.SetFunction(COLL_SPHERE, COLL_SPHERE, IntersectSphereSphere);
m_xIntersectTable.SetFunction(COLL_BOX , COLL_SPHERE, IntersectBoxSphere);
m_xIntersectTable.SetFunction(COLL_BOX , COLL_BOX , IntersectBoxBox);
}

bool Intersect(CCollObject* A, CCollObject* B)
{
if (A->GetType() < B->GetType())
{
CCollObject* C = A;
A = B;
B = C;
}

fnIntersectType pxIntersectFunc = m_xIntersectTable(A->GetType(), B->GetType());

if (pxIntersectFunc)
return pxIntersectFunc(A, B);

return false;
}

private:
static bool IntersectSphereSphere(CCollObject* A, CCollObject* B)
{
cout<<"Test : SPHERE - SPHERE"<<endl;
cout<<"Objects : "<<A->strName()<<" : "<<B->strName()<<endl<<endl;
return true;
}
static bool IntersectBoxSphere(CCollObject* A, CCollObject* B)
{
cout<<"Test : BOX - SPHERE"<<endl;
cout<<"Objects : "<<A->strName()<<" : "<<B->strName()<<endl<<endl;
return true;
}
static bool IntersectBoxBox(CCollObject* A, CCollObject* B)
{
cout<<"Test : BOX - BOX"<<endl;
cout<<"Objects : "<<A->strName()<<" : "<<B->strName()<<endl<<endl;
return true;
}


CIntersectTable m_xIntersectTable;
};


//------------------------------------------------------------------------------------------------

// List of objects

//------------------------------------------------------------------------------------------------

class CCollObjectManager
{
public:
CCollObjectManager()
{
for(int i = 0; i < 32; i ++)
{
if (rand() & 1)
m_pxObjects[i] = new CCollSphere();
else
m_pxObjects[i] = new CCollBox();
}
}

~CCollObjectManager()
{
for(int i = 0; i < 32; i ++)
{
delete m_pxObjects[i];
}
}

void TestIntersect()
{
for(int i = 0; i < 32; i ++)
{
for(int j = i+1; j < 32; j ++)
{
cout<<"("<<i<<", "<<j<<")"<<endl;
m_xIntersectManager.Intersect(m_pxObjects[i], m_pxObjects[j]);
}
}
}

CCollObject* m_pxObjects[32];
CIntersectTestManager m_xIntersectManager;
};





void main(void)
{
CCollObjectManager xManager;

while (1)
{
if (getchar())
{
xManager.TestIntersect();
}
}
}

Share this post


Link to post
Share on other sites
Personally i like the stl map idea for containing the f() pointers. That way, it is possible to easily return NULL if there is no such pointer (i.e. object A does not react with object B) without wasting space on array elements that don't need to be.

[edited by - leiavoia on March 26, 2004 11:50:58 AM]

Share this post


Link to post
Share on other sites
probably, but I''m not 100% sure, with the way the compilers optimise things those days. but it certainly looks a lot better, is easier to maintain, more readable, is self contained, and is reusable for other things. It''s like a virtual table, but in 2D And nothing prevents you from doing it in 3D, ect...

for the std thing, isn''t that doing a search on a list every time? Maybe it uses less space (although doubtful, since I only waste a few 32 bit pointer, and that''s if you want to avoid code duplication or an extra function call, whereas I assume the std allocates memory and other stuff), but searching for things in a time critical part of the code is not good in my book But you really have to use a 2D array like I do, you can still store the function pointers in a dynamic array, sort them, have a hash table for quick lookups, ect... It''s a balance thing.

The visit intersect method is the cleanest looking, but probably the slowest (at least two virtual function calls), and has some pretty efty dependencies as well, if you start considering using 10 different types of objects.

This stuff is not the first thing you should consider optimising, but keeping the intersect function declarations consistent (little dependencies, all static members or global functions, taking the exact same parameters, ...), like fallenangel does, give you a better choice of methods.

Share this post


Link to post
Share on other sites
Funny, I was trying to solve the exact same problem but no one posted an answer. Maybe it was how I worded it. Anyways I was thinking that over and the problem came not from dectecting the collision but dealing with it. The problem is:
IObject::VOnCollide(IObject* otherObject);
Now what happens when this gets called. (this will get called twice, once for each object) Basicly you want each object to be able to interact with out knowing what IObject points to(ie: no dynamic checks, type ids, or anyother hardcoded dependancies) however this is almost imposible without severly reducing flexiblity. Because you would need, anything that each object needs to know as a virtual member of IObject. Now with out knowing what objects you are going have in the future you can''t possible think of everything your going to need. So unless you reduce every possible collision down to a very simple process( like sub-atomic collision rules(not that there every simple, lol)) it severly limits the type of objects you can have. SO the only solution I came up with was to use dynamic casts to determine if each object knows what to do. Ie; it asks if it is a CPhysicObject and if it is, casts it up and use the new members that were exposed to determine the new velocity ect... I''m not sure if this will work yet, so please, if it won''t work someone PLEASE tell me before i code all that.
Enough of my blabing. lol


Nick
Müsli Games
www.musli.tk

Share this post


Link to post
Share on other sites
will work, but you''ll be doing things like
if (dynamic_cast(pxObject))
{ ... }
else if (dynamic_cast(pxObject))
{ ... }

which defeats the point of a fast solution. You might as well use a VisitIntersect method, it''s a lot faster, and does not require typeIDs, or use

class CCar: public CObject
{
virtual CCar* GetCar() { return *this; }
virtual CCar* GetBike() { return NULL; }
....
....
...
..
.
};

Share this post


Link to post
Share on other sites
@nickmerritt

i think what you are saying is that once you''ve established that there is a collision, you can''t effectively deal with it since you don''t know what kinds of objects you actually have. Right?

I can''t think of any brilliant way around that. Here is my plan so far, but i''d like advice from oliii as to whether or not it might work:

Let''s go with the table of function pointers idea. This idea relies somewhat on the fact that we do in fact have a Type Field. The good news about type fields is that they let us determine what an object* should be since the type is a member of the base class. like...

base_class_obj->GetType();

We can then have our table of function pointers that handle each (appropraite) specific collision type. So now we get the part where we deal with the collision. Let''s say we have a basic ENEMY vs PLAYER collision. The collision manager finds that, based on types, we do in fact have a player and an enemy. So it calls:

void player_vs_enemy_collision(Object* player, Object* enemy);

In this function, if we''''ve gotten to this point, we already know that we have 1 player vs 1 enemy so:

player = static_cast<objectPlayer*>(player);
enemy = static_cast<objectEnemy*>(enemy);

And we can now unlock all the non-virtual goodness of those classes.

That''s the plan...


ISSUE #2
@oliii

First of all, i like your function-pointer table template. It''s makes me sound smart just saying it :-) You''ve solved another problem i had: getting the appropriate responses to deal with the 3 processes in collision detection:

1) Check to see if the collision makes sense
2) Check to see if we actually collided
3) Act upon the other object we collided with.

In my mind, each of these 3 things needs it''s own table, and a template solves that very nicely. Thanks


Now, the more advanced issue:

I have 3 basic classes for arguement:
CollisionObjectPlayer and
CollisionObjectEnemy
CollisionObjectWall

They are included in the tables and return function pinters and the whole system works great. OK, now i want to add some arbitrary new class that inherits from one of these. let''s call it:
CollisionObjectExplodingEnemy

Instead of simply hurting you when you touch it, it literally blows up and hurts you and destroys itself. It''s behaviour is different enough to warrant a new class and possibly a new entry into the function table.

In your previous code example, you made all the functions in the function table external from any class. My questions to you are:

1) can i safely make these members of classes? Make all the Enemy vs OtherObject functions static members of CollisionObjectEnemy?

2) If yes, i''d like to create new versions with "virtual" of the collision handling functions, for say, enemy_vs_player() since the way it needs to be handles by CollisionObjectExplodingEnemy and CollisionObjectEnemy are different. I DO NOT want to create an entirely new type to check against, i just want to inherit these collision functions from the basic Enemy class.

the question is: if i grab the (static virtual) function pointer out of the function table, will it actually behave "virtually"?

This is getting into some rather complicated territory, so i hope i explaine myself well. I will test these things if they work or not, but perhaps my approach is, uh, "not smart" :-)

Share this post


Link to post
Share on other sites
After some testing:

I CAN make the functions in the function-pointer table static class members of the respective classes.

I CANNOT make those functions both static and virtual, so i can''t simply inherit a class from a higher class that contains those functions if i need to redefine what those functions do.

This means that every time i have an object that deviates from the others, i have to create a completely new collision object type. I cannot simply inherit from something i already have unless the collision checking works the same way. That bites :-(

There are creative ways around this issue however. I could wrap a static member function around a class-specific version of the error checking code. This way i could have pseudo "static virtual functions". But already you can see this is getting messy.

Share this post


Link to post
Share on other sites