Share
Un pathfinder basato su griglia funziona bene per i giochi in cui i personaggi possono muoversi liberamente lungo entrambi gli assi xey. Il problema con l'applicazione di questo ai platform è che il movimento sull'asse y è fortemente limitato, a causa delle forze gravitazionali simulate.
In questo tutorial darò un'ampia panoramica su come modificare un algoritmo A * standard per lavorare con i platforming simulando queste restrizioni gravitazionali. (Nella parte successiva, passerò attraverso la codifica dell'algoritmo.) L'algoritmo adattato potrebbe essere usato per creare un personaggio AI che segue il giocatore, o per mostrare al giocatore un percorso verso il loro obiettivo, per esempio.
Presumo che tu abbia già familiarità con il pathfinder A *, ma se hai bisogno di un'introduzione, A * Pathfinding for Beginners di Patrick Lester è eccellente.
Puoi giocare alla demo di Unity o alla versione WebGL (64 MB) per vedere il risultato finale in azione. Uso WASD spostare il personaggio, sinistro del mouse su un punto per trovare un percorso da seguire per arrivarci, e tasto destro del mouse una cella per alternare il terreno in quel punto.
Entro la fine di questa serie, avremo anche aggiunto piattaforme a una via, esteso il codice per gestire diverse dimensioni di carattere e codificato un bot che può seguire automaticamente il percorso! Guarda qui la demo di Unity (o la versione da 100 MB + WebGL).
Prima di poter adattare l'algoritmo del pathfinder, è necessario definire chiaramente quali forme possono essere prese dai percorsi stessi.
Diciamo che il nostro personaggio riprende una cella, e può saltare tre celle alto.
Non permetteremo al nostro personaggio di muoversi in diagonale attraverso le celle, perché non vogliamo che attraversi terreno solido. (Cioè, non permetteremo che si muova attraverso l'angolo di una cella, solo attraverso il lato superiore, inferiore, sinistro o destro.) Per spostarsi in una cella diagonalmente adiacente, il personaggio deve spostare una cella verso l'alto o verso il basso e una cella a sinistra o a destra.
Dal momento che l'altezza di salto del personaggio è di tre celle, quindi ogni volta che salta, dopo che è salito tre volte, non dovrebbe essere in grado di muoversi su più celle, ma dovrebbe comunque essere in grado di spostarsi sul lato.
Sulla base di queste regole, ecco un esempio del percorso che il personaggio avrebbe intrapreso durante il suo salto di massima distanza:
Ovviamente il personaggio può saltare direttamente in alto, o con qualsiasi combinazione di movimenti sinistro e destro, ma questo esempio mostra il tipo di approssimazione che avremo bisogno di abbracciare quando calcoliamo il percorso usando la griglia.
Ognuna delle celle nel percorso dovrà mantenere i dati sull'altezza di salto, in modo che il nostro algoritmo possa rilevare che il giocatore non può saltare più in alto e deve iniziare a cadere.
Iniziamo assegnando il valore di salto di ogni cella aumentandolo di uno, ogni cella, fino a quando il salto continua. Naturalmente, quando il personaggio è a terra, dovrebbe essere il valore di salto 0.
Ecco la regola applicata allo stesso percorso di salto della massima distanza di prima:
La cella che contiene a 6 segna il punto più alto del percorso. Questo ha senso, poiché questo è il doppio del valore dell'altezza massima di salto del personaggio, e il personaggio si alterna spostando una cella verso l'alto e una cella verso il lato, in questo esempio.
Nota che, se il personaggio salta dritto e continuiamo ad aumentare il valore di salto di una cella, allora non funziona più, perché in quel caso la cella più alta avrebbe un valore di salto di 3.
Modifichiamo la nostra regola per aumentare il valore di salto in prossimo numero pari ogni volta che il personaggio si muove verso l'alto. Quindi, se il valore di salto è pari, il personaggio può spostarsi a sinistra, a destra o in basso (o in alto, se non hanno raggiunto un valore di salto di 6 ancora), e se il valore di salto è dispari, il personaggio si sposta solo verso l'alto o verso il basso (a seconda che abbia già raggiunto il picco del salto).
Ecco come si presenta un salto verso l'alto:
E qui c'è un caso più complicato:
Ecco come vengono calcolati i valori di salto:
Come puoi vedere, con questo tipo di numerazione sappiamo esattamente quando il personaggio raggiunge la massima altezza di salto: è la cella con il valore di salto uguale a due volte l'altezza di salto massima del personaggio. Se il valore di salto è inferiore a questo, il personaggio può ancora muoversi verso l'alto; altrimenti, dobbiamo ignorare il nodo direttamente sopra.
Ora che siamo a conoscenza del tipo di movimenti che il personaggio può eseguire sulla griglia, consideriamo la seguente configurazione:
La cella verde in posizione (3, 1) è il personaggio; la cella blu in posizione (2, 5) è l'obiettivo. Disegniamo un percorso che l'algoritmo A * può scegliere prima di tentare di raggiungere l'obiettivo @
Il numero giallo nell'angolo in alto a destra di una cella è il valore di salto della cella. Come puoi vedere, con un salto dritto verso l'alto, il personaggio può saltare tre tessere, ma non oltre. Questo non va bene.
Potremmo trovare più fortuna con un'altra rotta, quindi riavvolgiamo la ricerca e ricominciamo dal nodo (3, 2).
Come puoi vedere, saltare sul blocco a destra del personaggio gli ha permesso di saltare abbastanza in alto per raggiungere l'obiettivo! Tuttavia, c'è un grosso problema qui ...
Con ogni probabilità, il primo percorso che l'algoritmo prenderà è il primo che abbiamo esaminato. Dopo averlo preso, l'algoritmo non arriverà molto lontano e finirà per tornare al nodo (3, 2). Può quindi cercare tra i nodi (4, 2), (4, 3), (3, 3) (ancora), (3, 4) (ancora), (3, 5), e infine la cella obiettivo, (2, 5).
In una versione base dell'algoritmo A *, se un nodo è già stato visitato una volta, non è necessario elaborarlo mai più. In questa versione, tuttavia, lo facciamo. Questo perché i nodi non sono distinti solo dalle coordinate xey, ma anche dai valori di salto.
Nel nostro primo tentativo di trovare un percorso, il valore di salto al nodo (3, 3) era 4; nel nostro secondo tentativo, lo è stato 3. Dal momento che nel secondo tentativo il valore di salto di quella cella era più piccolo, significava che potevamo potenzialmente ottenere più in alto di quanto potessimo nel primo tentativo.
Questo significa fondamentalmente quel nodo (3, 3) con un valore di salto di 4 è un nodo diverso rispetto al nodo a (3, 3) con un valore di salto di 3. La griglia deve essenzialmente diventare tridimensionale con alcune coordinate per accogliere queste differenze, in questo modo:
Non possiamo semplicemente cambiare il valore di salto del nodo in (3, 3) a partire dal 4 a 3, perché alcuni percorsi utilizzano lo stesso nodo più volte; se lo facessimo, sostanzialmente annulleremmo il nodo precedente e questo naturalmente corromperà il risultato finale.
Avremmo lo stesso problema se il primo percorso avesse raggiunto l'obiettivo nonostante i valori di salto più alti; se avessimo sostituito uno dei nodi con uno più promettente, allora non avremmo modo di recuperare il percorso originale.
Ricorda, è il algoritmo che utilizza un approccio basato sulla griglia; in teoria, il tuo gioco e i suoi livelli non devono.
È importante che il personaggio abbia almeno tanta libertà di movimento come l'algoritmo si aspetta, e preferibilmente un po 'di più.
Avere il movimento del personaggio corrisponde esattamente ai vincoli dell'algoritmo non è un approccio praticabile, a causa della natura discreta della griglia e della dimensione della griglia della griglia. È possibile codificare la fisica in modo tale che l'algoritmo lo farà sempre trova un modo se ce n'è uno, ma questo richiede che tu costruisca la fisica per quello scopo.
L'approccio che prendo in questo tutorial è quello di adattare l'algoritmo alla fisica del gioco, non viceversa.
I problemi principali si verificano nei casi limite quando la libertà di libertà di movimento prevista dall'algoritmo non coincide con la vera libertà di movimento del personaggio nel gioco..
Diciamo che l'intelligenza artificiale consente di saltare sei celle, ma la fisica del gioco consente un salto di sette celle. Se c'è un percorso che richiede il salto più lungo per raggiungere l'obiettivo nel momento più veloce, allora il bot ignorerà quel percorso e sceglierà quello più conservatore, pensando che il salto più lungo è impossibile.
Se c'è un percorso che richiede il salto più lungo e non c'è altro modo per raggiungere l'obiettivo, allora il pathfinder concluderà che l'obiettivo è irraggiungibile.
Se, al contrario, l'algoritmo pensa che sia possibile saltare sette celle di distanza, ma la fisica del gioco in realtà consente solo un salto di sei celle, allora il bot può seguire il percorso sbagliato e cadere in un punto dal quale non può ottenere fuori, o provare a trovare un percorso di nuovo e ricevere lo stesso risultato errato, causando un ciclo.
(Tra questi due problemi, è preferibile lasciare che la fisica del gioco consenta una maggiore libertà di movimento rispetto a quanto previsto dall'algoritmo.)
Il primo modo per garantire che l'algoritmo sia sempre corretto è avere livelli che i giocatori non possono modificare. In questo caso, devi solo assicurarti che qualsiasi terreno progettato o generato funzioni bene con l'IA del pathfinder.
La seconda soluzione a questi problemi consiste nel modificare l'algoritmo, la fisica o entrambi, per assicurarsi che corrispondano. Come ho detto prima, questo non significa che devono corrispondere Esattamente; per esempio, se l'algoritmo pensa che il personaggio possa saltare cinque celle verso l'alto, è meglio impostare il salto massimo reale a 5.5 celle alte. (A differenza dell'algoritmo, la fisica del gioco può utilizzare valori frazionari).
A seconda del gioco, potrebbe anche essere vero che il bot AI non trova un percorso esistente non è un grosso problema; semplicemente lascerà e tornerà al suo posto, o semplicemente siederà e aspetterà il giocatore.
A questo punto, dovresti avere una comprensione concettuale decente di come il pathway A * può essere adattato a un platform. Nel mio prossimo tutorial, lo renderemo concreto, adattando in realtà un algoritmo A * Pathfinding esistente per implementarlo in un gioco!
Accentsconagua