Cet article repose en grande partie sur les techniques exposées dans l'article Pousser plus à fond la métaprogrammation, plus haut. Pour l'idée d'utiliser types en tant que booléens, une idée pourtant toute simple, je me suis inspiré des débats entourant l'élaboration du standard C++ 11 et des idées des développeurs de la bibliothèque Boost (voir cet article pour une étude en français sur le sujet). Les références au monde du jeu tiennent du fait que j'ai écrit cet article en bonne partie pour des cours données dans le cadre du Diplôme de développement du jeu vidéo offert au Centre de formation en technologies de l'information (CeFTI) de l'Université de Sherbrooke.
Les systèmes informatiques comprenant une part d'intelligence artificielle, comme le sont pratiquement toujours les jeux vidéo, comprennent souvent un moteur d'évaluation de règles.
Les règles peuvent être divisées en diverses catégories. Parmi les découpages possibles, un nous intéressera tout particulièrement ici : un découpage entre règles reposant sur un savoir statique et règles reposant sur un savoir dynamique.
Par savoir statique, nous entendrons ici toute considération appelée à changer d'une compilation à l'autre mais pas nécessairement en cours d'exécution. Tout ce qui peut être connu à la compilation : valeur de certaines constantes, particularités de certaines plateformes de développement, dimensions de certaines surfaces de jeu, proportion de mémoire ou de temps processeur allouée pour certains modules, etc.
Dans un système complexe, une part importante de données repose habituellement sur du savoir statique, et il est fréquent de voir l'évaluation de plusieurs expressions constantes faite à l'exécution plutôt qu'à la compilation parce que le programme ne présume pas de la stabilité de certaines conditions pour chaque compilation.
Par exemple, pensez à un script qui doit être invoqué seulement si la surface d'un jeu est plus grande ou égale qu'un certain seuil. Si les dimensions de la surface sont des constantes, elles peuvent changer d'un jeu à l'autre (ou d'une carte à l'autre dans un même jeu, si certaines macros sont appliquées) mais le script voudra quand même évaluer la condition déterminant s'il doit être activé ou non.
Par savoir dynamique, nous entendrons ici toute considération reposant sur au moins un élément variable dans le jeu. Comparer une variable avec une constante (comme par exemple vérifier si le niveau de vie restant d'un personnage est supérieur à zéro) exige une évaluation de savoir dynamique puisque le niveau de vie du personnage est une variable.
Dans un jeu, les règles sont pratiquement toujours exprimées en termes de savoir dynamique et le savoir statique est habituellement codé à la main. Pourtant, il est possible d'exprimer de manière homogène les règles reposant sur un savoir statique et celles reposant sur un savoir dynamique, à l'aide de diverses techniques de POO et de programmation générique.
L'approche proposée dans cet article est peu répandue[1], alors il se peut que vous soyez résistant(e)s de prime abord à y avoir recours. Quels en sont les avantages? Difficile de faire une liste exhaustive, la technique étant peu connue, mais en voici quelques-uns :
La plupart des programmeuses et des programmeurs souhaitent écrire des programmes à la fois élégants, compacts et rapides à l'exécution. Lorsque certaines conditions peuvent être évaluées a priori, le temps processeur récupéré peut être investi à d'autres fins.
Les bénéfices de l'approche que propose cet article seront plus importants si le code d'un système est exprimé de manière à en tirer profit. Si une entreprise ne réfléchit pas aux décisions prises sur la base d'éléments statiques dans le code, alors l'essentiel de ce qui suit restera une simple implémentation d'un système polymorphique d'évaluation de règles comme il en existe plusieurs autres sur le marché.
Le modèle proposé ici est de définir une interface Evaluateur (un autre nom intéressant aurait été Evaluable). Comme toute entité abstraite, elle exposera un service polymorphique (la méthode booléenne Evaluer(), qui sera sa raison d'être) et un destructeur virtuel.
Deux dérivés de l'interface Evaluateur nous intéresseront :
La méthode Evaluer() de Evaluateur sera implémentée différemment selon le type d'enfant. Pour un EvaluateurStatique, la méthode Evaluer() sera implémentée par une évaluation statique (à la compilation) du fait, ce qui signifie que, concrètement, la méthode retournera une valeur constante. Pour un EvaluateurDynamique, la méthode Evaluer() sera implémentée par une délégation de l'invocation vers le prédicat, d'une manière facile à optimiser pour le compilateur.
Nous utiliserons des règles, statiques ou dynamiques, qui ne demandent pas de paramètres lors de l'évaluation. Dans le cas d'une règle statique, cela va de soi; pour les règles dynamiques, l'injection de paramètres particuliers, s'il y a lieu, se fera à la construction du prédicat qui, dans ce cas, sera un foncteur.
Utiliser un parent commun pour les deux familles de règles permettra de les regrouper de manière opérationnelle dans un conteneur. Utiliser une approche générique pour les enfants aura de son côté la qualité de simplifier (à coût zéro) l'expression de règles pouvant être intégrées à notre petit moteur.
Notez que le passage par la méthode Evaluer() d'un Evaluateur entraînera le coût d'un appel polymorphique, mais que cet appel était probablement déjà en place dans la plupart des systèmes informatiques qui pourraient bénéficier de la technique proposée ici.
L'autre coût de cette technique est le recours à des indirections, typique des systèmes polymorphiques. Encore une fois, ce n'est probablement pas un coût supplémentaire dans les systèmes à base de règles puisque ceux-ci fonctionnent selon toute probabilité déjà sur ce mode.
Examinons maintenant le détail de la technique. Une partie du code suivant sera simple et une autre partie pourra vous sembler étrange. En particulier, vous trouverez très peu de code traditionnel dans ce qui suit : un petit nombre de classes, mais un grand nombre de types.
#ifndef EVALUATEUR_H
#define EVALUATEUR_H
struct Evaluateur
{
virtual bool Evaluer() = 0;
virtual ~Evaluateur() = default;
};
#endifL'interface Evaluateur sera telle que décrite plus haut : une classe strictement abstraite exposant un destructeur virtuel (comme il se doit) et une méthode booléenne abstraite nommée Evaluer().
Clairement, Evaluateur sera une racine polymorphique dont nous dériverons les véritables règles. Elle nous servira à la fois de parent commun et d'abstraction opératoire.
#ifndef EVALUATEURDYNAMIQUE_H
#define EVALUATEURDYNAMIQUE_H
#include "Evaluateur.h"
template <class Pred>
class EvaluateurDynamique
: public Evaluateur
{
Pred pred_;
public:
EvaluateurDynamique(Pred pred)
: pred_{pred}
{
}
bool Evaluer()
{ return pred_(); }
};
template <class Pred>
Evaluateur *CreerEvaluateurDynamique(Pred pred)
{
return new EvaluateurDynamique<Pred>{pred};
}
#endifLa classe EvaluateurDynamique sera l'implémentation plus traditionnelle d'une règle.
Tel qu'indiqué précédemment, cette classe encapsulera un prédicat nullaire (sans paramètres) quelconque, qu'il s'agisse d'un foncteur ou d'une fonction, et sa méthode Evaluer() jouera le rôle d'un relais pour fins de délégation vers ce prédicat.
Nous accompagnerons la classe générique EvaluateurDynamique d'une fonction de fabrication pour permettre son instanciation sans avoir à insister sur les types impliqués, lorsque cela s'avère possible (elle déduira le type du prédicat du type de son paramètre). Cela permettra, sans coût à l'exécution, d'alléger l'écriture du code client.
#ifndef EVALUATEURSTATIQUE_H
#define EVALUATEURSTATIQUE_H
#include "Evaluateur.h"
#include "ReglesStatiques.h"
template <class Fait>
struct EvaluateurStatique
: Evaluateur
{
bool Evaluer()
{ return static_eval<Fait>::value; }
};
template <class Fait>
Evaluateur *CreerEvaluateurStatique()
{
return new EvaluateurStatique<Fait>;
}
#endifUne instance de EvaluateurStatique évaluera, à coût zéro (une fois l'invocation polymorphique de Evaluer() réalisée) lors de l'exécution d'un programme, un fait.
évidemment, qui dit fait dit information connue (ou, du moins, disponible) au préalable, mais notez que ce qui est connu du compilateur peut ne pas l'être des programmeuses et des programmeurs. Toute l'idée des constantes symboliques est incluse dans ce constat : l'humain aime comprendre les choses en termes symboliques, mais le compilateur, lorsqu'il génère le code en tant que tel, connaît les valeurs derrière les symboles (lorsque ces symboles ont une valeur statique, bien entendu).
La clé du mécanisme ici est de représenter les faits par des types. Ici, le type générique Fait sera évalué à la compilation (expression static_eval<Fait>::value) ce qui produira une constante dans le programme, constante connue du programme sans nécessairement être connue des programmeuses et des programmeurs.
Pour nous assister dans notre travail, nous aurons recours à certains outils statiques offerts à même la bibliothèque <type_traits>, soit :
Le fonctionnement de ces outils est expliqué dans l'article Pousser plus à fond la métaprogrammation si vous êtes curieuse ou curieux d'en savoir plus.
// divers types et algorithmes statiques (voir cet article)
//
// Macros utilitaires pour alléger le code
//
#define LISTE_TYPES_1(T0) \
liste_types< T0, Vide >
#define LISTE_TYPES_2(T0,T1) \
liste_types< T0, LISTE_TYPES_1(T1) >
#define LISTE_TYPES_3(T0,T1,T2) \
liste_types< T0, LISTE_TYPES_2(T1, T2) >
#define LISTE_TYPES_4(T0,T1,T2,T3) \
liste_types< T0, LISTE_TYPES_3(T1, T2, T3) >
// etc.Les fabuleuses listes de types d'Alexandrescu ont été présentées dans l'article Pousser plus à fond la métaprogrammation et nous ne les répéterons pas ici.
Pour justifier leur présence ici, notons que, si un fait est représenté par un type, alors une liste de types peut représenter une liste de faits, donc une règle statique complexe.
Notez aussi que des macros (inspirées de l'oeuvre d'Alexandrescu) seront insérées dans le fichier liste_types.h pour faciliter la construction de listes de types de longueur arbitraire. Cela allégera nettement l'écriture du code client.
|
Le noeud du volet plutôt novateur de notre démarche, sans surprises, sera le fichier ReglesStatiques.h. Voyons un peu ce dont il en retourne. La clé algorithmique de la démarche sera l'algorithme statique static_eval, qui définira une constante booléenne value en fonction d'un type donné. |
|
|
Les cas des types true_type et false_type sont les plus simples à gérer : true_type exprime une tautologie alors que false_type exprime une contradiction. Pour des algorithmes statiques, fortement récursifs, le recours à des points d'arrêt clairs et simples est souhaitable. |
|
|
Pour examiner la valeur logique d'une liste de faits, il nous faut une règle. La norme semble être, en pratique, de faire en sorte qu'une liste de faits soit vraie si au moins une de ses règles est vraie (sinon, les règles peuvent être combinées par des connecteurs logiques statiques, tels que ceux proposés plus haut). Nous procéderons donc en trois temps, donc en trouvant le type de la première expression statique vraie, en évaluant la liste sur cette base, et en exprimant static_eval pour en tirer profit :
|
|
|
évaluer une liste de faits représentés par des types signifiera trouver la valeur du premier type exprimant de manière statique l'idée de vrai. |
|
|
Enfin, évaluer une liste se fera par délégation, comme nous le faisions plus haut pour évaluer une conjonction, une disjonction ou une négation logique. |
|
|
Enfin, pour alléger le code, une macro sera offerte pour faciliter le passage d'une expression booléenne statique aux types représentant une tautologie ou une contradiction. |
|
Pour illustrer (et clarifier) cette approche, voici un petit programme de démonstration, montrant comment il est possible de créer un EvaluateurStatique, comment il est possible de créer un EvaluateurDynamique et comment il est possible de placer les deux dans un même conteneur pour les invoquer à loisir.
Dans les deux cas, les conditions évaluées ici sont banales. Pour mettre plus clairement en relief l'utilité de la technique, il faudrait utiliser un prédicat consultant de véritables états dynamiques de jeu et un fait basé sur des constantes d'un jeu donné. Une utilité propre à cette technique serait de générer des évaluateurs statiques ou des évaluateurs dynamiques à partir d'un langage de script en fonction de la nature des conditions évaluées, pour avoir droit à la souplesse des scripts et à la vitesse (à l'instantanéité!) de l'inférence statique de faits. Un tel exemple serait trop massif pour être intégré à des notes de cours.
|
Vous pouvez toutefois examiner quelques programmes plus massifs des notes de cours et utilisant de l'information statique comme des traits pour explorer l'utilisation d'évaluateurs statiques dans un contexte un peu plus riche. Tout d'abord, pour les fins du programme de démonstration, nous inclurons quelques en-têtes habituels, de même que les en-têtes que nous venons de mettre en place. |
|
|
Pour créer un EvaluateurStatique, il nous faut des faits, et il faut que ces faits puissent être exprimés sous la forme de types. Heureusement, nous avons déjà défini comment passer statiquement d'un booléen à un type (et inversement). Il ne nous faut donc plus qu'une série de faits booléens, représentés par une liste de types (nommée ici liste_faits) construite à partir d'une série de faits booléens statiques, chacun basé sur des constantes du système (ici, des constantes symboliques bidons). L'évaluateur est fabriqué sur la base de la liste de faits, obtenant ainsi un savoir constant et connu à la compilation, mais est invoqué de manière polymorphique. Notez que, dans le code d'affichage, l'écriture de deux littéraux const char* consécutifs est une demande au compilateur de les concaténer à la compilation. C'est donc tout à fait légal. |
|
|
Pour l'évaluateur dynamique, nous utiliserons un simple foncteur local (EstNegatif) qui indiquera si un entier connu à la compilation est négatif ou non. En pratique, il est plus probable que l'on utilise des objets qui examinent des données de manière indirecte (à l'aide de références ou de pointeurs, par exemple). La fabrication de l'évaluateur est une fonction capable de déduire le type du prédicat de celui de son paramètre. Remarquez qu'une fois instancié, un EvaluateurDynamique est traité comme un Evaluateur de la même manière que l'est sa contrepartie statique. Le coût de l'invocation polymorphique est fixe; la différence entre les deux est le travail à faire pour évaluer la condition. |
|
|
Enfin, le nettoyage des évaluateurs instanciés dynamiquement est banal. |
|
[1] En fait, je doute qu'elle soit mise en application présentement. Pourtant, les avantages sont indéniables. L'idée des techniques de cette section m'est venue en lisant le chapitre sur les systèmes à base de règles du livre Artificial Intelligence for Games de Ian Millington (ISBN : 0124977820). Je doute que même lui ait envisagé une telle approche, à cause de son étrangeté. À vous de juger.
[2] Notez évidemment qu'un script reposant sur un savoir statique devra la plupart du temps être compilé et intégré au système. Pour des modifications applicables alors que le système informatique s'exécute, il faudra avoir recours à des règles reposant sur un savoir dynamique – à moins bien entendu qu'il existe a priori une banque suffisante d'objets d'évaluation de savoir statique préalablement construits.
