Binary Function - Design Pattern Question

Hi,

so lets assume i wanted to write i collision system that can determine wheter some objects collide (e.g. sphere - cuboid, or triangle cylinder, or whatever).

The thing is, that all these objects should be stored in a container, e.g.

Code:

---

    typedef Set<IGeometricObject*> MyContainer;

---

So how can i test wheter 2 objects of this container collide? The problem is, that i do not know the original type of the objects anymore. So i end up with something like:

Code:

---

    bool is_collision(const IGeometricObject &r_lhs, const IGeometricObject &r_rhs)
    {
        // Hmmm... what now?
        // check with type-id/dynamic cast?
    }

---

So whats the best way to solve this without having long if blocks with dynamic casts and type-id checks?

Provide such a collision detection function in IGeometricObject, perhaps a virtual function?

Well actually most troubles i have with my current solutions is, that i would need somthing like the java "instanceof" operator -
so i need to check wheter some typeid(XXX) is a base of typeid(YYY). Ideally something like dynamic_cast<typeid(target)>(source).

Ahh i guess i just gave myself the answer:

Code:

---

// The base collider provides methods which return true if the object may be part of the relation
class ICollider
{
    virtual bool is_collision(const IGeometricObject &r_lhs, const IGeometricObject &r_rhs) const = 0;
    virtual bool does_accept(const IGeometricObject &r_lhs, const IGeometricObject &r_rhs) const = 0;
};

template <typename A, typename B>
class AbstractCollider
    : public ICollider
{
public:
    typedef A First;
    typedef B Second;

    virtual bool does_accept(const IGeometricObject &r_lhs, const IGeometricObject &r_rhs) const
    {
        return (dynamic_cast<const First*>(&r_lhs) != NULL) &&
            (dynamic_cast<const Second*>(&r_rhs) != NULL);
    }

    bool is_collision(const IGeometricObject &r_lhs, const IGeometricObject &r_rhs) const
    {
        return __is_collision(dynamic_cast<const First&>(r_lhs),
            dynamic_cast<const Second &>(r_lhs));
    }

    // The actual implementation belongs to some derived class
    virtual __is_collision(const First &r_lhs, const Second &r_rhs) const = 0;
};


// So all a collider writer now has to do is to inherit from AbstractCollider
// and the does_accept method automatically returns true for the correct types.
class Custom_Sphere_Sphere_Collider
    : public AbstractCollider<ISphere, ISphere>
{
public:
    bool __is_collision(const ISphere &r_lhs, const ISphere &r_rhs)
    {
        // Implementation goes here
    }
};

// Eventually, there can be a container where colliders can be registered. The container
// can lookup colliders lazily when they are needed (using the does_accept method),
// and cache the result, so that the next collider lookup can happen in constant time
// (if colliders are stored in a matrix, and the types of the objects that can collide
// are LAZILY assigned appropriate index values)
// now i just need to figure out how to get rid of that lazily...

---

Quote:

---

Originally Posted by laserlight

Provide such a collision detection function in IGeometricObject, perhaps a virtual function?

---

Well but still the collision detection function would have to check the type of the OTHER object.
And actually its not the sphere's business to know how to collide with a cuboid. Some meta level (container to be more specific) should take care of that imo.
(Of course it may end up with wrappers that provide virtual functions again, but under the hood i think i there should be some way to dynamically register und unregister collision functions).

oh... and it makes sense to split up "does_accept(a, b)" method into a does_accept_first(a) and does_accept_second(b) method. then a container can figure out which types are accepted in linear time (scanning all objects in the container once).

but then the 2 arguments must be independent (so it must not happen, that does_accept_first and does_accept_second return true on e.g. {Sphere, Cuboid}, but actually the collider only
supports Spere-Sphere and Cuboid-Cuboid, but not Cuboid-Sphere)

Scott Meyers talks about this exact problem in "More Effective C++" (item 31). Unfortunately, I don't think he actually manages to solve it, but at least you could head to your local library and have a look.

Hm, thanks.
Basically i guess it turns out that typeinfo should at least provide inheritance information.
(Are there plans to adding this to C++ (maybe even an introspection API))?
Because the problem is actually simply to find an appropriate function that accepts a set of given arguments (of certain dynamic types) among a set of candidate functions. (so this is just what the compiler does at compile time anyway).

Alexander Alexandrescu presents various ways to write multimethods in his "Modern C++ Design".

C++ has no direct support for them.

Andre Alexandrescu's book uses a lot of code which he has released via the Loki library (such as typelists, which i believe are one of the cornerstones of his multimethods).

Loki is available from here - http://loki-lib.sourceforge.net/

I believe the whole multimethod implementation is in there.