Share
Une machine à états finis est un modèle utilisé pour représenter et contrôler le flux d'exécution. Il est parfait pour implémenter l'intelligence artificielle dans les jeux, produisant d'excellents résultats sans code complexe. Ce tutoriel décrit la théorie, la mise en œuvre et l'utilisation de machines à états finis simples et basées sur des piles..
Toutes les icônes créées par Lorc et disponibles sur http://game-icons.net.
Remarque: Bien que ce tutoriel ait été écrit avec AS3 et Flash, vous devriez pouvoir utiliser les mêmes techniques et concepts dans presque tous les environnements de développement de jeux..
Une machine à états finis, ou FSM, est un modèle de calcul basé sur une machine hypothétique constituée d'un ou de plusieurs états. Un seul état peut être actif en même temps, donc la machine doit passer d'un état à un autre pour effectuer différentes actions.
Les FSM sont couramment utilisés pour organiser et représenter un flux d'exécution, ce qui est utile pour implémenter l'IA dans les jeux. Le "cerveau" d'un ennemi, par exemple, peut être implémenté à l'aide d'un FSM: chaque état représente une action, telle que attaque ou éluder:
FSM représentant le cerveau d'un ennemi.Un FSM peut être représenté par un graphique, où les nœuds sont les états et les arêtes sont les transitions. Chaque bord a une étiquette informant quand la transition doit avoir lieu, comme le le joueur est proche étiquette dans la figure ci-dessus, qui indique que la machine passera de errer à attaque si le joueur est proche.
La mise en œuvre d'un FSM commence par les états et les transitions qu'il aura. Imaginez le FSM suivant, représentant le cerveau d’une fourmi portant des feuilles:
FSM représentant le cerveau d'une fourmi.Le point de départ est le trouver une feuille qui restera actif jusqu’à ce que la fourmi trouve la feuille. Lorsque cela se produit, l'état actuel est transféré à rentrer chez soi, qui reste actif jusqu'à ce que la fourmi rentre à la maison. Quand la fourmi arrive enfin à la maison, l'état actif devient trouver une feuille encore, alors la fourmi répète son voyage.
Si l'état actif est trouver une feuille et le curseur de la souris s'approche de la fourmi, il y a une transition vers la fuyez Etat. Tant que cet état est actif, la fourmi s'éloignera du curseur de la souris. Lorsque le curseur n'est plus une menace, il y a une transition vers la trouver une feuille Etat.
Puisqu'il y a des transitions reliant trouver une feuille et fuyez, la fourmi sera toujours fuir le curseur de la souris quand il approche tant que la fourmi trouve la feuille. Cette ne sera pas arriver si l'état actif est rentrer chez soi (consultez la figure ci-dessous). Dans ce cas, la fourmi rentrera chez elle sans crainte, ne faisant que passer au trouver une feuille l'état quand il arrive à la maison.
FSM représentant le cerveau d'une fourmi. Notez le manque de transition entre 
Accentsconagua
fuyez et rentrer chez soi. Un FSM peut être implémenté et encapsulé dans une classe unique, nommée FSM par exemple. L’idée est d’implémenter chaque état en tant que fonction ou méthode, en utilisant une propriété appelée état actif dans la classe pour déterminer quel état est actif:
Classe publique FSM private var activeState: Function; // pointe sur la fonction d'état actuellement active fonction publique FSM () fonction publique setState (état: Fonction): void actifState = état; public function update (): void if (activeState! = null) activeState ();
Puisque chaque état est une fonction, lorsqu'un état spécifique est actif, la fonction représentant cet état sera appelée à chaque mise à jour du jeu. le état actif La propriété est un pointeur sur une fonction, elle pointe donc sur la fonction de l'état actif..
le mettre à jour() méthode du FSM La classe doit être invoquée à chaque cadre de jeu pour pouvoir appeler la fonction indiquée par le état actif propriété. Cet appel mettra à jour les actions de l'état actuellement actif.
le setState () méthode va faire passer le FSM à un nouvel état en pointant le état actif propriété à une nouvelle fonction d'état. La fonction d'état ne doit pas nécessairement être membre de FSM; il peut appartenir à une autre classe, ce qui rend le FSM classe plus générique et réutilisable.
En utilisant le FSM classe déjà décrite, il est temps de mettre en œuvre le "cerveau" d'un personnage. La fourmi précédemment expliquée sera utilisée et contrôlée par un FSM. Ce qui suit est une représentation des états et des transitions, en se concentrant sur le code:
FSM de fourmis cerveau en mettant l'accent sur le code.La fourmi est représentée par le Fourmi classe, qui a une propriété nommée cerveau et une méthode pour chaque état. le cerveau la propriété est une instance du FSM classe:
classe publique Ant public var position: Vector3D; vitesse de propagation publique: Vector3D; cerveau public: FSM; fonction publique Ant (posX: Number, posY: Number) position = new Vector3D (posX, posY); vélocité = nouveau Vector3D (-1, -1); cerveau = nouveau FSM (); // Dites au cerveau de commencer à chercher la feuille. brain.setState (findLeaf); / ** * L'état "findLeaf". * Il fait avancer la fourmi vers la feuille. * / public function findLeaf (): void / ** * L'état "goHome". * Elle fait bouger la fourmi vers son domicile. * / public function goHome (): void / ** * Etat "runAway". * Cela fait fuir la fourmi du curseur de la souris. * / public function runAway (): void fonction publique update (): void // Met à jour le FSM contrôlant le "cerveau". Il invoquera la // fonction d'état actuellement active: findLeaf (), goHome () ou runAway (). brain.update (); // Applique le vecteur vitesse à la position en faisant bouger la fourmi. moveBasedOnVelocity (); (…)
le Fourmi la classe a aussi un rapidité et un position propriété, tous deux utilisés pour calculer le mouvement à l'aide de l'intégration d'Euler. le mettre à jour() Cette méthode est appelée chaque cadre de jeu, elle va donc mettre à jour le FSM..
Pour que les choses restent simples, le code utilisé pour déplacer la fourmi, tel que moveBasedOnVelocity (), sera omis. Vous trouverez plus d'informations à ce sujet dans la série Comprendre les comportements de pilotage.
Ci-dessous, la mise en œuvre de chaque état, en commençant par findLeaf (), l'état responsable de guider la fourmi à la position de la feuille:
fonction publique findLeaf (): void // Déplace la fourmi vers la feuille. vélocité = nouveau Vector3D (Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance (Game.instance.leaf, this) <= 10) // The ant is extremelly close to the leaf, it's time // to go home. brain.setState(goHome); if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) // Mouse cursor is threatening us. Let's run away! // It will make the brain start calling runAway() from // now on. brain.setState(runAway);
le rentrer chez soi() état, utilisé pour guider la maison de la fourmi:
fonction publique goHome (): void // Déplace la fourmi vers la vitesse de retour = new Vector3D (Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance (Game.instance.home, this) <= 10) // The ant is home, let's find the leaf again. brain.setState(findLeaf);
Finalement, le fuyez() state, utilisé pour faire fuir la fourmi par le curseur de la souris:
fonction publique runAway (): void // Éloigne la fourmi de la souris curseur velocity = new Vector3D (position.x - Game.mouse.x, position.y - Game.mouse.y); // Le curseur de la souris est-il toujours proche? if (distance (Game.mouse, this)> MOUSE_THREAT_RADIUS) // Non, le curseur de la souris est parti. Revenons à la recherche de la feuille. brain.setState (findLeaf);
Le résultat est une fourmi contrôlée par un "cerveau" FSM:
Fourmi contrôlée par un FSM. Déplacez le curseur de la souris pour menacer la fourmi.Imaginez que la fourmi ait également besoin de fuir le curseur de la souris lorsqu'elle rentre chez elle. Le FSM peut être mis à jour comme suit:
Ant FSM mis à jour avec de nouvelles transitions.Cela semble une modification anodine, l’ajout d’une nouvelle transition, mais cela crée un problème: si l’état actuel est fuyez et le curseur de la souris n'est plus proche, dans quel état la fourmi doit-elle passer à: rentrer chez soi ou trouver une feuille?
La solution à ce problème est un FSM sur pile. Contrairement à notre FSM existant, un FSM basé sur une pile utilise une pile pour contrôler les états. Le haut de la pile contient l'état actif. les transitions sont gérées en poussant ou en sortant des états de la pile:
FSM basé sur la pileL'état actuellement actif peut décider quoi faire pendant une transition:
Transitions dans un FSM basé sur une pile: pop lui-même + push new; pop lui-même; pousser de nouveaux.Il peut sortir de la pile et pousser un autre état, ce qui signifie une transition complète (comme le faisait le simple FSM). Il peut sortir lui-même de la pile, ce qui signifie que l'état actuel est terminé et que l'état suivant de la pile devrait devenir actif. Enfin, il peut simplement pousser un nouvel état, ce qui signifie que l'état actuellement actif changera pendant un moment, mais lorsqu'il disparaîtra de la pile, l'état précédemment actif reprendra le contrôle..
Un FSM basé sur une pile peut être implémenté en utilisant la même approche qu'auparavant, mais cette fois en utilisant un tableau de pointeurs de fonction pour contrôler la pile. le état actif Cette propriété n'est plus nécessaire, car le haut de la pile pointe déjà vers l'état actuellement actif:
Classe publique StackFSM private var stack: Array; fonction publique StackFSM () this.stack = new Array (); public function update (): void var currentStateFunction: Function = getCurrentState (); if (currentStateFunction! = null) currentStateFunction (); public function popState (): Function return stack.pop (); fonction publique pushState (state: Function): void if (getCurrentState ()! = state) stack.push (state); fonction publique getCurrentState (): Fonction return stack.length> 0? stack [stack.length - 1]: null;
le setState () Cette méthode a été remplacée par deux nouvelles méthodes: pushState () et popState (); pushState () ajoute un nouvel état en haut de la pile, tandis que popState () supprime l'état en haut de la pile. Les deux méthodes font automatiquement passer la machine à un nouvel état, puisqu'elles changent le haut de la pile..
Lorsque vous utilisez un FSM basé sur une pile, il est important de noter que chaque état est responsable de se sortir de la pile. Habituellement, un état se supprime de la pile lorsqu'il n'est plus nécessaire, comme si attaque() est actif mais la cible vient de mourir.
À l'aide de l'exemple ant, quelques modifications sont nécessaires pour adapter le code à l'utilisation d'un FSM basé sur une pile. Le problème de la non-connaissance de l'état de transition est maintenant résolu de manière transparente grâce à la nature même du FSM en pile:
public class Ant (…) public var brain: StackFSM; fonction publique Ant (posX: Number, posY: Number) (…) brain = new StackFSM (); // Dites au cerveau de commencer à chercher la feuille. brain.pushState (findLeaf); (…) / ** * L'état "findLeaf". * Il fait avancer la fourmi vers la feuille. * / public function findLeaf (): void // Déplace la fourmi vers la feuille. vélocité = nouveau Vector3D (Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance (Game.instance.leaf, this) <= 10) // The ant is extremelly close to the leaf, it's time // to go home. brain.popState(); // removes "findLeaf" from the stack. brain.pushState(goHome); // push "goHome" state, making it the active state. if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) // Mouse cursor is threatening us. Let's run away! // The "runAway" state is pushed on top of "findLeaf", which means // the "findLeaf" state will be active again when "runAway" ends. brain.pushState(runAway); /** * The "goHome" state. * It makes the ant move towards its home. */ public function goHome() :void // Move the ant towards home velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) // The ant is home, let's find the leaf again. brain.popState(); // removes "goHome" from the stack. brain.pushState(findLeaf); // push "findLeaf" state, making it the active state if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) // Mouse cursor is threatening us. Let's run away! // The "runAway" state is pushed on top of "goHome", which means // the "goHome" state will be active again when "runAway" ends. brain.pushState(runAway); /** * The "runAway" state. * It makes the ant run away from the mouse cursor. */ public function runAway() :void // Move the ant away from the mouse cursor velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Is the mouse cursor still close? if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) // Non, le curseur de la souris est parti. Revenons à l'état // précédemment actif. brain.popState (); (…)
Le résultat est une fourmi capable de fuir le curseur de la souris et de revenir à l'état antérieurement actif avant la menace:
Ant contrôlé par un FSM basé sur une pile. Déplacez le curseur de la souris pour menacer la fourmi.Les machines à états finis sont utiles pour implémenter la logique de l'IA dans les jeux. Ils peuvent être facilement représentés à l'aide d'un graphique, ce qui permet au développeur de voir la situation dans son ensemble, de peaufiner et d'optimiser le résultat final..
L'implémentation d'un FSM utilisant des fonctions ou des méthodes pour représenter des états est simple mais puissante. Des résultats encore plus complexes peuvent être obtenus à l'aide d'un FSM basé sur une pile, ce qui garantit un flux d'exécution maniable et concis sans impact négatif sur le code. Il est temps de rendre tous vos ennemis plus intelligents en utilisant un FSM!
