Búsqueda de ruta en un juego Java 2d?

Question

Esencialmente es un juego de clones de Pacman en el que estoy trabajando. Tengo una clase Enemy y se crearon 4 instancias de esta clase que representan 4 fantasmas del juego.

Todos los fantasmas se inician en áreas aleatorias de la pantalla y luego tienen que abrirse camino hacia el personaje de pacman. A medida que el jugador controla el pacman, moviéndolo, debe seguirlo y tomar el camino más cercano posible hacia él.

No hay laberintos/obstáculos (todavía) por lo que todo el mapa (400x400 píxeles) está abierto para ellos.

Para el jugador y cada Fantasma, puedo recuperar los atributos X, Y, ancho y alto de la imagen. Además, ya tengo un algoritmo de detección de colisión, así que no me preocupa eso, solo los fantasmas encuentran su camino hacia pacman.

Answer 1

Para un buen algoritmo de pathfinding, usar A* probablemente sería una buena idea, sin embargo, para un juego simple que no requiere una búsqueda de ruta sofisticada, eficiente ni efectiva, simplemente haciendo que los personajes se muevan hacia un objetivo descubriendo la dirección del objetivo debería ser suficiente.

Por ejemplo, la decisión de hacer que el personaje se mueva, en pseudocódigo:

if (target is to the left of me): 
    move(left); 
else 
    move(right); 

if (target is above me): 
    move(up); 
else 
    move(down); 

Sí, el personaje no se va a hacer el movimiento más eficiente, pero va a acercarse cada vez más a la meta de cada iteración del bucle del juego.

También creo que un juego de arcade de principios de los 80 probablemente no usaría sofisticados algoritmos de ruta.

Answer 2

Se podría empezar looking at A* (A star)

Y here is a page que tiene enlaces a los algoritmos de búsqueda de otras rutas.

[edit] gah ... el cerebro es demasiado lento ... se olvidó de este libro, es C o C++ (se me olvida cuál), pero aún puede obtener los conceptos para Java. Puede que no sea lo más fácil para ti leer, pero no está mal en general. AI for Game Developers by David M. Bourg, Glenn Seemann.

Answer 3

Si solo tiene una cuadrícula de píxeles, un "gran campo" en el que pacman y fantasma se pueden mover libremente, entonces la ruta más corta es fácil: una línea recta entre el fantasma y el pacman.

Pero el "camino más corto" invariablemente significa que estamos tratando de resolver un problema de teoría de grafos. (¡Estoy asumiendo el conocimiento de gráficos, algunas teorías de grafos, matrices adj, etc.!)

En el caso anterior, considere cada píxel como un nodo en un gráfico. Cada nodo está conectado a sus vecinos por un borde, y cada borde tiene el mismo "peso" (moverse al nodo "arriba" no es más lento que moverse al nodo "debajo").

Así que tienes esto: ("*" = nodo "-, /, \, |" = orilla)

*-*-* 
|\|/| 
*-*-* ... (etc) 
|/|\| 
*-*-* 

Si Pacman está en el centro, se puede mover a cualquier otro nodo muy fácilmente.

Algo más cerca de la realidad podría ser la siguiente:

*-*-* 
| | | 
*-*-* ... (etc) 
| | | 
*-*-* 

Ahora, pacman no puede moverse en diagonal.Para ir del centro a la parte inferior derecha, se requieren 2 "saltos" en lugar de uno.

Para continuar con la progresión:

*-*-*-* 
| | | | 
| | | | 
| | | | 
*-*-*-* 
| | | | 
*-*-*-* 

Ahora, para ir de un nodo en el centro para un nodo en la parte superior, necesita 3 saltos. Sin embargo, para avanzar hacia la parte inferior solo se necesita 1 salto.

Sería fácil traducir cualquier configuración de tablero de juego en un gráfico. Cada "intersección" es un nodo. El camino entre dos intersecciones es un borde, y la longitud de ese camino es el peso de ese borde.

Introduzca A *. Al construir un gráfico (use una matriz de ajuste o una lista de nodos), puede usar el algoritmo A * para encontrar la ruta más corta. Otros algoritmos incluyen Dijkstra. ¡Y muchos otros! Pero primero necesitas enmarcar tu problema en términos de un gráfico, y luego jugar con cómo irías del nodo A (pacman) al nodo B (fantasma).

Espero que ayude!

Answer 4

Creo que vamos por el algoritmo de ruta más corto en cada movimiento realizado por pacman. Una muy buena implementación es Dijkstra's algorithm.

Solo para resumir: Visualice el laberinto como un gráfico con vértices y bordes. Cada borde tiene una espera (en su caso, todos los bordes tienen el mismo peso). El algoritmo encuentra la ruta más corta desde el vértice de origen al vértice de destino moviendo un paso hacia abajo cada borde accesible inmediato. Luego, en el siguiente vértice haces lo mismo y sigues haciendo hasta llegar al objetivo. El primer camino alcanzado es el camino más corto. Puede haber muchas optimizaciones hechas a este algoritmo para acelerar cosas como tener en cuenta dónde estaba el pacman en su posición anterior y en qué dirección se movió para que pueda obtener algo de herejía en el algoritmo. Sugeriría encontrar el camino más corto de cada fantasma a pacman en cada movimiento y mover el fantasma en esa dirección. Eventualmente la distancia se reducirá y podrás capturar pacman.

Otra heurística que se puede usar para encontrar todos los bordes inmediatos accesibles desde pacman y tratar de cubrir la mayor cantidad de estos vértices como sea posible por fantasmas. Entonces, en lugar de configurar a pacman como el vértice objetivo, establecemos los vértices inmediatamente accesibles por pacman como objetivo, el resultado será que los fantasmas disponibles tratarán de cubrir las principales rutas de escape de pacman y atraparlo.

Answer 5

Ha pasado mucho tiempo, pero de memoria los fantasmas en Pac-Man no hicieron mucho en el camino de la búsqueda. Realizarían un recorrido de laberinto aleatorizado bastante estándar hasta que lo "descubrieran", lo que implicaba encontrar un camino sin obstrucciones a lo largo del eje de un corredor hacia usted, y luego se moverían directamente hacia usted hasta que desapareciera de su línea de visión, con lo cual se reanudaría un patrón aleatorio. En niveles más altos, Pac-Man dejaría rastros invisibles detrás de él por un tiempo que los fantasmas "huelen" y a veces siguen.

Cuando Pac-Man tiene un encendido, la única diferencia en el algoritmo es que, cuando te vean, los fantasmas huirán de ti en lugar de moverse hacia ti.

Por lo tanto, para una experiencia auténtica, probablemente no necesite un algoritmo de ruta de acceso muy sofisticado. Si quieres ser elegante, por supuesto, puedes implementar A *.

Answer 6

Caminar directamente hacia tus enemigos es un comienzo, pero cuando agregas un laberinto querrás agregar un pathfinding un poco más inteligente para que tus fantasmas no se atasquen en curvas o callejones sin salida.

El siguiente tutorial es una gran guía ligera para comenzar con A *, con ejemplos descargables.

Path Finding on Tile based Maps

Answer 7

en Pacman todos los fantasmas tenían un algoritmo diferente persecución

• Blinky -> Chase. Por lo general, tomará la ruta más corta hacia usted y tenderá a seguirla.
• Pinky -> Emboscadas. Tiende a tomar una forma más indirecta de pac-man. Mortal. (meñique y parpadeante tienden a hacer una elección diferente al elegir una dirección, a menudo enjaulándolo en una esquina)
• Inky -> Freak. Este tipo actúa de manera extraña. Se mueve por el tablero bastante al azar, pero a veces persigue cuando se acerca.
• Clyde -> Idiota. Se mueve al azar. No es una gran amenaza.

Los fantasmas tienen un interesante patrón programado en sus movimientos: de vez en cuando, al mismo tiempo van a cesar y desistir de su búsqueda de la Pac-Man y regresar a sus respectivas esquinas del laberinto, entrar en "modo de dispersión".

hay una descripción completa de la the pacman dossier algo en

respecto

Guillaume