Macchine a Stati Finiti:Teoria e Implementazione

() translation by (you can also view the original English article)

Una macchina a stati finiti è un modello utilizzato per rappresentare e controllare un flusso di esecuzione. E' perfetta per implementare la AI (n.d.a. Intelligenza Artificiale) nei giochi, produce ottimi risultati senza scrivere un codice troppo complesso. Questo tutorial descrive la teoria, l'implementazione e l'uso di macchine a stati finiti semplici basate sullo stack (n.d.a. struttura dati a pila).

Tutte le icone sono fatti da Lorc e disponibile su http://game-icons.net.

Nota: Anche se questo tutorial è scritto utilizzando AS3 e Flash, dovreste essere in grado di utilizzare le stesse tecniche e concetti in quasi tutti gli ambienti di sviluppo di videogiochi.

Che cosa è un Macchina a Stati Finiti?

Una macchina a stati finiti, o FSM in breve, è un modello computazionale basato su una macchina ipotetica fatta di uno o più stati. Solo un singolo stato può essere attivo allo stesso tempo, per cui la macchina deve passare da uno stato all'altro per eseguire diverse azioni.

Le FSM sono comunemente usate per organizzare e rappresentare un flusso di esecuzione, e sono utili per implementare l'intelligenza artificiale nei giochi. Il "cervello" di un nemico, per esempio, può essere implementato utilizzando una FSM: ogni stato rappresenta un'azione, come attacco o eludere:

Una FSM che rappresenta il cervello di un nemico.

Una FSM può essere rappresentata da un grafo, in cui i nodi sono gli stati ed i collegamenti sono le transizioni. Ogni collegamento ha un'etichetta per sapere quando la transizione dovrebbe avvenire, come per l'etichetta player is near (il giocatore è vicino) nella figura sopra, che indica il passaggio della macchina da wander (vagare) ad attack (attaccare) se il giocatore è vicino.

Pianificazione degli Stati e le loro Transizioni

L'implementazione di un FSM inizia con gli stati e le transizioni che avrà. Immaginate la seguente FSM, che rappresenta il cervello di una formica che esce dal formicaio:

Il punto di partenza è lo stato find leaf (cerca foglia), che rimarrà attivo fino a quando la formica non trova la foglia. Quando ciò accade, la stato attuale passa a go home (tornare a casa), che rimane attivo fino a quando la formica non torna a casa. Quando finalmente la formica arriva a casa, lo stato attivo diventa find leaf (cerca foglia), in modo che la formica ripete il suo viaggio.

Se lo stato attivo è find leaf (cerca foglia) e il cursore del mouse si avvicina alla formica, avviene una transizione allo stato run away (scappare). Finché quello stato è attivo, la formica scapperà dal cursore del mouse. Quando il cursore non è più una minaccia, c'è una transizione che porta nuovamente allo stato find leaf (cerca foglia).

Dato che ci sono passaggi che collegano find leaf (cerca foglia) e run away (scappare), la formica scapperà sempre dal cursore del mouse quando questo si avvicina fino a quando la formica non trova la foglia. Questo non accadrà se lo stato attivo è go home (torna a casa) (controllate la figura seguente). Solo passando dalla transizione find leaf (cerca foglia) la formica tornerà a casa senza paura .

La FSM che rappresenta il cervello di una formica. Si noti la mancanza di una transizione tra `run away` (scappare) e `go home` (torna a casa).

Implementazione di una FSM

Una FSM può essere implementata e incapsulata in una sola classe, denominata ad esempio FSM. L'idea è quella di implementare ogni stato come una funzione o metodo, utilizzando una proprietà chiamata activeState nella classe per determinare quale stato è attivo:

public class FSM {
  private var activeState :Function; // points to the currently active state function

	public function FSM() {
	}

	public function setState(state :Function) :void {
		activeState = state;
	}

	public function update() :void {
		if (activeState != null) {
			activeState();
		}
	}
}

Dal momento che ogni stato è una funzione, finché uno stato specifico è attivo la funzione che lo rappresenta verrà richiamata ad ogni aggiornamento del gioco. La proprietà activeState è un puntatore ad una funzione, in modo che punti alla funzione dello stato attivo.

Il metodo update() della classe FSM deve essere invocato ad ogni frame del gioco, in modo che possa richiamare la funzione puntata dalla proprietà activeState. Quella chiamata aggiornerà le azioni dello stato attualmente attivo.

Il metodo setState() passerà la FSM in un nuovo stato puntando la proprietà activeState ad una nuova funzione di stato. La funzione di stato non deve essere un membro della FSM; può appartenere ad un'altra classe, così da rendere la classe FSM più generica e riutilizzabile.

Utilizzo di una FSM

L'uso della classe FSM è già stato descritto, è il momento di applicarlo al "cervello" di un personaggio. Useremo l'esempio precedente della formica per farla controllare da una FSM. La seguente è una rappresentazione di stati e transizioni, con particolare attenzione il codice:

La FSM del cervello della formica con un focus sul codice.

La formica è rappresentato dalla classe Ant (formica), che ha una proprietà denominata brain (cervello) ed un metodo per ciascuno stato. La struttura del brain (cervello) è un'istanza della classe FSM:

public class Ant
{
	public var position   :Vector3D;
	public var velocity   :Vector3D;
	public var brain      :FSM;

	public function Ant(posX :Number, posY :Number) {
		position 	= new Vector3D(posX, posY);
		velocity 	= new Vector3D( -1, -1);
		brain		= new FSM();

		// Tell the brain to start looking for the leaf.
		brain.setState(findLeaf);
	}

	/**
	 * The "findLeaf" state.
	 * It makes the ant move towards the leaf.
	 */
	public function findLeaf() :void {
	}

	/**
	 * The "goHome" state.
	 * It makes the ant move towards its home.
	 */
	public function goHome() :void {
	}

	/**
	 * The "runAway" state.
	 * It makes the ant run away from the mouse cursor.
	 */
	public function runAway() :void {
	}

	public function update():void {
		// Update the FSM controlling the "brain". It will invoke the currently
		// active state function: findLeaf(), goHome() or runAway().
		brain.update();

		// Apply the velocity vector to the position, making the ant move.
		moveBasedOnVelocity();
	}

	(...)
}

La classe Ant (formica) ha anche una velocity (velocità) ed una proprietà position (posizione), entrambe usate per calcolare il movimento mediante l'integrazione di Eulero. Il metodo update() viene chiamato ad ogni frame del gioco, in modo da aggiornare la FSM.

Per semplificare le cose, il codice utilizzato per spostare la formica, come ad esempio moveBasedOnVelocity(), verrà omesso. Maggiori informazioni potete trovarle sulla serie Understanding Sterring Behaviors.

Qui di seguito l'implementazione di ogni stato, a partire da findLeaf() (trova foglia), lo stato che ha la responsabilità di guidare la formica verso la posizione della foglia:

public function findLeaf() :void {
	// Move the ant towards the leaf.
	velocity = new 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);
	}
}

Lo stato goHome() (torna a casa) usato per guidare la formica a casa:

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.setState(findLeaf);
	}
}

Infine, lo stato runAway() (scappare), usato per fare fuggire la formica fuggire dal cursore del mouse:

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, the mouse cursor has gone away. Let's go back looking for the leaf.
		brain.setState(findLeaf);
	}
}

Il risultato è una formica controllata da un "cervello" a FSM:

Formica controllata da una FSM. Spostare il cursore del mouse per minacciare la formica.

Migliorare il processo: FSM basata su uno stack

Immaginate che la formica abbia anche bisogno di scappare dal cursore del mouse quando sta tornando a casa. La FSM può essere aggiornata come segue:

FSM della formica aggiornata con le nuove transizioni.

Sembra un banale modifica, l'aggiunta di una nuova transizione, ma ci crea un problema: se lo stato run away (scappare) viene eseguito mentre il cursore non è più vicino, in quale stato di transizione la formica dovrebbe andare?: a casa go home o a trovare foglie find leaf?

La soluzione per questo problema è un FSM basata sullo stack. A differenza della nostra FSM, una FSM stack-based utilizza uno stack per controllare gli stati. La parte superiore dello pila (stack) contiene lo stato attivo; le transazioni sono gestite spingendo (pushing) o stappando (popping) gli stati dallo stack:

Lo stato attualmente attivo può decidere cosa fare durante la transizione:

Le transizioni in una FSM stack-based sono: stappa + spingi nuovo; stappa; spingi nuovo.

Si può stappare da pila e spingere un altro stato, che significa una piena transizione (proprio come faceva la FSM semplice). Si può stappare dalla pila, il che significa completare lo stato attuale rendendo attivo lo stato successivo nella pila. Infine, si può spingere un nuovo stato, che significa cambiare lo stato attualmente attivo per un po', ma quando lo si stappa dalla pila, lo stato precedentemente attivo diventerà ancora il nuovo.

Implementazione di una FSM basata su stack

Una FSM basata su stack può essere implementata utilizzando lo stesso metodo di prima, ma questa volta usando un array di puntatori a funzione per controllare la pila. La proprietà activeState non è più necessaria, in quanto la parte superiore della pila indica già allo stato attivo:

public class StackFSM {
	private var stack :Array;

	public function StackFSM() {
		this.stack = new Array();
	}

	public function update() :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(state);
		}
	}

	public function getCurrentState() :Function {
		return stack.length > 0 ? stack[stack.length - 1] : null;
	}
}

Il metodo setState() è stato sostituito con due nuovi metodi: pushState() e popState(); pushState() aggiunge un nuovo stato alla sommità della pila, mentre popstate() rimuove lo stato in cima alla pila. Entrambe i metodi passato automaticamente la macchina ad un nuovo stato, poiché cambiano la cima della pila.

Utilizzare una FSM basata su stack

Quando si utilizza una FSM basata su stack, è importante notare che ogni stato è responsabile di stapparsi dallo stack da solo. Di solito un stato si rimuove dalla pila quando non è più necessario, come se attack() che è l'obiettivo attivo fosse appena morto.

Utilizzando l'esempio della formica, sono necessari pochi cambiamenti per adattare il codice all'uso di una FSM basata su stack. Il problema di non conoscere verso quale stato la transizione stava andando ora è risolto senza problemi, grazie alla natura stessa della FSM basata su stack:

public class Ant {
	(...)
	public var brain :StackFSM;

	public function Ant(posX :Number, posY :Number) {
		(...)
		brain = new StackFSM();

		// Tell the brain to start looking for the leaf.
		brain.pushState(findLeaf);

		(...)
	}

	/**
	 * The "findLeaf" state.
	 * It makes the ant move towards the leaf.
	 */
	public function findLeaf() :void {
		// Move the ant towards the leaf.
		velocity = new 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, the mouse cursor has gone away. Let's go back to the previously
			// active state.
			brain.popState();
		}
	}
	(...)
}

Il risultato è una formica in grado di scappare dal cursore del mouse ma la transizione torna allo stato precedentemente attivo prima che ci fosse la minaccia:

Formica controllata da una FSM basata su stack. Spostate il cursore del mouse per minacciare la formica.

Conclusione

Le Macchine a Stati Finiti sono utili per implementare la logica di AI nei giochi. Possono essere facilmente rappresentate utilizzando un grafo, che permette allo sviluppatore di vedere il quadro generale, ritoccare e ottimizzare il risultato finale.

L'implementazione di una FSM con funzioni o metodi per rappresentare gli stati è semplice, ma potente. Si possono ottenere risultati più complessi utilizzando una FSM basata su stack, che garantisce un flusso gestibile ed una esecuzione concisa senza compromettere il codice. E' tempo di fare tutti i nemici dei vostri giochi più intelligenti utilizzando un 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	}

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	}

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	}