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

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.

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 ...

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

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 ...)

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.

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.

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.

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.

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

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.

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.

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 =)

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.

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

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.

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!

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());
    }
}

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

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.

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.

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.