Follow

Il path-finding consiste nel calcolo da parte del computer del percorso più breve fra due punti all’interno di un ambiente complesso. Come potete immaginare imbattersi in questo problema durante sviluppo di un gioco non è un avvenimento insolito: a meno che non vi stiate dilettando in manageriali astratti avrete sempre a che fare con oggetti in movimento.

Spostarsi nella vita reale è un compito piuttosto semplice. Noi creature viventi animali abbiamo alle spalle milioni di anni di evoluzione che ci hanno portato a considerare un’operazione elementare come lo spostarsi da un punto A ad un punto B un compito banale ed istintivo. Nella realtà analitica dei fatti sfortunatamente di “banale ed istintivo” c’è poco.

Esistono decine e decine di tecniche di path-finding o motion planning, ognuna con i propri limiti e i propri punti di forza ma nei videogiochi quelle che vengono utilizzate si contano su una mano e tutte partono dallo stesso presupposto: suddividere lo spazio in zone ed utilizzare la ricerca su un grafo per trovare la strada giusta che collega A con B.

Sorvoliamo per un momento il problema di navigare un grafo alla ricerca del percorso minimo. Questo è un problema molto noto in informatica e ci torneremo con calma in un’altra occasione. Ciò che fa la differenza nel path-finding di un videogame è il modo in cui lo spazio viene suddiviso (processo chiamato quantizzazione).

È necessario quindi trovare un modo di convertire lo spazio fisico in cui si muovono i nostri agenti in uno spazio discreto rappresentabile con un grafo. Questa conversione deve essere biunivoca poiché una volta trovato il percorso sul grafo dobbiamo essere in grado di riportarlo nel mondo di gioco in modo tale che venga eseguito dai nostri personaggi.

Vediamo quindi qualche tecnica al riguardo.

Tile Graph

Questa tecnica appartiene agli albori dei videogiochi e sicuramente ne sarete a conoscenza. La tecnica, che consiste nel suddividere lo spazio di gioco in una griglia quadrata (o più raramente esagonale), è stata utilizzata intensivamente nei giochi 2D e isometrici dall’inizio dei tempi fino all’avvento diffuso del 3D. All’epoca la struttura a griglia non serviva solamente per il path-planning ma forniva da base anche (e soprattutto) per la grafica grazie all’uso e alla sovrapposizione di elementi grafici ripetuti di forma quadrata (i tile, appunto).

Dragon Quest (27 Maggio 1986), è evidente l’uso dei “tile” per la costruizione del mondo. A riprova che la tecninca non è nata per l’AI degli agenti, in questo gioco non c’è path-finding dei personaggi non giocanti.

Nonostante la tecnica non venga quasi più utilizzate per la grafica di un gioco il tiling è lungi dall’essere morto. Il suo punto di forza principale è che è semplice. Mappare un punto del mondo in un tile (e viceversa) è questione di due righe codice:

Il grafo risultante da questa quantizzazione è composto da un nodo per ogni casella libera (in cui è permesso il movimento) e per ogni nodo ci sono al massimo 4 archi che conducono a 4 nodi collegati (oppure 8 se permettiamo il movimento in diagonale).

Il principale svantaggio di questa tecnica è la velocità di esecuzione nel caso di zone troppo vaste. Questa tecnica genera un gran numero di nodi, in giochi caratterizzati da vasti spazi aperti il numero di tile può essere spropositatamente elevato se paragonato all’effettivo numero percorsi utilizzati. Prendete ad esempio Skyrim ed immaginate di tappezzarlo di tile e di pianificare il percorso in una grande valle per un personaggio non giocante (ad esempio un percorso fra due città). Quanti tile deve esplorare il gioco per trovare la strada giusta? La risposta è troppi.

Quando i nostri spazi diventano troppo vasti arriva il momento di pensare ad altro.

Domini di Dirichlet

Questa tecnica è decisamente più sofisticata del tiling. Immaginate di trovarvi in un corridoio buio e di sistemare tre fari sul soffitto: uno blu, uno rosso e uno verde. Una volta accesi questi tre fari proietteranno un cono di luce verso il basso. Bene, se guardate attentamente il pavimento vedrete che lo spazio è stato suddiviso in tre regioni: una rossa in cui è prevalente la luce del faro rosso, una blu, in cui è prevalente la luce del faro blu e una verde in cui domina il faro verde.

In ogni punto del corridoio coperto dalla luce possiamo quindi trovare un collegamento biunivoco che colleghi la regione al faro e il faro alla regione. Questo, in linea di massima, è il concetto di domini di Dririchlet. La differenza fondamentale è che i nostri fari sono chiamati punti caratteristici e vengono messi manualmente in fase di level design.

Esempio di una configurazione di tre punti caratteristici visti “di lato”. Come potete vedere il “mondo” viene diviso in tre zone collegate ad ogni punto caratteristico.

La stessa configurazione vista dall’alto. Nel caso in cui ci fossero più fari in posizioni più varie le regioni assumono forme sempre più complesse.

In ogni istante si può associare un agente nello spazio al punto caratteristico più vicino con una semplice ricerca. Badate bene che non è necessario cercare fra tutti i punti caratteristici in quanto è possibile sfruttare un principio di località spaziale assumendo, correttamente, che se in un frame il personaggio si trova vicino al punto caratteristico A nel frame successivo non potrà trovarsi troppo lontano (a meno che non sia un personaggio in grado di teletrasportarsi, ma questi sono dettagli).

Il vantaggio principale dei domini di Dirichlet è semplicità con cui è possibile quantizzare in modo automatizzato. Sfortunatamente il metodo è molto complesso per quello che resta. I domini di Dirichlet danno ad esempio luogo a forme molto complesse di cui è poco intuitivo calcolare i collegamenti (per informazioni cercate “triangolazione di Delaunay” su Google) e il cui transito non è nemmeno garantito.

Entrare nel dettaglio con questo metodo va al di là dello scopo di questo articolo quindi mi riservo futuri approfondimenti. Per il momento passiamo al terzo metodo.