Generación procesal de ríos o carreteras para terrenos infinitos

28

Debo decir caminos, no caminos, ya que estoy pensando más como medieval. Además, no busca el realismo. La respuesta que estoy buscando será encajar en el molde que describo en lugar del realismo.

Estoy buscando un método para generar caminos / ríos procesales de forma curvilínea, pero quiero hacerlo para un sistema de tipo de terreno infinito. Al igual que el ruido perlin genera manchas, quiero generar segmentos de línea de longitud aleatoria (posiblemente longitud infinita).

Soy consciente de estrategias como la respuesta sugerida que se encuentra aquí , sin embargo, se basa en un punto de inicio y final específico para trabajar, no tengo un punto de inicio y final específico. Me gustaría poder simplemente llamar a una función usando coordenadas arbitrarias y hacer que devuelva si las coordenadas específicas son parte del río / carretera.

No quiero exigir que se genere terreno por adelantado. Eso incluye un mapa de altura (como el usado para simulaciones de lluvia o similar). Tampoco me gustaría requerir un punto de inicio / finalización.

¿Existe tal algoritmo o ajuste en un algoritmo de ruido que alguien pueda conocer para lograr lo que estoy tratando de explicar?

Lo más cerca que he llegado hasta ahora son los fractales de múltiples crestas, si estoy usando el nombre correctamente. Solo estoy tomando el valor absoluto del ruido de valor (suponiendo que esté escalado a -1 a +1) y estableciendo un umbral. Mi problema principal con esto es que las líneas se superponen con demasiada frecuencia, son en su mayoría circulares, a veces convergen para formar grandes lagos, limpios pero no deseados, y muchas veces el grosor de las líneas varía demasiado.

Aquí hay una imagen de lo que tengo hasta ahora en 2D, pero a una frecuencia muy alta para mostrar más detalles:

ingrese la descripción de la imagen aquí

Mitos
fuente
dado que los ríos "fluyen", podría ser fácil determinar los ríos simplemente usando el ruido para determinar el punto de origen, después de eso simplemente use sus datos de mapa de altura sin procesar para determinar la ruta.
Guerra
Sin embargo, los caminos podrían ser un poco más difíciles, consideré construir caminos basados ​​en el uso, si un jugador / todos los jugadores caminaran regularmente sobre algún terreno, se convertiría en camino.
Guerra
1
@ user19142 OK, entonces no es un duplicado. También puede encontrar algún uso en esta pregunta / respuesta: gamedev.stackexchange.com/questions/53400/… Y volveré a incluir los enlaces anteriores como gamedev.stackexchange.com/questions/45403/… gamedev "relacionado" . stackexchange.com/questions/29044/… gamedev.stackexchange.com/questions/31263/…
MichaelHouse
44
Creo que las carreteras no serán muy creíbles si se generan con ruido. Los caminos son creados por la inteligencia en lugar de por la física y el tiempo. Si bien pueden parecerse entre sí a veces, son lo suficientemente diferentes como para que no pueda usar el mismo algoritmo para ambos.
MichaelHouse
1
Las carreteras en ese proyecto eran líneas de contorno que seguían alturas específicas, por lo que posiblemente podría generarlas localmente. Funcionó allí, pero los mapas de altura no se generan con el ruido de Perlin.
amitp

Respuestas:

11

Solo es mi idea archivar esto lo que quieres sin (mucha) precomputación y la posibilidad de un mundo infinito.

El primer pice del algoritmo es el uso de Voronoi-Diagramms . Divide su mundo en cuadrículas, cada cuadrícula tiene una dirección en forma (xgrid, ygrid). Para cada celda en la que necesita crear carreteras, coloca las variables xgrid e ygrid en una función hash que devuelve un número CellSeed . Utiliza CellSeed como semilla para un generador de números aleatorios que genera las coordenadas de los puntos para el Diagrama de Voronoi.

Ahora necesita buscar los bordes del diagrama y los nodos donde colisionan múltiples bordes. También puede almacenar la información en un gráfico para un acceso más fácil.

Después de este paso, puede buscar rutas a través de la red que sean válidas.

Para rutas válidas ahora puede crear las carreteras (tienen bordes afilados).

Nota : También debe generar las coordenadas del diagrama de Voronio para todas las celdas vecinas para que no tenga bordes en los bordes de la celda.

Si no desea bordes afilados, puede calcular el punto medio de cada conexión y usar la dirección como una tangente para una interpolación bezier entre dos bordes en el gráfico.

Sobre el uso de Voronoi-Diagramms

Para archivar las estructuras viales de la ciudad, los puntos de la función pseudoaleatoria pueden alinearse en una cuadrícula, por lo que las formas tienen forma de rectángulo.

Para más carreteras tipo condado, los puntos tienen que estar más desordenados.

diagrama de wikipedia

Acerca de la función pseudoaleatoria para generar las posiciones de los puntos para los Voronoi-Diagramms

Puede ser una función aleatoria normal o un conjunto de Hammersley para una distribución más uniforme y no agrupada de los puntos.

Quonux
fuente
¿Tienes algún ejemplo de función hash? Tengo el mismo objetivo (mundo infinito que usa voronoi para carreteras) pero parece que no puedo entender cómo se debe hacer esto. Cada lib voronoi que puedo encontrar espera coordenadas de un cuadro delimitador que inmediatamente anula el propósito.
BotskoNet
No, la función hash es solo para asignar una semilla inicial a la celda. Puede ser algo tan trivial como x * prime1 + y * prime2 + z * prime3. Donde los números primos son desiguales entre sí e idealmente grandes, debe calcular aquí con enteros de 64 bits / sin signo. No es un problema si la biblioteca utiliza un cuadro delimitador, porque para cada celda solo tiene que conserver todos los puntos en la celda más todos los puntos de las celdas vecinas (que son 8 celdas vecinas).
Quonux el
Probablemente se encontrará con problemas de precisión con precisión simple si la biblioteca usa precisión simple o si usa una precisión simple. Para evitar el problema si la lib solo usa precisión simple y no hace lo siguiente: antes de convertir las posiciones a precisión simple, reste la posición global de la celda central de ellas, luego ponga esto como flotantes en la lib, luego transforme el resultados de vuelta.
Quonux el
En realidad, nunca implementé este algoritmo, pero la función hash puede ser realmente trivial.
Quonux el
8

Para la creación de carreteras (y ciudades), el mejor artículo que encontré es este:

Modelado procesal de ciudades por Y Parish y P Müller

Esto utiliza el sistema L y puede generar patrones de carreteras de EE. UU. Y la UE. Si no desea generar carreteras para toda una ciudad, simplemente puede generar las carreteras principales. Puede tomar un mapa de altura, un mapa del agua y un mapa de densidad de población en la entrada.

Rak
fuente
+1 solo porque me gustó el papel. Realmente no encajaba con cómo quiero intentar generar los caminos / caminos / ríos MIENTRAS genero dinámicamente el terreno.
Míticos
6

La sección http://vterrain.org/Culture/Roads/ "Generando carreteras 3D" tiene información sobre la generación de carreteras .

El problema con las carreteras es que conectan puntos de referencia (aunque a menudo siguen el terreno en lugar de ir directamente de A a B).

Personalmente, generaría el terreno, luego colocaría ríos (tal vez usando la erosión, consulte http://vterrain.org/Water/ sección "hidrogeología"), luego colocaría ciudades en lugares donde tenga sentido (por ejemplo, cerca de un río u otro fuente de agua, o en un lugar donde el agua pueda transportarse a través de acueductos o torres de agua y tuberías) y finalmente generar caminos entre ciudades.

Para que esto sea más fácil de usar en un mundo de procedimientos, podría crear puntos intermedios en el terreno donde las carreteras tendrían más probabilidades de ir cuando se generan en ese lugar, luego conectar los puntos intermedios si realmente se crea una carretera en ese lugar.

Exilyth
fuente
4

Primero, los ríos y las carreteras son muy diferentes. Las carreteras tienden a seguir las isolinas (elevación igual / similar); la razón es que es mucho más fácil viajar en carreteras que no suben ni bajan mucho. Los ríos, por otro lado, viajan perpendicularmente a las isolinas / isoclinas (cuesta abajo). Los ríos se forman en cuencas (colecciones de montañas que fluyen hacia un valle determinado) y tienden a formar estructuras con forma de árbol. Además, las carreteras a menudo viajan perpendicularmente a los ríos, para formar puentes lógicos. La mejor idea es generar primero ríos y luego crear caminos lógicos (es decir, caminos entre ciudades). Lamentablemente, no tengo tiempo para entrar en más detalles, pero espero que esto te lleve por el camino correcto.

Puede parecer obvio, pero mira los mapas de Google en varios tipos de terreno y carreteras; obtendrá una mejor idea de cómo deberían verse.

Gavan Woolery
fuente
1
Modifiqué la pregunta nuevamente para que se entendiera más que no estoy interesado en el realismo ni en la forma en que el algoritmo debería funcionar. No obstante, agradezco la respuesta, aunque principalmente para algunos de los términos utilizados. Intento pensar en mi deseo más como garabatos infinitos de longitud aleatoria que se pueden generar con datos mínimos necesarios (como el mapa de altura).
Mítica