Búsqueda eficiente de caminos en el espacio libre

Tengo un juego situado en el espacio, y me gustaría emitir órdenes de movimiento, lo que requiere encontrar caminos. Ahora, entiendo que A * y tal se aplican principalmente a los árboles, y no al espacio vacío que no tiene nodos de búsqueda de ruta. Tengo algunos obstáculos, que actualmente se expresan como AABB fijos, es decir, no hay un obstáculo "terreno" ilimitado. Además, espero que la mayoría de los obstáculos sean razonablemente aproximables como cubos o esferas.

Así que he estado pensando en aplicar un algoritmo de búsqueda de ruta mucho más simple, es decir, simplemente lanzar un rayo desde la posición actual a la posición objetivo, y luego puedo obtener una lista de obstáculos usando la partición espacial relativamente rápido. De lo que no estoy tan seguro es de cómo determinar la parte donde la unidad ordenada maniobra alrededor de los obstáculos.

Lo que he estado pensando hasta ahora es que simplemente usaré campos potenciales, es decir, todas las unidades sentirán una fuerte fuerza repulsiva alejándose unas de otras y una fuerza moderada hacia el punto deseado. Esto también tiene la ventaja de que para emitir órdenes grupales, simplemente puedo ordenar una fuerza de nivel medio hacia otra entidad. Pero esto obviamente no logrará la solución óptima.

¿Los campos potenciales lograrán una aproximación razonable dados mis parámetros, o necesito otra solución?

Si bien los campos potenciales pueden funcionar, imagino que tendrá problemas con rutas subóptimas y "mínimos locales" donde sus unidades quedarán atrapadas por obstrucciones circundantes. A * es adecuado para entornos de espacios abiertos en 3D. Simplemente se convierte en una cuestión de generar una malla de navegación que se adapte a sus necesidades. Incluso puede usar estructuras como Octrees para nodos de navegación. Cuanto más pequeño sea el tamaño máximo de cada octante, más suave será el camino. Echa un vistazo a este artículo de los juegos cara a cara (ahora difunto, enlace de retroceso agregado). ¡A * combinado con la optimización de ruta (como atajos de línea de visión) y comportamientos de dirección y estará listo para comenzar! Vea la imagen a continuación como un ejemplo del uso de un octree para los nodos de ruta: