¿Cuál es el algoritmo utilizado por los monstruos perseguidores en Pac-Man?

No estoy diciendo que esto sea autoritario, pero Neal Ford tiene un papel en esto en su libro, El Programador Productivo:

¡Advertencia! Si todavía te gusta jugar PacMan, no leas los siguientes párrafos, ya que te arruinarán para siempre. A veces el conocimiento tiene un precio.
Considere el juego de consola PacMan. Cuando salió en la década de 1970, tenía menos capacidad computacional que un teléfono celular barato de hoy. Sin embargo, tenía que resolver un problema matemático realmente difícil: ¿cómo lograr que los fantasmas persigan a PacMan por el laberinto? Es decir: ¿cuál es la distancia más corta a un objetivo en movimiento a través de un laberinto? Ese es un gran problema, especialmente si tiene muy poca memoria o potencia de procesador para trabajar. Entonces, los desarrolladores de PacMan no resolvieron ese problema, usaron el enfoque antiabjeto y construyeron la inteligencia en el laberinto.
El laberinto en PacMan actúa como un autómata (como en Conway’s Game of Life). Cada celda tiene reglas simples asociadas, y las celdas se ejecutan una a la vez, comenzando en la esquina superior izquierda y continuando en la esquina inferior derecha. Cada celda recuerda un valor de “olor a PacMan”. Cuando PacMan se sienta en una celda, tiene el máximo olor a PacMan. Si acababa de desocupar la celda, tiene el máximo olor a PacMan –1. El olor se degrada por algunas vueltas más, luego desaparece. Los fantasmas pueden ser tontos: solo huelen el olor de PacMan, y cada vez que lo encuentran, van a la celda que tiene un olor más fuerte.
La solución “obvia” al problema construye inteligencia en los fantasmas. Sin embargo, la solución mucho más simple construye la inteligencia en el laberinto. Ese es el enfoque anti-objeto: voltear el primer plano y el fondo computacional. No caiga en la trampa de pensar que el modelado “tradicional” es siempre la solución correcta. Quizás un problema particular se resuelva más fácilmente en otro idioma por completo.

Cada fantasma tiene su propia personalidad que se utiliza para determinar cómo persigue a Pac-Man. Cada fantasma puede estar en modo persecución o dispersión: los cambios de modo se denotan mediante una inversión de dirección. En el modo de dispersión, cada fantasma tiene una esquina de inicio a la que va y circula: en el modo de persecución, cada fantasma exhibe un método de persecución individual.

Esta publicación:
http://home.comcast.net/~jpittma
proporciona detalles adicionales significativos, con gran parte de los puntos clave resumidos aquí:
http://gameinternals.com/post/20

Hay un curso de inteligencia artificial de Berkeley, ahora disponible gratuitamente en edX, usando Pacman como ejemplo, para que pueda ver todos los detalles usted mismo:

Sobre CS188.1x

También ha habido una competencia para programar IA para Pacman o fantasmas:

Sra. Pac-Man Competition

No creo que el algoritmo original sea calificado como AI. No sé cuán complejo es hoy, pero recuerdo haber escrito un clon de pac-man para un proyecto universitario; El algoritmo para los fantasmas consistía en unas pocas reglas. Obviamente, el objetivo es minimizar la distancia entre el fantasma y pac-man; la forma de hacerlo era intentar minimizar la distancia horizontal si es posible, o la distancia vertical si la posición horizontal ya era la misma (o si el movimiento horizontal no era posible). Y evite retroceder, aunque algún tiempo después noté que los fantasmas originales de pac-man retroceden ocasionalmente.

Comprender el comportamiento fantasma de Pac-Man tiene una gran explicación.

Definitivamente no es al azar. Cada fantasma tiene su propia “personalidad” cuidadosamente programada y se mueve en consecuencia.
http://gameinternals.com/post/20 … tiene los detalles.

Es mucho más simple de lo que imaginas. Las computadoras utilizadas para construir juegos como Pacman no tenían el poder de hacer ninguna de las cosas que sugieres.

http://gameinternals.com/post/20