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