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?
fuente
Respuestas:
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:
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.
fuente