En Pacman, ¿los fantasmas eligen caminos independientes para encontrar pacman?

Question

Así que he estado jugando mucho pacman en mi celular últimamente y me pregunto cómo los fantasmas parecen funcionar independientemente el uno del otro. Estaba pensando en cómo habría sido programado.

Una opción en la que pensé fueron los hilos. Los 4 fantasmas se ejecutan en sus propios hilos y de alguna manera encuentran la posición de pacman. Pero parece un poco demasiado tener cuatro hilos trabajando y la sincronización sería difícil. Además, google escribió pacman en Javascript, que no admite subprocesos, por lo que se puede hacer sin hilos y tiene que haber una manera más fácil.

Mi segundo pensamiento fueron los controladores de eventos. Simplemente conecto el evento 'directionChanged' que pacman disparará a 4 manejadores de eventos, uno para cada fantasma. Cada fantasma luego decide qué camino tomar para llegar a pacman. Esto creo que es más probable lo que está sucediendo. Pero puede ser lento si los controladores de eventos se ejecutan sincrónicamente, porque las rutas se deben calcular de forma secuencial y el cuarto fantasma tardará un tiempo en cambiar de dirección y esto podría crear un retraso visible (probablemente). Además, los fantasmas dispararían un evento ellos mismos cuando golpeen una pared y sus manejadores de eventos cambiarían la dirección de los fantasmas. Pero dada la frecuencia con la que pacman cambia de dirección y los cuatro fantasmas responden, los manejadores de eventos también parecen demasiado.

Digo que las ideas anteriores serían demasiado porque recuerdo que el juego fue escrito hace 30 años cuando el tiempo de la CPU y la memoria eran escasos, así que creo que tiene que haber una manera mucho más sencilla.

Además, parece que los fantasmas están siguiendo caminos diferentes incluso cuando pacman está quieto. ¿Todos los fantasmas utilizan algoritmos de búsqueda de ruta completamente diferentes o optimizados de forma diferente?

Estoy más interesado en descubrir cómo todos los fantasmas parecen funcionar por sí mismos de forma simultánea a los algoritmos de búsqueda de ruta que utilizan. ¿Pensamientos?

Answer 1

Estás drásticamente pensando demasiado en esto.

Los hilos y los controladores de eventos son terriblemente lentos según los estándares de los videojuegos. Los motores de juego con múltiples subprocesos son una invención relativamente nueva, literalmente décadas después de la liberación de Pacman. escasa lógica de Pacman se producirá dentro de un solo bucle bastante estrecho, algo como esto pseudocódigo muy simplificada:

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

Este es un patrón bastante común en los juegos, y le da la apariencia de concurrencia. Por lo general, un juego se ejecutará en un solo bucle, lo que "empujará" el estado del juego hacia delante en un pequeño incremento en el espacio entre los rediseños de la pantalla.Esta es la razón por la cual el rendimiento es muy importante en el desarrollo del juego: su juego debe iterar sobre cada objeto del juego que necesite hacer algo o tomar una decisión (oponentes controlados por AI, plataformas en movimiento, animaciones simples, etc.) y actualizar su estado al menos 30 veces por segundo.

Answer 2

Hay mucha información excelente acerca de cómo funciona el here de Pacman, incluyendo algunos comentarios detallados sobre el comportamiento de los fantasmas.

** Nota Encontré esta información de Pathfinding Algorithm For Pacman hace un tiempo.

EDIT:

Este blog post tiene aún más información acerca de los fantasmas.

Answer 3

Antes de procesar cada fotograma, me gustaría recorrer los fantasmas. No hay eventos, hilos o problemas de asincronización de esa manera. Cada fantasma probablemente tiene una heurística muy cruda para anotar sus movimientos y tomar una decisión (girando a la izquierda o a la derecha, sin acción, whatev).

Here's an implementation se puede retirar. :)