¿Cómo se generaría una cuadrícula de navegación para un mundo 3D?

11

Estoy intentando encontrar una solución a este problema. Estoy tratando de construir una malla de navegación en el formato de una cuadrícula de vértices bloqueados en coordenadas x, y con piso en forma de cuadrados para el espacio 3D. Pero tengo problemas para tratar de encontrar una manera de hacerlo.

Intenté buscar en la biblioteca de Recast. Es un método bastante robusto, pero aparentemente se ralentiza con mapas más grandes y espacios abiertos. Tampoco sé cómo generan vértices y bordes para el espacio mundial con el mapa de altura.

Mi siguiente pensamiento fue hacer lo que solía hacer Unreal Engine 3.

https://udn.epicgames.com/Three/NavigationMeshReference.html

Lo cual era usar rayos para generar la malla. No pude encontrar la manera de detener los rayos.

Entonces ... mi siguiente opción era la caja, posiblemente un molde de caja. Cree un volumen subdividido con un tamaño que sea una potencia de 2. Alinee el cuadro con la cuadrícula y dispare los prismas rectangulares hacia abajo como un rayo. Si cae sobre una pieza de geometría que es parte del suelo y el rectángulo no se cruza, deja un cuadrado allí. Y continúe hacia abajo hasta alcanzar los límites del volumen. Para verificar si los bordes deben estar vinculados, supongo que podría verificar si la pendiente entre dos pares de vértices está dentro de la pendiente transitable, fusionarlos si esto es cierto.

Mis principales problemas son ... esto no parece ser muy óptimo. Sin pensarlo, en la estimación, el proceso es O (N ^ 3) para un nivel multicapa. Lo que puede ser bastante desagradable.

Y el último bit es para crear automáticamente grupos rectangulares de estos cuadrados. No estoy completamente seguro de cómo hacer esto. La implementación de Unreal los separa por pendientes. Sin embargo, estoy tratando de mantener el formato de cuadrícula. Entonces eso no es del todo necesario. El problema sigue siendo la creación de grandes mosaicos rectangulares para dividir el proceso de búsqueda de ruta en una base por mosaico. Los azulejos no pueden ser demasiado grandes ni demasiado pequeños.

Entonces las preguntas son ...

¿Cuál sería una manera eficiente de generar este navmesh ceñido? ¿Y cuál sería una buena forma de crear los mosaicos?

luz de la luna
fuente
¿Cuándo esperas generar la malla? ¿Tiempo de compilación, tiempo de carga o tiempo real? Luchamos con este mismo problema y terminamos decidiendo que era excesivo para nuestro escenario (generación de tiempo de carga en un tirador de arriba hacia abajo sin caminos superpuestos), decidimos optar por un enfoque basado en cuatro árboles. Esto funcionó bastante bien para nosotros. Entonces, supongo que lo que pregunto es si realmente necesita esto, o cuál es la solución más fácil que cumpla con sus requisitos iniciales, ya que puede ser una pérdida de tiempo. Si logras una buena solución, me encantaría saber cómo lo solucionaste.
Niels
@Niels planeo pre-construir, luego cargarlo en el juego.
moonshineTheleocat
Entonces el consumo de tiempo no debería ser un gran inconveniente inicial, ya que el jugador no lo estará esperando. Siempre puede optimizar después de que algo funcione.
Niels
¿Qué tan grande es tu nivel? Hemos utilizado refundición de grandes juegos y tenía ningún problema - sólo hay que ajustar los valores de la TIIE, etc.
Steven
Creo que te estás perdiendo el bit "cuadriculado". Que no es lo mismo que los mosaicos que usa la refundición. Estoy tratando de descubrir cómo reutilizar la refundición para hacer tal cosa. Pero ha sido principalmente una pesadilla.
moonshineTheleocat

Respuestas:

1

Un mundo 3D básico podría estar representado por una malla de navegación que se puede construir convenientemente en la mayoría de los motores de juego. El actor puede viajar a lo largo de los bordes de los polígonos.

Esa sería una solución simple. Hay muchos algoritmos para encontrar rutas y generar una malla de navegación.

Me gustaría compartir algo que leí hace un tiempo.

Ejemplo01

Esto describe una posible solución donde podemos dividir nuestro mundo de juego en fichas cuadradas. cada vez que se agrega una ficha cuadrada al juego (cuando el jugador se acerca a un área / terreno de procedimiento), se agrega una ficha cuadrada. Sin embargo, ya no tenemos que calcular todo el navmesh. simplemente lo calculamos para ese mosaico y lo agregamos al gráfico existente. Aumento significativo del rendimiento allí.

Ejemplo02

El siguiente problema abordado es el movimiento irregular del ejemplo anterior. Puedo entender que al considerar giros futuros y generalizar la dirección reduciría mucho el movimiento en zigzag y haría que el movimiento sea fluido. Los juegos con animación detallada no lo delatan, pero puedes notar esto en algunos juegos de mundo abierto donde supongo que la navegación está horneada principalmente.

En cuanto a la pregunta, le recomendaría que consulte la respuesta de Kromster en una lista de algoritmos de generación de navmesh.

También echa un vistazo a The AI ​​Systems of Left 4 Dead del cual forman parte los ejemplos. Muchos más temas interesantes cubiertos

Buena suerte.

suvam0451
fuente
0

Hay muchas maneras, ¿por qué no solo hacer que sea local para el jugador, hacer una pequeña cuadrícula que siga al jugador y verifique debajo de cada intersección si es transitable o no, como si hubiera un piso allí y haga un rayo para ver si hay un muro / edificio en cualquier lado próximo ...

joe shmoe
fuente
Una buena idea, pero no viable para los objetivos finales. Necesito soportar un mundo grande y permitir que la IA navegue de un lado de un continente a otro lado del continente. Eso es factible, pero necesitaría tener una cuadrícula de navegación fija para generar los nodos superiores.
moonshineTheleocat
0

Este es un problema que he visto en todas partes. El truco es "separación de preocupaciones". "¿Decir qué?", ​​Te escuché pensar. Lo que se muestra en la pantalla NO es lo que es la "estructura de datos". Mantener los elementos visuales separados de los datos para construir el elemento visual es importante. Hacerlo siempre "preparará para el futuro" su juego cuando se lancen nuevas versiones de software subyacentes.

Cree una estructura de datos (también conocido como: modelo) que represente su mundo de juego. Luego construya una "vista" del modelo de estructura de datos. Si desea cambiar el mundo de una cuadrícula de tablero de ajedrez a una cuadrícula hexagonal, la estructura de datos (modelo) permanece igual, pero la pantalla "pintará" (renderizará) una vista diferente.

PBMCube
fuente
44
Si bien la separación de inquietudes es, de hecho, una buena práctica en general, esta respuesta actualmente es liviana en detalles específicos para responder la pregunta (es decir, cómo generar un modelo de trazado de ruta basado en la cuadrícula adecuado a partir de un conjunto dado de geometría mundial). Tiene toda la razón de que sea lo que sea este modelo, probablemente debería estar separado de los datos utilizados para dibujar el nivel, pero para responder a la pregunta todavía necesitamos un método para generar este modelo de búsqueda de ruta.
DMGregory
-2

Haz una doble matriz. Y luego, si un objeto / objetos son intransitables, tenga un método para indicarle a la matriz que la posición no es transitable. Cuando una IA intenta moverse, mirarán la matriz doble y verán si es pasable.

Peter J
fuente
44
El método para llenar esta matriz es la parte difícil. ;)
DMGregory