() translation by (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:
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:
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.
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:
1 |
public class FSM { |
2 |
private var activeState :Function; // points to the currently active state function |
3 |
|
4 |
public function FSM() { |
5 |
}
|
6 |
|
7 |
public function setState(state :Function) :void { |
8 |
activeState = state; |
9 |
}
|
10 |
|
11 |
public function update() :void { |
12 |
if (activeState != null) { |
13 |
activeState(); |
14 |
}
|
15 |
}
|
16 |
}
|
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:
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:
1 |
public class Ant |
2 |
{
|
3 |
public var position :Vector3D; |
4 |
public var velocity :Vector3D; |
5 |
public var brain :FSM; |
6 |
|
7 |
public function Ant(posX :Number, posY :Number) { |
8 |
position = new Vector3D(posX, posY); |
9 |
velocity = new Vector3D( -1, -1); |
10 |
brain = new FSM(); |
11 |
|
12 |
// Tell the brain to start looking for the leaf.
|
13 |
brain.setState(findLeaf); |
14 |
}
|
15 |
|
16 |
/**
|
17 |
* The "findLeaf" state.
|
18 |
* It makes the ant move towards the leaf.
|
19 |
*/
|
20 |
public function findLeaf() :void { |
21 |
}
|
22 |
|
23 |
/**
|
24 |
* The "goHome" state.
|
25 |
* It makes the ant move towards its home.
|
26 |
*/
|
27 |
public function goHome() :void { |
28 |
}
|
29 |
|
30 |
/**
|
31 |
* The "runAway" state.
|
32 |
* It makes the ant run away from the mouse cursor.
|
33 |
*/
|
34 |
public function runAway() :void { |
35 |
}
|
36 |
|
37 |
public function update():void { |
38 |
// Update the FSM controlling the "brain". It will invoke the currently
|
39 |
// active state function: findLeaf(), goHome() or runAway().
|
40 |
brain.update(); |
41 |
|
42 |
// Apply the velocity vector to the position, making the ant move.
|
43 |
moveBasedOnVelocity(); |
44 |
}
|
45 |
|
46 |
(...)
|
47 |
}
|
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:
1 |
public function findLeaf() :void { |
2 |
// Move the ant towards the leaf.
|
3 |
velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); |
4 |
|
5 |
if (distance(Game.instance.leaf, this) <= 10) { |
6 |
// The ant is extremelly close to the leaf, it's time
|
7 |
// to go home.
|
8 |
brain.setState(goHome); |
9 |
}
|
10 |
|
11 |
if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { |
12 |
// Mouse cursor is threatening us. Let's run away!
|
13 |
// It will make the brain start calling runAway() from
|
14 |
// now on.
|
15 |
brain.setState(runAway); |
16 |
}
|
17 |
}
|
El estado goHome(), utilizado para guiar a la hormiga a casa:
1 |
public function goHome() :void { |
2 |
// Move the ant towards home
|
3 |
velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); |
4 |
|
5 |
if (distance(Game.instance.home, this) <= 10) { |
6 |
// The ant is home, let's find the leaf again.
|
7 |
brain.setState(findLeaf); |
8 |
}
|
9 |
}
|
Finalmente, el estado runAway(), utilizado para hacer que la hormiga huya del cursor del mouse:
1 |
public function runAway() :void { |
2 |
// Move the ant away from the mouse cursor
|
3 |
velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); |
4 |
|
5 |
// Is the mouse cursor still close?
|
6 |
if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) { |
7 |
// No, the mouse cursor has gone away. Let's go back looking for the leaf.
|
8 |
brain.setState(findLeaf); |
9 |
}
|
10 |
}
|
El resultado es una hormiga controlada por un "cerebro" FSM:
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:
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:
El estado activo actualmente puede decidir qué hacer durante una transición:
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:
1 |
public class StackFSM { |
2 |
private var stack :Array; |
3 |
|
4 |
public function StackFSM() { |
5 |
this.stack = new Array(); |
6 |
}
|
7 |
|
8 |
public function update() :void { |
9 |
var currentStateFunction :Function = getCurrentState(); |
10 |
|
11 |
if (currentStateFunction != null) { |
12 |
currentStateFunction(); |
13 |
}
|
14 |
}
|
15 |
|
16 |
public function popState() :Function { |
17 |
return stack.pop(); |
18 |
}
|
19 |
|
20 |
public function pushState(state :Function) :void { |
21 |
if (getCurrentState() != state) { |
22 |
stack.push(state); |
23 |
}
|
24 |
}
|
25 |
|
26 |
public function getCurrentState() :Function { |
27 |
return stack.length > 0 ? stack[stack.length - 1] : null; |
28 |
}
|
29 |
}
|
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:
1 |
public class Ant { |
2 |
(...)
|
3 |
public var brain :StackFSM; |
4 |
|
5 |
public function Ant(posX :Number, posY :Number) { |
6 |
(...)
|
7 |
brain = new StackFSM(); |
8 |
|
9 |
// Tell the brain to start looking for the leaf.
|
10 |
brain.pushState(findLeaf); |
11 |
|
12 |
(...)
|
13 |
}
|
14 |
|
15 |
/**
|
16 |
* The "findLeaf" state.
|
17 |
* It makes the ant move towards the leaf.
|
18 |
*/
|
19 |
public function findLeaf() :void { |
20 |
// Move the ant towards the leaf.
|
21 |
velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); |
22 |
|
23 |
if (distance(Game.instance.leaf, this) <= 10) { |
24 |
// The ant is extremelly close to the leaf, it's time
|
25 |
// to go home.
|
26 |
brain.popState(); // removes "findLeaf" from the stack. |
27 |
brain.pushState(goHome); // push "goHome" state, making it the active state. |
28 |
}
|
29 |
|
30 |
if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { |
31 |
// Mouse cursor is threatening us. Let's run away!
|
32 |
// The "runAway" state is pushed on top of "findLeaf", which means
|
33 |
// the "findLeaf" state will be active again when "runAway" ends.
|
34 |
brain.pushState(runAway); |
35 |
}
|
36 |
}
|
37 |
|
38 |
/**
|
39 |
* The "goHome" state.
|
40 |
* It makes the ant move towards its home.
|
41 |
*/
|
42 |
public function goHome() :void { |
43 |
// Move the ant towards home
|
44 |
velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); |
45 |
|
46 |
if (distance(Game.instance.home, this) <= 10) { |
47 |
// The ant is home, let's find the leaf again.
|
48 |
brain.popState(); // removes "goHome" from the stack. |
49 |
brain.pushState(findLeaf); // push "findLeaf" state, making it the active state |
50 |
}
|
51 |
|
52 |
if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { |
53 |
// Mouse cursor is threatening us. Let's run away!
|
54 |
// The "runAway" state is pushed on top of "goHome", which means
|
55 |
// the "goHome" state will be active again when "runAway" ends.
|
56 |
brain.pushState(runAway); |
57 |
}
|
58 |
}
|
59 |
|
60 |
/**
|
61 |
* The "runAway" state.
|
62 |
* It makes the ant run away from the mouse cursor.
|
63 |
*/
|
64 |
public function runAway() :void { |
65 |
// Move the ant away from the mouse cursor
|
66 |
velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); |
67 |
|
68 |
// Is the mouse cursor still close?
|
69 |
if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) { |
70 |
// No, the mouse cursor has gone away. Let's go back to the previously
|
71 |
// active state.
|
72 |
brain.popState(); |
73 |
}
|
74 |
}
|
75 |
(...)
|
76 |
}
|
El resultado es una hormiga capaz de escapar del cursor del mouse, haciendo la transición al estado previamente activo antes de la amenaza:
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!
