¿Cómo puedo generar una ruta de mazmorra (relativamente) lineal?

8

Estamos desarrollando un concepto para un desplazamiento lateral de acción. Lo que necesitamos es una forma de generar un mapa (relativamente) recto. Con esto quiero decir algo así como ...

ingrese la descripción de la imagen aquí

Es claro ver que este mapa sigue una ruta simple, incluso si se desvía un poco. Con eso, también vamos a implementar caminos extraviados: atajos o pasajes secretos. De modo que, tal vez, para llegar desde la tercera área en círculo hasta la cuarta, tendrías el camino principal y un pasadizo secreto que está lleno de enemigos más fuertes, pero es más rápido y tiene mayores recompensas.

Aquí hemos llegado a un callejón sin salida. Estamos explorando algunas opciones, pero realmente no hemos hecho ningún progreso. ¿Qué enfoque podríamos utilizar para generar este tipo de ruta? No estamos sujetos a lenguajes de programación, ya que hasta ahora hemos experimentado con Java, C # y C ++. Del mismo modo, no tenemos dependencias actuales en motores de juegos específicos.

usuario2444503
fuente
11
Agregaría que no está claro cuál es el resultado final que está buscando. El 'mapa' que muestra es una vista de arriba hacia abajo de una región. Estás desarrollando un 2D desplazamiento lateral . ¿Cómo se relacionan los 2?
Vaillancourt
Eliminé la "mejor" redacción de su pregunta, ya que no es realmente útil. Yo también le extirpan los tres enfoques sugeridos, que son todos potencialmente respuestas válidas. En general, es mejor si no incluye posibles soluciones en su pregunta, ya que comparar las soluciones proporcionadas generalmente no es una consulta que consideremos sobre el tema aquí (pero preguntar cómo resolver el problema en ausencia de un sesgo de solución existente sí lo es). También limpié algunas de las charlas de comentarios que siento que son eliminadas por las ediciones.
1
Esa línea se ve casi exactamente como la que obtuve cuando comencé con una línea recta y le agregué ruido de perlin (o simplex) (varias octavas). Podría ser un área para explorar (estaba creando un tiempo dinámico que variaba la iluminación)
Richard Tingle

Respuestas:

15

Requisitos

  1. Desea múltiples caminos de A a B.
  2. Desea trabajar en el espacio de la cuadrícula, presumiblemente este es el espacio de mosaico para su desplazamiento lateral.
  3. No quieres que se crucen caminos, o estropeará la progresión del juego.
  4. Desea que los caminos se vean razonablemente orgánicos.

Diagramas de voronoi

Los diagramas de Voronoi son gráficos planos que llenan el espacio:

ingrese la descripción de la imagen aquí

Una cosa buena de ellos es cómo puedes usarlos para crear rutas orgánicas. Si dibuja una línea recta de centro a centro, obtendrá un camino bastante impredecible (léase: no ortolineal).

Cómo crear un diagrama de Voronoi para usar con un sistema basado en mosaicos

Cree un mapa de un tamaño razonable, digamos 128x128. Genere ncoordenadas de cuadrícula aleatorias (x, y) en el mapa y complete cada una con un id / color único. Cree una lista para ese color y agregue esa celda inicial; haz esto para cada color.

Ahora tiene estos puntos de color únicos flotando en un vacío, pero necesita crear islas enteras de color a su alrededor, con el resultado final así:

ingrese la descripción de la imagen aquí

Para hacer eso, necesitamos ver qué color posee cada celda en el mapa (celda = píxel en la imagen de arriba). Recorremos cada celda del mapa, verificando cuál de nuestros npuntos de color iniciales está más cerca (a través de Pitágoras). Esa celda entra en la lista asociada con esa identificación / color únicos ... en lo sucesivo denominados células de AKA Voronoi de las islas (en el diagrama anterior, grupos de píxeles con el mismo color).

Ahora debería tener un diagrama de Voronoi cuantizado. El siguiente paso es analizar la adyacencia de cada isla a otras islas. Configure un nodo simple y una estructura de borde para que pueda almacenar un gráfico (el nodo es solo la identificación, la lista para esa identificación y una lista vacía de bordes; el borde es solo el nodo inicial y final). Para cada isla con identificación única, cree un nodo y agregue bordes para vincularlo a cada isla a la que está adyacente.

Una vez que tiene el diagrama completo (gráfico), llega a la parte divertida: use el gráfico para encontrar cadenas de islas, y al hacer que todas las celdas de cada isla en la cadena tengan la misma ID, está creando una de tus caminos Digamos que una isla con todas las celdas con ID 503 está sentada junto a una isla con id 657. Puede reemplazar todas las celdas 503 con una ID 657, creando así una isla más grande de 657 adyacentes.

Por ejemplo: el rojo es la ruta 1, el azul es la ruta 2, el magenta es ambos:

ingrese la descripción de la imagen aquí

Puede usar cualquier algoritmo gráfico existente (A * incluido) para generar las rutas de principio a fin. Obtener un camino sinuoso es un caso de no siempre usar el paso óptimo hacia la isla de meta.

Por último, es trivial reducir las islas si desea caminos más estrechos, o utilizar un mapa más grande con muchas más islas para obtener una resolución más precisa.

Un paso final opcional para encontrar caminos

Puede usar el gráfico de alto nivel que construyó junto con las celdas / mosaicos subyacentes para ejecutar el tiempo de ejecución A *, O puede escalar las celdas / mosaicos subyacentes para un mejor movimiento:

En el centro (o cualquier) coordenada de tu isla objetivo, puedes colocar una celda de influencia. Esta influencia puede bombear "olor" como en la difusión colaborativa . Este aroma se extenderá por el camino de regreso a lo que fue la isla de inicio, cada vez más débil a medida que avanza. Ahora, para una entidad al comienzo, simplemente subimos de una celda con un aroma más bajo a una con un aroma más alto, cada vez acercándote a la meta, de la misma manera que opera un perro. Cada ruta es aproximadamente lineal, esto le permite evitar el uso de A * en tiempo de ejecución. O puede hacer lo mismo con el gráfico de islas, pero de esa manera es un poco más complejo porque probablemente querrá navegar por sus entidades a nivel de mosaico. Entonces, la primera forma es quizás mejor. De cualquier manera, podrá navegar hacia la meta con un bajo costo de procesamiento.

Ingeniero
fuente
Hice un generador de mapas usando Voronoi y Perlin Noise en Java, tal vez pueda ser útil como punto de partida: github.com/dragondgold/Map-Generator
Andres