1. Inicio
  2. Pregunta y respuesta
  3. Algoritmo de identificación de ruta para Pacman

Algoritmo de identificación de ruta para Pacman

2010-04-08 48 views
15

Quería implementar el juego Pacman. Para la IA, estaba pensando en usar el algoritmo A *, habiéndolo visto en numerosos foros. Sin embargo, implementé la primera búsqueda de amplitud para buscar caminos sencillos (yendo del punto a al punto b con ciertos obstáculos intermedios) y encontré que daba la ruta óptima siempre. Supongo que podría ser porque en un juego como pacman que utiliza una ruta simple, no hay ninguna noción de costos en el gráfico. Entonces, ¿estará bien si uso BFS en lugar de A * para la búsqueda de caminos en Pacman?Algoritmo de identificación de ruta para Pacman

Fuente

2010-04-08 Karan

Respuesta

13

para la trayectoria de investigación, cuenta lo siguiente

  • BFS mirará mucho más nodos que A *, que hace que sea mucho más lento
  • A *, vienen con la misma respuesta que BFS
  • a * es muy fácil de implementar

Si estamos hablando acerca del fantasma AI, echa un vistazo a la página de Chad mencionó: The Pac-Man Dossier - los fantasmas en realidad sólo tiene que utilizar la euclidiana distancia al determinar cómo llegar a sus casillas objetivo, lo que los hace muy malos para encontrar Pac Man en algunos casos.

Fuente

2010-04-08 23:35:48

+0

Desafortunadamente, el desmontaje del Pac-Man ha sido removido. –

+1

A * no es óptimo en el caso general, como dices. Solo se garantiza que encontrará la solución óptima con una heurística admisible y consistente. – b3bop

+1

@ b3bop Estás en lo correcto para el caso general; Estaba hablando sobre el uso de la distancia de Manhattan en una grilla (es decir, el laberinto de Pac-Man). En este caso, la heurística es tanto admisible como consistente, y A * obtendrá la misma respuesta que BFS. –

1

BFS siempre dará la ruta más corta si no se utilizan los pesos de borde. Si no necesitas pesas de borde, usaría eso. Siempre puedes cambiar más tarde.

Fuente

2010-04-08 23:04:09 rlbond

+0

gracias! Tuve la corazonada de que ese podría ser el caso – Karan

+0

bfs es innecesariamente lento, aunque – user151496

+0

Para un juego simple de pac-man, es poco probable que importe. – rlbond

20

Bueno, esto depende, ¿de verdad quieres hacer que los fantasmas funcionen como lo hacen en Pac-Man?

Here's a description of how the ghosts' chase AI works (cada uno funciona de manera diferente). Asegúrate de leer también el capítulo anterior sobre cómo intentan llegar a su target tile. Esa página es un análisis maravillosamente profundo de Pac-Man, lectura interesante.

Fuente

2010-04-08 23:04:27

+4

gracias por el enlace! – Karan

+0

Gracias Chad. No había leído ese artículo antes. – Audie

+2

El enlace está muerto ... – GingerPlusPlus

4

Depende. BFS es completo y óptimo (en el sentido de que encuentra la solución óptima)

¿La desventaja? ¡Puede llevar mucho, mucho, mucho tiempo encontrarlo! Además, dependiendo del factor de ramificación de su problema, puede quedarse sin memoria rápidamente.

Si no tiene problemas de rendimiento, guarde BFS, pero si quiere probarlo en un gran laberinto, puede llevar un tiempo obtener la solución.

Le sugiero que pruebe A *, la mejor estrategia de búsqueda en mi humilde opinión. Incluso si no tiene problemas con BFS, A * es un buen algoritmo para implementar, y aprenderá muchas cosas interesantes.

Fuente

2010-04-08 23:06:33 mcabral

3

Es posible que desee considerar el enfoque antiobjetivo que utilizaron los diseñadores originales de Pacman, puede leer sobre él here y here.

Sin embargo, para responder a su pregunta, utilice lo que funciona. Si obtiene buenos resultados de BFS, úselo. Solo recuerde resumir el pathfinding lo suficiente como para poder reemplazarlo más adelante si encuentra algo mejor.

¡Buena suerte!

Fuente

2010-04-08 23:12:29 Audie

Cuestiones relacionadas

 Cuestiones relacionadas