¿Cómo puedo generar una malla de navegación para una cuadrícula de mosaico?

18

Todavía no he empezado a programar para este, pero de todos modos quería ver cómo lo haría.

Digamos que tengo una cuadrícula de mosaicos, todos del mismo tamaño, algunos transitables y otros no. ¿Cómo haría para crear una malla de navegación de polígonos a partir de esta cuadrícula?

Mi idea era sacar los mosaicos no transitables y extender las líneas desde sus bordes para hacer polígonos ... eso es todo lo que tengo hasta ahora. ¿Algún consejo?

2d mathematics algorithm navmesh Ross Hays
fuente
2
Técnicamente, la cuadrícula es más o menos equivalente a una malla de navegación. Sospecho que en realidad estás pidiendo una forma de optimizar la cuadrícula y fusionar cuadrados adyacentes.
Kylotan
@Kylotan Sí, eso es exactamente lo que quise decir, solo una forma de combinar polígonos adyacentes.
Ross Hays

Respuestas:

28

Este es uno de los métodos que se me ocurrió al hacer navmesh para un juego de estrategia en tiempo real. Tenga en cuenta que es homebrew, no se utilizaron herramientas de terceros, me llevó alrededor de 3 semanas implementarlo y corregirlo:

  1. Use el algoritmo Cuadrados de marcha para convertir las fichas de obstáculos en contornos . Tenga en cuenta que los bordes del mapa también son un esquema y deben incluirse también.
  2. Reduzca el número de puntos en los contornos utilizando el algoritmo Douglas-Peucker (líneas moradas en la imagen inferior)
  3. Alimente todos los puntos en la triangulación de Delaunay (para obtener la mayoría de los triángulos uniformes)
  4. Agregue puntos adicionales en áreas vacías y a lo largo de los bordes del mapa (para obtener una navegación más uniforme)
  5. Verifique los contornos de obstáculos y voltee los polígonos producidos por Delaunay para que coincidan con los contornos. - A menudo Delaunay podría colocar triángulos (gris) que no coinciden con sus contornos (rojo), luego debe detectarlos y voltearlos. Junto a ellos de nuevo en un polígono, divídalo a lo largo de los contornos y triangúlelo manualmente ingrese la descripción de la imagen aquí
  6. Recorte los obstáculos hacia adentro : elimine los polígonos que se encuentran dentro de los obstáculos (rosa en la imagen de arriba)
  7. Complete los datos de conectividad entre los triángulos y vértices restantes según lo necesite ; esa es su malla de navegación.

Resultado:

tilemap navmesh

Kromster dice que apoya a Mónica
fuente
1

Las mallas se implementan típicamente como gráficos. Si desea implementar la búsqueda de ruta en un mapa basado en una cuadrícula, haga lo siguiente:

Cree un gráfico donde cada cuadrado transitable se represente como un vértice. Cada par de cuadrados transversales adyacentes representados como vértices tendrá un borde entre ellos. Y tu estas listo.

Wolfdawn
fuente
1
No es así como se implementan típicamente las navmeshes. El propósito de un navmesh (y, me imagino, la razón por la que el autor de la pregunta incluso hizo su pregunta aquí) es optimizar el gráfico hasta un número mínimo requerido de polígonos (generalmente triángulos) que abarcan los espacios más útiles para reducir tanto el número de pasos necesarios para encontrar una buena ruta y la huella de memoria requerida para definir la malla. Una implementación en bruto consumiría una tonelada más de memoria y desperdiciaría un valioso tiempo de procesamiento de IA.
Gurgadurgen
Estás en lo correcto. Por supuesto, la reducción (reducción de polígonos) es una optimización razonable y deseada. Es solo que cuando lees la pregunta del operador, tienes la sensación de que solo quiere convertir una cuadrícula en un gráfico.
wolfdawn