Encontrar posibles movimientos para una entidad en un juego en mosaico 2D

10

Tengo problemas para encontrar un término de búsqueda específico para esto, pero ¿cómo se puede encontrar los posibles movimientos en un juego de estrategia por turnos 2D (es decir, FF: tácticas, emblema de fuego, guerras avanzadas).

ingrese la descripción de la imagen aquí

No estoy pensando tanto en el terreno (o incluso la colisión) en este momento. Me pregunto qué algoritmo puedo usar para descubrir que la entidad X puede mover 5 fichas y atacar 2 fichas más lejos que eso.

Sé que puedo usar algo como Dijkstra para encontrar la distancia entre dos puntos. Una posible implementación es comenzar en la ubicación de los jugadores y luego ramificarse desde allí hasta que la distancia devuelta por Dijkstra sea mayor que el conteo de movimientos.

Solo me preguntaba si alguien podría señalarme en la dirección correcta (es decir, nombre de algoritmos, técnica, artículos, etc.).

tiles path-finding turn-based-strategy NRaf
fuente
Estoy pensando que se llama búsqueda de ruta, ¿para un término de búsqueda? Si usa la búsqueda de ruta, entonces podría tener contadores para manejar lo que necesita
Exikle
Esto es esencialmente parte de la búsqueda de ruta (cálculo de metadatos para costos de movimiento). Solo determina ubicaciones que están dentro del alcance, pero no necesariamente determina la ruta que tomaría también.
Mario
1
No es en tiempo real (RTS) si está basado en turnos a la FFTactics. : p
Alayric
En 2d, puede usar el cálculo de Taxicab / Manhattan en.wikipedia.org/wiki/Taxicab_geometry
Gerben Jacobs

Respuestas:

5

Creo que un Dijkstra acotado es precisamente lo que quieres usar. La forma en que Dijkstra encuentra la distancia entre dos puntos es mapeando la distancia a cada nodo desde un nodo de origen, y luego 'selecciona' la ruta más corta de este mapa de distancia. Desea hacer prácticamente lo mismo, excepto que desea el gráfico de nodo de distancia que crea como salida, en lugar de una ruta a un punto en particular.

La única modificación que querrá hacer es omitir el cálculo de la distancia desde los nodos que ya han excedido su rango de movimiento máximo. Luego, tendrá un gráfico de nodos de todos los nodos a los que la unidad puede viajar, más un borde, así que simplemente corte los nodos que tengan una distancia mayor que la capacidad de movimiento.

Viola.

En otras palabras, más o menos lo que describiste en tu pregunta es lo que debes hacer. También tiene la ventaja de poder utilizar la salida para hacer la búsqueda de ruta, sin necesidad de hacer ningún cálculo adicional.

TASagent
fuente
Creo que Dijkstra es excesivo en este caso. El OP no necesita una ruta a todos los destinos de movimiento posibles, solo una respuesta sí / no sobre si un agente puede llegar allí. Puede calcular una ruta más tarde una vez que el usuario haya elegido una.
Michael Kristofik
El costo de usar el algoritmo de Dijkstra para calcular la ruta después de que se haya decidido un destino es casi exactamente el mismo que usarlo por adelantado (a menos que use un enfoque heurístico como A * para la ruta). No hacerlo por adelantado simplemente crea trabajo redundante, ya que Dijkstra respondería tanto a las preguntas '¿a dónde puedo ir' como a 'cómo llego allí?'. También permite agregar complicaciones al entorno que cambian el costo de movimiento, aunque eso puede ser innecesario para la aplicación. Además, el enfoque está bien documentado, lo que es útil para el implementador.
TASagent
1
Al mirar la respuesta de Mario, en realidad describe el algoritmo de Dijkstra, excepto que invierte la distancia y no menciona que es Dijkstra.
TASagent
1
No diría que es Dijkstra, porque realmente no estás buscando una ruta más corta ni estás tratando de llegar a un punto específico. Es esencialmente la primera parte del algoritmo de Dijkstra, aunque eso es cierto. El problema con su redacción, usando Dijkstra, puede ser engañoso y creo que esto también es lo que confundió a Michael. Probablemente pensó que sugerías usar Dijkstra una vez para cada campo / celda.
Mario
1
Terminar usando este enfoque ya que funcionó bien y es muy fácil de extender para manejar obstáculos.
NRaf
12

El enfoque más simple (y probablemente más ingenuo) que se me ocurre en este momento:

  • Comience en su personaje y marque todos los campos circundantes como steps - 1.
  • Itere sobre todos los campos recién marcados y una vez más marque sus campos circundantes como steps - 1donde stepsestaría el número de paso del campo actual, a menos que el nuevo campo tenga un número ya mayor.
  • Repita el último paso hasta que se quede sin pasos.
Mario
fuente
1
Este algoritmo tiene un nombre: Flood Fill .
Michael Kristofik
66
@MichaelKristofik: Yo lo llamaría primera búsqueda de amplitud . El relleno de inundación no realiza un seguimiento de las distancias.
BlueRaja - Danny Pflughoeft
2

Creo que lo que estás buscando podría ser Manhattan Distance . Suponiendo que no haya obstáculos, puede decir que un cuadrado es accesible simplemente si:

| toX-fromX | + | toY-fromY | <maxMoveDistance

Es posible que este algoritmo no sea la dirección correcta si va a tener obstáculos más adelante; Una posible forma de adaptarlo podría ser hacer que los obstáculos arrojen 'sombras' y reevaluar desde el punto más cercano.

EDITAR (porque ahora tengo un poco más de tiempo libre):

Por 'sombras' quiero decir algo como esto, si 0 es un cuadrado alcanzable, C es el personaje y X es un obstáculo:

 012345678
0    0
1   00
2  000X
3 000C000
4  00000
5   000
6    0
 012345678

Dado que (5, 2) es un obstáculo, comienza suponiendo que no puede llegar a nada con x> = 5 AND y <= 2. Luego puede volver a calcular desde otro cuadrado; si quieres ir a (5, 1) puedes calcular la distancia de Manhattan desde (4, 1) y ver si eso + la distancia del personaje a (4, 1) es menor que la distancia de movimiento del jugador.

Este es un ejemplo bastante trivial, pero si tiene múltiples obstáculos y / o un rango de movimiento un poco más largo, debería ser capaz de manejar la complejidad.

Si en realidad sería mejor que solo el llenado de inundaciones, ya sea en la complejidad de la programación o en la eficiencia de la ejecución, no tengo idea. Simplemente parecía una forma más interesante de resolver el problema.

Hombre de hojalata
fuente
¿Qué quieres decir con proyectar sombras?
NRaf
1
Editado para aclaraciones.
Tin Man