di  -  giovedì 16 giugno 2011

Introduzione

Dopo aver introdotto l’isometria, possiamo affrontare un importante e delicato argomento che riguarda da vicino anche l’IA presente in un gioco. Quello di cui stiamo per parlare è : “la ricerca del percorso”.

In molti videogame il giocatore muove personalmente il suo alter-ego, senza preoccuparsi di calcolare gli spostamenti verso un dato punto. Questo purtroppo non accade per i personaggi non giocanti e nemmeno in alcune specifiche categorie di videogiochi, come per esempio gli strategici.

Che il gioco sia in 2D o in 3D, quello che abbiamo visto con l’isometria ci viene comunque in aiuto. Infatti, per ricercare il percorso tra due precisi punti della mappa, si cerca di suddividere quest’ultima in una griglia. Più precisamente, si costruiscono dei nodi collegati tra di loro così come sono adiacenti sul terreno. Attraversare i nodi sarà come attraversare la mappa.

Con queste poche parole però, siamo già andati molto oltre le basi spiegate in quest’articolo. Infatti ci sono dei punti che, a seconda di come sono delineati, cambiano l’esperieza di gioco :

  • Tipo dei nodi (quadrati, esagoni ecc…). In questo modo cambiano il numero di figure adiacenti al singolo nodo e quindi cambia anche il modo con cui si deve scegliere il miglior percorso (anche se non di molto, solo per la parte che riguarda i nodi adiacenti).
  • Come il giocatore deve percorrere il tragitto trovato
  • Qualità e quantità di nodi presenti sulla mappa

Gli ultimi due punti sono molto vasti e pieni di argomenti. Per esempio, più punti sono presenti sulla mappa, più gli spostamenti saranno precisi e veritieri (ma sarà più lenta la ricerca, non dobbiamo mai dimenticare le prestazioni, visto che non si dovrebbero superare i centesimi di secondo). Inoltre bisogna considerare se il giocatore deve prevedere nei suoi spostamenti anche la presenza di altri giocatori od oggetti in movimento. Possiamo anche decidere di preferire percorsi che attraversano parti della mappa meno pericolose ed impervie. Questi sono alcune delle problematiche che possono essere sollevate.

Tutti questi piccoli aspetti, variano da gioco a gioco, anche a seconda dei gusti dei programmatori. In questo esempio vedremo solo come far muovere su una semplice mappa il nostro giocatore.

Il programma potrà essere riutilizzato per una visione isometrica, visto che la parte grafica è completamente staccata dal meccanismo della ricerca del percorso. Infatti si può “lavorare” sui nodi (le nostre piastrelle nell’esempio dell’isometria, per intenderci) come se fossero parti della mappa esistente o semplicemente facendogli formare una mappa specchio, che viede utilizzata solo per questa ricerca. In questo esempio, la mappa sarà creata e gestita come abbiamo visto per l’isometria (quindi con un array), ma graficamente scarna per far intravedere il lavoro che avviene durante la ricercare del percoso più breve.

Prima di iniziare a vedere il codice, vorrei precisare che parleremo dell’Algoritmo A* (A-Star) e che ho preparato una traduzione del sito che ho utilizzato come riferimento:

http://www.policyalmanac.org/games/aStarTutorial.htm

Ringrazio l’autore per la disponibilità.

Il tutto verrà rilasciato in fondo all’articolo. Tenete conto che la traduzione potrebbe non presentarsi bellissima in italiano, ma i concetti chiave sono presentati facilmente e vi sarà molto utile come base per le vostre implementazioni e per la lettura delle parti sottostanti. Inoltre il codice che rilascio è, per questa volta, completo di commenti, così da evitare ulteriori dubbi durante la sua lettura.

Per comodità, analizzerò solo le parti salienti, ovvero come sono costituiti i nodi e come procede l’algoritmo.

class Nodo():
    """
    Rappresenta un nodo della griglia
    """
    def __init__(self,xy,num,screen,walkable = True):
        self.xy = xy
        self.center = (xy[0]+50,xy[1]+50)
        self.rect = pygame.Rect(xy,(100,100))
        self.num = num
        self.walkable = walkable
        self.screen = screen
        self.G = 0
        self.H = 0
        self.F = 0
        self.prev = None

La classe nodo si trova nel file principale per eseguire il programma. Naturalmente potete posizionarla all’interno del vostro engine di gioco per affiancarla al rendering grafico. Infatti come vedete, non necessita di molte informazioni in più rispetto quelle che si dovrebbero avere per una normale piastrella della mappa. Però sono essenziali ed importantissime :

  • G = Rappresenta il costo di movimento per raggiungere questo nodo, dal nodo precedente.
  • H = Rappresenta il costo (o distanza) per raggiungere l’obbiettivo. Si può definire in vari metodi. Quello utilizzato in questo esempio è detto metodo di Manhattan, che calcola questa distanza sommando il numero di nodi che servono per raggiungere l’obbiettivo orizzontalmente e verticalmente e poi lo moltiplica per 10. Potete capire meglio il perché di questa operazione leggendo la traduzione del sito di riferimento che ho allegato in quest’articolo.
  • F = E’ semplicemente la somma di G ed H.
  • prev = Il nodo che precede quello corrente (collegati naturalmente dal percorso più breve).

Questi sono i parametri essenziali per andare avanti. Se dal codice non comprendete il procedimento e/o la logica con cui è stato affrontato il problema, vi consiglio ancora di leggere il file pdf allegato, sopratutto perché queste parti possono essere soggette a variazioni che riguardano applicazioni e/o scelte specifiche prese per un determinato gioco.

Vediamo allora come si dovrebbe procedere per cercare il nostro percorso (ed il più breve) attraverso i nodi (mappa) disponibili:

class A_Star():
    """
    Classe per la ricerca del percorso
    """
    def __init__(self,nodi,partenza,arrivo):
        """
        Inizializza l'algoritmo per la ricerca e lo esegue
        """
        if partenza is None or arrivo is None:
            return

        self.lista_aperta = []
        self.lista_chiusa = []
        self.nodi = nodi

        # Setto F,G,H del nodo di partenza
        self.nodi[partenza[1]][partenza[0]].set(arrivo)

        # Metto il nodo di partenza nella lista aperta
        heapq.heappush(self.lista_aperta,(self.nodi[partenza[1]][partenza[0]].F,self.nodi[partenza[1]][partenza[0]]))

        vicini = [] # Lista per mantenere i nodi vicini

        while len(self.lista_aperta)>0 :

            # Recupero il nodo corrente
            nodo_corrente = heapq.heappop(self.lista_aperta)

            # Controllo se il nodo corrente è l'obbiettivo
            if nodo_corrente[1].num == arrivo:
                self.lista_chiusa.append(nodo_corrente[1])
                break

            # Aggiungo il nodo corrente alla lista chiusa
            self.lista_chiusa.append(nodo_corrente[1])

            # Recupero i nodi vicini a quello corrente
            xx,yy = nodo_corrente[1].num
            del vicini[:]
            for y in range(yy-1,yy+2):
                for x in range(xx-1,xx+2):
                    if not (x == nodo_corrente[1].num[0] and y == nodo_corrente[1].num[1]):
                        if self.nodi[y][x].walkable:
                            vicini.append(self.nodi[y][x])

            # Controllo se i rimanenti si trovano nella lista aperta
            # se No, li aggiungo alla lista aperta, mettendo come padre
            # il nodo corrente.
            # se SI, confronto le G passando per il quadrato corrente
            # per vedere se c'è un percorso migliore.
            # Controllo anche se il nodo è presente nella lista chiusa
            # se SI, confronto le G passando per il quadrato corrente.
            # Quando trovo un percorso migliore, si aggiorna opportunamente
            # il nodo padre.

            for vic in vicini:
                esiste = False
                for x in self.lista_aperta:
                    if vic.num == x[1].num:
                        esiste = True
                        if (self.calcola_G(nodo_corrente[1].num,vic.num) + self.calcola_G(vic.num,x[1].num)) < x[1].G:
                            x[1].set(arrivo,vic)
                            break

                for x in self.lista_chiusa:
                    if vic.num == x.num:
                        esiste = True
                        if (self.calcola_G(nodo_corrente[1].num,vic.num) + self.calcola_G(vic.num,x.num)) < x.G:
                            x.set(arrivo,vic)
                            break

                if not esiste:
                    vic.set(arrivo,nodo_corrente[1])
                    heapq.heappush(self.lista_aperta,(vic.F,vic))

    def punti(self):
        """
        Ritorna le coordinate che il giocatore deve seguire
        """
        temp = self.lista_chiusa[-1]
        punti = []

        while temp.prev != None:
            punti.append(temp.center)
            temp = temp.prev

        return punti[::-1]

Iniziamo con il creare due liste, una denominata “aperta” ed una “chiusa”. La prima sarà gestita come un heap, così da migliorare la velocità ed il rendimento, poiché sarà molto più semplice estrarre il nodo con il più piccolo valore di F, visto che si troverà sempre in testa. Questa naturalmente è solo un’ottimizzazione, potete benissimo utilizzare le liste, magari per fare qualche esperimento.

Preparato il nodo di partenza, lo posizioniamo nella lista aperta e creiamo una lista per memorizzare i nodi adiacenti. A questo punto comincia un ciclo per ricercare il nostro percorso, che avrà come condizione di uscita o la lista aperta vuota (quindi il percorso non esiste), oppure il raggiungimento dell’obbiettivo (ed in questo caso il tragitto sarà il più breve).

Il ciclo sostanzialmente preleva il nodo con costo minore di movimento (quindi con la F più piccola) dalla lista aperta e lo mette in quella chiusa. Poi si passano al setaccio i nodi adiacenti a quello selezionato; quindi si controlla se sono già presenti in una delle due liste, per verificare l’esistenza di un percorso migliore, altrimenti si aggiungono semplicemente come prossimi candidati nella lista aperta.

Una volta completato il procedimento, la lista chiusa conterrà i nodi che dobbiamo percorrere per arrivare all’obbiettivo. In questo caso, basterà richiamare la funzione punti() per partire dall’obbiettivo ed andare a ritroso verso l’origine (ecco spiegata la presenza di prev nei nodi), memorizzando mano a mano i punti da attraversare per poi ritornarli in una comoda lista.

Conclusioni

Spero che l’articolo non sia troppo dispersivo, ma ho preferito far luce sui procedimenti e le scelte chiave, visto che è corredato da materiale molto esplicativo. L’applicazione è banale e non sono state previste molte cose. Per esempio si potrebbe utilizzare una variabile booleana per avvertire il giocatore quando il percorso non esiste e di conseguenza non far muovere il personaggio sullo schermo.

Altre varianti e/o miglioramenti sono sempre presenti nel materiale correlato. Con i prossimi articoli finiremo questo viaggio nelle due dimensioni per passare al 3D, senza staccarci da python, naturalmente…

Downloads:

L’esempio è stato compresso utilizzando 7zip. Le azioni disponibili sono le seguenti:

  1. Tasto sinistro del mouse : indica nodo da raggiungere
  2. Tasto centrale del mouse : resetta il contenuto dei nodi della mappa
  3. Tasto destro del mouse : rende un nodo non attraversabile e viceversa

6 Commenti »

I commenti inseriti dai lettori di AppuntiDigitali non sono oggetto di moderazione preventiva, ma solo di eventuale filtro antispam. Qualora si ravvisi un contenuto non consono (offensivo o diffamatorio) si prega di contattare l'amministrazione di Appunti Digitali all'indirizzo info@appuntidigitali.it, specificando quale sia il commento in oggetto.

  • # 1
    Antonio Barba
     scrive: 

    Ottimo :-) l’algoritmo A*, nonostante la sua semplicità, è fondamentale per ogni game developer che si rispetti :-)

    Come hai giustamente detto ci sono dei casi più complessi, soprattutto con ostacoli mobili lungo la mappa, ma di solito si parte sempre da A* per il “percorso globale” e si tenta di risolvere “localmente” eventuali problemi di ostacoli mobili tramite un’euristica, per poi ricollegarsi al tracciato precalcolato con A* una volta risolto l’ostacolo.

  • # 2
    Mirco Tracolli
     scrive: 

    @ Antonio

    Infatti nel pdf allegato si accennano a queste soluzioni (che sono sempre parte dell’articolo originale a cui ho fatto riferimento). Magari nei futuri articoli, quando si presenterà il problema, tratterò separatamente l’argomento.

    Intanto per iniziare mi sembra il minimo e poi in python, gestire gli heap è stato troppo facile, ancora non ci credo :D

  • # 3
    Xeus32
     scrive: 

    Un bel articolo su un classico degli algoritmi!
    Penso che i due algoritmi fondamentali per i Game Developer A* e FSM.
    Questi sono proprio i fondamentali altro che OpenGL.

    Se volete leggere altri articoli di ottimo livello http://www.emanueleferonato.com/

  • # 4
    Z80Fan
     scrive: 

    Articolo interessante :)

    Come si può gestire il fatto di non trovare un percorso? Magari quando si cerca di accedere ad una zona completamente chiusa. Nell’esempio la pallina tende ad andare nel quadrato in basso a destra; immagino sia un dettaglio dell’implementazione.

    Premettendo che non ho letto il pdf: pensi che si possa usare anche un algoritmo Djikstra? Forse quest’ultimo tende ad usare più memoria dell’ A* ?

  • # 5
    Mirco Tracolli
     scrive: 

    @Z80Fan

    La cosa più semplice da fare è controllare se la lista aperta è uguale a zero. In questo caso, il percorso non esiste. Per fare questo basta modificare la funzione punti() dell’algoritmo:

    def punti(self):
            if len(self.lista_aperta)!=0:
                temp = self.lista_chiusa[-1]
                punti = []
        
                while temp.prev != None:
                    punti.append(temp.center)
                    temp = temp.prev        
            
                return punti[::-1]
    

    In questo modo, se il percorso non esiste, il giocatore non si muove.

    L’algoritmo di Djikstra è utile quando non si conosce la destinazione e bisogna trovare subito il miglior percorso per arrivarci. Come esempio nel pdf c’è una unità che cerca le risorse. Sappiamo in che zona si trovano, ma per trovare la più vicina con A* dovremmo ripetere l’algoritmo tante volte quante sono le risorse in quella zona. Mentre con Djikstra basta eseguirlo una volta, poiché ritornerà subito il più vicino, espandendosi a macchia d’olio sulla mappa. Spero di essermi spiegato bene :D .

    PS : utilizzare Djikstra è come avere la H sempre uguale a 0 nell’algoritmo A* (come c’è scritto nel pdf :P)

    @ Xeus32

    Grazie del sito, lo tenevo già tra i preferiti e mi hai ricordato di darci un’occhiata :D

  • # 6
    Antonio Barba
     scrive: 

    Diciamo che, nel caso peggiore, A* si comporta come Dijkstra.

    La differenza sta nel fatto che nell’algoritmo di Dijkstra i nodi vengono pescati dallo stack in modo arbitrario, mentre in A* la “pesca dei nodi” avviene in base alla bontà della funzione euristica.

    A parte questo, sono assolutamente due algoritmi identici. A* è in realtà un’affinamento di Dijkstra (algoritmo generale per qualsiasi grafo) attuabile soltanto quando esiste una relazione tra i nodi del grafo di tipo spaziale e misurabile tramite una norma (la distanza tra due punti ad esempio è una norma geometrica).

Scrivi un commento!

Aggiungi il commento, oppure trackback dal tuo sito.

I commenti inseriti dai lettori di AppuntiDigitali non sono oggetto di moderazione preventiva, ma solo di eventuale filtro antispam. Qualora si ravvisi un contenuto non consono (offensivo o diffamatorio) si prega di contattare l'amministrazione di Appunti Digitali all'indirizzo info@appuntidigitali.it, specificando quale sia il commento in oggetto.