Behavior Tree e il Decision Making (Parte 2)

Nella prima parte di questa serie di articoli sui Behavior Tree abbiamo visto alcune basi teoriche sul loro funzionamento e sulla loro formulazione. Adesso è giunto il momento di mettere in pratica qualche nozione. Lo faremo in Python per semplicità (anche se è un buon linguaggio per questi script di AI anche a livelli avanzati).

Esempio di BT completo


In questo esempio prenderemo in esame l’ultimo BT presentato nello scorso articolo: l’agente che apre una porta chiusa (se è chiusa). Per questo esempio (testuale, per non complicare troppo il codice con librerie esterne) immaginate un agente posto a N passi da una porta (aperta o chiusa). L’agente deve mantenere la porta aperta, se questa è chiusa allora si avvicina e la apre.

Innanzitutto definiamo lo stato del mondo con una classe ad hoc.

class WorldStatus(object) :
    def __init__(self) :
        self.aperta = False   # La porta aperta?
        self.step = 3         # Quanto dista la porta?

A questo punto iniziamo definendo una classe “base” che costituisce il singolo nodo di un BT.

class Task(object):
    """
    Classe base per descrivere un nodo di un Behavior Tree
    """

    def __init__(self) :
        self._children = []
   
    def run(self) :
        pass
   
    def add_child(self,c):
        self._children.append(c)

La classe è composta da due soli metodi:

  • run – Questo metodo esegue il nodo.
  • add_child – Questo metodo serve ad aggiungere dei figli al nodo nel caso non sia una foglia

L’attributo privato _children contiene una lista di Task figli. A partire da questa classe possiamo definire le varie specializzazioni, in particolare il Selector e il Sequence. Per fare questo basta ridefinire il metodo run della classe Task

class Selector(Task):
    """
    Implementazione di un Selector
    """

    def __init__(self):
        super(Selector,self).__init__()
   
    def run(self):
        for c in self._children :
            if c.run() :
                return True
        return False
   
class Sequence(Task):
    """
    Implementazione di un Sequence
    """

    def __init__(self):
        super(Sequence,self).__init__()
       
    def run(self):
        for c in self._children :
            if not c.run() :
                return False
        return True

Le due classi, come si può notare, sono duali. Il Selector si limita ad eseguire i nodi figli fino a quando non ne trova uno che restituisce il valore vero e nel caso ritorna con successo. Il Sequence invece esegue i nodi figli fino a quando non ne trova uno che restituisce falso e nel caso ritorna con un fallimento.

Fino a questo punto l’implementazione del BT è generica. Possiamo usare lo stesso codice per qualunque progetto e qualunque comportamento dell’AI. Il momento della “specializzazione” coinvolge solamente i nodi foglia e quindi le specifiche azioni da eseguire.

Nel nostro esempio le azioni sono tre: controllare se la porta è aperta, avvicinarsi alla porta e aprire la porta. Tutte queste azioni ereditano dalla classe Task e prendono lo stato del mondo come attributo aggiuntivo (le azioni devono leggere e interagire con il mondo). Potete vedere il codice di queste azioni nell’esempio sottostante.

class PortaAperta(Task):
    def __init__(self,status):
        super(PortaAperta,self).__init__()
        self._status = status
   
    def run(self):
        if self._status.aperta :
            print("La Porta è aperta")
        else :
            print("La Porta è chiusa!")
        return self._status.aperta
     
class Avvicinati(Task):
    def __init__(self,status):
        super(Avvicinati,self).__init__()
        self._status = status
   
    def run(self):
        if self._status.step>0 :
            print("Mi avvicino!")
            self._status.step -= 1
            return True
        return False
   
class Apri(Task):
    def __init__(self,status):
        super(Apri,self).__init__()
        self._status = status
   
    def run(self):
        if self._status.step != 0 :
            print("Ancora troppo lontano!")
            return False
        print("Apro la porta!")
        self._status.aperta = True        
        return True

A questo punto non ci resta che assemblare l’albero nell’immagine iniziale ed eseguirlo.

# MAIN #
def main() :
    # Definisco i nodi funzionali
    root = Sequence()
    seq = Sequence()
    sel = Selector()
   
    # Creo lo stato del mondo
    status = WorldStatus()
   
    # Creo le azioni
    checkaperta = PortaAperta(status)
    avvicinati = Avvicinati(status)
    apri = Apri(status)

    # Assemblo l'albero
    root.add_child(sel)
   
    sel.add_child(checkaperta)
    sel.add_child(seq)
   
    seq.add_child(avvicinati)
    seq.add_child(apri)
   
    bt = BehaviorTree(root)

    # Eseguo la radice finché non ritorna vero
    while not root.run() :
        print("---")

Una volta assemblato l’albero eseguiremo il nodo radice finché non ritornerà vero (segnalandoci che la porta è aperta). Semplice. Dopo tutto questo qual’è il risultato? Ecco l’output del programma nello stato descritto in WorldStatus.

La Porta è chiusa!
Mi avvicino!
Ancora troppo lontano!
---
La Porta è chiusa!
Mi avvicino!
Ancora troppo lontano!
---
La Porta è chiusa!
Mi avvicino!
Apro la porta!

Ovviamente per ottenere un risultato simile non serve scomodare i BT ma spero siano chiari i vantaggi di tale implementazione.

  • I nodi funzionali non dipendono dal contesto. Questo significa che è possibile creare una libreria di nodi funzionali ed utilizzarla in ogni progetto tale e quale.
  • È possibile riutilizzare e spostare in libreria delle “azioni generiche” in modo da massimizzare la riusabilità del codice. Dopotutto nei videogiochi ci sono molte azioni sempre uguali (movimento, controllo di condizioni, linee di vista e via discorrendo). È possibile riutilizzare interi alberi o anche particolari sotto alberi creando librerie di comportamenti standardizzati.
  • L’AI può essere costruita e modificata in run-time con estrema facilità. Una volta definita una gamma di azioni gli alberi possono essere descritti in XML e assemblati in modo automatico da un modulo specifico. Questo permette di non dover ricompilare il progetto durante il tuning o la modifica delle componenti di AI. Inoltre questo apre anche la strada al modding.

Una piccola nota nel finale. Fino ad ora abbiamo utilizzato i valori vero/falso per indicare i valori di ritorno. Questo non è una condizione necessaria. È possibile utilizzare anche valori più complessi (come una enum) per indicare una gamma di valori di ritorno più varia. È bene farlo subito a meno che non si è sicuri che non serva mai perché modificare tutti i nodi per adattarli ad una nuova serie di valori di ritorno è un compito lungo e noioso.

A questo punto avete anche un esempio di applicazione dei BT. Tutto qui? No. C’è ancora qualcosa che dobbiamo vedere e che è di importanza fondamentale per l’utilizzo dei BT nei videogame reali. In un gioco vengono eseguiti molti BT contemporaneamente (uno per ogni agente sullo schermo) e spesso per problemi prestazionali non si possono eseguire interamente in ogni frame. Dobbiamo quindi vedere come parallelizzare la loro esecuzione e renderli interrompibili in modo da ovviare a questi limiti. Vedremo tutto nella terza parte.

PS: Il codice utilizzato in questo articolo lo trovate qui su Gist.

Comments are closed.