Pathfinding en una superficie planetaria irregular

16

Mi pregunta es ¿cuál sería el mejor enfoque para encontrar caminos en una superficie planetaria irregular?


Información de contexto

He creado un planeta a partir del desplazamiento de mapeo de 6 planos proyectados de esfera. Los planos inicialmente formaron un cubo antes de proyectarse en forma de esfera.

ingrese la descripción de la imagen aquí

Me pregunto si es posible usar cada "cara de cubo proyectada de esfera" como cuadrículas y usar un algoritmo A * simple para encontrar la mejor ruta posible, también me gustaría tener en cuenta la altura de desplazamiento para que el camino evite escalar montañas, etc. (supongo que esto sería una heurística dentro del algoritmo A *) Otra consideración es que he logrado el movimiento planetario al aprovechar el motor de física de Unity3d, aplicar la gravedad hacia el centro del planeta. ¿Mi solución propuesta requeriría que el movimiento de los agentes fuera controlado independientemente de la física gravitacional?

Para ayudar a articular mejor mi pregunta, este es mi cuerpo planetario actual:

ingrese la descripción de la imagen aquí

Cayo Eugenio
fuente
2
Quizás te interese este video de Aniquilación planetaria. Parecen estar haciendo lo mismo que envolver el mundo desde un cubo y encontrar el camino a su alrededor. No es realmente una respuesta, pero puede ver que están usando A * junto con algunas otras estrategias para optimizar la búsqueda de rutas en una esfera. El bit de búsqueda de ruta comienza a las 24:30 .
MichaelHouse
@ Byte56 Gracias por este enlace enfoque realmente interesante para el costo, ¡no puedo esperar a ver ese juego cuando haya terminado!
Caius Eugene

Respuestas:

12

Parece que ya has respondido tu propia pregunta. A * es probablemente el mejor enfoque. Sí, por supuesto, puede usarse de la manera que usted describe, incluido el uso de la información de altura para evitar montañas. Mientras pueda acceder a información sobre cualquier cuadrícula en la superficie de su mundo, no hay razón para que no pueda usarla en la heurística A *.

Finalmente, estás confundiendo la búsqueda de ruta con la ruta que sigue al final de tu pregunta. El hallazgo del camino no se preocupa por la gravedad, a menos que lo agregue como heurístico y dado que está en la superficie de un planeta, la gravedad será esencialmente la misma en toda la superficie. Muchos juegos tienen gravedad junto con movimiento, no veo razón para que no puedas.

Básicamente queremos mapear que va del rojo al azul, para que sea igual en una esfera que en un cubo.

ingrese la descripción de la imagen aquí

Dado que A * con frecuencia está obteniendo vecinos a su nodo actual, puede crear fácilmente un conjunto de funciones para obtener nodos adyacentes. Por ejemplo, getXPlus(), getXMinus(), getZPlus()y así sucesivamente. Estas funciones tomarán el nodo actual y lo devolverán en la dirección especificada por el nombre de la función.

La mayoría de las veces estas funciones solo pueden incrementar un valor y, sin embargo, en los bordes, eso cambiará.

Querrá asignar la superficie de su cubo a un sistema de coordenadas 2D. Independientemente de cómo lo haga, depende de usted, no tienen que alinearse, solo dele a cada espacio de la cuadrícula una coordenada X, Y única.

Ahora, cuando está en un borde, y obtiene el espacio adyacente de la cuadrícula, no necesariamente va a ser solo un incremento de las coordenadas. Tenemos que averiguar a qué cara nos estamos moviendo y cambiar a las coordenadas de esa cara.

Por ejemplo, obtener la coordenada XPlus aquí cambiará las coordenadas X e Y porque nos estamos moviendo a un nuevo espacio de cuadrícula en una nueva cara. La línea verde representa un borde entre dos caras.

ingrese la descripción de la imagen aquí

Ahora bien, estas son solo coordenadas globales, puede ser más fácil usar un sistema de coordenadas local interno, con una tercera dimensión que representa la cara del cubo en la que se encuentra actualmente.

De cualquier manera, debe tener una coordenada única para cada espacio de la cuadrícula en la cara del cubo. Atravesarlos dependerá de cómo implemente el sistema de coordenadas. También necesita saber dónde se asignan esas coordenadas a la superficie de la esfera.

Todo esto eventualmente debería abstraerse para que ni siquiera lo sepas.

MichaelHouse
fuente
Saludos por la respuesta. Creo que estoy luchando con que cada plano sea una cuadrícula aislada. ¿Tendrían alguna sugerencia (o lecturas adicionales) sobre cómo lidiar con las costuras, supongo que voy a desplegar matemáticamente mi "cubo", combinar todas las cuadrículas y calcular la ruta utilizando ese conjunto de datos?
Caius Eugene
Realmente solo debes preocuparte por los bordes. Eso se resuelve fácilmente con una función de envoltura (envolviendo su cubo en una función de envoltura, que envuelve su mundo ...). Puede abstraer el cubo en una superficie plana que se envuelva. Cree funciones para obtener el espacio de cuadrícula adyacente, getXPlus () obtendrá la cuadrícula en la dirección XPlus, no importa si está en el límite entre caras, la función solo cambiará las caras y devolverá la información de cuadrícula adecuada.
MichaelHouse
La única inexactitud con la búsqueda de trayectoria en el cubo doblado es que los vértices están sesgados y, por lo tanto, los bordes tienen diferentes longitudes. Es posible que no haga una diferencia notable en las rutas resultantes y de lo contrario simplemente podría tener en cuenta las longitudes.
danijar
1
Lo importante a entender aquí es que A * no necesariamente opera en un avión; Funciona en un gráfico. Aunque dentro de cada cara del cubo, los nodos están dispuestos y conectados en una cuadrícula, también hay conexiones de nodos a través de los bordes del cubo.
jmegaffin
1
@ Byte56 Gracias por la excelente respuesta, comencé a implementar una solución, sin embargo, me encontré con un obstáculo. Quizás he entendido mal. He publicado una pregunta en stackoverflow porque sentí que era más un problema matemático / de programación stackoverflow.com/questions/16089074/…
Caius Eugene