Best practice approach to code structure in this situation?

Question

Hey, I have a question regarding code structure, and was wondering what the best practice is or if there was a specific design pattern I should be using.

I have an abstract base class BoundingVolume which can have subclasses such as BoundingSphere, BoundingBox, etc. A comparison has to be made between two BoundingVolumes to determine if they overlap, this comparison is made by a World class which keeps track of all objects in the simulation and is responsible for handling collisions between volumes.

My initial thought was that the World class would hold a collection of BoundingVolume objects, and call a virtual CollidesWith method defined on BoundingVolume which would accept another BoundingVolume to make the comparison with. The problem is the algorithm for determining if two BoundingVolumes overlap is different for each subclass, for example the algorithm for sphere collides with sphere is not the same as box collides with box, or box collides with sphere.

Using my initial plan each subclass would have to determine what the actual type of the BoundingVolume being passed to it was and make a switch to use the correct algorithm. Additionally each subclass would have to be extended every time a new subclass is added, effectively eliminating all benefit of having subclasses in the first place. Is there a better way to structure this?

I'm more looking for a solution to situations like this in general than an answer to this specific scenario.

Thanks for your help.

Answer 1

This seems like a situation where a separate function sounds like the best solution. Make a function, which is a friend of the subclasses so it can acres it's members. To determine which subclasses are being passes to it, it can read a private/protected member function className().

That way, you just need to do a switch for all the possible combinations of bounding shapes. I would give each shape a number. This would be for a switch statement, and so that you can get the highest and lowest. This is to avoid formula repeats ( A==B = B==A ).

I hope I've made sense. I'm typing this on iPhone

Answer 2

Is there a better way to structure this?

One solution here is to use double dispatch, which is where the target function is determined by the concrete types of two objects. In languages like C#, the default function call mechanism is single dispatch, i.e. the target function is just determined by the concrete type of a single object.

In languages like C# or C++, double dispatch is achievable through the visitor pattern. For example, in your case, this might look like the following:

interface BoundingVolume
{
    bool CollidesWith(BoundingVolume v);

    bool CollidesWith(BoundingBox b);
    bool CollidesWith(BoundingSphere s);
}

class BoundingBox : BoundingVolume
{
    public bool CollidesWith(BoundingVolume v)
    {
        return v.CollidesWith(this);
    }

    public bool CollidesWith(BoundingBox b)
    {
        Console.WriteLine("box/box");
        return true;
    }

    public bool CollidesWith(BoundingSphere s)
    {
        Console.WriteLine("box/sphere");
        return true;
    }
}

class BoundingSphere : BoundingVolume
{
    public bool CollidesWith(BoundingVolume v)
    {
        return v.CollidesWith(this);
    }

    public bool CollidesWith(BoundingBox b)
    {
        Console.WriteLine("sphere/box");
        return true;
    }

    public bool CollidesWith(BoundingSphere s)
    {
        Console.WriteLine("sphere/sphere");
        return true;
    }
}

class Program
{
    static void Main(string[] args)
    {
        BoundingVolume v1 = new BoundingBox();
        BoundingVolume v2 = new BoundingSphere();
        Console.WriteLine(v1.CollidesWith(v2));
    }
}

You could imagine that the box/sphere and sphere/box implementations just call out to a common collision utility function for detecting collisions between a sphere and a box.

Additionally each subclass would have to be extended every time a new subclass is added, effectively eliminating all benefit of having subclasses in the first place

Depending on what they do, the subclasses could still give you benefit through other polymorphic behavior, e.g. a ContainsPoint virtual method would return whether or not the specific BoundingVolume contained a Point.

Essentially, though, you can't avoid the combinatorial explosion if you have the need to special-case each type of collision since something somewhere will need to say "if I have an X and a Y, how do I compute their intersection efficiently?" This could be a big switch statement, a table of methods, or the double dispatch via visitor pattern mentioned above.

Answer 3

Without knowing more, it sounds like you may be missing a level of abstraction.

In an ideal scenario, there would be a CollissionDetector that could take objects with just enough information to detect collisions. Now, presumably, the shapes of various objects can be quite different, as you've pointed out, but that's why you want that code separated out into a different class with nothing in it but overloaded methods or (even better). The overloads would recognize something like IBoundingBox, IEllipitcalBoundingBox, and so forth, and handle them from there.

You're right, though: this isn't something you want each box itself to know about. Eventually, you'll be wondering which box knows what, and you'll find that you've violated the principle of least knowledge.