Share
Una macchina a stati finiti è un modello utilizzato per rappresentare e controllare il flusso di esecuzione. È perfetto per l'implementazione dell'IA nei giochi, producendo ottimi risultati senza un codice complesso. Questo tutorial descrive la teoria, l'implementazione e l'uso di macchine a stati finiti semplici e basati su stack.
Tutte le icone realizzate da Lorc e disponibili su http://game-icons.net.
Nota: Sebbene questo tutorial sia scritto usando AS3 e Flash, dovresti essere in grado di utilizzare le stesse tecniche e concetti in quasi tutti gli ambienti di sviluppo di giochi.
Una macchina a stati finiti, o in breve FSM, è un modello di calcolo basato su un'ipotetica macchina composta da uno o più stati. Solo un singolo stato può essere attivo allo stesso tempo, quindi la macchina deve passare da uno stato all'altro per eseguire azioni diverse.
Gli FSM sono comunemente usati per organizzare e rappresentare un flusso di esecuzione, che è utile per implementare l'intelligenza artificiale nei giochi. Il "cervello" di un nemico, ad esempio, può essere implementato utilizzando un FSM: ogni stato rappresenta un'azione, come ad esempio attacco o eludere:
FSM che rappresenta il cervello di un nemico.Un FSM può essere rappresentato da un grafico, in cui i nodi sono gli stati e i bordi sono le transizioni. Ogni spigolo ha un'etichetta che informa quando dovrebbe avvenire la transizione, come la il giocatore è vicino etichetta nella figura sopra, che indica che la macchina passerà da vagare a attacco se il giocatore è vicino.
L'implementazione di un FSM inizia con gli stati e le transizioni che avrà. Immagina il seguente FSM, che rappresenta il cervello di una formica che trasporta foglie a casa:
FSM che rappresenta il cervello di una formica.Il punto di partenza è il trova la foglia stato, che rimarrà attivo fino a quando la formica non troverà la foglia. Quando ciò accade, lo stato corrente viene passato a andare a casa, che rimane attivo fino a quando la formica non torna a casa. Quando la formica arriva finalmente a casa, lo stato attivo diventa trova la foglia di nuovo, così la formica ripete il suo viaggio.
Se lo stato attivo è trova la foglia e il cursore del mouse si avvicina alla formica, c'è una transizione al scappa stato. Mentre quello stato è attivo, la formica scappa dal cursore del mouse. Quando il cursore non è più una minaccia, c'è una transizione verso il trova la foglia stato.
Dal momento che ci sono le transizioni che si connettono trova la foglia e scappa, la formica scapperà sempre dal cursore del mouse quando si avvicina finché la formica sta trovando la foglia. Quello non lo farò succede se lo stato attivo è andare a casa (controlla la figura sotto). In quel caso la formica camminerà a casa senza paura, solo passando al trova la foglia stato quando arriva a casa.
FSM che rappresenta il cervello di una formica. Si noti la mancanza di una transizione tra 
Accentsconagua
scappa e andare a casa. Un FSM può essere implementato e incapsulato in una singola classe, denominato FSM per esempio. L'idea è di implementare ogni stato come una funzione o un metodo, usando una proprietà chiamata ActiveState nella classe per determinare quale stato è attivo:
public class FSM private var activeState: Function; // punta alla funzione di stato attualmente attiva public function FSM () public function setState (state: Function): void activeState = state; public function update (): void if (activeState! = null) activeState ();
Poiché ogni stato è una funzione, mentre uno stato specifico è attivo, la funzione che rappresenta tale stato verrà invocata ad ogni aggiornamento di gioco. Il ActiveState la proprietà è un puntatore a una funzione, quindi punterà alla funzione dello stato attivo.
Il aggiornare() metodo del FSM la classe deve essere invocata su ogni frame di gioco, in modo che possa chiamare la funzione puntata dal ActiveState proprietà. Quella chiamata aggiornerà le azioni dello stato attualmente attivo.
Il setState () il metodo passerà il FSM a un nuovo stato puntando il ActiveState proprietà a una nuova funzione di stato. La funzione di stato non deve essere un membro di FSM; può appartenere a un'altra classe, che rende il FSM classe più generica e riutilizzabile.
Usando il FSM classe già descritta, è il momento di implementare il "cervello" di un personaggio. La formica precedentemente spiegata sarà usata e controllata da un FSM. Quanto segue è una rappresentazione di stati e transizioni, concentrandosi sul codice:
FSM del cervello delle formiche con focus sul codice.La formica è rappresentata dal Formica classe, che ha una proprietà chiamata cervello e un metodo per ogni stato. Il cervello la proprietà è un'istanza del FSM classe:
public class Ant public var position: Vector3D; velocità var pubblica: Vector3D; cervello di var pubblico: FSM; funzione pubblica Ant (posX: Number, posY: Number) position = new Vector3D (posX, posY); velocity = new Vector3D (-1, -1); cervello = nuovo FSM (); // Dì al cervello di iniziare a cercare la foglia. brain.setState (findLeaf); / ** * Lo stato "findLeaf". * Fa muovere la formica verso la foglia. * / public function findLeaf (): void / ** * Lo stato di "goHome". * Fa muovere la formica verso la sua casa. * / public function goHome (): void / ** * Lo stato "runAway". * Fa allontanare la form dal cursore del mouse. * / public function runAway (): void public function update (): void // Aggiorna l'FSM che controlla il "cervello". Richiama la funzione attualmente // stato attivo: findLeaf (), goHome () o runAway (). brain.update (); // Applica il vettore di velocità alla posizione, facendo muovere la formica. moveBasedOnVelocity (); (...)
Il Formica la classe ha anche un velocità e a posizione proprietà, entrambi utilizzati per calcolare il movimento utilizzando l'integrazione di Eulero. Il aggiornare() il metodo viene chiamato ogni frame del gioco, quindi aggiornerà l'FSM.
Per mantenere le cose semplici, il codice utilizzato per spostare la formica, come ad esempio moveBasedOnVelocity (), sarà omesso. Maggiori informazioni su questo possono essere trovate nella serie Understanding Steering Behaviors.
Di seguito è riportata l'implementazione di ogni stato, a partire da findLeaf (), lo stato responsabile della guida della formica alla posizione della foglia:
public function findLeaf (): void // Sposta la formica verso la foglia. 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);
Il andare a casa() stato, usato per guidare la casa delle formiche:
public function goHome (): void // Sposta la formica verso 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);
Finalmente, il scappa() stato, usato per fare in modo che la formica fugga dal cursore del mouse:
public function runAway (): void // Sposta il form dal cursore del mouse velocity = new Vector3D (position.x - Game.mouse.x, position.y - Game.mouse.y); // Il cursore del mouse è ancora chiuso? if (distance (Game.mouse, this)> MOUSE_THREAT_RADIUS) // No, il cursore del mouse è scomparso. Torniamo indietro cercando la foglia. brain.setState (findLeaf);
Il risultato è una formica controllata da un "cervello" di FSM:
Formica controllata da un FSM. Muovi il cursore del mouse per minacciare la formica.Immagina che la formica debba anche scappare dal cursore del mouse quando sta andando a casa. L'FSM può essere aggiornato come segue:
Ant FSM aggiornato con nuove transizioni.Sembra una modifica banale, l'aggiunta di una nuova transizione, ma crea un problema: se lo stato attuale lo è scappa e il cursore del mouse non è più vicino, quale stato dovrebbe essere la transizione della formica a: andare a casa o trova la foglia?
La soluzione per questo problema è a FSM stack-based. A differenza del nostro FSM esistente, un FSM basato sullo stack utilizza uno stack per controllare gli stati. La cima della pila contiene lo stato attivo; le transizioni sono gestite spingendo o scoppiando gli stati dallo stack:
FSM basato su stackLo stato attualmente attivo può decidere cosa fare durante una transizione:
Transizioni in un FSM stack-based: pop stesso + push new; pop stesso; spingere di nuovo.Può saltar fuori dallo stack e spingere un altro stato, il che significa una transizione completa (proprio come stava facendo il semplice FSM). Può saltar fuori dallo stack, il che significa che lo stato corrente è completo e lo stato successivo nello stack dovrebbe diventare attivo. Infine, può solo premere un nuovo stato, il che significa che lo stato attualmente attivo cambierà per un po ', ma quando si apre dallo stack, lo stato precedentemente attivo riprenderà.
Un FSM stack-based può essere implementato usando lo stesso approccio di prima, ma questa volta utilizzando una serie di puntatori a funzione per controllare lo stack. Il ActiveState la proprietà non è più necessaria, poiché la parte superiore dello stack punta già allo stato attualmente attivo:
public class StackFSM private var stack: Array; funzione pubblica 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 (stato); public function getCurrentState (): Function return stack.length> 0? stack [stack.length - 1]: null;
Il setState () il metodo è stato sostituito con due nuovi metodi: pushState () e popstate (); pushState () aggiunge un nuovo stato in cima allo stack, mentre popstate () rimuove lo stato in cima alla pila. Entrambi i metodi trasferiscono automaticamente la macchina in un nuovo stato, poiché cambiano la parte superiore della pila.
Quando si utilizza un FSM basato sullo stack, è importante notare che ogni stato è responsabile dello scoppio stesso dallo stack. Di solito uno stato si rimuove dallo stack quando non è più necessario, come se fosse attacco() è attivo ma l'obiettivo è appena morto.
Usando l'esempio di formica, sono necessarie poche modifiche per adattare il codice all'uso di un FSM basato su stack. Il problema di non sapere a quale stato passare è ora risolto senza soluzione di continuità grazie alla natura stessa di FSM stack-based:
public class Ant (...) public var brain: StackFSM; funzione pubblica Ant (posX: Number, posY: Number) (...) brain = new StackFSM (); // Dì al cervello di iniziare a cercare la foglia. brain.pushState (findLeaf); (...) / ** * Lo stato "findLeaf". * Fa muovere la formica verso la foglia. * / public function findLeaf (): void // Sposta la formica verso la foglia. 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, il cursore del mouse è scomparso. Torniamo allo stato // precedente in precedenza. brain.popState (); (...)
Il risultato è una formica in grado di scappare dal cursore del mouse, tornando allo stato precedentemente attivo prima della minaccia:
Ant controllata da un FSM stack-based. Muovi il cursore del mouse per minacciare la formica.Le macchine a stati finiti sono utili per implementare la logica AI nei giochi. Possono essere facilmente rappresentati utilizzando un grafico, che consente a uno sviluppatore di vedere il quadro generale, modificando e ottimizzando il risultato finale.
L'implementazione di un FSM che utilizza funzioni o metodi per rappresentare stati è semplice, ma potente. Risultati ancora più complessi possono essere ottenuti utilizzando un FSM stack-based, che garantisce un flusso di esecuzione gestibile e conciso senza influire negativamente sul codice. È ora di rendere più intelligenti tutti i tuoi nemici grazie a un FSM!
