Share
Una máquina de estado finito es un modelo usado para representar y controlar el flujo de ejecución. Es perfecto para implementar la inteligencia artificial en juegos, produciendo excelentes resultados sin un código complejo. Este tutorial describe la teoría, la implementación y el uso de máquinas de estado finito simples y basadas en pila.
Todos los íconos hechos por Lorc, y disponibles en http://game-icons.net.
Nota: Aunque este tutorial está escrito con AS3 y Flash, debería poder utilizar las mismas técnicas y conceptos en casi cualquier entorno de desarrollo de juegos..
Una máquina de estado finito, o FSM para abreviar, es un modelo de cálculo basado en una máquina hipotética hecha de uno o más estados. Solo un estado puede estar activo al mismo tiempo, por lo que la máquina debe pasar de un estado a otro para realizar diferentes acciones..
Los FSM se usan comúnmente para organizar y representar un flujo de ejecución, que es útil para implementar AI en juegos. El "cerebro" de un enemigo, por ejemplo, puede implementarse utilizando un FSM: cada estado representa una acción, como ataque o evadir:
FSM representando el cerebro de un enemigo..Un FSM se puede representar mediante un gráfico, donde los nodos son los estados y los bordes son las transiciones. Cada borde tiene una etiqueta que informa cuándo debe ocurrir la transición, como la el jugador esta cerca etiqueta en la figura anterior, que indica que la máquina pasará de deambular a ataque si el jugador esta cerca.
La implementación de un FSM comienza con los estados y las transiciones que tendrá. Imagina el siguiente FSM, que representa el cerebro de una hormiga que lleva las hojas a casa:
FSM representando el cerebro de una hormiga..El punto de partida es el encontrar hoja Estado, que permanecerá activo hasta que la hormiga encuentre la hoja. Cuando eso sucede, el estado actual pasa a Vete a casa, que permanece activa hasta que la hormiga llega a casa. Cuando la hormiga finalmente llega a casa, el estado activo se convierte en encontrar hoja De nuevo, así la hormiga repite su viaje..
Si el estado activo es encontrar hoja y el cursor del mouse se acerca a la hormiga, hay una transición a la huir estado. Mientras ese estado esté activo, la hormiga huirá del cursor del mouse. Cuando el cursor ya no es una amenaza, hay una transición de regreso a la encontrar hoja estado.
Como hay transiciones que conectan encontrar hoja y huir, La hormiga siempre huirá del cursor del mouse cuando se acerque. Mientras la hormiga encuentre la hoja.. Ese no lo hará suceder si el estado activo es Vete a casa (Echa un vistazo a la figura de abajo). En ese caso, la hormiga caminará a casa sin temor, solo haciendo la transición a la encontrar hoja Estado cuando llega a casa.
FSM representando el cerebro de una hormiga. Note la falta de una transición entre 
Accentsconagua
huir y Vete a casa. Un FSM se puede implementar y encapsular en una sola clase, llamada FSM por ejemplo. La idea es implementar cada estado como una función o método, utilizando una propiedad llamada estado activo en la clase para determinar qué estado está activo:
public class FSM private var activeState: Function; // apunta a la función pública activa actual función pública FSM () public function setState (state: Function): void activeState = state; actualización de la función pública (): void if (activeState! = null) activeState ();
Como cada estado es una función, mientras que un estado específico está activo, la función que representa ese estado se invocará en cada actualización del juego. los estado activo la propiedad es un puntero a una función, por lo que apuntará a la función del estado activo.
los actualizar() método de la FSM La clase debe invocarse en cada cuadro de juego, para que pueda llamar a la función señalada por el estado activo propiedad. Esa convocatoria actualizará las acciones del estado activo actual..
los setState () El método pasará el FSM a un nuevo estado al señalar el estado activo Propiedad a una nueva función de estado. La función de estado no tiene que ser un miembro de FSM; Puede pertenecer a otra clase, lo que hace que la FSM clase mas genérica y reutilizable.
Utilizando la FSM clase ya descrita, es hora de implementar el "cerebro" de un personaje. La hormiga previamente explicada será utilizada y controlada por un FSM. La siguiente es una representación de estados y transiciones, centrándose en el código:
FSM del cerebro de hormigas con foco en el código..La hormiga está representada por la Hormiga clase, que tiene una propiedad llamada cerebro y un método para cada estado. los cerebro La propiedad es una instancia de la FSM clase:
public class Ant public var position: Vector3D; public var speed: Vector3D; cerebro de var público: FSM; función pública Ant (posX: Number, posY: Number) position = new Vector3D (posX, posY); velocidad = nuevo Vector3D (-1, -1); cerebro = nuevo FSM (); // Dile al cerebro que comience a buscar la hoja. brain.setState (findLeaf); / ** * El estado "findLeaf". * Hace que la hormiga se mueva hacia la hoja. * / public function findLeaf (): void / ** * El estado "goHome". * Hace que la hormiga se mueva hacia su hogar. * / public function goHome (): void / ** * El estado "runAway". * Hace que la hormiga se aleje del cursor del mouse. * / public function runAway (): void public function update (): void // Actualice el FSM controlando el "cerebro". Invocará la función actual // activa del estado: findLeaf (), goHome () o runAway (). brain.update (); // Aplicar el vector de velocidad a la posición, haciendo que la hormiga se mueva. moveBasedOnVelocity (); (…)
los Hormiga clase también tiene una velocidad y un posición Propiedad, ambos utilizados para calcular el movimiento utilizando la integración de Euler. los actualizar() El método se llama en cada cuadro de juego, por lo que actualizará el FSM.
Para mantener las cosas simples, el código utilizado para mover la hormiga, como moveBasedOnVelocity (), será omitido. Puede encontrar más información al respecto en la serie Understanding Steering Behaviors..
A continuación se muestra la implementación de cada estado, comenzando con findLeaf (), El estado responsable de guiar a la hormiga a la posición de la hoja:
función pública findLeaf (): void // Mueve la hormiga hacia la hoja. velocidad = nuevo 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);
los Vete a casa() Estado, utilizado para guiar el hogar de la hormiga:
función pública goHome (): void // Mueve la hormiga hacia la velocidad inicial = nuevo 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);
Finalmente, el huir() Estado, usado para hacer que la hormiga huya del cursor del mouse:
public function runAway (): void // Aleje la hormiga del cursor del mouse velocidad = nuevo Vector3D (position.x - Game.mouse.x, position.y - Game.mouse.y); // ¿Está el cursor del mouse todavía cerca? if (distance (Game.mouse, this)> MOUSE_THREAT_RADIUS) // No, el cursor del mouse se ha ido. Volvamos a buscar la hoja. brain.setState (findLeaf);
El resultado es una hormiga controlada por un "cerebro" FSM:
Hormiga controlada por un FSM. Mueve el cursor del mouse para amenazar a la hormiga..Imagina que la hormiga también necesita huir del cursor del mouse cuando se va a casa. El FSM se puede actualizar a lo siguiente:
Ant FSM actualizado con nuevas transiciones..Parece una modificación trivial, la adición de una nueva transición, pero crea un problema: si el estado actual es huir y el cursor del mouse ya no está cerca, en qué estado debería cambiar la hormiga a: Vete a casa o encontrar hoja?
La solución para ese problema es una FSM basado en pila. A diferencia de nuestro FSM existente, un FSM basado en pila usa una pila para controlar estados. La parte superior de la pila contiene el estado activo; las transiciones se manejan empujando o haciendo estallar estados de la pila:
FSM basado en pilaEl estado activo actual puede decidir qué hacer durante una transición:
Transiciones en un FSM basado en pila: pop en sí + empujar nuevo; pop en sí mismo empujar nuevo.Puede salirse de la pila. y empujar a otro estado, lo que significa una transición completa (tal como lo hacía el FSM simple). Puede salirse de la pila, lo que significa que el estado actual está completo y que el siguiente estado de la pila debería estar activo. Finalmente, puede simplemente empujar un nuevo estado, lo que significa que el estado activo actual cambiará por un tiempo, pero cuando salga de la pila, el estado previamente activo volverá a tomar el control..
Un FSM basado en pila puede implementarse utilizando el mismo enfoque que antes, pero esta vez utilizando una serie de punteros de función para controlar la pila. los estado activo la propiedad ya no es necesaria, ya que la parte superior de la pila ya apunta al estado activo actual:
clase pública StackFSM private var stack: Array; función pública StackFSM () this.stack = new Array (); actualización de la función pública (): void var currentStateFunction: Function = getCurrentState (); if (currentStateFunction! = null) currentStateFunction (); public function popState (): Function return stack.pop (); public function pushState (state: Function): void if (getCurrentState ()! = state) stack.push (estado); función pública getCurrentState (): función return stack.length> 0? stack [stack.length - 1]: null;
los setState () El método fue reemplazado por dos nuevos métodos: pushState () y popState (); pushState () agrega un nuevo estado a la parte superior de la pila, mientras que popState () elimina el estado en la parte superior de la pila. Ambos métodos hacen que la máquina pase automáticamente a un nuevo estado, ya que cambian la parte superior de la pila.
Cuando se utiliza un FSM basado en pila, es importante tener en cuenta que cada estado es responsable de sacarse de la pila. Por lo general, un estado se elimina de la pila cuando ya no es necesario, como si ataque() está activo pero el objetivo acaba de morir.
Usando el ejemplo de ant, solo se requieren algunos cambios para adaptar el código para usar un FSM basado en pila. El problema de no saber el estado de transición se resuelve ahora sin problemas gracias a la naturaleza misma del FSM basado en pila:
clase pública Ant (...) public var brain: StackFSM; función pública Ant (posX: Number, posY: Number) (…) brain = new StackFSM (); // Dile al cerebro que comience a buscar la hoja. brain.pushState (findLeaf); (…) / ** * El estado "findLeaf". * Hace que la hormiga se mueva hacia la hoja. * / public function findLeaf (): void // Mueve la hormiga hacia la hoja. velocidad = nuevo 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) // No, el cursor del mouse se ha ido. Volvamos al estado anterior // activo. brain.popState (); (…)
El resultado es una hormiga capaz de huir del cursor del mouse y pasar al estado previamente activo antes de la amenaza:
Hormiga controlada por un FSM basado en pila. Mueve el cursor del mouse para amenazar a la hormiga..Las máquinas de estado finito son útiles para implementar la lógica AI en los juegos. Se pueden representar fácilmente mediante un gráfico, que permite a un desarrollador ver el panorama general, ajustar y optimizar el resultado final..
La implementación de un FSM que usa funciones o métodos para representar estados es simple, pero potente. Se pueden lograr resultados aún más complejos utilizando un FSM basado en la pila, que garantiza un flujo de ejecución manejable y conciso sin afectar negativamente al código. Es hora de hacer que todos tus enemigos del juego sean más inteligentes usando un FSM!
