Il problema del cancello

Negli articoli precedenti ho già toccato un po' il tema dell'arte di ingannare il giocatore come si deve, con il coyote time e i ritocchi alla registrazione dei colpi. Guardando quei casi avrete probabilmente notato che il buon codice di gioco passa parecchio tempo a costruire un modello del mondo che coincida abbastanza bene con quello che una persona si aspetta dal gioco.

Anche con la navigazione nei giochi tocca ricorrere ad altrettanti hack, solo che stavolta non si ha a che fare con la durata di un salto o con lo stato fisico del personaggio così come lo percepisce il giocatore, ma con un mucchio di poligoni, nodi, archi e costi, insomma con tutto ciò che determina il percorso di un NPC sulla mappa. E anche qui bisogna guardare alle aspettative del giocatore nei confronti degli NPC, non alla correttezza del comportamento.

Negli strategici i bot di solito hanno un compito semplicissimo: passare attraverso un cancello, un collo di bottiglia qualsiasi, aggirare un muro e ritrovarsi nel cortile; e finché abbiamo un solo soldato che cammina su una mappa vuota, non c'è nessun problema particolare. Basta però aggiungere sulla mappa dieci, cinquanta, cento, duecento soldati e un unico cancello, attraverso il quale fisicamente riescono a infilarsi solo poche unità alla volta, e si scopre che non ci passano, anche se l'algoritmo di pathfinding (tipo A*) ha fatto il suo lavoro alla perfezione. Il lavoro l'ha fatto, sì, ma i soldatini restano lì imbambolati, e si scopre che stiamo chiedendo all'algoritmo di risolvere un problema per cui non è stato progettato.

I nostri duecento NavMeshAgent hanno ricevuto tutti insieme lo stesso ordine di correre verso quel povero cancello: trovano in fretta i percorsi, si muovono sulla mappa, ma man mano che si avvicinano al cancello lo spazio si fa più stretto e una parte di loro si ammassa a quindici metri dal passaggio, comincia a tremolare, alcuni indietreggiano mentre altri cercano di sgomitare tra i vicini. Nel frattempo nel cortile ne passa sì e no una decina.

Se a questo punto apriamo il profiler e diamo un'occhiata ai soldati bloccati, vediamo che A* si prende un sacco di tempo, e se lo prende perché ogni NPC ha bisogno di un percorso, quindi abbiamo duecento ricerche di percorso, il pathfinding rallenta ed è ovvio che bisogna ottimizzarlo perché vada più veloce. Ovvio un corno...

Non è affatto ovvio, perché stiamo cercando di risolvere il problema della navigazione globale, «come arrivo dal punto A al punto B», mentre il comportamento della folla dipende da un'altra domanda: «come mi muovo lungo questo percorso quando accanto a me ci sono qualche decina di personaggi identici a me?».

A vederli, però, i due problemi sembrano uguali: il soldato deve semplicemente arrivare a destinazione. Ma se si confondono le soluzioni, si possono passare ore a regolare A*, cambiare i raggi, ricostruire la NavMesh, aumentare le repulsioni, e continuare comunque a vedere davanti al cancello quella folla che sa benissimo dove deve andare, ma non riesce ad arrivarci.

(Prova tu stesso) Puoi variare la larghezza del cancello e il numero di agenti, e guardare in tempo reale come si forma l'ingorgo.

Come funziona la NavMesh

Perché il personaggio si «incastra» sulla porta, quando nell'editor e nel gioco il passaggio sembra abbastanza largo? La NavMesh non è il pavimento che il giocatore vede nel viewport, ma una geometria a parte, costruita sopra la superficie percorribile tenendo conto dei parametri di uno specifico agente della navmesh. Per questo un corridoio visivamente largo può rivelarsi un bel collo di bottiglia dal punto di vista del centro dell'NPC, perché dai muri va tolto il suo raggio, così che non ci resti agganciato (l'area grigia è intorno alla geometria, quella rossa è la navmesh)

Nella nostra scena il cancello era largo 1,6 metri e l'Agent Radius era di mezzo metro, e dal punto di vista del designer e del giocatore il cancello sembra abbastanza largo da farci passare addirittura tre NPC; ma se guardiamo il tutto con gli occhi dell'algoritmo della NavMesh, da ogni lato bisogna lasciare mezzo metro, e per il centro dell'agente restano appena 0.6 metri, cioè in un cancello largo 1,6 metri può passare un solo NPC.

Un agente ci passa ancora, due agenti affiancati cominciano già a darsi fastidio, e se ne portiamo lì duecento otteniamo la situazione in cui la mesh di navigazione dice che il percorso esiste, ma il sistema di movimento locale non è fisicamente in grado di farci passare nemmeno uno.

Si può provare a ridurre l'Agent Radius a 0,35 metri, cosa molto allettante che risolve il problema localmente, soprattutto se si guarda solo quella porta in particolare; ma insieme a lei cambia tutta la geometria della navigazione, e gli NPC cominciano ad avvicinarsi di più ai muri, a compenetrare la geometria, a entrare in posti dove, secondo il level design, non dovrebbero proprio starci. La vostra piccola ottimizzazione locale ha inaspettatamente rotto mezzo livello, e vedendo questi problemi concreti il designer decide di non toccare l'agente, e cosa fa? Esatto... allarga il cancello (guardate la larghezza delle porte, soprattutto nei giochi vecchi: non erano più alte e più larghe per caso, è tutta una conseguenza del «problema del cancello»)

Il che è anche un buon esempio del perché i parametri della NavMesh non vanno presi come impostazioni cosmetiche, e del perché il raggio dell'agente non è semplicemente «quanto grosso disegnare il cerchietto intorno al personaggio», ma un parametro che determina dove compare in assoluto l'area percorribile.

L'agente è bloccato

C'è anche un'altra variante di questo problema, quando siamo convinti che il personaggio si sia bloccato da qualche parte lungo il percorso, mentre in realtà un percorso non l'ha mai avuto, perché la destinazione si trova fuori dalla navmesh. L'agente è fermo, il QA dice che il personaggio si incastra, il programmatore apre il profiler e non trova niente di sospetto, comincia a guardare A*, poi la NavMesh, poi la repulsione locale, e alla fine viene fuori che A* non è mai partito. È difficile dare la colpa al programmatore, e il designer di solito scambia questa causa per un bug di navigazione e apre un ticket.

Un'altra variante è quando il percorso esiste, ma termina nel punto raggiungibile più vicino, e da fuori anche questa situazione sembra un «NPC bloccato». In generale questo costringe prima a riportare la destinazione sulla navmesh, e solo dopo a lavorarci. E spiega anche perché gli NPC non possono entrare in posti arbitrari dove invece il giocatore riesce ad arrampicarsi.

(Prova tu stesso) Bisogna cliccare dentro un muro: la destinazione verrà attratta verso il punto percorribile più vicino oppure (se nei dintorni non c'è alcun passaggio) resterà dov'è

Un altro modo per far sì che A* non cerchi

Anche i buchi tra le porzioni di NavMesh sono un problema, per questo scale, fosse, vani delle porte e altri punti in cui la navigazione non è un'unica superficie continua richiedono un OffMeshLink. E anche questo dà grattacapi, perché il semplice fatto che esistano più percorsi non significa ancora che il sistema sceglierà quello che una persona considera ragionevole.

Supponiamo di avere un varco largo 1,2 metri, attraverso cui si poteva passare, e con il costo standard del link, pari a 1.0, circa 140 agenti su 200 cercavano di finirci dentro, anche se sulla mappa esisteva un percorso più lungo ma meno trafficato.

Per il computer, se un percorso costa meno di un altro, allora bisogna prendere quello economico, e il fatto che lì si sia già formata una coda spesso non si riflette in alcun modo nel costo del percorso. Aumentare il costo del link ha spinto la maggior parte degli agenti a scegliere un'altra strada, il che mostra come funziona il meccanismo di saturazione dei passaggi; ma l'A* normale non può arrivarci da solo, perché ottimizza soltanto il costo del percorso che gli è stato dato.

(Prova tu stesso) Cambia il costo di attraversamento del link per vedere come gli agenti si ridistribuiscono da soli dal collo di bottiglia all'aggiramento largo.

Quando A* comincia a diventare costoso

Adesso possiamo finalmente parlare di A* in sé, anche se dopo i problemi precedenti è già chiaro che l'algoritmo semplicemente non è in grado di risolvere una parte dei compiti. A* espande i nodi e confronta i costi per trovare un percorso, e se la navmesh contiene 41K poligoni e bisogna costruire un percorso da un capo all'altro della mappa, una singola richiesta del genere nella scena di test toccherà in media più di un terzo di tutti i poligoni.

Supponiamo che una richiesta del genere richieda 0.35 millisecondi: tentare di eseguirne duecento contemporaneamente fa, fisicamente, 70 millisecondi. Abbiamo imparato da tempo ad aggirare casi del genere, e ormai da una ventina d'anni i sistemi reali mettono in coda le richieste alla navmesh, e finché il percorso non è pronto (cosa che può succedere anche dopo qualche frame), l'agente continua a muoversi lungo il percorso vecchio. Il problema non si presenta sempre come un freeze: a volte è solo un innocuo ritardo, quando il personaggio per un paio di frame va contro il muro o resta indietro.

A* gerarchico

Se la mappa è composta da alcune grandi aree, tra le quali esiste un numero relativamente ridotto di passaggi, non è affatto necessario costringere ogni volta A* a esplorare tutti i 41K poligoni, perché sappiamo in anticipo parecchio sulla struttura del livello e possiamo prima stabilire attraverso quali grandi aree bisogna passare.

Per farlo si può suddividere la mappa in regioni e costruire tra loro un grafo di portali, poi cercare prima il percorso su questo grafo grezzo, che può contenere appena qualche decina di nodi, e solo dopo lanciare la ricerca dettagliata all'interno delle regioni che il percorso attraversa davvero.

Prima otteniamo qualcosa come A → B → C, cioè definiamo il percorso tra le grandi regioni, e solo dopo cerchiamo il percorso dettagliato Agent → Portal B → Portal C → Target, evitando così che ogni richiesta riesamini da capo l'intera mappa, anche se per l'agente il risultato finale appare esattamente come se avesse costruito un normale percorso completo.

Per di più, un grafo grezzo del genere si può costruire una volta sola durante la build o il caricamento del livello e aggiornarlo solo quando un ostacolo chiude uno dei portali, ed è di nuovo il solito vecchio principio di ottimizzazione che salta fuori di continuo nei sistemi di gioco. Se un'informazione si può calcolare in anticipo e poi riutilizzare molte volte, ricalcolarla ogni volta da capo è di solito piuttosto stupido.

(Prova tu stesso) Alterna A* e Hierarchical A* per vedere i tile open/closed e la differenza nei tempi di ricerca.

E se vanno tutti nello stesso punto?

Ed ecco che qui A* comincia a perdere contro qualsiasi algoritmo di movimento di folla, perché se abbiamo duecento agenti e hanno tutti la stessa destinazione, bisogna lanciare duecento ricerche di percorso indipendenti, anche se buona parte delle informazioni sul percorso verso quella destinazione sarà la stessa per tutti.

Le diverse posizioni di partenza non permettono di usare A* così com'è, eppure una parte consistente del percorso, da un certo punto in poi, diventa comune. Ne risulta che risolviamo duecento volte lo stesso problema solo perché abbiamo duecento personaggi, ed è per questo che hanno inventato il flow field.

Invece di cercare separatamente per ogni agente il percorso da lui alla destinazione, propaghiamo una volta sola il costo dalla destinazione all'indietro verso la folla, e poi per ogni cella salviamo la direzione verso la cella vicina con il costo minore. Dopodiché qualunque agente finisca in quella cella guarda semplicemente la direzione e prosegue: in pratica abbiamo tirato fuori tutte le informazioni che A* generava durante il lavoro e le abbiamo conservate per un certo periodo, per cui il costo di costruzione del campo quasi non dipende dal numero di agenti.

Per il test ho usato una griglia 128×128 con celle da 0.5 metri; la ricostruzione completa del campo richiede 4 millisecondi, ma questo è il costo di modifica del campo stesso, non il costo di elaborazione di ciascun agente, e aggiornandolo tre-quattro volte al secondo il costo medio di ricostruzione era di appena 12 millisecondi al secondo. Per confronto, la stessa folla con l'A* gerarchico costava 12 millisecondi per ogni richiesta.

È un compromesso, ed è ottimo per una folla; ma quando ogni agente ha la propria destinazione, e invece di una sola deve tenerne d'occhio tre o quattro, il numero di campi necessari comincia a crescere, e con esso crescono la memoria e il costo di ricostruzione, e a un certo punto si scopre di aver costruito un sistema enorme e bellissimo solo per ottenere più o meno lo stesso lavoro che il normale A* svolgeva in modo molto più semplice.

Per questo è del tutto normale usare un sistema ibrido, in cui gli NPC con un nome, i boss e i personaggi con compiti individuali usano A*, perché a loro servono davvero percorsi separati, mentre i grandi gruppi di soldati semplici usano il flow field, perché il loro compito principale è muoversi tutti insieme, in modo abbastanza efficiente, nella stessa direzione.

(Prova tu stesso) Puoi confrontare il benchmark di A* su 200+ agenti con un unico campo di direzioni condiviso.

Local avoidance

Ma anche dopo aver trovato il percorso globale giusto, il problema del cancello non sparisce, perché ora ogni agente sa dove deve andare, ma sessanta agenti possono ancora voler occupare contemporaneamente lo stesso punto dello spazio. E di nuovo, A* questo problema non lo può risolvere.

Qui entra in scena RVO o il suo derivato ORCA, che risolvono un problema completamente diverso: l'agente guarda le posizioni e le velocità dei vicini, individua le direzioni che porterebbero a una collisione, le scarta e sceglie tra quelle rimaste la velocità più simile possibile a quella desiderata. In altre parole, in quel momento all'agente non interessa «come arrivo in città?», ma solo «come faccio a non andare addosso al tizio davanti a me, adesso?».

Per questo la local avoidance non si può usare come sostituto della navigazione globale, e se le si dà solo il comportamento locale dicendo «bene, ora arrangiati ad arrivare a destinazione», può benissimo passare minuti interi a evitare perfettamente ogni collisione senza arrivare da nessuna parte, soprattutto se davanti si ritrova un muro a U. (Prova tu stesso)

Quando tutti gli agenti hanno lo stesso avoidancePriority, per esempio il valore standard 50, il sistema diventa troppo simmetrico: ogni agente si considera importante quanto il vicino, ognuno cerca di evitare la collisione, il vicino fa esattamente lo stesso, e alla fine sono tutti abbastanza intelligenti da non scontrarsi tra loro, ma nessuno abbastanza sfacciato da passare finalmente dal cancello. A volte, per una folla, è più utile dare agli agenti un po' di priorità, e nella scena di test un avoidancePriority casuale da 0 a 99 ha ridotto il tempo dell'ingorgo al cancello da 4,2 secondi a 1,1 secondi.

E anche questo è un buon esempio del perché il profiler da solo vale meno della visualizzazione del comportamento, o del perché anche un algoritmo sofisticato può incartarsi quando tutta questa enorme folla cerca onestamente di seguire le stesse regole. E per risolvere il problema, invece di una complicata modifica all'algoritmo, è bastata una piccola asimmetria nel comportamento. (Prova tu stesso) Puoi confrontare le priorità Uniform e Random con lo stesso cancello e la stessa folla.

Ostacoli dinamici

Ora aggiungiamo alla scena qualche barile che rotola per il livello e impostiamo la ricostruzione automatica della navmesh intorno a loro. Funzionerà tutto, ma il problema è che ricostruire una parte della mesh di navigazione costa caro, e se l'ostacolo si muove di continuo, di fatto chiediamo al motore di rifare regolarmente la NavMesh per colpa di un oggetto che mezzo secondo dopo si trova già da un'altra parte.

Anche qui bisogna capire quale problema risolve ciascun sistema: se l'oggetto sta fermo, ha senso tenerne conto nella geometria globale; se invece si muove di continuo, forse la NavMesh non c'entra proprio niente, e costringere la navigazione globale a reagire a ogni spostamento dell'oggetto sarebbe come ridisegnare la mappa stradale di una città ogni volta che un'auto cambia corsia. Perché per tutti gli altri utenti della strada la struttura della città non è cambiata affatto.

(Prova tu stesso) Puoi trascinare l'ostacolo in due modalità, «Every drag move» e «Only on release».

Il numero di richieste

Dopo tutte queste ottimizzazioni resta ancora una cosa che in molti si dimenticano di fare. Anche se una singola richiesta di percorso è abbastanza economica, questo non significa affatto che duecento agenti debbano farla tutti nello stesso momento, perché in un gioco vero ci interessa non solo il costo di una singola operazione, ma anche come queste operazioni influiscono sul tempo di frame.

Il motivo è semplice: se tutti gli agenti sono comparsi contemporaneamente e hanno tutti lo stesso intervallo di aggiornamento, con buona probabilità si aggiorneranno anche tutti insieme, e invece di un carico uniforme otterremo un piccolo esercito che decide in perfetta sincronia che proprio adesso a tutti serve un nuovo percorso, dopodiché il profiler mostrerà un picco periodico, anche se ogni singola richiesta di per sé può essere economicissima.

Se le richieste superano il budget, l'agente non è affatto obbligato a ricalcolare subito il percorso, perché si trova già su un qualche percorso e può continuare a seguire quello vecchio mentre la nuova richiesta aspetta il suo turno; il giocatore molto probabilmente non se ne accorgerà nemmeno, perché per lui conta molto di più un movimento fluido che il fatto che il nuovo percorso sia stato calcolato un frame più tardi, mentre per il motore questo significa poter trasformare un picco improvviso di lavoro in una coda più uniforme senza alcun cambiamento visibile nel comportamento.

(Prova tu stesso) Con jitter 0 e unlimited budget si vede un picco periodico sul grafico del frame time; puoi aggiungere jitter o budget e guardare gli spike trasformarsi in una coda.

Il problema di solito non è dove lo cerchiamo

Alla fine il «problema del cancello» si rivela non riguardare affatto il cancello, e nemmeno la navigazione, ma un errore piuttosto tipico: sottovalutare il dominio del problema, quando vediamo un comportamento concreto del personaggio e cerchiamo la causa nell'algoritmo più vicino che sembra collegato a quel comportamento.

L'NPC non passa dal cancello, quindi bisogna sistemare A*; l'NPC è bloccato, quindi bisogna ricostruire la NavMesh; la folla scatta, quindi bisogna migliorare l'avoidance; e poi si scopre che A* ha trovato il percorso, la NavMesh considera il passaggio percorribile, l'avoidance evita le collisioni e ogni singolo componente fa esattamente quello che gli si chiede.

È solo che il problema che stiamo cercando di risolvere sta fuori da questi sistemi, e dopo averci ripensato spesso si scopre che il cancello, per tutto questo tempo, ce l'avevamo in testa.