Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Game Development
  2. Artificial Intelligence
Gamedevelopment

Máquinas de estados finitos: teoría e implementación

by
Difficulty:IntermediateLength:LongLanguages:

Spanish (Español) translation by Elías Nicolás (you can also view the original English article)

Una máquina de estado finito es un modelo utilizado para representar y controlar el flujo de ejecución. Es perfecto para implementar AI 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 estados finitos simples y basadas en la pila.

Todos los iconos hechos por Lorc, y disponibles en http://game-icons.net.

Nota: Aunque este tutorial está escrito usando AS3 y Flash, debería ser capaz de utilizar las mismas técnicas y conceptos en casi cualquier entorno de desarrollo de juegos.


¿Qué es una máquina de estados finitos?

Una máquina de estado finito, o FSM para abreviar, es un modelo de computación basado en una máquina hipotética hecha de uno o más estados. Solo un estado individual 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 usando un FSM: cada estado representa una acción, como atacar attack o evadir evade:

FSM que representa 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 producirse la transición, al igual que el jugador está cerca player is near de la etiqueta en la figura anterior, lo que indica que la máquina hará la transición de deambular wander a atacar attack si el jugador está cerca.


Estados de planificación y sus transiciones

La implementación de un FSM comienza con los estados y las transiciones que tendrá. Imagine el siguiente FSM, que representa el cerebro de una hormiga que lleva hojas a casa:

FSM que representa el cerebro de una hormiga.

El punto de partida es el estado de hoja de búsqueda find leaf, que permanecerá activo hasta que la hormiga encuentre la hoja. Cuando eso sucede, el estado actual se transfiere go home para irse a casa, que permanece activo hasta que la hormiga llega a casa. Cuando la hormiga finalmente llega a casa, el estado activo find leaf se vuelve a buscar hoja, por lo que la hormiga repite su viaje.

Si el estado activo es encontrar hoja find leaf y el cursor del mouse se acerca a la hormiga, hay una transición al estado de escape run away. Mientras ese estado esté activo, la hormiga se escapará del cursor del mouse. Cuando el cursor ya no es una amenaza, hay una transición al estado buscar hoja find leaf.

Dado que hay transiciones que conectan la find leaf y run away, la hormiga siempre huirá del cursor del mouse cuando se aproxime mientras la hormiga encuentre la hoja. Eso no sucederá si el estado activo es go home (vea la figura a continuación). En ese caso, la hormiga caminará a casa sin miedo, solo haciendo la transición al estado de find leaf cuando llegue a casa.

FSM que representa el cerebro de una hormiga. Observe la falta de una transición entre run away e go home.

Implementando un FSM

Implementando un FSMUn 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, usando una propiedad llamada activeState en la clase para determinar qué estado está activo:

Como cada estado es una función, mientras un estado específico está activo, se invocará la función que representa ese estado en cada actualización del juego. La propiedad activeState es un puntero a una función, por lo que apuntará a la función del estado activo.

El método update() de la clase FSM debe invocarse en cada cuadro de juego, de modo que pueda llamar a la función apuntada por la propiedad activeState. Esa llamada actualizará las acciones del estado actualmente activo.

El método setState() hará la transición del FSM a un nuevo estado apuntando la propiedad activeState a una nueva función de estado. La función de estado no tiene que ser miembro de FSM; puede pertenecer a otra clase, lo que hace que la clase FSM sea más genérica y reutilizable.


Usando un FSM

Usando la clase de FSM 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 de hormiga cerebral con enfoque en el código.

La hormiga está representada por la clase Ant, que tiene una propiedad llamada brain y un método para cada estado. La propiedad brain es una instancia de la clase FSM:

La clase Ant también tiene una propiedad velocity y de position, ambas usadas para calcular el movimiento usando la integración de Euler. El método update() se llama cada cuadro de juego, por lo que actualizará el FSM.

Para mantener las cosas simples, se omitirá el código utilizado para mover la hormiga, como moveBasedOnVelocity(). Se puede encontrar más información sobre esto 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:

El estado goHome(), utilizado para guiar a la hormiga a casa:

Finalmente, el estado runAway(), utilizado para hacer que la hormiga huya del cursor del mouse:

El resultado es una hormiga controlada por un "cerebro" FSM:

Hormiga controlada por un FSM. Mueva el cursor del mouse para amenazar a la hormiga.

Mejorando el flujo: FSM basado en pila

Imagine que la hormiga también necesita huir del cursor del mouse cuando se va a casa. El FSM puede actualizarse 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 run away y el cursor del mouse ya no está cerca, ¿a qué estado debería pasar la hormiga: go home o find leaf?

La solución para ese problema es un 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 presionando o saltando estados de la pila:

FSM basado en pila

El estado activo actualmente puede decidir qué hacer durante una transición:

Transiciones en un FSM basado en pila: pop en sí mismo + push nuevo; pop en sí mismo; push nuevo

Puede salir de la pila e impulsar otro estado, lo que significa una transición completa (como lo hacía el FSM simple). Puede salir de la pila, lo que significa que el estado actual está completo y el siguiente estado en la pila debería activarse. Finalmente, puede simplemente presionar un nuevo estado, lo que significa que el estado activo actualmente cambiará por un tiempo, pero cuando salga de la pila, el estado previamente activo tomará el control otra vez.


Implementación de un FSM basado en pila

Un FSM basado en pila se puede implementar utilizando el mismo enfoque que antes, pero esta vez usando una matriz de indicadores de función para controlar la pila. La propiedad activeState ya no es necesaria, ya que la parte superior de la pila ya apunta al estado actualmente activo:

El método setStat() fue reemplazado por dos métodos nuevos: 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 cambian automáticamente la máquina a un nuevo estado, ya que cambian la parte superior de la pila.


Uso de un FSM basado en pila

Cuando se usa un FSM basado en pila, es importante tener en cuenta que cada estado es responsable de salir de la pila. Por lo general, un estado se elimina de la pila cuando ya no es necesario, como si el attack() estuviera activo pero el objetivo acabara muerto.

Usando el ejemplo de la hormiga, solo se requieren algunos cambios para adaptar el código para usar un FSM basado en pila. El problema de no conocer el estado de transición ahora se resuelve sin problemas gracias a la naturaleza misma de FSM basado en pila:

El resultado es una hormiga capaz de escapar del cursor del mouse, haciendo la transición al estado previamente activo antes de la amenaza:

Ant controlado por un FSM basado en pila. Mueva el cursor del mouse para amenazar a la hormiga.

Conclusión

Las máquinas de estado finito son útiles para implementar la lógica de IA en los juegos. Se pueden representar fácilmente usando un gráfico, que permite a un desarrollador ver la imagen completa, ajustar y optimizar el resultado final.

La implementación de un FSM usando funciones o métodos para representar estados es simple, pero poderoso. Incluso se pueden lograr resultados más complejos utilizando un FSM basado en pila, que garantiza un flujo de ejecución manejable y conciso sin afectar negativamente al código. ¡Es hora de hacer todos los enemigos de tu juego más inteligentes usando un FSM!

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.