Intelligenza Artificiale e Videogiochi – Le Macchine a Stati Finiti

Le macchine a stati finiti sono utilizzate in molti settori dell’informatica e in particolare nella programmazione dei videogiochi. In questo articolo descriveremo questa tipologia di macchina astratta e le sue implementazioni nell’ambiente Unity3D.

---

1) L’intelligenza artificiale nei videogiochi

L’intelligenza artificiale è una materia molto vasta e complessa; l’obiettivo finale è quello di simulare il comportamento umano nel risolvere problemi e prendere decisioni.
Nella letteratura si utilizza il termine di agenti intelligenti per indicare le entità dotate di comportamento complesso, non casuale. L’agente può essere un personaggio, un robot, ma anche un’automobile o altro ancora. Per analizzare il comportamento di un agente intelligente può essere utilizzato il paradigma sense-think-act. Il modello prevede tre fasi:

• Sense: l’agente osserva l’ambiente per individuare gli oggetti e gli eventi che possono influenzare il suo comportamento
• Think: l’agente analizza la situazione per decidere quale azione intraprendere in risposta agli eventi
• Act: l’agente implementa le decisioni prese nella fase precedente

Le azioni intraprese dall’agente causano una modifica all’ambiente e il ciclo riprende dall’inizio, sulla base della nuova situazione.
Attualmente la ricerca scientifica è in fase di grande espansione e comprende diversi settori: visione artificiale, elaborazione del linguaggio, apprendimento automatico, guida autonoma, ecc. Si tratta come è ovvio di progetti di grande complessità, il cui successo non è assicurato, e comunque sono progetti a lunga scadenza.
Nel mondo dei videogiochi l’obiettivo è più limitato: si tratta di progettare algoritmi che permettano ai personaggi di avere un comportamento simile a quello umano. Hanno grande importanza le fasi Think e Act, mentre è secondaria la fase Sense.
Uno dei primi giochi ad applicare concetti di intelligenza artificiale è stato Pacman, pubblicato nel 1980 (vedi link).

Per un’introduzione all’intelligenza artificiale nei videogiochi vedere ^[1] oppure ^[2] .

---

2) Le macchine a stati finiti

Un macchina a stati finiti (FSM) associata ad un oggetto è un modello costituito da un numero finito di stati; in ogni istante di tempo la macchina si trova in un solo stato. La macchina può ricevere input dall’ambiente e fare transizioni fra gli stati in base a eventi esterni o temporali. La macchina passa da uno stato all’altro in modalità discreta. Una FSM può essere rappresentata mediante un grafo orientato, dove i nodi denotano gli stati e gli archi le transizioni.
L’idea che sta alla base del modello della macchina a stati finiti è di scomporre il comportamento complesso di un oggetto in un numero finito di stati più semplici. Ogni stato descrive un comportamento ben definito dell’oggetto associato.
Lo studio teorico delle macchine a stati finiti è un settore dell’informatica chiamato Teoria della calcolabilità (Computability theory). Dal punto di vista formale una macchina a stati finiti è composta dai seguenti elementi:

• un insieme \(I\) chiamato alfabeto di input
• un insieme \(U\) di possibili simboli in uscita
• un insieme \(S\) contenente gli stati
• una funzione \(T: S \times I \to S\) che definisce le transizioni degli stati
• una funzione \(G: S \times I \to U\) che definisce l’uscita in funzione dello stato e dell’input
• uno stato iniziale \(s_{0} \in S\)

La macchina inizia con lo stato iniziale \(s_{0}\). Quindi legge una stringa di caratteri dall’alfabeto. Per ogni carattere \(c\) letto, se si trova nello stato \(s\) la macchina passa allo stato \(T(s,c)\). Il programma continua fino a che tutti i caratteri sono stati elaborati.
Le macchine a stati finiti sono classificate in due tipi principali proposti da E. Moore (1925-2003) e da G. Mealey (1927-2010).

2.1) Macchine di Moore

La caratteristica della macchina di Moore consiste nel fatto che l’uscita (output) dipende solo dallo stato corrente. Il seguente diagramma illustra una macchina di Moore con due stati:

2.2) Macchine di Mealey

Se l’uscita dipende sia dallo stato corrente sia dall’ingresso (input) allora la FSM viene chiamata macchina di Mealey. Il seguente diagramma illustra una macchina di Mealey con due stati:

In generale una FSM di Mealey richiede un numero di stati inferiore rispetto alla FSM di Moore. Le macchine di Mealy eseguono le azioni quando si verifica una transizione, mentre le macchine di Moore eseguono le azioni all’interno dello stato. Comunque è possibile trasformare una macchina di Mealey in una equivalente di Moore e viceversa.
Come esempio vediamo un semplice addizionatore di cifre binarie. Definiamo due stati:

• \(S_{0}\) se la somma di due cifre binarie non dà la cifra di riporto
• \(S_{1}\) se è presente il riporto

Il diagramma seguente rappresenta la FSM relativa:

Ad esempio il simbolo della transizione \(01/1\) nello stato \(S_{0}\) significa che sommando le cifre binarie \(0\) e \(1\) otteniamo \(1\) come output e rimaniamo nello stato senza riporto \(S_{0}\).

---

3) Implementazione con una singola classe

Un modo semplice per programmare una macchina a stati finiti in Unity 3D è quello di utilizzare una singola classe. All’interno della classe ogni stato viene implementato mediante una funzione specifica; per determinare in ogni momento qual è lo stato attivo viene definita una proprietà, ad esempio currentState. Nella classe si definiscono gli stati possibili tramite una struttura enum. Quindi nella funzione Update si analizzano gli stati e si eseguono le opportune azioni:

public class AnalizeState : MonoBehaviour {
    private State currentState;
    private enum State {
       stateOne,
       stateTwo,
       stateThree
    }; 
    
    void Start () {
        currentState = State.stateOne;
    }
    
    void Update () {
        switch (currentState) {
            case State.stateOne: stateOne(); 
                break;
            case State.stateTwo: stateTwo(); 
                break;
            case State.stateThree: stateThree(); 
                break;
            default: break;
    }

// function for stateOne
    void stateOne() {
        // logic
    }

// function for stateTwo
    void stateTwo() {
        // logic
    }

// function for stateThree
    void stateThree() {
        // logic
    }
}

Tutta la logica della macchina a stati finiti si trova in un’unica classe. Questo metodo può andare bene nei casi semplici, con macchine di pochi stati. All’aumentare del numero degli stati il software diventa complesso e ingestibile nel tempo. Inoltre spesso per ogni stato è necessario gestire separatamente l’evento di entrata (enter) e l’evento di uscita (exit). Questo rende il codice ancora più complesso e difficile da manutenere.

---

4) Lo State design pattern

Il pattern State offre una soluzione migliore per gestire il comportamento di un oggetto in funzione del suo stato. L’idea base è di definire una classe per ogni stato. Inoltre si definisce una classe astratta dalla quale vengono derivate le varie classi stato concrete. Ogni classe prevede tre funzioni fondamentali:

• enter()
• exit()
• execute()

I principali componenti del pattern State sono i seguenti:

• Context (AIController) – definisce le interfacce con il Client e tiene traccia dello stato corrente
• State – classe astratta che definisce le interfacce per un particolare stato
• ConcreteState – ogni sottoclasse derivata che implementa un particolare stato del Context

Per aggiungere un nuovo stato basta creare una nuova classe.
Il pattern State non specifica il punto dove le transizioni di stato devono essere definite. Di fatto si hanno due alternative: dentro l’oggetto Context oppure in ognuna delle classi stato derivate. Questa seconda soluzione introduce delle dipendenze fra le classi, in quanto in ognuna c’è un collegamento con le altre. Un buon disegno strutturato in genere dovrebbe minimizzare la coesione (coupling) fra oggetti. Tuttavia questa seconda soluzione facilita l’aggiunta di un nuovo stato.
Il pattern State incapsula tutti gli stati concreti nell’oggetto Context; per tener traccia dello stato corrente attivo utilizza una apposita variabile (currentState).
Nella programmazione dell’intelligenza artificiale nei videogiochi il Context corrisponde al controller dell’agente AI (AIController). Il controller tiene traccia dello stato corrente attivo e implementa la funzione Set_State (State newState) quando si deve effettuare una transizione. In questo modo in ogni frame in base allo stato corrente attivo si chiama la funzione di aggiornamento (update) corrispondente.

La struttura base della classe è la seguente:

using UnityEngine;

public class AI_Controller: MonoBehaviour {
    private State currentState;

    private void Start() {
        SetState(State newState);
    }

    private void Update() {
        currentState.Execute();
    }

    public void SetState(State newState){
        if (currentState != null) {
            currentState.OnStateExit();
        }   
        currentState = newState;
        currentState.Enter();
    }
}  

La classe astratta definisce i metodi che verranno implementati dalle classi concrete derivate.

public abstract class State {
  protected AI_Controller controller;

  public abstract void Execute();
  public virtual void OnStateEnter();
  public virtual void OnStateExit();
}

Mediante il riferimento alla classe AI_Controller vengono comunicati al controller i cambiamenti di stato. La definizione di un metodo con la proprietà abstract senza implementazione costringe la classe concreta derivata a implementare il metodo stesso. Le funzioni OnStateEnter e OnStateExit sono in genere non obbligatorie, e quindi possono essere definite con la proprietà virtual.
Ognuna delle classi concrete derivate implementerà le funzioni della classe astratta in funzione dello stato che rappresenta.

4.1) Implementazione in Unity 3D con Mecanim e coroutine

Come è noto Unity3D ha un sistema di animazione, chiamato Mecanim, che oltre a permettere l’animazione degli oggetti, offre anche la possibilità di implementare macchine a stati finiti. Il componente Animator è di fatto una macchina a stati finiti, in grado di gestire differenti stati e passare da uno stato all’altro mediante delle transizioni.
Per creare una semplice macchina a stati finiti basata sull’Animator di Unity3D basta eseguire i seguenti passi:

• creare un GameObject
• creare un Animator Controller
• definire gli stati, le transizioni e i parametri
• creare delle classi associate agli stati
• creare un componente Animator associato al GameObject
• trascinare l’Animator controller nel campo Controller del componente Animator

Per una ripasso vedere l’articolo nel presente blog.

Per gestire la macchina a stati finiti in base al modello descritto nel paragrafo precedente (state pattern) è in primo luogo necessario definire una classe AIController. Dentro questa classe possono essere definiti gli stati mediante una struttura enum. La classe AIController tra le altre cose tiene aggiornato l’indirizzo dello stato corrente. Per ogni stato viene chiamata una coroutine. Una coroutine viene eseguita in ogni frame update fino a quando incontra l’istruzione yield, che causa un ritorno del controllo a Unity. Nel frame successivo l’esecuzione riprende da dove era stata interrotta. Una funzione normale invece viene eseguita fino al suo completamento nell’ambito di un singolo frame.
Lo pseudocodice per lo schema base della classe AI_Controller può essere il seguente:

//  AI_CONTROLLER  CLASS
using UnityEngine;
using System.Collections;

public enum AI_STATE {
    IDLE,
    PATROL,
    CHASE,
    DEAD
}

public class AI_Controller : MonoBehaviour {
    // Current state 
    public AI_STATE CurrentState= AI_STATE.IDLE;

    void Awake() {
    } 
   
    void Start() {
    // Activate first state
        StartCoroutine(Activate_State_Idle());
    }
  
// If idle animation is completed change the state. 
// The event OnIdleCompleted is defined in GameObject // Animation 

    public void OnIdleCompleted() {
        StopAllCoroutines();
        StartCoroutine(Activate_State_Patrol());
    }
    
    void Update() {
    }
}

Lo schema base per la coroutine State_Idle può essere il seguente:

//Coroutine for management of idle state
public IEnumerator Activate_State_Idle() {

    // memorize current state
    CurrentState = AI_ENEMY_STATE.IDLE;
  
    // Activate idle state with Mecanim  
    ThisAnimator.SetTrigger("Idle");

    //Loop forever while in idle state
    while(CurrentState == AI_STATE.IDLE) {
        // Check if we can see the player
        if(Player is on sight) {
            StartCoroutine(Activate_State_Chase());
            yield break;
        }
            
        //Wait for next frame
        yield return null;
    }
}

Lo schema per la coroutine relativa allo stato PATROL può essere il seguente:

// Coroutine for management of patrol state
public IEnumerator Activate_State_Patrol(){

    //Set current state
    CurrentState = AI_STATE.PATROL

    // Activate idle state with Mecanim           
    ThisAnimator.SetTrigger("Patrol");

    //Loop forever while in patrol state
    while (CurrentState == AI_STATE.PATROL){       
        //Check if we can see player
        if(Player on sight)  {
            StartCoroutine(Activate_State_Chase());
            yield break;
        }
        
        //Wait for next frame
        yield return null;
    }
}

In modo simile si possono scrivere le altre coroutine.

---

5) Limiti delle macchine a stati finiti

Nonostante gli indubbi vantaggi le FSM presentano problemi di manutenibilità, che si rivelano nella loro gravità nel caso di applicazioni con un grande numero di stati. Un limite in particolare è rappresentato dalla duplicazione del codice nelle varie classi che rappresentano gli stati.
Per evitare la duplicazione del codice nella gestione dei vari stati, una soluzione è quella di definire delle classi intermedie nelle quali scrivere le funzioni comuni. Questa è la soluzione proposta con le cosiddette macchine a stati finiti gerarchiche (HFSM) introdotte D. Harel nel 1984. Una HFSM è sostanzialmente una FSM, nella quale ogni stato può contenere diversi sottostati, come se fosse una FSM separata. Vengono definite due nuove entità:

• Superstato – può contenere uno o più stati semplici
• Transizioni generalizzate fra superstati

Le transizioni generalizzate fra superstati permettono di ridurre le transizioni ridondanti fra stati semplici; una transizione fra superstati può sostituire diverse transizioni fra stati semplici.

Le HFSM rappresentano un modello più efficiente delle semplici FSM. Tuttavia, per le applicazioni sofisticate di intelligenza artificiale rimangono dei limiti intrinseci dovuti alla natura stessa del modello:

• prevedibilità delle azioni
• rigidità del modello

Le condizioni dei singoli stati possono essere troppo rigide in particolari applicazioni. Le FSM gestiscono i cambiamenti di stato mediante una logica discreta: se una variabile si trova in un certo range di valori allora si decide di cambiare stato, altrimenti no. Tuttavia, se le variabili in gioco hanno una natura continua e non discreta (ad esempio la distanza del nemico, il livello di temperatura di una centrale, ecc.), quando i valori sono al limite la decisione da prendere richiede un’analisi più complessa, basata anche su strumenti di natura probabilistica e statistica.

---

Conclusione

Nonostante i loro limiti, le macchine a stati finiti sono ancora strumenti importanti utilizzati dai programmatori. In un prossimo articolo esamineremo i behaviour trees, un modello che offre maggiore flessibilità e migliore gestione della manutenzione per le applicazioni di intelligenza artificiale. 

---

Bibliografia

^[1]I. Millington – AI for Games (CRC Press)

^[2]M. Buckland- Programming Game AI By Example (Jones and Bartlett Learning)