Inheritance/interface decisions for physics engine

Question

This is for a small game project with SDL on MinGW/Windows.

I am working on a physics engine, and my idea was to have a Physics::Object, which all physical objects should derive from and it registers itself with a global Physics::System class (it's a monostate pattern) so that the user doesn't need to track which objects are included in physics calculations and just needs to call a function like Physics::System::PerformTimestepCalculation(double dt).

This works fine, and I even implemented it using a single derived class Physics::Circle, which is a 2d circle. I was pretty happy with the predictive collision detection, even though I still need to optimise it.

Anyway, I ran into trouble when I started adding other primitives to include in the calculation, e.g. line. The Physics::System::PerformTimestepCalculation(double dt) became littered with calls to Object::GetID() or similar functions (may way to avoid dynamic_cast<>), but I feel dirty.

I did a bit of reading and realised that my the elements of my hierarchy are not substitutable (i.e. the collision between two circles is very different between the collision of two lines).

I like the way my Physics::Objects "self register" with the System class so they automatically get included in the calculations, and I don't really want to lose this.

There must be some other sensible design paths. How can I better redesign things so non-substitutable objects do not get in the way?

Edit FYI: In the end I have broken away entity and shape properties, similar to how it was described in the accepted answer, and similar to an entity-component-system model. It means I still have the yuk logic of "is this a circle or a line, and is that a line or a circle?", but I'm no longer pretending that polymorphism helps me here. It also means I use some sort of factory and can have multiple calculation worlds happening at once!

Answer 1

The most successful publically available physics engines are not very heavy on the 'patterns' or 'object oriented design'.

Here's a rundown to back up my, admittedly bold, assertion:

Chipmunk - written in C, enough said.

Box2d - Written in C++, and there is some polymorphism here. there's a hierarchy of shapes (base class b2Shape) with a few virtual function. That abstraction leaks like a sieve, though, and you'll find lots of casts to leaf classes throughout the source code. There's also a hierarchy of 'contacts', which proves more successful, although with a single virtual function it would be trivial to rewrite this without polymorphism (chipmunk uses a function pointer, I believe). b2Body is the class used to represent rigid bodies, and it is non-virtual.

Bullet - Written in C++, used in a ton of games. Tons of features, tons of code (relative to the other two). There's actually a base class that the rigid body and soft body representations extend, but only a small part of the code can make any use of it. Most of the base class's virtual function relate to serialization (save/load of the engine state), of the two remaining virtual functions soft body fails to implement one with a TODO informing us that some hack needs to be cleaned up. Not exactly a ringing endorsement of polymorphism in physics engines.

That's a lot of words, and I haven't even really started answering your question. All I want to hammer home is that polymorphism is not something that is applied effectively in existing physics engines. And that's probably not because the authors didn't "get" OO.

So anyway, my advice: ditch polymorphism for your entity class. You're not going to end up with 100 different types that you can't possibly refactor at a later date, your physics engine's shape data will be fairly homogeneous (convex polys, boxes, spheres, etc) and your entity data will likely be even more homogeneous (probably just rigid bodies to start with).

Another mistake that I feel you're making is only supporting one Physics::System. There is utility in being able to simulate bodies independently of eachother (for instance, for a two player game), and the easiest way to do this is to support multiple Physics::Systems.

With that in mind, the cleanest 'pattern' to follow would be a factory pattern. When users want to create a rigid body, they need to tell the Physics::System (acting as a factory) to do it for them, so in your Physics::System:

// returning a smart pointer would not be unreasonable, but I'm returning a raw pointer for simplicity:
rigid_body_t* AddBody( body_params_t const& body_params );

And in the client code:

circle_params_t circle(1.f /*radius*/);
body_params_t b( 1.f /*mass*/, &circle /*shape params*/, xform /*system transform*/ );
rigid_body_t* body = physics_system.AddBody( b );

Anyhoo, kind of a rant. Hope this is helpful. At the very least I want to point you towards box2d. It's written in a pretty simple dialect of C++ and the patterns applied therein will be relevant to your engine, whether it's 3D or 2D.

Answer 2

The problem of hierarchies is that they don't always make sense, and trying to cram everything into a hierarchy just results in awkward decisions and frustrating work down the line.

The other solution that can be used is the tagged union one, best embodied by boost::variant.

The idea is to create an object that can hold one instance of a given type (among a preselected list) at any given time:

typedef boost::variant<Ellipsis, Polygon, Blob> Shape;

And then you can provide the functionality by switching over the type list:

struct AreaComputer: boost::static_visitor<double> {
  template <typename T>
  double operator()(T const& e) { return area(a); }
};

void area(Shape const& s) {
  AreaComputer ac;
  return boost::apply_visitor(s, ac);
}

The performance is the same as a virtual dispatch (so not too much, normally), but you get greater flexibility:

void func(boost::variant<Ellipsis, Blob> const& eb);
void bar(boost::variant<Ellipsis, Polygon> const& ep);
// ...

You can provide functions only when relevant.

And on the subject of binary visitation:

struct CollisionComputer: boost::static_visitor<CollisionResult> {
   CollisionResult operator()(Circle const& left, Circle const& right);
   CollisionResult operator()(Line const& left, Line const& right);

   CollisionResult operator()(Circle const& left, Line const& right);
   CollisionResult operator()(Line const& left, Circle const& right);
};

CollisionResult collide(Shape const& left, Shape const& right) {
  return boost::apply_visitor(CollisionComputer(), left, right);
}