In Pacman i fantasmi scelgono i percorsi in modo indipendente per trovare pacman?

Question

Quindi ho giocato molto pacman nella mia cella ultimamente e mi sto chiedendo come facciano i fantasmi a funzionare indipendentemente l'uno dall'altro. Stavo pensando a come sarebbe stato programmato.

Un'opzione che ho pensato di essere thread. Tutti e 4 i fantasmi sono in esecuzione nei loro thread e in qualche modo trovano la posizione di Pacman. Ma sembra un po 'troppo avere quattro thread che funzionano e la sincronizzazione sarebbe difficile. Inoltre, Google ha scritto pacman in Javascript che non supporta i thread, quindi può essere fatto senza thread e ci deve essere un modo più semplice.

Il mio secondo pensiero erano i gestori di eventi. Trasmetto solo l'evento 'directionChanged' che pacman attiverà a 4 gestori di eventi, uno per ciascun fantasma. Ogni fantasma decide quale percorso prendere per arrivare a Pacman. Questo penso sia più probabile di ciò che sta accadendo. Ma può essere lento se i gestori di eventi vengono eseguiti in modo sincrono, poiché i percorsi dovranno essere calcolati in sequenza e il 4 ° fantasma impiegherà del tempo per cambiare direzione e questo potrebbe creare un lag visibile (probabilmente). Inoltre, i fantasmi sparerebbero un evento loro stessi quando colpiscono un muro e i loro gestori di eventi cambieranno la direzione dei fantasmi. Ma data la frequenza con cui pacman cambia direzione e i quattro fantasmi rispondono, anche i gestori di eventi sembrano un po 'troppo.

Sto dicendo che le idee di cui sopra sarebbero un po 'troppo perché ricordo che il gioco è stato scritto 30 anni fa, quando il tempo e la memoria della cpu erano scarsi, quindi penso che ci debba essere un modo molto più semplice.

Inoltre, sembra che i fantasmi stiano seguendo percorsi diversi anche quando pacman è ancora. Tutti i fantasmi utilizzano algoritmi di individuazione dei percorsi completamente diversi o ottimizzati in modo diverso?

Sono più interessato a scoprire come tutti i fantasmi sembrano funzionare autonomamente rispetto agli algoritmi di individuazione dei percorsi che utilizzano. Pensieri?

Answer 1

Ti stai drasticamente pensando troppo.

I thread e gli event-handlers sono terribilmente lenti rispetto agli standard dei videogiochi. I motori di gioco multi-thread sono un'invenzione relativamente nuova, letteralmente decenni dopo che Pacman è stato rilasciato. logica magro di Pacman si verifica all'interno di un unico ciclo abbastanza stretto, qualcosa di simile a questo pseudocodice molto semplificato:

while (!pacman_dead) { 
    foreach ghost { 
    if (ghost has hit a wall) { 
     if (pacman to left) turn left 
     if (pacman to right) turn right 
    } else { 
     go straight 
     if (ghost touched pacman) { 
     pacman_dead = true 
     } 
    } 
    } 

    handle_input(); 
    move_pacman(); 
    draw_screen();  
} 

Questo è un modello abbastanza comune nel gioco, e dà l'apparenza di concorrenza. In genere un gioco viene eseguito in un singolo ciclo, il che "fa sobbalzare" lo stato di gioco in avanti di qualche piccolo incremento nello spazio tra i ridisegni dello schermo.Questo è il motivo per cui le prestazioni sono ancora molto importanti nello sviluppo del gioco: il tuo gioco deve scorrere su ogni oggetto di gioco che necessita di do qualcosa o prendere una decisione (avversari controllati dall'IA, piattaforme mobili, semplici animazioni, ecc.) E aggiornare i loro stato almeno 30 volte al secondo.

Answer 2

Ci sono molte ottime informazioni su come funziona pacman here, incluse alcune annotazioni dettagliate sul comportamento dei fantasmi.

** Nota Ho trovato queste informazioni da Pathfinding Algorithm For Pacman qualche tempo fa.

EDIT:

Questo blog post ha ancora più informazioni sui fantasmi.

Answer 3

Prima di eseguire il rendering di ciascun fotogramma, eseguivo il loop dei fantasmi. Nessun evento, thread o problema asincrono in questo modo. Probabilmente ogni fantasma ha un'euristica molto cruda per segnare le sue mosse e prendere una decisione (girando a sinistra oa destra, nessuna azione, whatev).

Here's an implementation si potrebbe verificare. :)