¿Cómo puedo generar una malla de navegación 2D en un entorno dinámico en tiempo de ejecución?

9

Así que he comprendido cómo usar A * para encontrar rutas, y puedo usarlo en una cuadrícula. Sin embargo, mi mundo de juego es enorme y tengo muchos enemigos que se mueven hacia el jugador, que es un objetivo en movimiento, por lo que un sistema de cuadrícula es demasiado lento para encontrar el camino. Necesito simplificar mi gráfico de nodos usando una malla de navegación.

Comprendo el concepto de "cómo" funciona una malla (encontrar un camino a través de nodos en los vértices y / o los centros de los bordes de los polígonos).

Mi juego utiliza obstáculos dinámicos que se generan procesalmente en tiempo de ejecución.

No puedo entender cómo tomar un avión que tiene múltiples obstáculos y dividir programáticamente el área transitable en polígonos para la malla de navegación, como en la siguiente imagen.

malla de navegación

¿Dónde empiezo? ¿Cómo sé cuándo un segmento de área transitable ya está definido, o peor, cuando me doy cuenta de que necesito subdividir un área transitable previamente definida a medida que el algoritmo "recorre" el mapa?

Estoy usando JavaScript en nodejs, si es importante.

Stephen
fuente
1
La partición dinámica que está intentando implementar dependerá de los detalles de los elementos del mapa. ¿Están sus elementos de obstáculos completamente compuestos de rectángulos alineados con la cuadrícula como se muestra en su ejemplo? Rectángulos rotados? Polígonos irregulares? ¿O formas no poligonales con muchas curvas? ¿Tiene datos de punto / poli para la forma de los obstáculos? Si es así, ¿son datos de forma en términos de triángulos, rectángulos, polígonos exclusivamente convexos o una combinación de polígonos convexos y cóncavos?
Matthew R
@Matthew Mi mundo está compuesto de obstáculos de polígonos convexos, sin curvas y sin polígonos cóncavos. Cada obstáculo se almacena como un objeto poligonal con vértices representados por objetos vectoriales.
Stephen
1
Por lo que vale, estoy trabajando en una solución basada en este documento: gradworks.umi.com/3493710.pdf Si tengo éxito, publicaré mi solución.
Stephen
1
la malla de navegación no está ahí al 100% para decirle si puede ir a algún lado o no, es solo un esquema básico de áreas transitables, aún tiene que hacer controles de colisión contra objetos dinámicos, editar: más o menos lo que dijo Ray
dreta
@Stephen - Ver respuesta de comentario largo .
Matthew R

Respuestas:

3

@Stephen - Comentario largo - Parece que valdría la pena leerlo cuando tenga algo de tiempo. Básicamente, lo que hubiera sugerido es algo similar al algoritmo Hertel-Mehlhorn que se menciona en el documento (puede encontrar una referencia para este algoritmo específico aquí http://www.bringyou.to/compgeom/ ) con la adición de subdividir los lados del mapa (fuera del límite del área de juego) una cierta cantidad de tiempo para reducir la aparición de múltiples triángulos pequeños formados en las esquinas. Esos triángulos pequeños pueden ser problemáticos, ya que pueden llegar a ser más pequeños que lo que estás buscando para encontrar el camino. El Hertel-Mehlhorn es para la reducción de los polígonos producidos por una partición triangular, si está interesado aquí hay más sobre triangulación:http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/PolyPart/polyPartition.htm .

Además, si prefiere no reinventar la rueda, creo que esta biblioteca realmente hará todo lo que necesita: http://code.google.com/p/polypartition/ . Preforma las triangulaciones y reducciones con una de varias opciones diferentes, incluyendo Hertel-Mehlhorn. Es una licencia MIT, lo que significa que puede usarse para proyectos de código cerrado y comerciales si eso es un problema.

Si decides seguir trabajando en tu propia implementación, me encantaría ver qué se te ocurre.

Matthew R
fuente
1
Gran respuesta, @Mathew. ¡Y definitivamente deberías leer ese periódico! Es fácil de seguir y explica una gran técnica (especialmente el Apéndice A que habla sobre el descubrimiento basado en agentes / generación de la malla). Estoy codificando una versión de este algoritmo para javascript, y está funcionando bien. Lo publicaré como respuesta cuando esté listo.
Stephen
@Stephen me encantaría ver este trabajo
kevzettler
@Stephen También estoy buscando una versión de JavaScript
Apolo
6

En lugar de una malla, podría considerar un enfoque jerárquico A *. La mayor ventaja de una malla es tratar con mundos de juego que no están alineados con la cuadrícula, en lugar de reducir la complejidad de una cuadrícula.

Con un enfoque jerárquico, usted subdivide su mundo repetidamente (como un árbol cuádruple) y genera información de conectividad entre los nodos. Luego, puede generar rápidamente una ruta entre grandes porciones del mundo, y solo usar la cuadrícula de alta resolución para encontrar la ruta dentro de una porción más grande.

El enfoque jerárquico le dará a las órdenes de magnitud un mejor rendimiento, mientras que una malla en el mejor de los casos solo le dará una pequeña mejora lineal.

El enfoque ingenuo es simplemente dividir su mundo en trozos alineados de cuadrícula X por X más grandes, generar la información de conectividad entre ellos (por ejemplo, ¿hay una ruta entre el fragmento 2x1 de 3x1 a 2x2, y cuál es la distancia de la ruta promedio) .

Tenga en cuenta que no siempre puede obtener caminos ideales con este enfoque en algunas circunstancias particulares. La generación de capas de trozos de tamaño variable alivia el problema, pero honestamente, por lo general, es mucho más fácil evitar la creación de caminos problemáticos y confiar en el hecho de que es muy poco probable que el jugador note a algún enemigo tomando caminos subóptimos, excepto en el La mayoría de los casos degenerados.

Sean Middleditch
fuente
1
Debería explicar más: mi juego no está alineado con la cuadrícula. Estaba construyendo una cuadrícula en un área de 800 x 600 píxeles, cada píxel era un espacio en la cuadrícula (todavía estaba descubriendo A *, por lo que todavía no estaba pensando en el rendimiento de esto). Tengo obstáculos que no son tan simples como los de la imagen de ejemplo anterior, solo estaba tratando de ilustrar el problema. Obviamente, tal campo de juego necesitaba ser revisado, y después de algunas investigaciones, creo que una malla de navegación sería el camino correcto.
Stephen
3

Creo que podrías estar complicando demasiado esto. Probablemente no necesite generar mallas de navegación sobre la marcha. En cambio, tenga una malla de navegación estática para su mundo base.

El camino alrededor de los obstáculos se puede resolver utilizando comportamientos de dirección (evite los obstáculos). Si en caso de que su obstáculo sea tan grande que se llene o bloquee completamente el viaje de un nav-poly al siguiente, entonces tenga alguna forma de verificar este caso límite y recalcule el camino entre el poly en el que se encuentra actualmente y el uno del que estás bloqueado.

Ray Dey
fuente