Follow

Questa è l’ultimo articolo per il momento sui BT. L’argomento necessiterebbe ulteriore trattazione ma direi che per avere un’idea di cosa sono, come funzionano e come si implementano è sufficiente.

In questa parte completeremo i BT andando a rispondere ad alcune domande che sorgono spontanee durante il passaggio da “esempio didattico” a “applicazione reale”.

Parallelizzazione e Concorrenza

Il primo problema che ci viene in mente nella pratica è gestire una moltitudine di BT.In un videogioco qualsiasi è molto probabile trovarsi davanti più di un nemico alla volta e poiché, in generale, ogni BT comanda un solo agente è necessario avere almeno un BT per ogni personaggio non giocante sullo schermo.

Il secondo problema invece riguarda il tempo. Nelle precedenti sezioni abbiamo assunto che ogni azione fosse eseguita istantaneamente. In un gioco reale questo non è possibile poiché, per esempio, l’azione “avvicinati alla porta” impiega del tempo fisico non trascurabile (che consiste nel tempo di eseguire l’animazione del personaggio che si sposta verso la porta). Dobbiamo quindi essere in grado di arrestare l’esecuzione del BT e, soprattutto, essere in grado di riprendere l’esecuzione dall’ultimo nodo eseguito.

Questi problemi non sono risolvibili a meno che di non introdurre il concetto di concorrenza nel gioco e in particolare nei BT.

All’interno di ogni schifosa creatura sullo schermo (almeno fino a prima di venire uccisa) batte il meccanico cuore di un BT.

L’idea da cui partire è di eseguire un BT in ogni thread. I BT diventano leggermente più complessi poiché ogni thread dovrà memorizzare l’ultimo nodo eseguito e gestire la concorrenza (semafori, race-condition, e tutta quella fastidiosa compagnia) ma avremo il vantaggio di poter semplicemente mettere in pausa ogni BT all’occorrenza e soprattutto la possibilità di eseguirne più di uno alla volta.

Ma l’introduzione alla concorrenza ci permette di espandere maggiormente la potenza di un BT anche all’interno dello stesso albero. A tale proposito possiamo introdurre un nuovo nodo: il parallelo

Il concetto alla base del nodo parallelo è lo stesso di quello del sequence (esegue tutti i figli fino al primo che fallisce) con la differenza che tutti i figli vengono eseguiti in contemporanea.

Questo può essere molto utile nel caso dell’esecuzione di azioni che possono essere eseguite in parallelo. Ad esempio possiamo scrivere un BT che comandi un gruppo di nemici ed usare il parallelo per far eseguire contemporaneamente delle azioni alla squadra (ad esempio appostarsi o fare fuoco di copertura).

La concorrenza nei BT è un punto molto complesso e potente della tecnica, per maggiori e dettagliate informazioni vi rimando al libro “Artificial Intelligence for Games” di Ian Millington.

Dati nei Behavior Tree

La maggior parte dei dati necessari ad un BT vengono acceduti direttamente dalla memoria di gioco. Non è insolito però trovarsi davanti alla necessità di immagazzinare dati all’interno dello stesso BT. È possibile ad esempio avere la necessità che una o più azioni abbiano bisogno di un target oppure di uno o più parametri. Allo stesso tempo però non vogliamo rovinare l’API del nostro BT inserendo parametri a destra e a manca.

La soluzione esiste e consiste in una struttura dati a lavagna (blackboard). La lavagna può essere vista come una zona della memoria in cui ogni nodo del BT può scrivere o leggere dati di qualunque genere durante la sua esecuzione. Nell’esempio del “target” ad esempio possiamo avere un nodo che scriva sulla lavagna

target: enemy-44fb

mentre in un altro nodo è possibile accedere a questi dati solamente conoscendo la chiave “target”.

Al’atto pratico una lavagna può essere vista come un dizionario eterogeneo di dati accessibile da ogni nodo che conosca la chiave.

La lavagna può essere aggiunta globalmente (ogni BT ha una sua lavagna) accessibile da ogni nodo. Oppure possiamo inserire le lavagne in modo gerarchico tramite un decoratore che renda accessibile la lavagna X a tutto il sottoalbero (in questo modo ogni nodo può accedere solo alle lavagne inizializzate in un suo antenato).

Limiti di un Behavior Tree

Come era facile immaginare anche i BT hanno i loro limiti. Il limite principale è strutturale: i BT si comportano bene fintanto il comportamento che vogliamo modellare può essere convenientemente descritto come reazioni a successi o fallimenti. Tuttavia questo non è sempre il caso.

Molti agenti dovrebbero reagire ad eventi esterni, cambiare strategia “a caldo” per sfruttare debolezze avversarie, pianificare delle azioni con un raggio di azione più elevato del primo successo/fallimento. In tutti questi casi complessi BT si comportano come una mosca che vuole uscire dalla finestra: continua a sbattere al vetro fino a quando casualmente non si trova davanti alla vera apertura.

Esistono soluzioni? Ovviamente. L’evoluzione più promettente (ma non ancora molto diffusa) è quella introdotta da Fear: si chiama Goal-Oriented Action Planning (GOAP) ed è un applicazione al mondo videoludico della tecnica di AI chiamata STRIPS conosciuta da decenni. Magari ne parleremo in un futuro.

Per il momento è tutto. I BT (nonostante i loro limiti) rappresentano un’incredibile tecnica per progettare in breve tempo e in modo pratico qualsiasi AI per qualsiasi agente ed hanno rappresentato il più grande salto “evolutivo” nell’AI dei giochi di consumo dell’ultimo decennio.

Spero di aver trattato in modo discreto l’argomento, almeno in quanto introduzione. Ora siete pronti ad addentrarvi nel mare di dettagli che i BT nascondono. Buon divertimento. 🙂