Jump to content
  • Advertisement

Archived

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

leiavoia

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

This topic is 5229 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
Advertisement
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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!