Encontré muchas referencias a la IA de los fantasmas en Pacman, pero ninguno de ellos mencionó cómo los ojos encuentran su camino de regreso al agujero central de los fantasmas después de que Pacman se come un fantasma.

En mi implementación, implementé una solución simple pero horrible. Simplemente codifiqué en cada esquina qué dirección debería tomarse.

¿Hay alguna mejor o mejor solución? ¿Tal vez uno genérico que funcione con diseños de diferentes niveles?

En realidad, diría que su enfoque es una solución bastante impresionante, con un costo de tiempo de ejecución casi cero en comparación con cualquier tipo de búsqueda de caminos.

Si necesita que se generalice a mapas arbitrarios, puede usar cualquier algoritmo de búsqueda de ruta, por ejemplo, la búsqueda de amplitud es simple de implementar, y usar eso para calcular qué direcciones codificar en cada una de las esquinas, antes de que se ejecute el juego.

EDITAR (11 de agosto de 2010): Me acaban de remitir a una página muy detallada sobre el sistema Pacman: el Dossier Pac-Man , y como tengo la respuesta aceptada aquí, sentí que debería actualizarla. El artículo no parece cubrir el acto de regresar a la casa de los monstruos explícitamente, pero afirma que la búsqueda directa en Pac-Man es un caso de lo siguiente:

• continúe avanzando hacia la siguiente intersección (aunque este es esencialmente un caso especial de 'cuando se le da la opción, elija la dirección que no implique invertir su dirección, como se ve en el siguiente paso);
• en la intersección, mire los cuadrados de salida adyacentes, excepto el que acaba de llegar;
• escogiendo uno que esté más cerca de la meta. Si hay más de uno igualmente cerca de la meta, elija la primera dirección válida en este orden: arriba, izquierda, abajo, derecha.

Así he resuelto este problema para los niveles genéricos: antes de que comience el nivel, hago algún tipo de "relleno de inundación" desde el agujero del monstruo; Cada azulejo del laberinto que no es una pared obtiene un número que dice qué tan lejos está del agujero. Entonces, cuando los ojos están en un mosaico con una distancia de 68, miran cuál de los mosaicos vecinos tiene una distancia de 67; ese es el camino a seguir entonces.

Para una alternativa a los algoritmos de búsqueda de ruta más tradicionales, puede echar un vistazo al patrón Antiobject Scent de Pac-Man .

Podrías difundir el olor de los agujeros de monstruos alrededor del laberinto al inicio y hacer que los ojos lo sigan a casa.

Una vez que se establece el olor, el costo de tiempo de ejecución es muy bajo.

Editar: lamentablemente, el artículo de Wikipedia se ha eliminado, por lo que WayBack Machine al rescate ...

Deberías echar un vistazo a un algoritmo de pathfindings, como el algoritmo de Dijsktra o el algoritmo A * . Este es tu problema: un problema de gráfico / ruta.

Cualquier solución simple que funcione es mantenible, confiable y funciona suficientemente bien, es una buena solución. Me parece que ya has encontrado una buena solución ...

Es probable que una solución de búsqueda de ruta sea más complicada que su solución actual y, por lo tanto, sea más probable que requiera depuración. Probablemente también será más lento.

OMI, si no está roto, no lo arregles.

EDITAR

OMI, si el laberinto está arreglado, entonces su solución actual es un código bueno / elegante. No cometa el error de equiparar "bueno" o "elegante" con "inteligente". El código simple también puede ser "bueno" y "elegante".

Si tiene niveles de laberinto configurables, tal vez debería hacer la búsqueda de ruta cuando configura inicialmente los laberintos. Lo más sencillo sería conseguir que el diseñador del laberinto lo hiciera a mano. Solo me molestaría en automatizar esto si tienes un laberinto de miles de millones ... o los usuarios pueden diseñarlos.

(Aparte: si las rutas se configuran a mano, el diseñador del laberinto podría hacer que un nivel sea más interesante utilizando rutas subóptimas ...)

En el Pacman original el Fantasma encontró al comedero de pastillas amarillo por su "olor", dejaría un rastro en el mapa, el fantasma deambularía al azar hasta que encontraran el olor, luego simplemente seguirían el camino del olor que los conducía directamente a el jugador. Cada vez que Pacman se movía, los "valores de olor" se reducían en 1.

Ahora, una manera simple de revertir todo el proceso sería tener una "pirámide de olor a fantasma", que tiene su punto más alto en el centro del mapa, luego el fantasma simplemente se mueve en la dirección de este olor.

Suponiendo que ya tiene la lógica requerida para perseguir a Pacman, ¿por qué no reutilizar eso? Solo cambia el objetivo. Parece que sería mucho menos trabajo que tratar de crear una rutina completamente nueva usando exactamente la misma lógica.

Es un problema de búsqueda de caminos. Para un algoritmo popular, consulte http://wiki.gamedev.net/index.php/A* .

¿Qué tal si cada cuadrado tiene un valor de distancia al centro? De esta manera, para cada cuadrado dado, puede obtener valores de cuadrados vecinos inmediatos en todas las direcciones posibles. Escoges el cuadrado con el valor más bajo y te mueves a ese cuadrado.

Los valores se calcularán previamente utilizando cualquier algoritmo disponible.

Esta fue la mejor fuente que pude encontrar sobre cómo funcionaba realmente.

http://gameai.com/wiki/index.php?title=Pac-Man#Respawn Cuando los fantasmas son asesinados, sus ojos incorpóreos regresan a su ubicación inicial. Esto se logra simplemente configurando el mosaico objetivo del fantasma en esa ubicación. La navegación usa las mismas reglas.

En realidad tiene sentido. Tal vez no sea el más eficiente del mundo, pero es una forma bastante agradable de no tener que preocuparse por otro estado ni nada por el estilo, solo está cambiando el objetivo.

Nota al margen: no me di cuenta de lo increíbles que eran esos programadores de pac-man, básicamente hicieron un sistema de mensajes completo en un espacio muy pequeño con memoria muy limitada ... eso es increíble.

Creo que su solución es la adecuada para el problema, más simple que eso, es hacer que una nueva versión sea más "realista" donde los ojos fantasmas puedan atravesar paredes =)

Aquí hay un análogo y un seudocódigo para la idea de relleno de inundación de 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

La idea es que es una búsqueda de amplitud, por lo que cada vez que encuentre un nuevo cuadrado adyacente s, el mejor camino es a través de p. Es O (N) lo que creo.

No sé mucho sobre cómo implementó su juego, pero podría hacer lo siguiente:

1. Determine la ubicación de los ojos en relación con la puerta. es decir, se deja arriba? ¿Justo debajo?
2. Luego mueva los ojos opuestos a una de las dos direcciones (como hacer que se mueva hacia la izquierda si está a la derecha de la puerta y debajo de la puerta) y verifique si hay paredes y paredes que le impiden hacerlo.
3. Si hay paredes que te impiden hacerlo, haz que se mueva en sentido opuesto a la otra dirección (por ejemplo, si las coordenadas de los ojos en relación con el pasador están hacia el norte y actualmente se movía hacia la izquierda pero hay una pared en el camino, hazlo moverse hacia el sur
4. Recuerde seguir verificando cada vez que se mueva para seguir verificando dónde están los ojos en relación con la puerta y verifique si no hay coordenadas latitudinales. es decir, solo está por encima de la puerta.
5. En el caso de que solo esté por encima de la puerta, baje si hay una pared, muévase hacia la izquierda o hacia la derecha y siga haciendo este número 1 - 4 hasta que los ojos estén en el estudio.
6. Nunca he visto un callejón sin salida en Pacman, este código no tendrá en cuenta los callejones sin salida.
7. Además, he incluido una solución para cuando los ojos "oscilarían" entre una pared que se extiende a través del origen en mi pseudocódigo.

Algunos pseudocódigo:

   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

La sugerencia de dtb23 de elegir una dirección aleatoria en cada esquina, y eventualmente encontrarás que el agujero del monstruo suena terriblemente ineficiente.

Sin embargo, puedes utilizar su algoritmo ineficiente de regreso al hogar para hacer que el juego sea más divertido al introducir más variación en la dificultad del juego. Lo haría aplicando uno de los enfoques anteriores, como sus puntos de referencia o el relleno de inundación, pero de manera no determinista. Por lo tanto, en cada esquina, podría generar un número aleatorio para decidir si tomar la forma óptima o una dirección aleatoria.

A medida que el jugador avanza de nivel, reduce la probabilidad de que se tome una dirección aleatoria. Esto agregaría otra palanca en el nivel de dificultad general además de la velocidad de nivel, la velocidad de fantasma, la pausa para comer pastillas (etc.). Tienes más tiempo para relajarte mientras que los fantasmas son solo ojos inofensivos, pero ese tiempo se vuelve más y más corto a medida que avanzas.

Respuesta corta, no muy bien. :) Si altera el laberinto de Pac-man, los ojos no necesariamente volverán. Algunos de los hacks que flotan tienen ese problema. Entonces depende de tener un laberinto cooperativo.

Yo propondría que el fantasma almacene el camino que ha tomado desde el agujero hasta el Pacman. Entonces, tan pronto como el fantasma muera, puede seguir este camino almacenado en la dirección inversa.

Sabiendo que los caminos pacman no son aleatorios (es decir, cada nivel específico 0-255, inky, blinky, pinky y clyde funcionarán exactamente en el mismo camino para ese nivel).

Tomaría esto y luego supongo que hay algunos caminos maestros que envuelven todo el laberinto como un "camino de regreso" que un objeto del globo ocular toma pendiente donde está cuando Pacman se comió al fantasma.

Los fantasmas en pacman siguen patrones más o menos predecibles en términos de tratar de hacer coincidir X o Y primero hasta que se cumpla el objetivo. Siempre supuse que esto era exactamente lo mismo para los ojos que encontraban el camino de regreso.

1. Antes de que comience el juego, guarde los nodos (intersecciones) en el mapa
2. Cuando el monstruo muere, toma el punto (coordenadas) y encuentra el nodo más cercano en tu lista de nodos
3. Calcule todos los caminos que comienzan desde ese nodo hasta el hoyo
4. Toma el camino más corto por longitud
5. Agregue la longitud del espacio entre el punto y el nodo más cercano
6. Dibuja y muévete por el camino

¡Disfrutar!

Mi enfoque requiere un poco de memoria (desde la perspectiva de la era de Pacman), pero solo necesita calcular una vez y funciona para cualquier diseño de nivel (incluidos los saltos).

Etiquetar nodos una vez

Cuando cargue un nivel por primera vez, etiquete todos los nodos de la guarida del monstruo 0 (que representa la distancia desde la guarida). Continúe etiquetando hacia afuera los nodos conectados 1, los nodos conectados a ellos 2, y así sucesivamente, hasta que todos los nodos estén etiquetados. (nota: esto incluso funciona si la guarida tiene múltiples entradas)

Supongo que ya tiene objetos que representan cada nodo y conexiones a sus vecinos. El pseudocódigo podría verse así:

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

Los ojos se mueven al vecino con la etiqueta de distancia más baja

Una vez que todos los nodos están etiquetados, el enrutamiento de los ojos es trivial ... simplemente elija el nodo vecino con la etiqueta de distancia más baja (nota: si varios nodos tienen la misma distancia, no importa cuál se elija). Pseudocódigo:

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

Ejemplo completamente etiquetado

Para mi juego PacMan, hice un " shortest multiple path home" algoritmo que funciona para cualquier laberinto que le proporcione (dentro de mi conjunto de reglas). También funciona a través de ellos túneles.

Cuando se carga el nivel, todo path home data in every crossroadestá vacío (predeterminado) y una vez que los fantasmas comienzan a explorar el laberinto, crossroad path home informationse actualizan cada vez que se topan con una "nueva" encrucijada o desde un camino diferente tropiezan nuevamente con su encrucijada conocida.

El pac-man original no usó la búsqueda de caminos ni la inteligencia artificial. Simplemente hizo que los jugadores creyeran que hay más profundidad de lo que realmente era, pero de hecho fue aleatorio. Como se indica en Inteligencia artificial para juegos / Ian Millington, John Funge.

No estoy seguro de si es verdad o no, pero tiene mucho sentido para mí. Honestamente, no veo estos comportamientos de los que la gente habla. Rojo / Blinky para ex no sigue al jugador en todo momento, como dicen. Nadie parece estar siguiendo constantemente al jugador a propósito. La posibilidad de que te sigan me parece aleatoria. Y es muy tentador ver el comportamiento al azar, especialmente cuando las posibilidades de ser perseguido son muy altas, con 4 enemigos y opciones de giro muy limitadas, en un espacio pequeño. Al menos en su implementación inicial, el juego fue extremadamente simple. Mira el libro, está en uno de los primeros capítulos.