¿Cómo determinar el rango de movimiento posible en un juego de estrategia basado en turnos y distancia?

11

Estoy creando un juego de estrategia bidimensional basado en turnos usando c ++ y SFML-2.0. El movimiento se basa en la distancia en lugar de en la cuadrícula, con varias piezas diferentes en forma de triángulo que, en un giro dado, cada una puede rotar en su lugar o avanzar.

El movimiento funcionará de tal manera que el jugador seleccione una ubicación para que la pieza se mueva, lo que genera un camino potencial para que la pieza tome. Una vez que el jugador confirma su decisión, la pieza se moverá a lo largo de ese camino a la ubicación deseada. Las rutas están limitadas por dos factores: distancia, qué tan lejos puede llegar una pieza, teniendo en cuenta cualquier giro (por lo tanto, si hay una curva, será la longitud a lo largo de la curva, y no directamente de un punto a otro); y ángulo de dirección, qué tan lejos puede girar la pieza en cualquier punto (y hasta todos) mientras se mueve (por ejemplo, de -30 a 30 grados).

Mi pregunta es, ¿cómo debo determinar el rango de ubicaciones potenciales que el jugador puede seleccionar para mover la pieza?

No estoy completamente seguro de qué ecuaciones y / o algoritmos usar aquí. Mi plan original era extremadamente complicado, hasta el punto de que era casi imposible de implementar, y mucho menos explicar, y en este punto estoy totalmente perdido con el proyecto estancado.

¿Cómo puedo determinar el alcance que puede mover una unidad, teniendo en cuenta su radio de giro?

Por ejemplo, en la imagen de abajo. Las líneas roja, azul y verde tendrían la misma longitud. El círculo morado indica el rango de movimiento que la unidad puede mover. (La forma es probablemente inexacta y las líneas probablemente no son en realidad la misma longitud, pero se entiende la idea)

ingrese la descripción de la imagen aquí

sfphilli
fuente
Todavía solo podrá moverse la misma distancia (total). Entonces, la pregunta es realmente averiguar "¿cuán lejos gira?" / "¿Cuánto necesita girar?" / "¿ Dónde debe girar?". Probablemente necesite comenzar por determinar la ruta regular, luego retroceder un inicio de giro para ángulos superiores a una cierta cantidad; tenga en cuenta que la distancia final será más larga en un camino en línea recta (girando más reciente) que con las curvas.
Clockwork-Muse
Sí, la distancia recorrida es el principal factor limitante. Mi mayor obstáculo aquí es que necesito tener en cuenta que la pieza puede girar y continuar girando, en cualquier punto que pueda alcanzar, siempre y cuando todavía tenga distancia disponible.
sfphilli
¿Qué quieres decir con el rango que puede mover una unidad? ¿Te refieres a los puntos a los que puede moverse? ¿Qué tan familiarizado está con el álgebra lineal (vectores)?
BlueRaja - Danny Pflughoeft
1
¿Qué escenario de la vida real estás tratando de modelar? Su problema es demasiado vago en cuanto a los requisitos, lo que resulta en que se proponen demasiados enfoques de solución. Existen enfoques bien conocidos para (virtualmente) cada problema específico en esta área, pero todos están adivinando cuál de estos muchos problemas está abordando realmente.
Pieter Geerkens
1
@PieterGeerkens Supongo que porque OP no está solicitando código, están solicitando un algoritmo. Y han proporcionado suficientes detalles sobre el escenario para que un algoritmo pueda concebirse razonablemente. Esto es común y aceptable.
MichaelHouse

Respuestas:

4

Genere un campo de flujo o distancia, utilizando Dijsktra's.

Esencialmente, complete una cuadrícula utilizando el algoritmo Dijkstra sin destino (probablemente un nombre diferente para eso; no lo sé). Simplemente tome cada nodo abierto, calcule vecinos accesibles, insértelos en la lista abierta, establezca en la lista cerrada, actualice la ruta "siguiente" del nodo principal, según corresponda, etc. Al determinar el costo para llegar a un nuevo nodo, tenga en cuenta las limitaciones de giro.

El resultado ahora será que tiene una red de todos sus nodos sobre cómo volver al inicio. Los nodos a los que no se puede llegar no habrán sido tocados por el primer paso. Los nodos a los que se puede llegar tendrán un elemento "siguiente nodo a lo largo de la mejor ruta posible hacia el padre" calculado para que pueda resaltar todos los nodos y luego usar esta información para mostrar o ejecutar la ruta de movimiento cuando el usuario se desplaza o hace clic en las áreas resaltadas.

Sean Middleditch
fuente
No exactamente cómo explicaría el concepto, o cómo lo implementaría, pero ciertamente el enfoque correcto.
Pieter Geerkens
Según tengo entendido, el algoritmo, tal como está, es que el recorrido de nodo debe ser independiente de la ruta. Entonces, para lograr esto, necesitará agregar otro grado de libertad (otro eje en el que crear sus nodos) dedicado a enfrentar. En otras palabras, tendría un nodo para cada combinación de diferentes X, Y, potencialmente Z y Orientación. De lo contrario, encontrar la ruta más corta para ingresar a un nodo no distingue entre los diferentes revestimientos al salir de él. ¿Es eso correcto? Si ese es el caso, ¿es este método posiblemente demasiado intensivo?
TASagent
@TASagent: buen punto, no pensé en eso por completo. El algoritmo puede estar un poco apagado, pero el enfoque debería funcionar.
Sean Middleditch
@PieterGeerkens: Estoy de acuerdo en que es una mala explicación. Debe hacer su propia respuesta que lo explique mejor.
Sean Middleditch
Parece que está bastante cerca de lo que necesito, pero tengo que admitir que nunca he oído hablar de ese algoritmo, por lo que no sé cómo generalizarlo a lo que necesito. ¿Por casualidad tienes un enlace a alguna buena información o tutoriales?
sfphilli
4

Una solución de fuerza bruta sería:

  1. Crea un círculo de vértices alrededor de la unidad, con la unidad en el centro. El radio del círculo es la distancia máxima de movimiento. La densidad de los vértices puede cambiar dependiendo de cuán detallado desee que sea el resultado final.
  2. Para cada posición de vértice, simule el movimiento de la unidad que se dirige hacia esa posición. Esto se realiza en un ciclo cerrado sin renderizado.
  3. Cuando se alcanza la distancia máxima en la simulación de dirección, mueva el vértice al punto de la unidad simulada. Este punto es lo más cercano que la unidad podría llegar a ese vértice antes de que terminara el turno actual. Esto tiene el efecto de reducir el círculo al tamaño del movimiento real.
  4. Use esos vértices, junto con un vértice centrado en la unidad para crear un círculo renderizado para dibujar las posibles distancias de movimiento.

ingrese la descripción de la imagen aquí

Entonces, comenzando con el círculo azul, procesarías tus caminos y terminarías con el círculo púrpura. Luego puede usar esos puntos con un punto central en la unidad para hacer los triángulos rojos necesarios para mostrar la forma. (Solo hacer esa imagen me hace darme cuenta de que esa forma no es correcta, pero será interesante ver qué es realmente correcto)

MichaelHouse
fuente
3

Voy a ampliar la solución de Sean en una respuesta separada, ya que representa un enfoque diferente de lo que inicialmente estaba proponiendo.

Esta solución probablemente representa el método más accesible. Requiere particionar su entorno en nodos. Sí, se trata de reintroducir un enfoque basado en la cuadrícula, pero se puede hacer relativamente bien o se puede utilizar para encontrar una ruta amplia con un posicionamiento más fino manejado dentro del nodo. Cuanto más gruesa sea la estructura del nodo, más rápido será el pathfinding.

El gran problema aquí es que en realidad estás lidiando con el frente del barco, por lo que muchas soluciones de búsqueda de caminos tradicionales no se pueden usar sin modificación. Por lo general, son independientes de la ruta, ya que no les importa cómo llegaste al nodo en el que te encuentras. Eso funciona bien cuando la aceleración, la desaceleración y el giro son instantáneos y libres. Desafortunadamente para ti girar no es gratis. Sin embargo, dado que realmente hay una información adicional que se elimina en esta simplificación, podemos codificarla como otra variable. En física, esto se conocería como espacio de fase.

Asumiendo 2 dimensiones por ahora, puede extrapolar por 3:

Normalmente, necesitaría un nodo para cada posición de coordenadas discreta permitida. Por ejemplo:

(0,0) - (1,0) - (2,0)
  | \  /  |  \  / |
(0,1) - (1,1) - (2,1)

Etc. Construiría un nodograma de puntos adyacentes y los conectaría por adyacencia espacial. Entonces usarías el algoritmo de Dijkstra, matando nodos que excedan el valor de movimiento permitido para el turno, hasta que no queden nodos vivos y no explorados que permanezcan conectados a nodos explorados. Cada nodo realiza un seguimiento de la menor distancia requerida para alcanzarlo.

Para expandir este método para que pueda usarse con Rotación, imagine este mismo nodograma en 3 dimensiones. La dirección Z corresponde a la rotación / orientación, y es cíclica, lo que significa que si sigue viajando en la dirección + Z volverá a donde comenzó. Ahora, los nodos correspondientes a posiciones adyacentes solo están conectados a través de la cara que corresponde a esa dirección. Usted itera sobre los nodos conectados a nodos ya explorados como de costumbre. Recomendaría restringir a N, NE, E, SE, S, SW, W, NW en este esquema.

Esta solución puede decirle todas las regiones accesibles del espacio, así como el mejor camino para llegar allí, cuánta rotación tiene cuando llega allí y todas las orientaciones que podría tener cuando llegue allí.

Luego, al ejecutar la ruta, puede interpolar / dividir cúbicamente su camino para que parezca más auténtico.

TASagent
fuente
1
Esto es excelente. Tendré que investigar un poco sobre el algoritmo y experimentar con él en mi juego terminado, pero esto realmente me parece el ajuste perfecto, especialmente porque puedo generalizarlo a otras partes importantes del juego.
sfphilli
1

Parece que es posible que primero deba decidir cómo desea exactamente que funcione el encendido sobre la marcha. Opciones como:

  • Si se mueven dentro del cono, primero gire, luego comience a moverse. Esta es la solución más fácil de implementar y de seguir. También es menos interesante, así que no me gustaría usarlo.

  • Giro continuo mientras se mueve, hasta un total de 45 grados. Este es mucho más complicado y, con suerte, el que buscas. Integrar numéricamente sobre el camino usando un paso de tiempo fijo es probablemente la forma más fácil de acercarse a este. Su cono estará limitado por el giro máximo (+ X grados en cada paso) y mínimo (-X grados en cada paso).

La mejor manera de atravesar el espacio con el segundo de estos requisitos depende en gran medida del entorno en el que se moverán. Si hay muchos obstáculos por los que hay que sortear, las cosas pueden volverse realmente difíciles y muy caras. Sin embargo, si no lo hay, entonces puede cargar por adelantado (e incluso disminuir) la rotación para terminar en la ubicación deseada.

Tengo la sensación de que es posible que haya cubierto solo parcialmente los temas sobre los que tenía una pregunta, así que siéntase libre de agregar más en los comentarios y puedo ampliar la discusión.

TASagent
fuente
Definitivamente quiero usar la segunda opción, de subir (por ejemplo) a 45 grados en cualquier punto, y potencialmente en todos, a lo largo de un camino. También habrá obstáculos, cada uno más grande que las piezas (piense en rocas gigantes). La forma en que originalmente estaba pensando en esto era generar un cono de posibles puntos finales, y luego para cada uno de esos puntos finales generar un nuevo cono, y así sucesivamente para cada ubicación posible hasta que alcance la distancia máxima recorrida. Dicho esto, no estoy completamente seguro de cómo implementar esto sin una complicación excesiva.
sfphilli
Hmmm, parece que estaba / no estoy un poco claro acerca de algunos de los detalles. Mirando hacia atrás sobre la pregunta, veo que especificó 'por turnos' y que las unidades pueden 'rotar o moverse' en su turno. ¿Significa eso, entonces, que el jugador traza sus acciones con muchos turnos de antemano, y usted quiere hacer la búsqueda del camino mientras se mueve? Sería útil alguna aclaración adicional sobre cómo se supone que funciona el movimiento.
TASagent
No, lo que quise decir es que en un turno dado el jugador puede rotar su pieza en su lugar, por más que quiera, o puede moverse en la dirección que ya está mirando. Si se mueven, pueden recorrer una distancia particular a lo largo de un camino, y pueden girar o girar hacia un ángulo particular (por ejemplo, en cualquier lugar de -45 a 45 grados) mientras se mueven. Entonces, imagine que un camino elegido implicaría una curva para moverse hacia la izquierda o hacia la derecha. El camino será determinado por el jugador que elija un punto al que quiera moverse, dentro del rango de puntos posibles que tengo problemas para determinar.
sfphilli
Ok, en realidad parece que, desafortunadamente, sus características deseadas son posiblemente demasiado restrictivas para el algoritmo de Dijkstra del que estamos hablando anteriormente: - \. Posiblemente. Esbozaré algunas cosas para esto más tarde cuando llegue a casa.
TASagent
Es posible que desee editar parte de esta información que ha reunido para aclarar el problema en la pregunta original, para que las personas que vengan después puedan comenzar con más información.
TASagent