Follow

Punti di Visibilità

Dovete prendere una mia frase per certa: è dimostrato che un percorso ottimale in un ambiente 2D ha dei flessi (variazioni di direzione) in corrispondenza di vertici convessi dell’ambiente.

Il punto chiave dei punti di visibilità è:

• Identificare i vertici convessi dell’ambiente.
• Variare tali punti per tenere in considerazione la fisicità degli agenti (non essendo punti materiali avranno una loro larghezza e non possiamo pretendere che camminino radenti agli spigoli).
• Utilizziamo questi punti come nodi del grafo di navigazione
• Colleghiamo ogni nodo del grafo a tutti i punti visibili dal punto rappresentato da questo nodo.

Il concetto di visibilità è piuttosto semplice. Un nodo è visibile ad un altro nodo se è possibile collegare questi due punti con una linea retta che non intersechi nessun ostacolo.

Esempio di punti di visibilità. I pallini rossi sono i vertici convessi. I pallini verdi sono i punti di visibilità ottenuti applicando un offset ai punti di vertice. Le linee tratteggiate sono i collegamenti fra i punti mentre la linea blu è un esempio di percorso “ottimo”

I punti di visibilità possono essere usati come punti caratteristici di un dominio di Dirichlet per automatizzare l’associazione zona del mondo – nodo del grafo.

Il metodo è comunque tutt’altro che perfetto. Soffre di molti problemi derivanti dai domini di Dirichlet e in alcuni casi (specie zone vaste e aperte) tutti i punti di visibilità vedono quasi tutti gli altri punti di visibilità. Questo genera un grafo completo (o quasi) che può rendere molto poco efficiente l’algoritmo. In questi casi il level designer può inserire degli ostacoli virtuali con lo scopo di rendere il grafo più sparso ma spesso anche questa non è una soluzione accettabile.

Nonostante ciò i punti di visibilità sono una delle tecniche più usate nel mondo dei videogame.

Navigation Mesh

Le navigation mesh sono uno dei metodi consigliati ed utilizzato dalla maggior parte dei giochi moderni. Si basano sulla divisione del mondo in poligoni convessi. Ogni poligono (solitamente triangoli) sarà un nodo del grafo e sarà collegato ai poligoni confinanti(nel caso di un triangolo avremo al massimo tre collegamenti).

Sebbene questa suddivisione possa apparire macchinosa bisogna ricordare che il motore grafico già utilizza poligoni convessi per rappresentare tutto, compreso il pavimento. È quindi possibile sfruttare le stesse mesh grafiche come mesh di navigazione.

Nella maggior parte dei casi, ma non sempre, è garantito che in ogni punto di un poligono della mesh è possibile raggiungere ogni punto di poligono confinante senza incontrare ostacoli lungo il cammino. Questo, come dicevo, non è sempre vero e richiede un attimo di attenzione da parte del level designer durante la pianificazione delle mesh di navigazione.

L’associazione personaggio-poligono viene effettuata con una semplice ricerca. Ancora una volta possiamo sfruttare la località spaziale per evitare una ricerca su tutti i poligoni della mesh di navigazione.

Esempio di navigazione con il metodo delle Navigation Mesh. Ogni poligono è un nodo (rappresentato dal punto rosso). Nell’esempio è possibile comparare il percorso generato dalle navigation mesh (in giallo) con il percorso ottimo (in rosa).

Data l’importanza di questo metodo torneremo a parlarne in maggior dettaglio in un prossimo articolo.

Conclusione

Spero che questo articolo, lungi dal voler essere esaustivo, possa fornirvi spunti di ricerca nell’affrontare il problema della quantizzazione del mondo nei videogiochi. Nel prossimo articolo parleremo un po’ di grafi e parleremo di come ricercare il percorso minimo.