¿Hay algún algoritmo de búsqueda de ruta que pueda manejar diferentes tipos de movimiento?

12

Estoy desarrollando un bot para un simulador de juego de mesa BattleTech http://en.wikipedia.org/wiki/BattleTech , está basado en turnos.

El tablero está dividido en hexágonos, cada uno tiene un tipo de terreno y elevación diferentes. Conduces un robot que se mueve sobre ellos para destruir a otros robots.

Solo conozco los algoritmos de búsqueda de caminos Dijkstra y A *, pero el problema es que hay 3 tipos de movimientos: caminar, correr y saltar varios hexágonos (cada uno de ellos tiene sus propias reglas). Caminar y correr son casi lo mismo.

El mejor camino podría ser una combinación o cada tipo de movimiento. Aquí hay un ejemplo de mapa http://megamek.info/sites/default/files/isometric_view.png

¿Conoces un buen algoritmo para esta compleja búsqueda de caminos o una forma de combinar resultados A * para cada tipo de movimiento?

alexvisio
fuente
Creo que esto a menudo se maneja mediante una manipulación inteligente de una ruta ponderada con A * (el peso es el costo de esa ruta / cuadrado). Por ejemplo, si es preferible saltar, obtiene un peso menor (por ejemplo, 5) que caminar (por ejemplo, 10).
cenizas999
¿En qué se diferencian exactamente los tres tipos de movimiento? ¿Se pueden combinar (caminar a la casilla A, luego correr a B y luego saltar a C en el mismo turno)? En caso afirmativo, ¿cuáles son las reglas que impiden que el jugador utilice siempre el método más barato para pasar de la casilla A a la casilla B?
Philipp
@Philipp Sí, pueden ser, cuando se usa A *. Puede agregar todos los mosaicos a los que puede moverse con cada tipo de movimiento a la lista abierta, luego, según el precio de cada uno + una buena heurística, puede determinar cuál avanzar más adelante.
akaltar
@Philipp No, solo puedes usar un tipo de movimiento en cada turno.
alexvisio
Caminar: moverse a través de los hexágonos con poca diferencia en la elevación. Correr: lo mismo pero puedes llegar lejos, aunque generarás calor y perderás precisión al disparar (por lo que no siempre es el mejor). Saltar: puedes saltar obstáculos (una pared o un río) en lugar de caminar alrededor de ellos.
alexvisio

Respuestas:

10

Tanto Dijkstra como A * pueden agregar diferentes costos a los bordes (= conexiones) de un mosaico a otro. También permiten conectar dos nodos (= mosaicos) con más de un borde, cada uno con un costo diferente.

El modo de salto alternativo significaría que hay un borde directo alternativo de cada mosaico a cada mosaico en la distancia de salto. Pero debido a que un mech puede caminar o saltar en un turno, el costo de usar este borde sería los puntos de movimiento de un turno completo, más los puntos restantes del turno actual cuando ya hubo un movimiento este turno.

Según su descripción, la decisión de caminar versus correr no hace mucha diferencia con respecto a la elección del camino, sino que parece ser una decisión estratégica. El actor definitivamente puede caminar cuando se puede llegar al destino en el turno actual sin recurrir a correr. Pero de lo contrario, hay muchos factores a tener en cuenta, como:

  • nivel de calor actual y probabilidad de estar involucrado en combate antes de poder enfriarse
  • dificultad de los disparos que necesitan ser disparados esta ronda
  • cuán estratégicamente importante es llegar al destino rápidamente

No hay una regla estricta para tomar esta decisión. Lo mejor que puede hacer es utilizar un enfoque heurístico. Asigne valores de puntos positivos o negativos a todas las circunstancias, súmelos y vea si el resultado es positivo o negativo.

También hay otro factor en la búsqueda de rutas que debe tener en cuenta: bajo ciertas condiciones, podría tener sentido que un mecánico evite finalizar su turno en ciertos lugares. Cuando se encuentre en una zona de peligro, usar tres turnos para pasar de A a B, pero terminar cada uno en la cobertura podría ser mejor que usar solo dos, pero estar expuesto al final de cada uno. O tal vez no. Depende de las circunstancias y la mecánica exacta del juego. Esto, nuevamente, es una decisión estratégica que debe tomar basándose en la heurística. Puede representar esto agregando un costo adicional a los bordes que finalizan el turno en una ficha peligrosa para desalentar a la IA de hacer este movimiento.

Philipp
fuente