artificial-intelligence path-finding heuristics pacman

artificial intelligence - Pacman: ¿cómo encuentran los ojos su camino de regreso al agujero del monstruo?



artificial-intelligence path-finding (22)

  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. Calcula todos los caminos que comienzan desde ese nodo hasta el agujero.
  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 avanza por el camino.

¡Disfrutar!

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 fantasma central después de que Pacman se comió un fantasma.

En mi implementación implementé una solución simple pero horrible. Simplemente codifiqué en cada esquina la dirección que se debe tomar.

¿Hay alguna mejor / o la mejor solución? Tal vez un genérico que funciona con diferentes diseños de nivel?

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

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

Aquí hay un análogo y un pseudocódigo para la idea del relleno por inundación de munición.

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 se trata de una búsqueda en primer lugar, por lo que cada vez que encuentre una nueva plaza adyacente, el mejor camino es a través de p. Es O (N) Yo sí creo.

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

Cualquier solución simple que funcione es mantenible, confiable y se desempeña lo suficientemente bien como una buena solución. Me parece que ya has encontrado una buena solución ...

Es probable que una solución de búsqueda de rutas sea más complicada que su solución actual y, por lo tanto, 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, 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, entonces tal vez debería hacer el pathfinding cuando configura inicialmente los laberintos. Lo más simple sería conseguir que el diseñador de laberinto lo haga a mano. Solo me molestaría en automatizar esto si tienes un montón de laberintos ... o los usuarios pueden diseñarlos.

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

El pacman original no usó la búsqueda de caminos o la inteligencia artificial. Acaba de hacer que los jugadores crean que hay más profundidad de lo que realmente era, pero en realidad 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 habla la gente. Red / Blinky for ex no está siguiendo al jugador en todo momento, como dicen. Nadie parece estar siguiendo sistemáticamente al jugador, a propósito. La posibilidad de que te sigan me parece aleatoria. Y es muy tentador ver un comportamiento aleatorio, especialmente cuando las posibilidades de ser perseguidos 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 era extremadamente simple. Mira el libro, está en uno de los primeros capítulos.

En el Pacman original, el Fantasma encontró la píldora amarilla devoradora por su "olor", dejaría un rastro en el mapa, el fantasma vagaría aleatoriamente hasta que encontraran el olor, luego simplemente seguirían el camino del olfato que los llevaría directamente a el jugador. Cada vez que Pacman se movía, los "valores de olor" se reducían en 1.

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

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

Si lo necesita para generalizar a mapas arbitrarios, podría usar cualquier algoritmo de búsqueda de rutas, por ejemplo, la búsqueda de amplitud es fácil de implementar, y usarla para calcular qué direcciones codificar en cada una de las esquinas, antes de ejecutar el juego.

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

  • continúe moviéndose hacia la siguiente intersección (aunque esto es esencialmente un caso especial de ''cuando se le da una 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 las casillas de salida adyacentes, excepto la que acaba de llegar;
  • Escoger uno que esté más cerca de la portería. Si hay más de uno cerca del objetivo, elija la primera dirección válida en este orden: arriba, izquierda, abajo, derecha.

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

http://gameai.com/wiki/index.php?title=Pac-Man#Respawn Cuando los fantasmas mueren, sus ojos sin cuerpo vuelven a su ubicación inicial. Esto se logra simplemente estableciendo la ficha objetivo del fantasma en esa ubicación. La navegación utiliza las mismas reglas.

En realidad tiene sentido. Tal vez no sea la forma más eficiente del mundo, pero es una buena manera de no tener que preocuparse por otro estado o por cualquier otra razón, simplemente está cambiando el objetivo.

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

He resuelto este problema para los niveles genéricos de esa manera: antes de que comience el nivel, hago algún tipo de "relleno de inundación" desde el agujero del monstruo; Cada baldosa del laberinto que no es una pared recibe un número que dice qué tan lejos está del agujero. Entonces, cuando los ojos están en una baldosa con una distancia de 68, miran cuál de las baldosas vecinas tiene una distancia de 67; Ese es el camino a seguir entonces.

La sugerencia de dtb23 de simplemente elegir una dirección aleatoria en cada esquina, y eventualmente encontrarás que el agujero de los monstruos suena horriblemente ineficiente.

Sin embargo, puedes hacer uso de su algoritmo ineficaz de regreso al hogar para hacer que el juego sea más divertido introduciendo más variaciones en la dificultad del juego. Haría esto aplicando uno de los enfoques anteriores, como sus puntos de ruta o el relleno de inundación, pero al hacerlo de manera no determinista. Entonces, en cada esquina, podría generar un número aleatorio para decidir si desea tomar la forma óptima o una dirección aleatoria.

A medida que el jugador avanza los niveles, reduce la probabilidad de que se tome una dirección aleatoria. Esto agregaría otra palanca en el nivel de dificultad general, además del nivel de velocidad, la velocidad del 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.

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

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

Etiqueta los nodos una vez

Cuando cargue un nivel por primera vez, etiquete todos los nodos de la guarida de monstruo 0 (que representan la distancia desde la guarida). Continúe etiquetando hacia afuera los nodos 1 conectados, 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 entradas múltiples)

Supongo que ya tienes objetos que representan cada nodo y conexiones a sus vecinos. El pseudo código podría verse algo como esto:

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 los nodos tienen la misma distancia, no importa cuál se elija). Pseudo código:

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

Ejemplo completamente etiquetado

No sé mucho sobre cómo implementaste tu juego, pero podrías hacer lo siguiente:

  1. Determine la posición relativa de la ubicación de los ojos a la puerta. es decir, se deja arriba? ¿Justo debajo?
  2. Luego mueva los ojos frente a una de las dos direcciones (por ejemplo, haga que se mueva a la izquierda si está a la derecha de la puerta y debajo de la puerta) y verifique si hay paredes y paredes que le impidan hacerlo.
  3. Si hay muros que le impiden hacerlo, hágalo moverse en dirección opuesta a la otra (por ejemplo, si las coordenadas de los ojos en relación con el alfiler están justo al norte y actualmente se movían a la izquierda, pero hay un muro en el camino que lo hace mover al sur
  4. Recuerde seguir revisando cada vez que se mueva para seguir verificando dónde están los ojos en relación con la puerta y verifique que no haya una coordenada latitudinal. es decir, es sólo por encima de la puerta.
  5. En el caso de que solo esté por encima de la puerta, mueva hacia abajo 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 se "bambolearan" 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

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

Cuando se carga el nivel, todos los path home data in every crossroad están vacíos (predeterminado) y una vez que los fantasmas comienzan a explorar el laberinto, la crossroad path home information se actualiza cada vez que se encuentran en un cruce de "nuevo" o desde un Otro camino tropieza nuevamente en su encrucijada conocida.

Para obtener una alternativa a los algoritmos de búsqueda de rutas más tradicionales, puede echar un vistazo al patrón antiobjeto de aroma a hombre de Pac-Man .

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

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

Edición: lamentablemente el artículo de wikipedia ha sido eliminado, así que WayBack Machine al rescate ...

Propongo que el fantasma almacene el camino que ha tomado desde el agujero hasta el Pacman. Entonces, tan pronto como el fantasma muere, puede seguir este camino almacenado en la dirección inversa.

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

Sabiendo que las rutas de pacman no son aleatorias (es decir, cada nivel específico 0-255, inky, blinky, pinky y clyde funcionarán exactamente en la misma ruta para ese nivel).

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

Suponiendo que ya tiene la lógica necesaria para perseguir a pacman, ¿por qué no reutilizarlo? Solo cambia el objetivo. Parece que sería mucho menos trabajo que intentar crear una rutina completamente nueva usando la misma lógica exacta.