Les automates à états finis (AEF)



  1. Définition et généralités


    Un automate fini est défini par la donnée d'un alphabet , d'un ensemble fini d'états , d'une relation de transition, sous-ensemble de , d'un état initial et d'un ensemble d'états finaux . Une transition , dite de l'état vers l'état et étiquetée par le symbole , est notée . Un calcul de cet automate est une suite de transitions ; ce calcul est réussi si le dernier état, , est un état final, et on dit alors que le mot est reconnu par l'automate fini.

    images et définition provenant du site http://cermics.enpc.fr/

  2. Application pratique



    Les automates sont très souvent utilisés dans les jeux vidéos car ils sont très simples à mettre en oeuvre et peuvent être plus ou moins élaborés (ex: plusieurs automates en parallèles, transitions stochastiques, aléatoires, etc...).
    Appliqués aux agents du moteur, un état est un état de l'agent ie un ensemble de valeurs de ces attributs et une transition est une condition pour passer d'un état à l'autre. Par exemple, un papillon peut passer de l'état "je vole" à l'état "je suis posé" si il rencontre une fleur (condition).

    On peut implémenter les AEF avec une classe état et une classe transition, cette dernière ayant deux liens vers deux classes état. Ce n'est pas comme ca que nous avons choisi d'implémenter nos AEF.

  3. Implémentation et outils


    Nous avons préféré utiliser des pointeurs de fonctions chaînées. En fait, il existe un pointeur de fonction (ie état) courant qui est sur "je vole" et qui, si "fleur à côté papillon" (ie transition), va prendre la valeur "je me pose". Il s'agit bien sur d'un pointeur de fonction membre en c++, puisqu'on ne manipule que les attributs de l'agent concerné. Cette implémentation a le mérite d'être très concise et efficace et de ne pas alourdir le diagramme objet par de multiples instances d'objet état et transition. On peut de plus changer très facilement l'état courant d'un agent depuis l'extérieur par exemple pour le mettre dans l'état sleep ou wake up (reprise après un sleep): il suffit d'appeler la méthode sleep ou wake_up de l'agent!
    Le moteur de jeu va ensuite appeler automatiquement la fonction d'action courante à chaque pas de temps...

    Voici l'exemple pratique d'un automate représentant un bouton d'interface, qui permet de fermer la fenêtre à laquelle il appartient:

    button_quit.cpp
    /**************************************************************************/
    /* Classe button_quit (.cpp) */
    /* */
    /* Date : 19 janvier 2003 */
    /* Projet: Moteur de jeu Auteur: Akhres Nader */
    /**************************************************************************/

    #include "button_quit.hxx"
    #include "container.hxx"

    void button_quit::on(void)
    {
    if (container_)
    {
    container_->sleep();
    container_->unset_visible();
    }
    action_courante_=(void (Actif::*) (void)) (& button_quit::off);
    }



    void button_quit::off(void)
    {
    if (input_ && input_->go_fire1() && input_->selected(this)) //on clique sur l'objet? alors on le bouge
     {
    action_courante_=(void (Actif::*) (void)) (& button_quit::on);
    }
    }



    button_quit.hxx
    /**************************************************************************/
    /* Classe button_quit (.hxx) */
    /* */
    /* Date : 19 janvier 2003 */
    /* Projet: RPG Auteur: Akhres Nader */
    /**************************************************************************/

    #ifndef __BUTTON_QUIT_HXX__
    #define __BUTTON_QUIT_HXX__

    #include "InputMOUSESDL.hxx"
    #include "Actif.hxx"
    #include "Sprite_a.hxx"
    #include "List_dat.hxx"
    #include "Tile_Map.hxx"
    #include "PlayerCharacter.hxx"
    #include "TypeRPG.hxx"
    #include "objet.hxx"

    class container;

    class button_quit : public objet

    {
    protected :

    InputMOUSESDL * input_;

    public :

    //fonctions d'action
    void off(void);
    void on(void);


    public : button_quit(int xworld,int yworld,int nb_step_entre_chq_action,Liste_anim_data* liste_anim_data,int place) : objet(xworld,yworld,nb_step_entre_chq_action,liste_anim_data,place)
    {
    action_courante_=(void (Actif::*) (void)) (& button_quit::off); //par défaut le bouton n'est pas enclenché
    input_ = NULL;
    };

    ~button_quit() { }

    virtual bool est_manipulable()
    {
    return false;
    };


    void set_input(InputMOUSESDL * in)
    {
    input_ = in;
    }


    };


    #endif


    Il devient vite assez pénible d'écrire ces automates, d'autant plus quand ces derniers deviennent complexes (cf exemple du rpg). C'est pourquoi nous avons crée un outil graphique d'édition d'automates, appelé aeditor. Il génère alors automatiquement le .hxx et le .cpp et il n'y a plus qu'à compiler...