Estoy buscando la mejor solución para encontrar caminos en mi juego. En última instancia, el mapa se basa en la cuadrícula, pero las entidades se posicionan mediante flotadores y pueden moverse en cualquier dirección a cualquier punto del mapa. El 'terreno' en mi juego tiene un costo de movimiento uniforme, pero por supuesto puede haber obstáculos que bloqueen el camino. La mayoría de los obstáculos serán estáticos, y aunque habrá otras entidades animadas en el juego, es posible que me salga con la suya sin considerarlos: es un juego de estrategia isométrica al estilo de Theme Hospital , así que no hay peleas.
La mayoría de los artículos de búsqueda de ruta que he visto cubren movimientos en 3D o en cuadrícula 2D. ¿Alguna sugerencia para algo que pueda cubrir mi caso de uso? Muchas gracias.
fuente
Respuestas:
Esto se llama el "problema de orientación de cualquier ángulo". Básicamente tienes dos opciones:
Genere una malla de navegación para su mapa y busque sobre eso usando A *
Busque en una cuadrícula utilizando un algoritmo destinado específicamente a la búsqueda de rutas en cualquier ángulo. Tradicionalmente, la forma de hacerlo era el suavizado de ruta A * + (interpolación lineal, etc.) , pero en estos días una alternativa más popular es Theta * , que es más fácil de implementar, se ejecuta más rápido y produce mejores resultados que el suavizado de ruta.
Todos los métodos anteriores generan resultados casi óptimos. Si por alguna razón necesita resultados óptimos, este documento fue publicado hace unas semanas. Sin embargo, todavía no he tenido la oportunidad de leerlo, así que no sé qué tan eficiente es o qué tan difícil es implementarlo.
fuente