Ricerca del percorso in un gioco Java 2d?

Question

Essenzialmente sto lavorando a un clone pacman. Ho una classe Enemy e sono state create 4 istanze di questa classe che rappresentano tutte 4 fantasmi del gioco.

Tutti i fantasmi si avviano in aree casuali dello schermo e poi devono farsi strada verso il personaggio pacman. Mentre il giocatore controlla il pacman, spostandolo, dovrebbe seguirlo e prendere il modo più vicino possibile verso di lui.

Non ci sono labirinti / ostacoli (ancora), quindi l'intera mappa (400x400 pixel) è aperta per loro.

Per il giocatore e ogni fantasma, posso recuperare gli attributi X, Y, larghezza immagine e altezza. Inoltre, ho già un algoritmo di rilevamento delle collisioni, quindi non sono preoccupato per questo, solo per i fantasmi che trovano la loro strada per Pacman.

Answer 1

Per un buon algoritmo di pathfinding, utilizzare A * sarebbe probabilmente una buona idea, tuttavia, per un gioco semplice che non richiede una ricerca del percorso sofisticata, efficiente o efficace, basta semplicemente far muovere i personaggi verso un bersaglio scoprendo la direzione del bersaglio.

Ad esempio, la decisione di far muovere il personaggio, in pseudocodice:

if (target is to the left of me):
    move(left);
else
    move(right);

if (target is above me):
    move(up);
else
    move(down);

Sì, il personaggio non farà il movimento più efficiente, ma si avvicinerà sempre più al bersaglio su ogni iterazione del ciclo di gioco.

Suppongo anche che un gioco arcade dei primi anni 80 probabilmente non userebbe sofisticati algoritmi di pathfinding.

Answer 2

Se hai solo una griglia di pixel, un "grande campo" su cui pacman e fantasma possono muoversi liberamente - quindi il percorso più breve è facile - una linea retta tra il fantasma e il pacman.

Ma "percorso più breve" invariabilmente significa che stiamo cercando di risolvere un problema di teoria dei grafi. (Sto assumendo la conoscenza dei grafici, della teoria dei grafi, delle matrici aggiustate, ecc.)

Nel caso precedente, considera ogni pixel come un nodo su un grafico. Ogni nodo è collegato ai suoi vicini da un bordo e ogni bordo ha uguale "peso" (passare al nodo "sopra" e non è più lento che passare al nodo "sotto").

Quindi hai questo: (" * " = nodo, " -, /, \, | " = bordo)

*-*-*
|\|/|
*-*-*  ... (etc)
|/|\|
*-*-* 

Se Pacman è al centro, può spostarsi facilmente su qualsiasi altro nodo.

Qualcosa di più vicino alla realtà potrebbe essere questo:

*-*-*
| | |
*-*-*  ... (etc)
| | |
*-*-* 

Ora Pacman non può muoversi in diagonale. Per passare dal centro in basso a destra sono necessari 2 "luppoli" piuttosto che uno.

Per continuare la progressione:

*-*-*-*
| | | |
| | | |
| | | |
*-*-*-*
| | | |
*-*-*-*

Ora, per passare da un nodo in mezzo a un nodo in alto, hai bisogno di 3 salti. Tuttavia, per spostarsi verso il basso richiede solo 1 hop.

Sarebbe facile tradurre qualsiasi configurazione del tabellone in un grafico. Ogni "incrocio" è un nodo. Il percorso tra due intersezioni è un bordo e la lunghezza di quel percorso è il peso di quel bordo.

Immettere A *. Costruendo un grafico (utilizzare una matrice di adeguatezza o un elenco di nodi), è possibile utilizzare l'algoritmo A * per trovare il percorso più breve. Altri algoritmi includono Dijkstra. E molti altri! Ma prima devi inquadrare il tuo problema in termini di un grafico, e poi giocare con come andresti dal nodo A (pacman) al nodo B (fantasma).

Spero che ti aiuti!

Answer 3

È passato molto tempo, ma dalla memoria i fantasmi di Pac-Man non hanno fatto molto per quanto riguarda il pathfinding. Avrebbero fatto un traversamento randomizzato abbastanza standard del labirinto fino a quando non fossero stati "individuati" tu, che comportavi trovare un percorso libero lungo l'asse di un corridoio verso di te, e poi si sarebbero mossi direttamente verso di te fino a quando non saresti scomparso dalla loro linea di vista, dopodiché avrebbero ripreso uno schema casuale. Ai livelli più alti Pac-Man avrebbe lasciato dietro di sé tracce invisibili per un po 'che i fantasmi avrebbero "annusato". e a volte seguire.

Quando Pac-Man si è potenziato, l'unica differenza nell'algoritmo è che, quando ti individuavano, i fantasmi ti scappavano invece di spostarsi verso di te.

Quindi, per un'esperienza autentica, probabilmente non hai bisogno di un algoritmo di ricerca dei percorsi molto sofisticato. Se vuoi essere elegante, ovviamente, puoi implementare A *.

Answer 4

Camminare direttamente verso i tuoi nemici è un inizio, ma quando aggiungi un labirinto vorrai aggiungere un po 'più intelligente tracciamento in modo che i tuoi fantasmi non rimangano bloccati in curve o vicoli ciechi.

Il seguente tutorial è un'ottima guida leggera per iniziare con A *, con esempi scaricabili.

Ricerca di percorsi su mappe basate su piastrelle

Answer 5

in Pacman tutto il fantasma aveva un diverso algoritmo di inseguimento

• Blinky - > Chase. Di solito ti seguirà il percorso più breve e tende a seguirlo.
• Pinky - > Imboscate. Tende a prendere una strada più rotonda per pac-man. Mortale. (il mignolo e il battito di ciglia tendono a fare una scelta diversa quando si sceglie una direzione, spesso ingabbiando il giocatore in un angolo)
• Inky - > Freak. Questo tizio si comporta in modo strano. Si muove sulla scacchiera in modo abbastanza casuale, ma a volte insegue quando si avvicina.
• Clyde - > Idiota. Si sposta in modo casuale. Non c'è molta minaccia.

I fantasmi hanno uno schema interessante programmato nei loro movimenti: ogni tanto cessano e desistono simultaneamente la loro ricerca di Pac-Man e ritornano ai rispettivi angoli del labirinto, entrando in "modalità scatter".

c'è una descrizione completa dell'algo su il dossier pacman

Per quanto riguarda

Guillaume

Answer 6

Potresti iniziare guardando A * (una stella)

E ecco una pagina che contiene collegamenti ad altri algoritmi per la ricerca di percorsi.

[modifica] gah ... il cervello è troppo lento ... ho dimenticato questo libro, è C o C ++ (dimentico quale), ma puoi ancora ottenere i concetti per Java. Potrebbe non essere il più facile da leggere, ma nel complesso non è male. AI for Game Developers di David M. Bourg, Glenn Seemann .

Answer 7

Penso che scelga l'algoritmo del percorso più breve ad ogni mossa fatta da pacman. Un'ottima implementazione è Algoritmo di Dijkstra .

Solo per riassumere: visualizza il labirinto come un grafico con vertici e bordi. Ogni bordo ha un'attesa (nel tuo caso tutti i bordi hanno lo stesso peso). L'algoritmo trova il percorso più breve dal vertice di origine al vertice di destinazione spostando di un gradino verso il basso ogni bordo raggiungibile immediatamente. Quindi sul vertice successivo fai lo stesso e continua a fare fino a quando non raggiungi il bersaglio. Il primo percorso raggiunto è il percorso più breve. Ci possono essere molte ottimizzazioni apportate a questo algoritmo per accelerare cose come tenere conto di dove si trovava il pacman nella sua posizione precedente e in quale direzione si muoveva in modo da poter ottenere un po 'di eredità nell'algoritmo. Suggerirei di trovare il percorso più breve da ciascun fantasma a pacman su ogni movimento e spostare il fantasma in quella direzione. Alla fine la distanza si ridurrà e sarai in grado di catturare pacman.

Un altro euristico che può essere usato per trovare tutti i bordi immediati raggiungibili da pacman e provare a coprire quanti più vertici possibile dai fantasmi. Quindi, invece di impostare pacman come vertice bersaglio, impostiamo i vertici immediatamente raggiungibili da pacman come bersaglio, il risultato sarà che i fantasmi disponibili cercheranno di coprire le principali vie di fuga di pacman e catturarlo.