¿Encontrar caminos en un juego Java 2d?

Question

Esencialmente es un juego de clones pacman en el que estoy trabajando. Tengo una clase de Enemigo 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 pacman. Mientras el jugador controla al pacman, moviéndolo, debe seguirlo y tomar el camino más cercano posible hacia él.

No hay laberinto / 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 preocupo por eso, solo por los fantasmas que 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 hacer 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 hará el movimiento más eficiente, pero se acercará más y más al objetivo en cada iteración del bucle del juego.

También supongo que un juego arcade de principios de los 80 probablemente no usaría algoritmos sofisticados de búsqueda de caminos.

Answer 2

Si solo tiene una cuadrícula de píxeles, un " campo grande " en el que pacman y fantasma pueden moverse libremente, entonces el camino más corto es fácil: una línea recta entre el fantasma y el pacman.

Pero " camino más corto " invariablemente significa que estamos tratando de resolver un problema de teoría de grafos. (Asumo conocimientos de gráficos, algo de teoría de gráficos, matrices adjuntas, 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 igual '' peso '' (moverse al nodo "arriba" no es más lento que moverse al nodo "abajo").

Entonces tiene esto: (" * " = nodo, " -, /, \, | " = edge)

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

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

Algo más cercano a la realidad podría ser esto:

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

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

Para continuar la progresión:

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

Ahora, para pasar de un nodo en el medio a un nodo en la parte superior, necesita 3 saltos. Sin embargo, para moverse hacia abajo 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.

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

¡Espero que eso ayude!

Answer 3

Ha pasado mucho tiempo, pero de memoria los fantasmas en Pac-Man no hicieron mucho en la búsqueda de caminos. Harían un recorrido de laberinto aleatorio bastante estándar hasta que `` descubrieran '' usted, que implicaba encontrar un camino sin obstáculos 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 que reanudarían un patrón aleatorio. En niveles superiores, Pac-Man dejaría rastros invisibles detrás de él por un tiempo para que los fantasmas '' olieran '' y a veces seguir.

Cuando Pac-Man obtuvo un poder, la única diferencia en el algoritmo es que, cuando te vieron, los fantasmas huirían de ti en lugar de moverse hacia ti.

Entonces, para una experiencia auténtica, probablemente no necesite un algoritmo de búsqueda de ruta muy sofisticado. Si quiere ser elegante, por supuesto, puede implementar A *.

Answer 4

Caminar directamente hacia tus enemigos es un comienzo, pero cuando agregues un laberinto querrás agregar un camino más inteligente para que tus fantasmas no se queden atrapados en curvas o callejones sin salida.

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

Búsqueda de rutas en mapas basados ??en mosaicos

Answer 5

en Pacman, todo el fantasma tenía un algoritmo de persecución diferente

• Blinky - > Persecuciones. Por lo general, tomará la ruta más corta hacia usted y tiende a seguirla.
• Pinky - > Emboscadas Tiende a tomar un camino más indirecto hacia pac-man. Mortal. (Pinky y Blinky tienden a tomar decisiones diferentes al elegir una dirección, a menudo enjaulando al jugador en una esquina)
• Tinta - > Monstruo. Este tipo actúa de manera extraña. Se mueve por el tablero de manera bastante aleatoria, pero a veces persigue cuando se acerca.
• Clyde - > Idiota. Se mueve al azar. No es una gran amenaza.

Los fantasmas tienen un patrón interesante programado en sus movimientos: ocasionalmente, cesarán simultáneamente y dejarán de perseguir a Pac-Man y regresarán a sus respectivos rincones del laberinto, entrando en el "modo de dispersión".

hay una descripción completa del algo en el expediente pacman

saludos

Guillaume

Answer 6

Podría comenzar mirando A * (una estrella)

Y aquí hay una página que tiene enlaces a otros algoritmos de búsqueda de 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 la más fácil de leer, pero en general no es malo. AI para desarrolladores de juegos por David M. Bourg, Glenn Seemann .

Answer 7

Creo que elige el algoritmo de ruta más corta en cada movimiento realizado por pacman. Una muy buena implementación es Algoritmo de Dijkstra .

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 el camino más corto desde el vértice de origen al vértice de destino moviendo un paso hacia abajo en cada borde accesible inmediato. Luego, en el próximo vértice, haces lo mismo y sigues haciendo hasta llegar al objetivo. El primer camino alcanzado es el camino más corto. Se pueden hacer muchas optimizaciones para este algoritmo para acelerar las cosas, como tener en cuenta dónde estaba el pacman en su posición anterior y en qué dirección se movía para que pueda obtener algo de herencia en el algoritmo. Sugeriría encontrar el camino más corto de cada fantasma a pacman en cada movimiento y mover al fantasma en esa dirección. Eventualmente, la distancia se reducirá y podrás atrapar a pacman.

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