risposta-alla-domanda-sullo-sviluppo-web-bd.com

Pacman: come fanno gli occhi a tornare alla buca dei mostri?

Ho trovato molti riferimenti all'intelligenza artificiale dei fantasmi in Pacman, ma nessuno di loro ha menzionato il modo in cui gli occhi tornano al buco fantasma centrale dopo che un fantasma è stato mangiato da Pacman.

Nella mia implementazione ho implementato una soluzione semplice ma terribile. Ho appena programmato su ogni angolo quale direzione dovrebbe essere presa.

Esistono soluzioni migliori/migliori? Forse uno generico che funziona con disegni di livello diverso?

321

In realtà, direi che il tuo approccio è una soluzione davvero fantastica, con un costo a tempo quasi zero rispetto a qualsiasi tipo di pathfinding.

Se ne hai bisogno per generalizzare su mappe arbitrarie, puoi usare qualsiasi algoritmo di rilevamento dei percorsi - ad esempio la ricerca della larghezza di campo è semplice da implementare - e usarlo per calcolare quali direzioni codificare in ciascuno degli angoli, prima che il gioco venga eseguito.

EDIT (11 agosto 2010): Mi è stato appena fatto riferimento a una pagina molto dettagliata sul sistema Pacman: The Pac-Man Dossier , e dato che ho la risposta accettata qui, ho sentito di doverlo aggiornare. L'articolo non sembra riguardare l'atto di tornare alla casa dei mostri in modo esplicito, ma afferma che il percorso diretto in Pac-Man è un caso del seguente:

  • continua a spostarti verso l'incrocio successivo (anche se questo è essenzialmente un caso speciale di "quando ti viene data una scelta, scegli la direzione che non implica invertire la tua direzione, come visto nel passaggio successivo);
  • all'incrocio, guarda i quadrati di uscita adiacenti, tranne quello da cui sei appena arrivato;
  • sceglierne uno più vicino all'obiettivo. Se più di uno è ugualmente vicino all'obiettivo, scegli la prima direzione valida in questo ordine: su, sinistra, giù, destra.
151
Kylotan

Ho risolto questo problema per i livelli generici in quel modo: prima che inizi il livello, faccio una sorta di "riempimento" dal buco del mostro; ogni tessera del labirinto che non è un muro riceve un numero che indica quanto è lontano dal buco. Quindi quando gli occhi sono su una piastrella con una distanza di 68, guardano quale delle tessere vicine ha una distanza di 67; questa è la strada da percorrere allora.

85

Per un'alternativa agli algoritmi di pathfinding più tradizionali, è possibile dare un'occhiata al (nome appropriato!) modello Antiobject di profumo di Pac-Man .

All'avvio potresti diffondere odore di buco mostro attorno al labirinto e far sì che gli occhi lo seguano a casa.

Una volta impostato l'odore, il costo di runtime è molto basso.


Modifica: purtroppo l'articolo di Wikipedia è stato cancellato, quindi WayBack Machine in soccorso ...

42
Dan Vinton

Dovresti dare un'occhiata a un algoritmo di pathfinding, come Aljit di Dijkstra o Algoritmo A * . Questo è il tuo problema: un problema grafico/percorso.

18
Clement Herreman

Qualsiasi soluzione semplice che funzioni sia mantenibile, affidabile e che funzioni abbastanza bene è una buona soluzione. Mi sembra che tu abbia già trovato una buona soluzione ...

È probabile che una soluzione di individuazione del percorso sia più complicata della soluzione attuale e quindi più probabilmente richiederà il debug. Probabilmente sarà anche più lento.

IMO, se non è rotto, non aggiustarlo.

[~ ~ #] modifica [~ ~ #]

IMO, se il labirinto è stato risolto, la soluzione corrente è codice buono/elegante. Non commettere l'errore di equiparare "buono" o "elegante" a "intelligente". Il codice semplice può anche essere "buono" ed "elegante".

Se hai livelli di labirinto configurabili, allora forse dovresti semplicemente fare il pathfinding quando configuri inizialmente i labirinti. La cosa più semplice sarebbe convincere il designer del labirinto a farlo a mano. Mi preoccuperei solo di automatizzare questo se hai un labirinto di labirinti ... o gli utenti possono progettarli.

(A parte: se i percorsi sono configurati a mano, il progettista del labirinto potrebbe rendere un livello più interessante usando percorsi non ottimali ...)

18
Stephen C

Nell'originale Pacman lo Spettro trovò il mangiatore di pillole gialle con il suo "odore" che avrebbe lasciato una traccia sulla mappa, il fantasma avrebbe vagato in modo casuale fino a quando non avessero trovato l'odore, quindi avrebbero semplicemente seguito il percorso dell'olfatto che li conduce direttamente a il giocatore. Ogni volta che Pacman si muoveva, i "valori dell'olfatto" venivano ridotti di 1.

Ora, un modo semplice per invertire l'intero processo sarebbe quello di avere una "piramide dell'odore fantasma", che ha il suo punto più alto al centro della mappa, quindi il fantasma si sposta semplicemente nella direzione di questo odore.

14
Ivo Wetzel

Supponendo che tu abbia già la logica necessaria per inseguire pacman perché non riutilizzarlo? Basta cambiare il bersaglio. Sembra che sarebbe molto meno lavoro che cercare di creare una routine completamente nuova usando la stessa logica esatta.

5
John Gardeniers

Questa è stata la migliore fonte che ho potuto trovare su come funzionava effettivamente.

http://gameai.com/wiki/index.php?title=Pac-Man#Respawn Quando i fantasmi vengono uccisi, i loro occhi disincarnati tornano alla loro posizione iniziale. Ciò si ottiene semplicemente impostando la tessera bersaglio del fantasma in quella posizione. La navigazione utilizza le stesse regole.

In realtà ha senso. Forse non è il più efficiente al mondo, ma un modo piuttosto carino di non doversi preoccupare di un altro stato o di qualcosa del genere, stai solo cambiando il bersaglio.

Nota a margine: non mi rendevo conto di quanto fossero fantastici quei programmatori pac-man che fondamentalmente creavano un intero sistema di messaggi in uno spazio molto piccolo con una memoria molto limitata ... è incredibile.

3
Midpipps

Che ne dici di ogni quadrato che ha un valore di distanza dal centro? In questo modo per ogni dato quadrato è possibile ottenere i valori dei quadrati vicini immediati in tutte le direzioni possibili. Scegli il quadrato con il valore più basso e passa a quel quadrato.

I valori sarebbero pre-calcolati usando qualsiasi algoritmo disponibile.

3
mvbl fst

È un problema patogeno. Per un algoritmo popolare, vedi http://wiki.gamedev.net/index.php/A* .

3
Marijn

il suggerimento di dtb23 di scegliere semplicemente una direzione casuale ad ogni angolo, e alla fine troverai che il mostro suona orribilmente inefficace.

Tuttavia, potresti sfruttare il suo inefficiente algoritmo di ritorno a casa per rendere il gioco più divertente introducendo più variazioni nella difficoltà del gioco. Lo faresti applicando uno dei suddetti approcci come i tuoi waypoint o il riempimento di alluvione, ma facendo ciò in modo non deterministico. Quindi ad ogni angolo, potresti generare un numero casuale per decidere se prendere la strada ottimale o una direzione casuale.

Man mano che il giocatore avanza di livello, riduci la probabilità che venga presa una direzione casuale. Ciò aggiungerebbe un'altra leva sul livello di difficoltà generale in aggiunta alla velocità del livello, alla velocità dei fantasmi, alla pausa del consumo di pillole (ecc.). Hai più tempo per rilassarti mentre i fantasmi sono solo occhi innocui, ma quel tempo diventa sempre più breve man mano che avanzi.

2
imoatama

Risposta breve, non molto bene. :) Se alteri il labirinto di Pac-man gli occhi non torneranno necessariamente. Alcuni degli hack che fluttuano intorno hanno questo problema. Quindi dipende dall'avere un labirinto cooperativo.

2
dwidel

Penso che la tua soluzione sia giusta per il problema, più semplice di così, è rendere una nuova versione più "realistica" in cui gli occhi fantasma possono attraversare i muri =)

2
Hernán Eche

Ecco un analogo e uno pseudocodice all'idea di riempimento inondazione di ammoQ.

queue q
enqueue q, ghost_Origin
set visited

while q has squares
   p <= dequeue q
   for each square s adjacent to p
      if ( s not in visited ) then
         add s to visited
         s.returndirection <= direction from s to p
         enqueue q, s
      end if
   next
 next

L'idea è che si tratta di una prima ricerca, quindi ogni volta che incontri un nuovo quadrato adiacente s, il percorso migliore è attraverso p. È O(N) Credo.

2
Mark Peters

Non so molto su come hai implementato il tuo gioco, ma potresti fare quanto segue:

  1. Determina la posizione relativa degli occhi rispetto al cancello. cioè è lasciato sopra? Proprio sotto?
  2. Quindi sposta gli occhi di fronte a una delle due direzioni (ad esempio, fai in modo che si sposti a sinistra se si trova a destra del cancello e sotto il cancello) e controlla se ci sono e muri che ti impediscono di farlo.
  3. Se ci sono muri che ti impediscono di farlo, allora spostalo nella direzione opposta (ad esempio, se le coordinate degli occhi rispetto al perno sono proprio a nord e si stava muovendo a sinistra ma c'è un muro nel modo di farlo spostati a sud.
  4. Ricorda di continuare a controllare ogni volta per muoverti per continuare a controllare dove si trovano gli occhi rispetto al cancello e controlla per vedere quando non ci sono coordinate latitudinali. cioè è solo sopra il cancello.
  5. Nel caso in cui sia solo sopra il cancello spostati verso il basso se c'è un muro, muoviti a sinistra oa destra e continua a fare questo numero 1 - 4 fino a quando gli occhi non sono nella tana.
  6. Non ho mai visto un vicolo cieco in Pacman questo codice non terrà conto dei vicoli ciechi.
  7. Inoltre, ho incluso una soluzione a quando gli occhi "oscillano" tra un muro che attraversa l'origine nel mio pseudocodice.

Alcuni pseudocodici:

   x = getRelativeOppositeLatitudinalCoord()
   y
   origX = x
    while(eyesNotInPen())
       x = getRelativeOppositeLatitudinalCoordofGate()
       y = getRelativeOppositeLongitudinalCoordofGate()
       if (getRelativeOppositeLatitudinalCoordofGate() == 0 && move(y) == false/*assume zero is neither left or right of the the gate and false means wall is in the way */)
            while (move(y) == false)
                 move(origX)
                 x = getRelativeOppositeLatitudinalCoordofGate()
        else if (move(x) == false) {
            move(y)
    endWhile
2
thyrgle

Proporrei che il fantasma memorizzi il percorso che ha preso dal buco al Pacman. Quindi non appena il fantasma muore, può seguire questo percorso memorizzato nella direzione opposta.

2
Fischer Ludrian
  1. Prima che inizi il gioco, salva i nodi (intersezioni) nella mappa
  2. Quando il mostro muore, prendi il punto (coordinate) e trova il nodo più vicino nell'elenco dei tuoi nodi
  3. Calcola tutti i percorsi a partire da quel nodo alla buca
  4. Prendi il percorso più breve per lunghezza
  5. Aggiungi la lunghezza dello spazio tra il punto e il nodo più vicino
  6. Disegna e sposta sul percorso

Godere!

1
GingerHead

Il mio approccio richiede un po 'di memoria (dal punto di vista dell'era Pacman), ma devi solo calcolarlo una volta e funziona per qualsiasi livello di progettazione (compresi i salti).

Etichetta nodi una volta

Quando carichi un livello per la prima volta, etichetta tutti i nodi 0 della tana dei mostri (che rappresentano la distanza dalla tana). Procedere con l'etichettatura esterna verso nodi collegati 1, nodi collegati a loro 2 e così via, fino a quando tutti i nodi sono stati etichettati. (nota: questo funziona anche se la tana ha più ingressi)

Presumo che tu abbia già oggetti che rappresentano ciascun nodo e connessioni ai loro vicini. Lo pseudo codice potrebbe assomigliare a questo:

public void fillMap(List<Node> nodes) { // call passing lairNodes
    int i = 0;

    while(nodes.count > 0) {
        // Label with distance from lair
        nodes.labelAll(i++);

        // Find connected unlabelled nodes
        nodes = nodes
            .flatMap(n -> n.neighbours)
            .filter(!n.isDistanceAssigned());
    }
}

Flood-fill out from lair

Gli occhi si spostano sul vicino con l'etichetta della distanza più bassa

Una volta che tutti i nodi sono stati etichettati, instradare gli occhi è banale ... basta scegliere il nodo vicino con l'etichetta della distanza più bassa (nota: se più nodi hanno la stessa distanza, non importa quale sia selezionato). Pseudo codice:

public Node moveEyes(final Node current) {
    return current.neighbours.min((n1, n2) -> n1.distance - n2.distance);
}

Esempio completamente etichettato

Complete map

1
AjahnCharles

Sapendo che i percorsi pacman sono non casuali (cioè, ogni livello specifico 0-255, inky, blinky, pinky e clyde funzioneranno nello stesso identico percorso per quel livello).

Lo prenderei e indovinerei che ci sono alcuni percorsi principali che avvolgono l'intero labirinto come un "percorso di ritorno" che un oggetto bulbo oculare porta in attesa dove si trova quando l'uomo pac ha mangiato il fantasma.

1
Incognito

I fantasmi in Pacman seguono schemi più o meno prevedibili in termini di tentare di abbinare prima su X o Y fino al raggiungimento dell'obiettivo. Ho sempre pensato che fosse esattamente lo stesso per gli occhi che cercavano di tornare indietro.

1
plinth

Per il mio gioco PacMan ho fatto un po '" shortest multiple path home "algoritmo che funziona per qualsiasi labirinto che fornisco (nel mio insieme di regole). Funziona anche attraverso i tunnel.

Quando il livello è caricato, tutti i path home data in every crossroad è vuoto (impostazione predefinita) e una volta che i fantasmi iniziano a esplorare il labirinto, essi crossroad path home information continua ad essere aggiornato ogni volta che si imbatte in un "nuovo" incrocio o da un percorso diverso inciampano di nuovo sul loro incrocio noto.

0
iNyuu