Se sei uno sviluppatore di giochi, potresti aver sempre voluto implementare A* come pathfinding dei personaggi (o nemici). So che un paio di anni fa l’ho fatto, ma con il mio livello di programmazione all’epoca ho avuto problemi con gli articoli attuali là fuori. Ho voluto scrivere questo come una facile introduzione con un chiaro esempio di codice sorgente per il pathfinding A* in modo che chiunque possa facilmente prenderlo e usarlo nel proprio gioco.
Un aspetto importante di A* è f = g + h. Le variabili f, g e h sono nella nostra classe Node e vengono calcolate ogni volta che creiamo un nuovo nodo. Velocemente andrò oltre il significato di queste variabili.
- F è il costo totale del nodo.
- G è la distanza tra il nodo corrente e il nodo iniziale.
- H è l’euristica – distanza stimata dal nodo corrente al nodo finale.
Diamo un’occhiata ad un rapido grafico per aiutare ad illustrare questo.
Fantastico! Diciamo che node(0) è la nostra posizione iniziale e node(19) la nostra posizione finale. Diciamo anche che il nostro nodo attuale è al quadrato rosso node(4).
G
G è la distanza tra il nodo attuale e il nodo iniziale.
Se contiamo all’indietro possiamo vedere che node(4) è a 4 spazi dal nostro nodo iniziale.
Possiamo anche dire che G è 1 più del nostro nodo padre (node(3)). Quindi in questo caso per node(4), currentNode.g = 4.
H
H è l’euristica – distanza stimata dal nodo corrente al nodo finale.
Quindi calcoliamo la distanza. Se diamo un’occhiata vedremo che se andiamo oltre 7 spazi e su 3 spazi, abbiamo raggiunto il nostro nodo finale (node(19)).
Applichiamo il Teorema di Pitagora! a² + b² = c². Dopo averlo applicato, vedremo che currentNode.h = 7² + 3². Oppure currentNode.h = 58.
Ma non dobbiamo applicare la radice quadrata a 58? No! Possiamo saltare quel calcolo su ogni nodo e ottenere lo stesso risultato. Intelligente!
Con un’euristica, dobbiamo assicurarci di poterla effettivamente calcolare. E’ anche molto importante che l’euristica sia sempre una sottostima del percorso totale, poiché una sovrastima porterà A* a cercare attraverso nodi che potrebbero non essere i “migliori” in termini di fvalore.
F
F è il costo totale del nodo.
Perciò sommiamo h e g per ottenere il costo totale del nostro nodo. currentNode.f = currentNode.g + currentNode.h. Oppure currentNode.f = 4+ 58. Oppure currentNode.f = 62.
Tempo di usare f = g + h
Va bene, questo era un sacco di lavoro. Ora con tutto quel lavoro, per cosa userò questo valore f?
Con questo nuovo valore f, possiamo guardare tutti i nostri nodi e dire: “Ehi, questo è il miglior nodo che posso scegliere per andare avanti in questo momento? Piuttosto che passare attraverso tutti i nodi, possiamo scegliere quelli che hanno la migliore possibilità di portarci al nostro obiettivo.
Ecco un grafico per illustrare. In alto abbiamo l’algoritmo di Dijkstra, che cerca senza questo valore f, e sotto abbiamo A* che usa questo valore f.
Algoritmo di Dijkstra
Dando un’occhiata all’algoritmo di Dijkstra, vediamo che continua a cercare. Non ha idea di quale nodo sia il ‘migliore’, quindi calcola percorsi per tutti.
Algoritmo A*
Con A*, vediamo che una volta superato l’ostacolo, l’algoritmo dà la priorità al nodo con il più basso fe la ‘migliore’ possibilità di raggiungere la fine.