Share
Pathfinding è onnipresente nei giochi. Quindi è importante capire le implicazioni che sono presenti quando si usano algoritmi come A *. In questo tutorial tratteremo un metodo relativamente nuovo per la ricerca di mondi basati sulla griglia: Jump Point Search, che può accelerare A * per ordine di grandezza.
Nota: Sebbene questo tutorial sia scritto usando AS3 e Flash, dovresti essere in grado di utilizzare le stesse tecniche e concetti in quasi tutti gli ambienti di sviluppo di giochi.
Questa implementazione si basa sulla carta originale e sull'articolo su JPS trovato qui: Jump Point Search. Il
L'implementazione basata su Lua, Jumper, è stata utilizzata come aiuto per alcune parti dell'implementazione.
Fai clic sul file SWF per focalizzarlo, quindi sposta il mouse sulle aree non bloccanti della mappa per fare in modo che gli NPC tentino di raggiungerlo. Hit Space per alternare tra A *, Jump Point Search ed entrambi.
Senza il flash? Guarda invece il video di YouTube:
L'implementazione demo qui sopra utilizza AS3 e Flash con Starling Framework per il rendering accelerato GPU e la libreria polygonal-ds per le strutture dati.
Il PathFinding è spesso usato nei videogiochi e durante la tua carriera di sviluppo del gioco ti troverai sicuramente a scontrarti. Il suo uso principale è quello di dare un comportamento di movimento dall'aspetto intelligente alle entità artificiali (NPC), per evitare che si imbattano in cose (spesso).
In alcuni giochi, l'avatar del giocatore è anche soggetto a pathfinding (giochi di strategia, molti giochi di ruolo in terza persona e giochi di avventura). Quindi potresti presumere che il problema del path-finding sia risolto, ma sfortunatamente non è così; non c'è un proiettile d'argento che tu possa usare e sia fatto solo con esso.
E anche nei grandi giochi AAA, troverai ancora cose divertenti come questa:
Potrebbe non esserci un proiettile d'argento, ma c'è un proiettile: l'algoritmo A * (Una stella). In questo tutorial vedremo una breve panoramica di A * e come accelerarlo usando un altro algoritmo, Jump Point Search.
Per prima cosa abbiamo bisogno di un modo per rappresentare il nostro mondo di gioco in modo che un algoritmo di individuazione del percorso possa usarlo.
Una delle cose più importanti da considerare quando si pensa al pathfinding per il tuo gioco è rappresentazione del mondo. Come sono organizzati i dati delle aree e degli ostacoli percorribili con strutture di programmazione in memoria?
La rappresentazione più semplice che è possibile utilizzare è una struttura basata sulla griglia, in cui i nodi del percorso sono organizzati in una griglia e possono essere rappresentati da un array 2D. Utilizzeremo questa rappresentazione in questo tutorial. In particolare sarà una rappresentazione a griglia a otto vie: permettendo il movimento in direzioni diritte e diagonali.
I tuoi requisiti potrebbero essere diversi, quindi questa struttura potrebbe non essere adatta a te. La cosa buona è che con alcune elaborazioni (solitamente effettuate offline) è possibile modificare le rappresentazioni dei percorsi in altri formati. Le alternative all'approccio basato sulla griglia includevano cose come il poligono (ostacoli rappresentati dai poligoni) o le maglie di navigazione (aree di navigazione rappresentate dai poligoni); questi possono rappresentare gli stessi dati con meno nodi.
Altri dati che possono essere memorizzati nella rappresentazione della mappa sono costi: quanto costa viaggiare da un nodo all'altro. Questo può essere usato per l'IA per determinare il percorso che, ad esempio, preferisce strade su terreno regolare (rendendo il costo della strada meno del terreno).
Jump Point Search è specificamente progettato per la rappresentazione della mappa basata sulla griglia a otto vie, quindi la useremo. Inoltre, nella sua forma vaniglia non supporta mappe ponderate. (Nella sezione finale discuterò un possibile modo di porvi rimedio.)
Ora abbiamo una rappresentazione del mondo diamo una rapida occhiata all'implementazione di A *. È un algoritmo di ricerca del grafico ponderato che utilizza l'euristica (piccoli "suggerimenti") su come cercare l'area dal nodo iniziale al nodo finale.
Consiglio vivamente di dare un'occhiata a questa visualizzazione degli algoritmi di pathfinding:
PathFinding.js - visual. Giocare con esso può aumentare la tua intuizione di ciò che l'algoritmo sta effettivamente facendo - più è divertente!
Per il rilevamento dei percorsi usando A * nelle griglie rettangolari facciamo quanto segue:
1. Trova il nodo più vicino alla tua posizione e dichiaralo come nodo iniziale e mettilo nell'elenco aperto. 2. Mentre ci sono nodi nell'elenco aperto: 3. Selezionare il nodo dall'elenco aperto con il punteggio F più piccolo. Mettilo nella lista chiusa (non vuoi considerarlo di nuovo). 4. Per ciascun vicino (cella adiacente) che non è nella lista chiusa: 5. Imposta il suo genitore sul nodo corrente. 6. Calcola il punteggio G (distanza dal nodo iniziale a questo vicino) e aggiungilo all'elenco aperto 7. Calcola il punteggio F aggiungendo l'euristica al valore G.Post correlati
L'euristica sta essenzialmente facendo un'ipotesi sulla possibilità che il nodo valutato stia conducendo all'obiettivo. L'euristica può fare una grande differenza nell'efficienza degli algoritmi di individuazione dei percorsi in quanto tendono a limitare il numero di nodi che devono essere visitati. Useremo la distanza di Manhattan per i nostri scopi (nel senso che i nodi più vicini all'obiettivo avranno un numero inferiore):
private function manhattanDistance (inizio: Nodo, fine: Nodo): int return Math.abs (end.x - start.x) + Math.abs (end.y - start.y);
Questo è più o meno. Interrompiamo l'algoritmo quando troviamo il nodo obiettivo e quindi tracciamo utilizzando la variabile padre del nodo per costruire il percorso.
Gli algoritmi di ricerca possono essere utilizzati anche per altre cose. A * è un algoritmo di ricerca del grafico ponderato generale e può essere utilizzato su qualsiasi di questi grafici. Questo può coprire altri campi nell'intelligenza artificiale, come trovare i passi ottimali per raggiungere determinati obiettivi: lanciare una bomba o correre per ripararsi e cercare di intrufolarsi dietro un nemico?
Nello sviluppo del gioco dobbiamo fare le cose velocemente, aggiornando i nostri giochi a 60 frame al secondo ogni millisecondo. Anche se A * funziona abbastanza bene per alcuni usi, esiste la necessità di renderlo più veloce o usare meno memoria.
La scelta della rappresentazione è la prima cosa che avrà un impatto sulle prestazioni del pathfinding e sulla scelta dell'algoritmo di pathfinder. La dimensione del grafico che viene ricercato avrà una grande correlazione sul rendimento del pathfinder (che ha senso, è più facile trovare la strada nella tua stanza che in una grande città).
Quindi, si prenderanno in considerazione ottimizzazioni di livello più elevato che di solito coinvolgono i dati di raggruppamento in regioni più piccole e poi le ricerche, mentre in seguito perfezionano i percorsi in regioni più piccole. Ad esempio, se vuoi andare in un ristorante in una città vicina, per prima cosa consideri come si arriva dalla tua città a quella e, una volta che sei in quella città, limiti la tua "ricerca" all'area in cui si trova il ristorante , ignorando il resto. Ciò includerebbe cose come le paludi, l'eliminazione del vicolo cieco e l'HPA *.
Al livello più basso devi fare la ricerca. Hai scelto la rappresentazione dei dati e le possibili astrazioni e poi le hai inserite in un algoritmo che individuasse i nodi, viaggi qua e là alla ricerca dell'obiettivo. Questi algoritmi sono solitamente basati sull'algoritmo di ricerca A * con possibili modifiche. In casi più semplici, puoi usare l'A dritto che ti offre la semplicità. Ho fornito un'implementazione basata sulla griglia nel download sorgente.
Poiché questo tutorial riguarda l'implementazione della Jump Point Search, il grafico del pathfinder sarà rappresentato con una griglia. E in particolare deve essere una griglia a otto vie poiché l'algoritmo la utilizza direttamente.
Quello che la Jump Point Search fa veramente è eliminare un sacco di nodi intermedi in certi tipi di combinazioni di griglia. Salta un po 'di questi elementi che si aggiungerebbero alla lista aperta e alla lista chiusa, così come ad altri calcoli, in favore di ulteriori elaborazioni quando si seleziona il nodo successivo.
Come per A * selezioniamo dalla scena aperta il nodo con il punteggio F più basso. Ma è qui che le cose cominciano a diventare interessanti. Invece di selezionare nodi adiacenti chiameremo questa funzione per farlo per noi:
function identifySuccessors (corrente: Nodo, inizio: Nodo, fine: Nodo): Vector.Var successori: Vector. = nuovo vettore. (); Vari vicini: Vector. = nodeNeighbours (corrente); per ciascuna (var neighbor: Node in neighbors) // Direzione dal nodo corrente al prossimo: var dX: int = clamp (neighbour.x - current.x, -1, 1); var dY: int = clamp (neighbour.y - current.y, -1, 1); // Cerca di trovare un nodo per passare a: var jumpPoint: Node = jump (current.x, current.y, dX, dY, start, end); // Se trovato, aggiungilo alla lista: if (jumpPoint) successors.push (jumpPoint); return successor;
Ciò che fa è eliminare nodi che non sono interessanti per il nostro percorso. Per questo usiamo la direzione dal genitore come linea guida principale. Ecco alcuni esempi di potatura dei nodi che ignoreremo per le direzioni orizzontali e verticali:
Esempio di una delle situazioni di potatura orizzontale.
Nel codice questo finirà come una serie di Se dichiarazioni che controllano queste situazioni. Puoi vedere l'esempio qui, descrivendo il caso giusto dall'immagine:
if (directionY == 0) if (! _world.isBlocked (current.x + directionX, current.y)) if (_world.isBlocked (current.x, current.y + 1)) // crea un nodo con la nuova posizione neighbours.push (Node.pooledNode (current.x + directionX, current.y + 1));
Dopo aver scelto il vicino, cerchiamo di trovare un punto di salto, che è un nodo che può essere raggiunto da quello corrente, ma non necessariamente solo in un modo. Per dirla in modo più formale, ciò che fa JPS è eliminare la simmetria tra i percorsi: ognuno ha una diversa permutazione delle stesse mosse:
Quindi per i grandi spazi aperti possiamo avere enormi vincite. Ecco come funziona il metodo di salto:
function jump (cX: int, cY: int, dX: int, dY: int, inizio: Nodo, fine: Nodo): Nodo // cX, cY - Posizione attuale nodo, dX, dY - Direzione // Posizione di nuovo nodo che considereremo: var nextX: int = cX + dX; var nextY: int = cY + dY; // Se è bloccato, non possiamo saltare qui se (_world.isBlocked (nextX, nextY)) restituisce null; // Se il nodo è l'obiettivo, restituisce if (nextX == end.x && nextY == end.y) restituisce il nuovo Nodo (nextX, nextY); // Diagonal Case if (dX! = 0 && dY! = 0) if (/ * ... Diagonal Forced Neighbor Check ... * /) return Node.pooledNode (nextX, nextY); // Controlla le direzioni orizzontali e verticali per i vicini forzati // Questo è un caso speciale per la direzione diagonale if (salta (nextX, nextY, dX, 0, start, end)! = Null || jump (nextX, nextY, 0 , dY, start, end)! = null) return Node.pooledNode (nextX, nextY); else // Caso orizzontale if (dX! = 0) if (/ * ... Orizzontale Forced Neighbor Check ... * /) return Node.pooledNode (nextX, nextY); /// Vertical case else if (/ * ... Verticale Forced Neighbor Check ... * /) return Node.pooledNode (nextX, nextY); /// Se il vicino forzato non è stato trovato, provare a eseguire il jump point return jump (nextX, nextY, dX, dY, start, end);
Ho rimosso i controlli dei vicini forzati dalle dichiarazioni if in quanto sono abbastanza grandi. Fondamentalmente consistono in verifiche simili a quelle in cui per la prima volta abbiamo selezionato i vicini per un nuovo nodo (molti controlli per vedere se le celle sono bloccate). Servono allo scopo di rilevare quando siamo autorizzati ad avere le nostre ipotesi sulla simmetria.
Il caso diagonale è speciale e dobbiamo guardare non solo ai vicini forzati nelle direzioni diagonali, ma anche nelle direzioni orizzontale e verticale, e se qualcuno di questi fallisce dobbiamo mettere un nodo forzato come punto di salto. Dobbiamo anche considerare un caso speciale del nodo obiettivo, in cui termina il metodo di salto.
Ogni volta che non troviamo un nodo di ricerca, chiamiamo la funzione di salto in modo ricorsivo nella direzione specificata. Nella demo ho effettivamente srotolato questa chiamata ricorsiva poiché questo sarà chiamato molto. (Nei miei test, questo ha migliorato le prestazioni di un fattore due).
Questo è ciò che fa JPS; il risultato finale sono i nuovi nodi per A * da controllare e procediamo con l'algoritmo. Quando viene trovato il nodo obiettivo, ricostruiamo il percorso e lo restituiamo.
JPS può saltare un sacco di nodi durante la ricerca, il che può dare buoni miglioramenti di velocità (nel mio progetto è di circa 30x su A *), ma ha un costo.
Funziona meglio su una griglia uniforme, ma può essere utilizzato per lavorare con uniformi non uniformi mediante tweaking aggiuntivo, contrassegnando i vicini come obbligati in caso di transizione verso un nodo di costi diversi (meglio usare i costi discreti).
In una partita a cui sto lavorando, la griglia è uniforme tranne che per le strade, che costano molto meno che camminare su un terreno normale. (Sembra molto meglio quando il personaggio rispetta quello.) Alla fine ho risolto questo precalcando alcuni valori delle posizioni stradali. Quando viene avviato il path-finding, l'algoritmo ricerca possibili punti più vicini al percorso dai nodi di inizio e di arrivo, quindi cerca un grafico speciale ad alto livello delle strade (che è precalcolato), quindi utilizza il JPS per cercare aree del terreno.
Una breve nota sul debug. Il debug di questi tipi di algoritmi può essere molto difficile, ed è quasi certo che la prima implementazione avrà qualche bug difficile da trovare. Puoi fare un favore a te stesso e costruire un qualche tipo di visualizzazione funzionalmente e disegnare ciò che sta accadendo quando l'algoritmo funziona.
Se si verifica un errore, è necessario ridurre al minimo il dominio (dimensione della griglia) che consente di riprodurre il problema e testare da lì. Come probabilmente puoi immaginare, la mia prima implementazione di JPS non funzionò immediatamente!
Accentsconagua