Follow

Cosa hanno in comune l’AI di Pac-Man, icona dei videogame comparso nel lontano 1980, e Halo: Combat Evolved, spara-tutto campione di incassi del 2001? A separarli ci sono quasi 21 anni di differenza, vent’anni di evoluzione che ci ha portato da una serie di pixel semi-antropomorfi a un mondo 3D immersivo. Eppure in pratica in questi vent’anni l’AI nei vedeogiochi non è cambiata poi molto: sebbene l’aumento delle prestazioni dei PC abbia permesso agli algoritmi di AI di valutare un numero maggiore di variabili l’algoritmo alla base è rimasto grossomodo lo stesso.

Fino al 2004 infatti il decision making nei videogiochi si basava semplicemente sulle macchine a stati (o automi a stati finiti). Il concetto alla base di questa tecnica è piuttosto semplice.

Supponiamo di voler progettare l’AI di un nemico in un videogioco. L’approccio a stati consiste nel descrivere i vari stati in cui il nemico può trovarsi (ad esempio può essere nello stato AVVICINATI in cui si avvicina al giocatore o SCAPPA in cui se la da a gambe) e delle transazioni fra stati che corrispondono ad eventi che fanno passare il nostro agente da uno stato all’altro (ad esempio quando la vita del nemico scende sotto i 20 punti, entra nello stato SCAPPA e si allontana dal giocatore).

Le macchine a stati sono facili da implementare, facili da comprendere e con ottime prestazioni (ad ogni iterazione si fa solamente un check su tutte le transizioni dello stato attuale). Di contro questo metodo è difficile da mantenere (aggiungere e rimuovere uno stato comporta un bel po’ di lavoro su tutta la macchina) e inoltre non permettono una grande espressività senza aumentare esponenzialmente il numero degli stati. Eppure nonostante questo sono stati la base dell’AI dall’alba dei videogame fino al recentissimo 2004.

Nel 2004 fa infatti la sua comparsa Halo 2 con una nuova tecnica che ha rivoluzionato l’AI nei videogame: i behavior tree. I BT, nel loro tentativo di aumentare l’espressività e la riusabilità delle macchine a stati mantenendone intatta la semplicità, sono talmente apprezzati che le hanno soppiantate quasi del tutto. Ma vediamoli nel dettaglio.

Come spiega anche il nome i BT sono alberi (e non grafi come le macchine a stati). Le foglie di tali alberi corrispondono a delle azioni che l’agente può eseguire mentre i nodi interni sono nodi funzionali che descrivono secondo quale politica si deve scendere al livello inferiore dell’albero.

Ogni nodo o foglia ha un valore di ritorno. Nelle foglie tale valore è vero se l’azione corrispondente ha avuto successo (è stata eseguita) e falso altrimenti. Nei nodi interni il valore di ritorno è funzione dei valori di ritorno dei figli.

Iniziamo con un esempio basilare. In figura potete vedere un semplicissimo BT con un nodo funzionale chiamato selector (selettore). Tale nodo esegue i nodi figli da sinistra verso destra fermandosi al primo nodo che ritorna un valore positivo. Nell’esempio specifico un agente con questo BT tenterà prima di attaccare. Se l’attacco va a buon fine allora il selettore ha finito il suo lavoro e termina positivamente. Se invece l’attacco non va a buon fine (non posso attaccare perché sono troppo lontano) passerò all’azione successiva: provocare. Se anche provocare non ha effetto o non può essere eseguito l’agente si limiterà ad osservare il giocatore.

Quest’altro esempio utilizza un nodo sequence (sequenza). Questo nodo è il duale del selettore in quanto termina negativamente al primo figlio che ritorna un valore negativo. In pratica esegue i suoi figli da sinistra verso destra fintanto essi ritornano positivamente. Nel caso in esame l’agente eseguirà in sequenza (da qui il nome):

• 1. Controlla se vede il giocatore
• 2. Si gira
• 3. Scappa.

Il risultato è un agente che scappa nella direzione opposta al giocatore.

Questi due nodi funzionali bastano da se a costruire comportamenti di grande complessità e possono essere ovviamente combinati fra loro.

In questo esempio, in cui vediamo i due nodi funzionali combinati, possiamo riconoscere un BT che modella il comportamento di un agente che deve attraversare una porta.

Oltre a questi due nodi base è possibile definire altri nodi quali:

• Random Selector – Simboleggiato da ~?. È uguale al selector semplice ma esegue i suoi figli in ordine casuale.
• Random Sequence – Simboleggiato da una freccia a zigzag (~>). Come per la sequence classica ma con i nodi eseguiti in ordine casuale.
• Until – È un nodo romboidale con un unico figlio. Questo nodo ripete l’esecuzione del suo unico BT figlio fino a quando quest’ultimo non restituisce valore falso.

Ovviamente nulla vi vieta di inventarvi nuovi nodi funzionali ed utilizzarli nel vostro BT.

Dopo questa piccola introduzione è il momento di andare ad affrontare le problematiche implementative di questa tecnica. Ma questo lo vedremo nella seconda parte.