Generar regiones procesales en la isla

29

Actualmente tengo islas que se ven así:

isla

Y quiero subdividirlo procesalmente en regiones, así:

isla con regiones

¿Qué algoritmo hace lo que estoy buscando? ¿Tiene sugerencias sobre cómo crear regiones coherentes como en la imagen inferior? Tu ayuda es apreciada.

domisum
fuente
¿Cómo conseguiste esa imagen de la isla en primer lugar? ¿Lo generó y, de ser así, cómo lo logró?
Vaillancourt
Lo obtuve de un generador de mapas en línea.
domisum
Perdón por la demora en actualizar mi respuesta, tardé más en llegar a casa de lo planeado originalmente. Agregué algunas ilustraciones y enlaces.
Pikalek
Si recibiste esto de un generador en línea, deberías mirar el generador de mapas de fantasía de Azgaar . Tiene regiones y nombres, con parámetros personalizables, y WB.SE dice hola. Es un github, por lo que puede verificar su código.
Anoplexian - Restablece a Monica el

Respuestas:

40

En el mundo real, esas fronteras provinciales a menudo seguirán características geológicas como los ríos.

Entonces, ¿quizás un buen enfoque sería modelar la geología de la isla y hacer que las fronteras se salgan de esto?

Red Blob Games tiene algunos buenos artículos sobre este tema, con buenos resultados.

Su enfoque parece implicar el uso de la teselación de Voronoi y definir los ríos como los límites entre las células.

Mira los otros artículos en su sitio, ha escrito mucho sobre el tema de la generación de mapas .

isla

Bram
fuente
3
Tenga en cuenta que en el mundo real, las divisiones políticas o administrativas también a veces tienen divisiones arbitrarias, generalmente líneas rectas (por ejemplo, a lo largo de líneas de latitud / longitud, líneas entre picos de montañas, etc.).
Pablo H
2
@PabloH Buen punto, aunque las fronteras rectas parecen ser un fenómeno post-medieval de la era colonial. Pero dado que no conocemos la configuración del problema de OP, podría ser relevante
Sentry
27

Resolvería este problema con dos pases de diagramas de Voronoi:

Primer Pase: Particionamiento de Región

La primera pasada usaría una distribución de puntos algo dispersa (es decir, la distancia entre los puntos debería ser relativamente grande) para dividir aproximadamente la isla en regiones (ver la nota a continuación sobre la generación de puntos). Luego genere un diagrama de Voronoi basado en estos puntos. Esto dividirá la isla en regiones poligonales alrededor de cada punto como se muestra a continuación:

ingrese la descripción de la imagen aquí

Segundo pase: aleatorización de fronteras

Ahora que la isla se ha dividido en regiones, el siguiente paso es 'desbastar' los límites entre ellas. Para hacerlo, genere una nueva capa de puntos usando una distribución más compacta de puntos (es decir, la distancia entre puntos debe ser pequeña) y nuevamente use estos puntos para crear otro diagrama de Voronoi. Luego, para cada región más pequeña, asígnela a una región más grande marcando su punto 'semilla'. Esto dará como resultado límites más irregulares entre las subdivisiones más grandes. Aquí hay un primer plano de cómo se ve con ambos diagramas de Voronoi en su lugar:

ingrese la descripción de la imagen aquí

Y aquí está esa misma área que muestra solo los límites finales:

ingrese la descripción de la imagen aquí

Comentarios en Generación de puntos

Con respecto a la generación de puntos, me gusta usar una distribución de disco de Poisson para obtener una distribución de puntos relativamente agradable y uniforme. La otra opción común es obtener una distribución igualmente pareja es usar el algoritmo de Lloyd en un conjunto de puntos aleatorios 'regulares'. LLoyd's es más fácil de codificar, pero puede tomar algunas pruebas y errores para determinar cuántos pases se requieren para obtener el resultado deseado.

Un problema potencial con este enfoque es que la partición de primer paso puede generar algunas regiones muy pequeñas. Si no los quiere en su resultado final, simplemente los fusionaría con una región adyacente aleatoria.

Notas finales

Las ilustraciones que proporcioné son imágenes rasterizadas, pero esta técnica también funciona con representaciones poligonales / vectoriales.

Pikalek
fuente
1
Para los planos de procedimiento, esto es lo que hago, hacer un diagrama de Voronoi desde puntos dentro de la región (la isla), construir una cuadrícula (no tiene que ser rectangular, para su caso una cuadrícula deformada) que encierra la misma región, luego calcule las intersecciones booleanas de la cuadrícula y el Voronoi, calcule las áreas y asigne a un árbol de datos (lista de listas, matriz dentada, etc., cualquier estructura de datos que prefiera) de acuerdo con el porcentaje de 0.6 de la celda de cuadrícula más pequeña, obtendrá algunas celdas faltantes, pero puede comparar su cuadrícula eliminada con el original para encontrar y reasignar a su árbol.
Felipe Gutiérrez
¡Agregaste imágenes! Esto es exactamente lo que estoy haciendo para un propósito diferente
Felipe Gutiérrez,
4

MineCraft hace esto muy bien, y su algoritmo de generación mundial ha sido analizado y documentado a fondo.

Hay varias descripciones del algoritmo, una de ellas aquí: https://github.com/UnknownShadow200/ClassiCube/wiki/Minecraft-Classic-map-generation-algorithm

El núcleo del algoritmo es un generador de ruido Perlin . Esto controla la elevación directamente (más o menos, ya que el paso posterior para crear cuevas también puede cambiar la superficie), así como la generación de biomas. Probablemente, algo como el generador de bioma es lo que desea utilizar para crear sus áreas.

(Una versión anterior) está documentada , básicamente funciona mediante el uso de dos generadores de ruido Perlin diferentes, uno para "temperatura", uno para "precipitación", y luego elige el bioma de esos dos. Las variables mismas (temperatura y precipitación) no se usan realmente en el juego más tarde; por ejemplo, los desiertos no tienen lluvia, pero el juego determina esto a partir de la propiedad "desierto", no del valor de precipitación original.

Existen varias herramientas en línea para generar un mapa de bioma a partir de una semilla aleatoria, una de ellas es mineatlas.com . Supongo que, internamente, usan un servidor java que usa las clases internas de MineCraft; No sé si alguno de sus códigos fuente está disponible directamente.

Guntram Blohm apoya a Monica
fuente
4

Un algoritmo típico utilizado, por ejemplo, por Azgaar ( código fuente ). Es más o menos así:

  1. divida su masa de tierra en áreas más pequeñas, por ejemplo, mediante triangulación retardada o células voronoi.
  2. determine (al azar o de otro modo) ubicaciones "iniciales" para sus culturas, reinos, religiones o cualquier otra cosa que desee simular.
  3. determinar (aleatoriamente o no) un "factor de crecimiento" para cada uno de ellos. Cuanta más diferencia tenga en los factores de crecimiento, menos uniforme será su mapa final.
  4. Ahora repita sobre sus reinos (etc.) y, dependiendo del factor de crecimiento, haga que se distribuyan en mosaicos vacíos circundantes hasta que se llene todo el mapa.
  5. Probablemente quiera terminar con enderezar un poco los bordes, cambiando las celdas que solo tienen un vecino en su propio color y que, de lo contrario, están rodeadas por otro diferente a ese color.
Tom
fuente
3

Si está interesado en hacer esto en formato vectorial en lugar de enfoques basados ​​en ráster, he escrito una publicación de blog hace un tiempo sobre casi exactamente esto.

http://blog.particracy.com/worlds-and-their-geography/

La idea es comenzar con una malla (generalmente basada en Voronoi) y hacer crecer las regiones concéntricamente a partir de puntos sembrados al azar que están suficientemente separados.

Wouter Lievens
fuente
2

Qué pregunta más divertida :) Este enfoque se basa en las células de Vornoi, pero la métrica de distancia no es del todo euclidiana (utilicé el poder de 1.5 en lugar de 2.0) y tiene algo de aleatoriedad incorporada. Puede saltar sobre el agua, lo que no es ideal.

Las regiones cercanas se pueden fusionar para obtener formas más interesantes, aquí utilicé los N vecinos más cercanos para determinar esto.

Si está interesado, puedo entrar en más detalles y compartir el código de Python.

mapa 1 mapa 2

NikoNyrh
fuente