Share
In questo tutorial spiegherò tracciamento del campo vettoriale e i suoi vantaggi rispetto ad algoritmi di pathfinding più tradizionali, come quelli di Dijkstra. Una comprensione di base dell'algoritmo di Dijkstra e dei potenziali campi ti aiuterà a capire questo articolo, ma non è necessario.
Pathfinding è un problema con molte soluzioni e ognuna ha i suoi pro e contro. Molti algoritmi di pathfinder funzionano calcolando un percorso verso l'obiettivo per ogni pathfinder, il che significa che il pathfinder impiegherà il doppio del tempo per calcolare con il doppio di pathfinder. Questo è accettabile in molte situazioni, ma quando si lavora con migliaia di pathfinder è possibile un approccio più efficiente.
Conosciuto come tracciamento del campo vettoriale, questo approccio calcola il percorso dall'obiettivo a ogni nodo nel grafico. Per consolidare questa spiegazione del pathfinding del campo vettoriale, spiegherò l'algoritmo usando la mia particolare implementazione come esempio.
Nota: Il tracciamento del campo vettoriale può essere astratto a nodi e grafici in generale; solo perché lo spiego usando il mio approccio con tessere e griglia non significa che questo algoritmo è limitato ai mondi basati su tessere!
Il tracciamento del campo vettoriale è composto da tre passaggi.
Questo video ti mostra i risultati finali e poi ti fornisce una panoramica generale dei concetti presentati nel tutorial completo di seguito:
La heatmap memorizza la distanza del percorso dall'obiettivo per ogni tessera sulla mappa. La distanza del percorso è distinta dalla distanza euclidea in quanto è un calcolo della distanza tra due punti che passano solo attraverso un terreno percorribile. Ad esempio, un GPS calcola sempre la distanza del percorso, poiché le strade sono l'unico terreno percorribile.
Sotto, puoi vedere la differenza tra la distanza del percorso e la distanza lineare dall'obiettivo (segnata in rosso) a una tessera arbitraria (contrassegnata in rosa). Le tessere non attraversabili sono disegnate in verde. Come puoi vedere, la distanza del percorso (indicata in giallo) è 9, mentre la distanza lineare (mostrata in azzurro) è approssimativamente 4.12.
I numeri nell'angolo in alto a sinistra di ciascuna tessera mostrano la distanza del percorso rispetto all'obiettivo calcolato dall'algoritmo di generazione della heatmap. Nota che esiste più di una possibile distanza tra i due punti; in questo articolo, ci interessa solo il più breve.
L'algoritmo di generazione della heatmap è a algoritmo del fronte d'onda. Inizia dall'obiettivo con un valore di 0, e poi scorre verso l'esterno per riempire l'intera regione attraversabile. Ci sono due passaggi per l'algoritmo del fronte d'onda:
Accentsconagua
0.la distanza del percorso della tessera precedente + 1.Nota: L'algoritmo del fronte d'onda sta semplicemente eseguendo una prima ricerca sulla griglia e memorizzando quanti passi ci sono voluti per raggiungere ogni tessera lungo il percorso. Questo algoritmo è talvolta chiamato anche il algoritmo di brushfire.
Ora che la distanza del percorso da ogni tessera all'obiettivo è stata calcolata, possiamo facilmente determinare il percorso che deve essere preso per avvicinarsi all'obiettivo. È possibile farlo in fase di esecuzione per ogni pathfinder per ogni frame, ma spesso è meglio calcolare un campo vettoriale una volta e poi fare in modo che tutti i pathfinder si riferiscano al campo vettoriale in fase di esecuzione.
Il campo vettoriale memorizza semplicemente un vettore che punta verso il basso il gradiente della funzione distanza (verso l'obiettivo) in ogni tessera. Ecco una visualizzazione del campo vettoriale, con i vettori che puntano dal centro della tessera lungo il percorso più breve verso l'obiettivo (di nuovo mostrato in rosso).
Questo campo vettoriale viene generato una tessera alla volta guardando la mappa termica. Le componenti xey del vettore sono calcolate separatamente, come mostrato nello pseudocodice seguente:
Vector.x = left_tile.distance - right_tile.distance Vector.y = up_tile.distance - down_tile.distance
Nota: La variabile di distanza di ogni tessera memorizza la distanza del percorso verso l'obiettivo come calcolato dall'algoritmo del fronte d'onda sopra.
Se una delle tessere referenziate (sinistra / destra / su / giù) non è attraversabile e quindi non ha alcuna distanza utilizzabile memorizzata, al posto del valore mancante viene utilizzata la distanza associata al riquadro corrente. Una volta che il vettore del percorso è stato calcolato approssimativamente, viene normalizzato per evitare incoerenze in seguito.
Ora che il campo vettoriale è stato calcolato, è molto facile calcolare il movimento per un esploratore. Supponendo che vector_field (x, y) restituisca il vettore calcolato in precedenza sulla piastrella (X, y), e quella desiderata_velocità è uno scalare, lo pseudocodice per calcolare la velocità di una particella nella tessera (X, y) Somiglia a questo:
velocity_vector = vector_field (x, y) * desired_velocity
Le particelle hanno semplicemente bisogno di iniziare a muoversi nella direzione indicata dal vettore. Questo è il modo più semplice per farlo, ma i sistemi di movimento più complessi possono essere facilmente implementati utilizzando i campi di flusso.
Ad esempio, le tecniche illustrate in Comprendere i comportamenti dello sterzo potrebbero essere applicate al movimento del tastatore. In una situazione del genere, il velocity_vector abbiamo calcolato sopra sarebbe usato come la velocità desiderata, e i comportamenti di guida verrebbero utilizzati per calcolare il movimento effettivo in ogni momento.
Nel calcolare il movimento, c'è un problema che a volte può verificarsi, noto come optima locale. Ciò si verifica quando esistono due percorsi ottimali (più corti) da eseguire per raggiungere l'obiettivo da una determinata tessera.
Questo problema può essere visto nell'immagine qui sotto. La tessera (mostrata in rosa) immediatamente a sinistra del centro del muro ha un vettore di percorso i cui componenti (xey) sono uguali a 0.
Optima locale fa sì che i pathfinder rimangano bloccati; si riferiranno al campo vettoriale che non riuscirà a indicare una direzione per entrare. Quando ciò accade, i pathfinder rimarranno nella stessa posizione a meno che non venga implementata una correzione.
Il modo più elegante (che ho trovato) per risolvere il problema è di suddividere sia la heatmap che il campo vettoriale una volta. Ogni singola tessera termoarea e campo vettoriale è stata divisa in quattro tessere più piccole. Il problema rimane lo stesso con una griglia suddivisa; è stato solo leggermente ridotto al minimo.
Il vero trucco che risolve il problema di optima locale è di aggiungere inizialmente quattro nodi obiettivo, invece di uno solo. Per fare ciò, dobbiamo semplicemente modificare il primo passo dell'algoritmo di generazione della heatmap. Quando abbiamo solo aggiunto un obiettivo con una distanza di percorso pari a 0, ora aggiungiamo le quattro tessere più vicine all'obiettivo.
Ci sono diversi modi per scegliere le quattro tessere, ma il modo in cui vengono scelte è in gran parte irrilevante - finché le quattro tessere sono adiacenti (e attraversabili), questa tecnica dovrebbe funzionare.
Ecco lo pseudocodice modificato per la generazione della heatmap:
0.la distanza del percorso della tessera precedente + 1.E ora, ecco i risultati finali, che mostrano chiaramente che il problema di optima locale è stato eliminato:
Sebbene questa soluzione sia elegante, non è l'ideale. Usarlo significa che il calcolo della heatmap e del campo vettoriale richiede quattro volte più tempo a causa del maggior numero di tessere.
Altre soluzioni richiedono di effettuare controlli e quindi determinare su quale direzione andare, caso per caso, il che rallenta in modo significativo i calcoli del movimento delle particelle. Nel mio caso, la suddivisione delle mappe era l'opzione migliore.
Speriamo che questo tutorial ti abbia insegnato come implementare il path-finding basato sull'obiettivo in un mondo basato su tile. Tieni presente che questo tipo di path-finding è, al suo interno, semplice: le particelle seguono il gradiente della funzione di distanza verso l'obiettivo.
L'implementazione è più complessa, ma può essere suddivisa nei seguenti tre passaggi gestibili:
Spero di vedere le persone espandere le idee presentate qui. Come sempre, se avete domande, sentitevi liberi di chiedere loro nei commenti qui sotto!
