Un nemico che si dirige in linea retta verso il giocatore funziona finché non c'è un muro in mezzo. A quel punto resta bloccato contro l'ostacolo, e l'illusione di intelligenza svanisce. Per muoversi in un livello con muri, porte e corridoi, i personaggi hanno bisogno di pathfinding: un algoritmo che calcoli un percorso percorribile dal punto di partenza alla destinazione. Su una griglia, il metodo più usato è A*.
Il livello come grafo
Il primo passo è rappresentare lo spazio come un grafo. Su una mappa a tasselli è immediato:
- ogni cella percorribile è un nodo;
- ogni coppia di celle adiacenti percorribili è collegata da un arco;
- ogni arco ha un costo, per esempio 1 per un passo ortogonale.
Si possono assegnare costi diversi a terreni diversi: una palude può costare 3, una strada 1. L'algoritmo cercherà il percorso di costo totale minimo, non necessariamente quello con meno passi.
L'idea di A*
A* esplora i nodi partendo dall'origine e sceglie sempre per primo quello che sembra più promettente. Per ogni nodo n calcola:
g(n): il costo reale del percorso migliore trovato finora dall'origine an;h(n): una stima del costo danalla destinazione, chiamata euristica;f(n) = g(n) + h(n): la stima del costo totale passando pern.
L'algoritmo mantiene due insiemi: la lista aperta, con i nodi da esaminare, e la lista chiusa, con quelli già elaborati.
aperta = {origine}; g[origine] = 0
finché aperta non è vuota:
corrente = nodo in aperta con f minimo
se corrente == destinazione: ricostruisci il percorso
sposta corrente da aperta a chiusa
per ogni vicino v di corrente non in chiusa:
nuovo_g = g[corrente] + costo(corrente, v)
se v non in aperta o nuovo_g < g[v]:
g[v] = nuovo_g
padre[v] = corrente
aggiungi v ad aperta con f = nuovo_g + h(v)
Il percorso si ricostruisce partendo dalla destinazione e seguendo i padri fino all'origine.
La scelta dell'euristica
L'euristica guida la ricerca. Se non sovrastima mai il costo reale, si dice ammissibile e A* garantisce di trovare il percorso ottimo. Le più comuni su griglia:
| Movimento consentito | Euristica | Formula |
|---|---|---|
| Solo 4 direzioni | Distanza di Manhattan | abs(dx) + abs(dy) |
| 8 direzioni, diagonale costo 1 | Distanza di Chebyshev | max(abs(dx), abs(dy)) |
| 8 direzioni, diagonale costo √2 | Distanza ottagonale | max + (√2 − 1) · min |
| Movimento libero | Distanza euclidea | √(dx² + dy²) |
Con un'euristica pari a zero, A* diventa l'algoritmo di Dijkstra: trova sempre il percorso ottimo ma esplora molti più nodi. Con un'euristica che sovrastima, per esempio moltiplicata per 1,5, la ricerca è più rapida ma il percorso può non essere il migliore: in un gioco è spesso un compromesso accettabile.
Movimento diagonale e spigoli
Se si permettono le diagonali, bisogna impedire di «tagliare» gli angoli dei muri: un passo diagonale tra due celle solide farebbe passare il personaggio attraverso uno spigolo. La regola tipica consente la diagonale solo se entrambe le celle ortogonali adiacenti sono libere.
Prestazioni
Il punto critico è trovare rapidamente il nodo con f minimo nella lista aperta. Scorrere una lista a ogni passo è lento; una coda di priorità, implementata con un heap binario, riduce molto il costo. Altri accorgimenti:
- usare array indicizzati per cella invece di dizionari per
g, padri e stato; - limitare il numero di nodi esplorabili per richiesta, interrompendo le ricerche impossibili;
- distribuire le richieste di molti nemici su più fotogrammi;
- ricalcolare il percorso solo quando la destinazione si sposta in modo significativo, non a ogni passo.
Percorsi più naturali
Il percorso su griglia tende a essere spezzato, con zigzag evidenti. Due correzioni migliorano molto il risultato:
- smussatura: si eliminano i punti intermedi quando esiste una linea di vista libera tra due punti non consecutivi;
- inseguimento del percorso: il personaggio non salta da cella a cella ma si dirige verso un punto qualche passo più avanti lungo il percorso, con movimenti fluidi.
Molte unità, una destinazione
Nei giochi di strategia o con orde di nemici, calcolare A* per ciascuna unità verso lo stesso obiettivo è uno spreco. Un campo di flusso risolve il problema al contrario: si esegue una sola ricerca a partire dalla destinazione, che assegna a ogni cella la distanza dall'obiettivo. Ogni unità guarda poi la propria cella e si muove verso il vicino con distanza minore. Il costo non dipende più dal numero di unità.
Oltre la griglia
Nei giochi 3D o con mappe non a tasselli si usano le navigation mesh: poligoni convessi che coprono le aree percorribili. A* opera sui poligoni invece che sulle celle, con molti meno nodi. I principali motori offrono strumenti per generarle automaticamente dalla geometria del livello.
In sintesi
- Il pathfinding trasforma il livello in un grafo di nodi e archi con costi.
- A* sceglie sempre il nodo con la stima di costo totale più bassa.
- Un'euristica ammissibile garantisce il percorso ottimo; sovrastimare accelera la ricerca.
- Code di priorità, limiti e ricalcoli rari mantengono buone le prestazioni.
- Campi di flusso e navigation mesh estendono le idee a molte unità e a mondi 3D.
