Multiméthodes – Exemple

Notez que les équations dans ce document sont affichées à l'aide de MathJax.

Il existe des problèmes pour lesquels l'approche polymorphique classique, exprimée sous la forme sujet.action(objet) où sujet est une abstraction polymorphique (p. ex. : une indirection vers une Forme, menant effectivement vers un Cercle, un Carré, un Triangle ou une autre sorte de forme) ne convient pas.

Ces cas, qu'on identifie en anglais sous le vocable Multiple Dispatch (mais le cas le plus fréquent est le polymorphisme sur deux types, ou Double Dispatch) sont des opérations (action(), dans notre écriture) tiennent compte du type effectif non seulement de l'instance réputée active (sujet dans notre écriture plus haut) mais bien de celle de plusieurs types (par exemple, le type effectif d'objet dans notre écriture). Le vocable technique utilisé pour des services polymorphiques sur la base de plusieurs types est multiméthode.

Le cas canonique est celui de la détection de collisions entre deux volumes. L'exemple qui suit est minimaliste, simpliste et incomplet, mais montre la structure générale d'une solution à ce problème en C++. Ce n'est pas une explication complète de ce que sont les multiméthodes et de diverses alternatives (je couvre ça en classe, habituellement).

Design général

Supposons Volume une abstraction polymorphique dont il existe au moins deux spécialisations (pour les fins de l'exemple, Boite et Sphere seront toutes deux des spécialisations de Volume).

Supposons que v0 et v1 soient deux volumes. Les cas possibles sont :

v0 est une Boite et v1 est une Boite
v0 est une Boite et v1 est une Sphere
v0 est une Sphere et v1 est une Boite
v0 est une Sphere et v1 est une Sphere

Sans surprises, ajouter des types de spécialisations de(comme c'est le cas dans de vrais projets) accroît de beaucoup le nombre de cas possibles ( $2^n$ cas à traiter pour $n$ types de spécialisations, quoique dans un cas comme celui des collisions, plusieurs des cas soient redondants – collisionner une Boite et une Sphere implique le même algorithme que collisionner une Sphere et une Boite, et peut s'implémenter par un simple relais), ce qui démontre que ce problème est un véritable problème de design.

Nous souhaitons savoir si v0 et v1 collisionnent (si leurs volumes s'intersectent). Il se trouve que les algorithmes pour détecter une collision entre deux sphères, entre deux boîtes, ou entre une sphère et une boîte sont différents. Connaître les types effectifs des deux volumes permet de choisir le meilleur algorithme dans les circonstances.

En gros l'idée de base derrière ce qui suit est que :

Le test démarre par un appel polymorphique à v0.collision(v1) où v0 et v1 sont tous deux au moins des instances de Volume
Cet appel mène à l'implémentation effective de collision() pour v0. Supposons que v0 soit en fait une Boite; alors, l'appel résolu par polymorphisme ici sera Boite::collision(const Volume&), et nous venons de découvrir le type effectif de v0
L'implémentation de cette collision pour une Boite et prenant en paramètre un Volume nommé v prendra le problème d'un autre angle, et appellera v.collision(*this) où *this et non pas un Volume mais bien une Boite. Ceci mènera, par polymorphisme, vers l'implémentation spécialisée de collision(const Boite&) pour le type effectif de v (donc de v1 à l'origine)
Supposons que v1 soit en fait une Sphere; alors, nous venons d'appeler Sphere::collision(const Boite&)
Bingo! Nous connaissons maintenant les deux types impliqués, et nous sommes en mesure de choisir le meilleur algorithme possible dans les circonstances.

Le coût à l'exécution de cette manoeuvre est une double indirection polymorphique, ce qui peut être dispendieux. Il y a aussi un coût architectural (ajouter un nouveau type dans le système est complexe).

Classe Point

Pour exprimer nos volumes, nous aurons recours à une classe Point. J'ai choisi une implémentation pour espaces tridimensionnels, l'idée étant de discuter de collisions entre volumes, et j'ai utilisé des nombres à virgule flottante de simple précision pour les coordonnées, mais ce sont des choix d'implémentation, pas des obligations.

L'implémentation est somme toute assez simple pour un exemple comme celui-ci.

#ifndef POINT_H
#define POINT_H
#include <cmath>
struct Point {
   using value_type = float;
   value_type x {}, y {}, z {};
   constexpr Point(value_type x, value_type y, value_type z) noexcept
      : x{ x }, y{ y }, z{ z } {
   }
   Point() = default;
   // présume un std::abs() constexpr (C++ 20)
   friend constexpr Point::value_type
      distance(const Point &p0, const Point &p1) noexcept {
      using namespace std;
      auto dx = abs(p0.x - p1.x);
      auto dy = abs(p0.y - p1.y);
      auto dz = abs(p0.z - p1.z);
      return sqrt(dx + dy + dz);
   }
   constexpr Point operator-() const noexcept {
      return { -x, -y, -z };
   }
   friend constexpr Point operator+(const Point &p0, const Point &p1) noexcept {
      return {p0.x + p1.x, p0.y + p1.y, p0.z + p1.z};
   }
   friend constexpr Point operator-(const Point &p0, const Point &p1) noexcept {
      return p0 + -p1;
   }
};
#endif

Classe Volume

Le Volume sera la racine polymorphique de notre exemple.

Notez les déclarations a priori des classes Sphere et Boite. En effet, une version spécialisée de la signature de notre multiméthode doit être déclarée dès la racine polymorphique, et spécialisée éventuellement dans tous les enfants.

Conséquemment, ajouter une classe dans le système implique au moins (a) l'ajout d'une déclaration a priori à même la racine polymorphique, (b) l'ajout d'une signature de méthode abstraite dès la racine polymorphique et, bien entendu, (c) l'ajout d'une implémentation de cette nouvelle méthode dans chaque classe du système. L'entretien du code d'un système de multiméthodes est relativement lourd.

#ifndef VOLUME_H
#define VOLUME_H
class Sphere;
class Boite;
struct Volume {
   virtual bool collision(const Volume&) const = 0;
   virtual bool collision(const Boite&) const = 0;
   virtual bool collision(const Sphere&) const = 0;
   virtual ~Volume() = default;
};
#endif

Classe Boite

Une Boite sera une sorte de Volume. Nous utiliserons un std::array pour entreposer les points qui en constitueront les coins.

Notez que l'implémentation proposée ici est banale et incomplète. Je vous invite à l'enrichir à la hauteur de vos souhaits. En particulier, ce que signifie « boîte par défaut » est éminemment politique, alors vous comprendrez que le choix fait ici soit discutable.

#ifndef BOITE_H
#define BOITE_H
#include "Volume.h"
#include "Point.h"
#include "AlgosCollision.h"
#include <algorithm>
#include <array>
class Sphere;
class Boite : public Volume {
   enum { NSOMMETS = 8 };
   static constexpr Point DEPLACEMENT{-0.5f, -0.5f, -0.5f };
   static constexpr std::array<Point,NSOMMETS> SOMMETS_DEFAUT {
      Point{ 0.0f, 0.0f, 0.0f } - DEPLACEMENT,
      Point{ 0.0f, 0.0f, 0.1f } - DEPLACEMENT,
      Point{ 0.0f, 0.1f, 0.0f } - DEPLACEMENT,
      Point{ 0.0f, 0.1f, 0.1f } - DEPLACEMENT,
      Point{ 0.1f, 0.0f, 0.0f } - DEPLACEMENT,
      Point{ 0.1f, 0.0f, 0.1f } - DEPLACEMENT,
      Point{ 0.1f, 0.1f, 0.0f } - DEPLACEMENT,
      Point{ 0.1f, 0.1f, 0.1f } - DEPLACEMENT
   };
   std::array<Point, NSOMMETS> sommets{ SOMMETS_DEFAUT };
public:
   using iterator = std::array<Point,NSOMMETS>::iterator;
   using const_iterator = std::array<Point,NSOMMETS>::const_iterator;
   iterator begin() noexcept {
      return sommets.begin();
   }
   iterator end() noexcept {
      return sommets.end();
   }
   const_iterator begin() const noexcept {
      return sommets.begin();
   }
   const_iterator end() const noexcept {
      return sommets.end();
   }
   Boite() = default;
   Boite(const std::array<Point, NSOMMETS> &sommets)
      : sommets{ sommets }
   {
   }
   bool collision(const Sphere &s) const {
      return Collision::evaluer(*this, s);
   };
   bool collision(const Boite &b) const {
      return Collision::evaluer(*this, b);
   }
   bool collision(const Volume &v) const {
      return v.collision(*this);
   }
   bool contient(const Point &p) const {
      return false; // insérer votre algo favori ici
   }
};
#endif

Classe Sphere

Une Sphere sera aussi un Volume somme toute banal. Ce qui est sympathique avec les sphères est, de toute manière, leur simplicité.

#ifndef SPHERE_H
#define SPHERE_H
#include "Volume.h"
#include "Point.h"
#include "AlgosCollision.h"
class Boite;
class Sphere : public Volume {
   Point centre_{};
   float rayon_{ 1.0f };
public:
   Sphere() = default;
   constexpr Sphere(const Point &centre, float rayon)
      : centre_{ centre }, rayon_{ rayon }
   {
   }
   constexpr Point centre() const {
      return centre_;
   }
   constexpr float rayon() const {
      return rayon_;
   }
   bool collision(const Sphere &s) const {
      return Collision::evaluer(*this, s);
   }
   bool collision(const Boite &b) const {
      return Collision::evaluer(*this, b);
   }
   bool collision(const Volume &v) const {
      return v.collision(*this);
   }
   bool contient(const Point &p) const {
      return distance(p, centre()) <= rayon();
   }
};
#endif

Bibliothèque d'algorithmes de collision

Nous utiliserons un dépôt d'algorithmes de détection de collisions pour les regrouper et réduire la répétition de code. On y trouvera $2^n$ déclarations pour $n$ types de volumes dont il faudra tenir compte. Il est toutefois possible de réduire le couplage entre fichiers en utilisant des déclarations a priori, comme nous le faisons ici.

Le recours à un dépôt d'algorithmes est un choix de design, pas une nécessité.

#ifndef ALGOS_COLLISION_H
#define ALGOS_COLLISION_H
class Sphere;
class Boite;
struct Collision {
   static bool evaluer(const Sphere&, const Sphere&);
   static bool evaluer(const Boite&,  const Boite&);
   static bool evaluer(const Boite&,  const Sphere&);
   static bool evaluer(const Sphere&, const Boite&);
};
#endif

Pour l'implémentation des algorithmes, on pourra toutefois réduire les cas possible en implémentant certaines définitions en termes d'autres définitions sur les mêmes types (ici, le test sur Boite et Sphere délègue au test sur Sphere et Boite).

Je ne prétends pas que les implémentations de tests de collision proposées ici soient efficaces (ou même correctes); en fait, elles le sont pour le cas d'une collision entre deux sphères, mais pour le reste, j'ai écrit un petit quelque chose rapidement et je n'ai rien validé, alors à vos risques et périls!

#include "AlgosCollision.h"
#include "Sphere.h"
#include "Boite.h"
#include <algorithm>
bool Collision::evaluer(const Sphere &s0, const Sphere &s1) {
   return distance(s0.centre(), s1.centre()) <= s0.rayon() + s1.rayon();
}
bool Collision::evaluer(const Boite&, const Boite&) {
   return false; // insérer votre algo ici
}
bool Collision::evaluer(const Boite& b, const Sphere &s) {
   return evaluer(s,b); // réduire la redondance
}
bool Collision::evaluer(const Sphere &s, const Boite &b) {
   using namespace std;
   return find_if(begin(b), end(b), [&](const Point &p) {
      return s.contient(p);
   }) != end(b) || b.contient(s.centre());
}

Programme de test

Enfin, un petit programme de test utilise un conteneur de quelques volumes et les teste pour découvrir des collisions. Rien de transcendant, soit, mais ça montre tout de même que l'ensemble fonctionnet et fait le travail.

#include "Sphere.h"
#include "Boite.h"
#include "Volume.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <memory>
int main() {
   using namespace std;
   vector<unique_ptr<Volume>> v{
      make_unique<Sphere>({Point{1.0f, 1.0, 2.0f}, 1.0f}),
      make_unique<Boite>(),
      make_unique<Sphere>(),
      make_unique<Sphere>(Point{10.0f, 10.0f, 10.0f}),
      make_unique<Sphere>()
   };
   using size_type = decltype(v.size());
   for (size_type i = 0; i < v.size() - 1; ++i)
      for (size_type j = i+1; j < v.size(); ++j)
         if (v[i]->collision(*v[j]))
            cout << "Collision entre le volume "
                 << i << " et le volume " << j << endl;
}

Revisiter (!) le problème avec std::variant

Le problème peut être significativement simplifié en utilisant des techniques et idiomes plus contemporains, en particulier le type std::variant de C++ 17. Pour une vision sommaire :

Pour que l'exemple demeure simple et se limite à la mécanique, supposons deux classes vides (purement symboliques) Sphere et Boite, et définissions Volume comme l'un de ces types (à l'aide de std::variant).

Détecter une collision entre deux volumes, plutôt que d'impliquer une découverte polymorphique de types de complexité linéaire en fonction du nombre de types impliqués, devient une multivisite du std::variant, ce qui mène à un appel (presque) direct de l'algorithme approprié.

On conviendra que le gain de simplicité est... appréciable.

#include <variant>
#include <iostream>
using namespace std;
class Sphere{};
class Boite{};
using Volume = variant<Sphere, Boite>;
bool collision(const Volume &v0, const Volume &v1) {
    struct Visiteur {
        bool operator()(const Boite&, const Boite&) const {
            cout << "Boite x Boite" << endl; return false;
        }
        bool operator()(const Boite&, const Sphere&) const {
            cout << "Boite x Sphere" << endl; return false;
        }
        bool operator()(const Sphere&, const Boite&) const {
            cout << "Sphere x Boite" << endl; return false;
        }
        bool operator()(const Sphere&, const Sphere&) const {
            cout << "Sphere x Sphere" << endl; return false;
        }
    };
    return visit(Visiteur{}, v0, v1);
}
int main() {
    collision(Boite{}, Sphere{});
}

Lectures complémentaires

Quelques liens pour enrichir le propos.

Série d'articles publiés sur le Code Project par Jean-Louis Leroy, en 2014 et en 2015, sur ce qu'il nomme des « multiméthodes ouvertes » :
En 2016, Eli Bendersky examine les multiméthodes dans une perspective polyglote :
En 2018, Andy G. recommande de cesser de réinventer la roue... et la vtbl, puis d'accepter le recours au Double Dispatch (entre autres pour implémenter le schéma de conception Visiteur sans recourir à de l'antipolymorphisme) : https://gieseanw.wordpress.com/2018/12/29/stop-reimplementing-the-virtual-table-and-start-using-double-dispatch/