There are a few specific techniques to test if one object has hit another object in a game. One of them is called "double dispatch." Can someone explain what double dispatch is, and how it can be used to test hit objects?
Double-dispatch doesn't help with collision detection per se, it helps with the prelude to collision detection: given two arbitrary shapes, determine which collision detection algorithm to use (ray-triangle, ray-circle, ray-box, triangle-circle, et cetera).
In many programming languages -- like C++ -- dynamic dispatch (what happens when you call a virtual member function) resolves based only on the type of a single parameter to that function (the "this" pointer, in other words the type of the invoking object). Double-dispatch is a way to resolve a function call based on two of the function's arguments.
In a collision detection scenario where you have two
Shape objects (
Shape being the base class for all possible concrete collision shapes), you want to select a collision detection function based on the actual run-time type of both objects.
There is a lot of information on implementing double dispatch (or its more general cousin, multiple dispatch) in C++ floating around. Many of them apply equally well, excepting in syntax, to whatever other C++-like language you may be using:
- A GDNet discussion thread on the topic
- Multiple dispatch using templates and RTTI
- Double dispatch revisited on Dr. Dobbs
- And another Dr. Dobbs article on the topic
Google can locate you many more. Note that "double dispatch" refers almost exclusively on the wide internet to a technique involving virtual methods, and many implementations C++ rely on constructs like templates or RTTI to alleviate some of the tedium of the technique (since it's not built-in to the language).
This can actually make those techniques poor choices for game development or other scenarios where very high performance may be required of a simulation that processes a large number of potential collisions per step, because the overhead of some of those techniques may be non-zero (and in particular may have cache coherency issues or issues on restricted platforms like consoles). Additionally, because it relies on dynamic dispatch, the implication is that all shape primitives must inherit a common base class -- which is not always a desirable design.
If nothing else, double-dispatch code may become overly complex, making it hard to maintain or extend.
For this reason you may want to explore alternative approaches, such as simply reducing the number of simple primitives you have in your game to the point where a simple function table is sufficient for resolving the collision function, or otherwise implementing the "dispatch" part of the technique manually. Double-dispatch is not a be-all, end-all solution.