09 avr. 2008

Exploration de XNA : Les machines à états

Dans un billet précédent, je faisais référence à la gestion d’états dans le cadre du développement d’un jeu vidéo. Une machine à états a des avantages intéressants dès lors qu’il s’agit de contrôler le flux des actions de l’utilisateur du jeu et de le séquencer en écrans multiples.

Avant d’aller plus loin dans cette analyse, ile nous faut définir ce qu’est une machine à état et à quoi elle peut bien servir.

Note: cet article, bien que basé sur des notions XNA, présente un concept qu'il est possible d'adapter à tous les autres langages (C++, Java, etc). NE vous sentez pas limités par le titre du billet ou par les paramètres des méthodes décrites.

Logo XNA [Télécharger Visual C# 2005 Express Edition] [Télécharger XNA Game Studio 2.0] [Télécharger le Service Pack 1 pour VC# 2005 EE] [TorqueX, de GarageGames.com] [XNA Resources] [Forum MSDN XNA Game Studio] [GameDev.Net - Plenty of 1s and 0s]



Définition

Comme le définit Wikipedia, une "machine à états" (state machine) ou "machine finie à états" (finite state machine) est un model de comportement composé d’un nombre fini d’états, de transitions entre ces états, et d’actions : on quitte un état particulier en effectuant une action qui va valider une transition. Un exemple vaut mieux qu’un long discours :

machine à état

Comme vous pouvez le voir, on représente une machine à état par un graphe orienté étiqueté (les arcs étiquetés sont les transitions). D’un point de vue informatique, la transition est en fait une condition booléenne qui, une fois vérifiée, permet de passer d’un état Ep à un état Eq.

Dans la théorie des graphes, il existe une autre entité qui utilise la même représentation : l’automate fini ou finite state automaton. Il y a une bonne raison à ça : les deux termes renvoient à la même chose.

C’est bien beau la théorie, mais…

Encore faut-il qu’une telle modélisation soit une abstraction correcte du modèle que l’on souhaite implémenter. Histoire de montrer la puissance de cet outil théorique, prenons un exemple.

Dans un jeu vidéo, on peut définir des séquences d’écran. Ces séquences d’écran sont généralement définies comme suit :

  • dans l’écran Menu Général
    • lorsque je sélectionne "Configuration" et que je valide avec le bouton "X" du gamepad, j’affiche l’écran Configuration
    • lorsque je sélectionne "Jouer" et que je valide avec le bouton "X" du gamepad, j’affiche l’écran Jeu
  • dans l’écran Configuration
    • lorsque je sélectionne "Retour" et que je valide avec le bouton "X" du gamepad, je retourne à l’écran Menu Général
    • lorsque je sélectionne "Jouer" et que je valide avec le bouton "X" du gamepad, j’affiche l’écran Jeu
  • dans l’écran Jeu
    • lorsque j’appuie sur le bouton "Back" du gamepad, je retourne à l’écran précédent (Menu Général ou Configuration)

Une telle description rend le principe évident : on voit aisément quels sont les états (écran Menu Général, Configuration ou Jeu affiché) et les transitions (validation de "Configuration", "Jeu" ou appui sur le bouton "Back"). Puisque la gestion complète des différents écrans du jeu est du même acabit, on peut en déduire que la représentation sous la forme d’un automate fini est pertinente.

On peut même caractériser cet automate plus précisément : dans certains cas particuliers (symbolisé dans l’exemple précédent par la gestion du bouton "back" dans l’écran Jeu), la même action peut avoir des conséquences différentes. Le graphe qu’on obtient est donc :

menu de jeu vidéo simple

Le fait d’avoir deux sorties sur l’état Jeu avec la même transition "Back" montre qu’on a affaire à un automate fini non déterministe. For heureusement, on peut le transformer en automate fini déterministe de manière très simple - soit en augmentant la transition d’une condition supplémentaire, soit en séparant l’état Jeu en deux états Jeu après Menu et Jeu après Configuration. Le fait de choisir l’un ou l’autre est bien souvent une affaire de complexité de code (si le nombre de combinaisons est important, il peut être judicieux de créer plusieurs états).

Et ça se transforme comment en code ?

Si vous lisez quelques articles sur les automates finis, vous vous apercevrez vite qu'ils parlent généralement d'analyse lexicale et qu'ils préconisent une gestion de l'automate via plusieurs tables, construites avec des règles complexes (notamment liés aux transformations entre automates finis déterministes et automates finis non déterministe). Cette représentation est probablement la meilleure dès lors que le nombre d'états à gérer est très important (plusieurs dizaines) et que le traitement attaché à un état quelconque est similaire ou identique à celui attaché aux autres états possibles. Dans un analyseur lexical, seul compte le passage d'un état à l'autre, ainsi que l'état de début et l'état final (il n'y a pas de traitement particulier attaché à un état).

Cependant, nous ne sommes pas du tout dans ce cas. Ce qui nous intéresse, c'est de pouvoir implémenter des états complexes et des transitions qui ne le sont pas moins. Une gestion externe des états et des transitions est donc de fait très mal adaptée. Une telle architecture ne respecte d'ailleurs pas le principe OCP ni le principe d'encapsulation. On préférera donc une architecture orientée objet et plus adaptée au besoin.

Cela signifie bien évidemment que nous allons représenter nos états par des objets. Diverses représentations existent (si vous surfez sur les forums dédiés à la programmation de jeux vidéo, vous avez peut être entendu parler de celle très orientée intelligence artificielle présentée par le site ai-junkie), mais peu adressent en fait notre problème exact. Le diagramme de classe UML ci-dessous montre deux classes - State et StateMachine. La seconde est une classe finale, la première peut être spécialisée de manière à implémenter les traitements spécifiques liés à un état particulier.

diagramme de classe StateMachine

Avant de donner un exemple concret, une petite visite guidée s'impose.

Premièrement, l'algorithme de gestion des états est simple : il est intégralement contenu dans les méthodes StateMachine.Update() et StateMachine.Draw(). StateMachine.Update() appelle CurrentState.BaseUpdate(). StateMachine.Draw() est un peu plus complexe puisque les opérations suivantes sont effectuées :

  • appel de CurrentState.Draw()
  • récupération de nextState = CurrentState.NextState
  • si nextState est différent de CurrentState
    • appel de CurrentState.Leave()
    • appel de nextState.Enter()
    • CurrentState = nextState

Le reste se passe dans CurrentState.BaseUpdate(), qui effectue les opérations suivantes :

  • appel de this.Update()
  • this.NextState = this
  • pour chaque transition T
    • si T est vrai, alors this.NextState est l'état associé à la transition et on arrête la boucle.

Ou, avec une présentation moins technique : après la mise à jour de l'état, on vérifie si l'une des transitions est passée. Dans ce cas, on considère que l'état suivant à exécuter est l'état qui est associé à la transition passée.

Puisque CurrentState.BaseUpdate() est appelée avant StateMachine.Draw(), on s'assure que CurrentState.NextState est toujours correct.

Il nous reste un problème (quelque peu ardu) à régler : la gestion des transitions. Le modèle décrit ci-dessus est relativement peu explicite. Tout au plus, il annonce qu'une transition a une méthode de vérification et qu'on associe des transitions et des états dans un objet Map<Transition,State> instancié dans la classe State.

Il y a deux école ici : soit on décide de gérer les transitions en interne dans les classes filles de State - auquel cas, il n'est pas besoin d'une map ni de transitions explicites. C'est notamment l'approche que j'avais retenu (pour des raisons de simplicité) dans le code du petit Tic-Tac-Toe (TTT) que j'avais réalisé (en C++ / OpenGL) pour un "concours" il y a quelques années[1] et que vous pouvez trouver ici. Dans cette architecture, chaque état connait le type statique des états qui lui sont liés (voir le constructeur de la classe ttt::MainGameState) et les transitions sont testées en direct dans le code de mise à jour de l'état (voir ttt::MainGameState::UpdateV(), qui mets à jour la variable mSelected).

Pour gérer un petit nombre d'états, cette vision peut être suffisante - mais dès lors que les liens entre les différents états deviennent complexes, il est nécessaire d'avoir une vision plus large et plus générique. C'est ce que j'ai tenté de faire dans le modèle par le diagramme de classe décrit ci-dessus.

Dans ce nouveau modèle, les deux options coexiste. Il est encore possible d'utiliser une vision proche de celle utilisée dans le petit TTT en laissant le constructeur des classes dérivées de State gérer l'initialisation de la map State.Links. Pour ce faire, on créer les autres états et on crée les instances de Transition en spécifiant le delegate qui effectue le test. Il est aussi possible de créer la liste des états et des transitions a l'extérieur des classes d'état, ce qui permet de découpler les états les uns des autres et offre au final une plus grande liberté dans le chainage des états.

Le fait est que les transitions ont souvent besoin de tester l'état du State en cours d'exécution. C'est la raison pour laquelle j'ai spécifié une classe DelegateTransition qui est une Transition batie sur une méthode déléguée. On peut ainsi l'initialiser avec une méthode d'une classe d'état ou une fonction lambda anonyme si besoin.

Et pour finir, un exemple...

Reprenons notre exemple ci-dessus : nous avons à gérer 3 états et leurs transitions associées. Les états sont représentés par des classes StateMainMenu, StateConfiguration et StateGame. Ces classes définissent des méthodes qui seront utilisées pendant la vérification des changements d'états.

classes de notre machine à états

La construction globale de notre automate ressemble à celle-ci :

private void ConstructAutomaton()
{
   StateMainMenu menu = new StateMainMenu();
   StateConfiguration config = new StateConfiguration();
   StateGame game = new StateGame();
DelegateTransition menuToConfig = new DelegateTransition(); menuToConfig.ValidationMethod += menu.CheckForConfiguration;
DelegateTransition menuToGame = new DelegateTransition(); menuToGame.ValidationMethod += menu.CheckForGame;
DelegateTransition configToMenu = new DelegateTransition(); configToMenu.ValidationMethod += config.CheckForReturn;
DelegateTransition configToGame = new DelegateTransition(); configToGame.ValidationMethod += config.CheckForGame;
DelegateTransition gameToMenu = new DelegateTransition(); gameToMenu.ValidationMethod += config.CheckForMainMenu;
DelegateTransition gameToConfig = new DelegateTransition(); gameToConfig.ValidationMethod += config.CheckForConfiguration;
menu.Links.Add(config, menuToConfig); menu.Links.Add(game, menuToGame); config.Links.Add(menu, configToMenu); config.Links.Add(game, configToGame); game.Links.Add(config, gameToConfig); game.Links.Add(menu, gameToMenu);
theStateMachine.CurrentState = menu; }

Conclusion

Nous présentons ici un modèle de gestion d'application très adapté à la gestion du flux global d'un jeux vidéo. Même si nous le présentons dans le contexte d'une série d'articles basés sur XNA, le modèle n'en est pas moins aisément modifiable pour être supporté par d'autres langages et d'autres framework. Enfin, nous quittons maintenant ce ton ronflant, très adapté aux conclusions de publications scientifique mais étonnament déplacé ici.

A bientôt !

Notes

[1] en fait, l'idée était partie d'un petit groupe d'utilisateurs de GameDev.Net qui avaient créé un forum spécifique. Afin de marquer le coup, ils avaient organisé un petit concours de programmation sur le sujet "réalisez un jeu de morpion". J'ai à l'époque profité d'un peu de temps pour me joindre à eux.

Commentaires

1. Le jeudi, mai 5 2011, 15:44 par xavraz

Bonjour,
Est-ce que le projet Tic-Tac-Toe (TTT) est toujours disponible sur le blog car il semble que le lien ne soit plus valide.
Est-ce qu'il serait possible de le réactiver.

Merci d'avance.

2. Le vendredi, mai 6 2011, 09:37 par Emmanuel Deloget

Hello,

Le plugin dlm étant supprimé, effectivement, le lien est à l'ouest.

Je vais voir ça, et si besoin, le remettre en ligne.

3. Le vendredi, mai 6 2011, 09:50 par xavraz

Merci d'avance !

Ajouter un commentaire

Les commentaires peuvent être formatés en utilisant une syntaxe wiki simplifiée.

Fil des commentaires de ce billet