Thread: Binary Function - Design Pattern Question

  1. #1
    Registered User
    Join Date
    Aug 2001
    Posts
    244

    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?
    signature under construction

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Provide such a collision detection function in IGeometricObject, perhaps a virtual function?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    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...
    signature under construction

  4. #4
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    Quote Originally Posted by laserlight View Post
    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).
    signature under construction

  5. #5
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    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)
    Last edited by Raven Arkadon; 07-16-2007 at 10:04 AM.
    signature under construction

  6. #6
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    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.
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  7. #7
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    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).
    signature under construction

  8. #8
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Alexander Alexandrescu presents various ways to write multimethods in his "Modern C++ Design".

    C++ has no direct support for them.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  9. #9
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    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/

  10. #10
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    I believe the whole multimethod implementation is in there.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 05-13-2011, 08:28 AM
  2. doubt in c parser coding
    By akshara.sinha in forum C Programming
    Replies: 4
    Last Post: 12-23-2007, 01:49 PM
  3. Calling a Thread with a Function Pointer.
    By ScrollMaster in forum Windows Programming
    Replies: 6
    Last Post: 06-10-2006, 08:56 AM
  4. <Gulp>
    By kryptkat in forum Windows Programming
    Replies: 7
    Last Post: 01-14-2006, 01:03 PM
  5. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM