¿Cuál es una buena forma de generar clústeres y rutas aleatorios?

Question

Estoy jugando con la escritura de un generador de mapas al azar, y no estoy muy seguro de cómo generar al azar paisajes realistas. Estoy trabajando con these sorts de mapas a escala local, lo que presenta algunos problemas interesantes.

Uno de los casos más simples es la forest:

    Sparse Medium Dense 
Typical trees  50%  70%  80% 
Massive trees  —  10%  20% 
Light undergrowth 50%  70%  50% 
Heavy undergrowth —  20%  50% 

Los árboles y maleza puede existir en el mismo espacio, por lo que un bosque ralo promedio tiene 25% de árboles típicos y la maleza luz, 25% árboles típicos, 25 % de sotobosque ligero y 25% de espacio abierto. Los bosques medianos y densos tomarán un poco más de pensamiento, pero tampoco es mi problema, ya que está disperso.

Mi problema radica en la generación de clústeres y rutas, manteniendo las restricciones de porcentaje. Marshes son un buen ejemplo de esto:

    Moor Swamp 
Shallow bog   20% 40% 
Deep bog   5% 20% 
Light undergrowth 30% 20% 
Heavy undergrowth 10% 20% 

cuadrados de pantano profundas son generalmente agrupados juntos y rodeados por un anillo irregular de los cuadrados de los pantanos poco profundos.

Un elemento de mapa adicional, un seto, también puede estar presente, así como una ruta de campo abierto, serpenteando a través del pantano. Ambos tipos de elementos de mapa (clusters y rutas) presentan problemas, ya que la composición total del mapa debe contener X% del elemento, pero no está distribuido uniformemente. Otros elementos, como las corrientes, los estanques y las arenas movedizas, también necesitan una generación de clúster o tipo de camino.

¿Qué técnica puedo usar para generar mapas realistas dadas estas restricciones?

---

estoy usando C#, FYI (pero esto no es una cuestión específica de C#.)

Answer 1

realista "al azar" distribución se hace a menudo usando Perlin Noise, que puede ser solía dar una distribución con "grumos" como usted menciona. Funciona al sumar/combinar varias capas de valores linealmente interpolados de puntos de datos aleatorios. Cada capa (u "octava") tiene el doble de puntos de datos que la anterior, y se limita a un rango más estrecho de valores. El resultado es una textura aleatoria de aspecto "realista".

Aquí hay una hermosa demostración de the theory behind Perlin Noise de Hugo Elias.

Aquí está lo primero que encontré en Perlin Noise in C#.

Lo que puede hacer es generar una imagen Perlin Noise y establecer un "umbral", donde todo lo que está por encima de un valor está "encendido" y todo lo que está debajo está "apagado". Con lo que terminarás son grupos donde las cosas están por encima del umbral, que se ven irregulares e impresionantes. Simplemente asigne los que están por encima del umbral al lugar donde desea que esté su característica de terreno.

Here is a demonstration si un programa genera un mapa de bits Perlin Noise y luego ajusta el umbral de corte a lo largo del tiempo. Un claro "agrupamiento" es visible. Podría ser justo lo que querías.

Observe que, con un umbral alto, muy pocos puntos están por encima de él, y es escaso. Pero a medida que desciende el umbral, esos puntos "crecen" en grupos (por la naturaleza del ruido perlin), y algunos de estos grupos se unirán entre sí, y básicamente crearán algo muy natural y parecido al terreno.

Tenga en cuenta que también puede establecer el "factor de agrupamiento" o la tendencia de las características a agruparse, configurando la "turbulencia" de su función Perlin Noise, que básicamente causa que los picos y valles de su función PN se acentúen y más juntos.

Ahora, ¿dónde establecer el umbral? Cuanto mayor sea el umbral, menor será el porcentaje de la función en el mapa final. Cuanto menor sea el umbral, mayor será el porcentaje. Puedes jugar con ellos.Probablemente puedas obtener porcentajes exactos jugando con un poco de matemática (parece que la distribución de valores sigue un Normal Distribution; podría estar equivocado). Tweak hasta que esté apenas a la derecha :)

EDITAR Como se señaló en los comentarios, se encuentra el porcentaje exacto mediante la creación de un histograma acumulativo (índice de lo que% del mapa está bajo un umbral) y recoger el umbral eso te da el porcentaje que necesitas.

Lo más genial aquí es que puede crear características que se agrupen en ciertas otras características (como las características de su pantano) trivialmente aquí - simplemente use el mismo mapa Perlin Noise dos veces - la segunda vez, bajando el umbral. El primero será grumoso, y el segundo será agrupado alrededor de las mismas áreas, pero con los grupos agrandados (refiérase a la animación flash publicada anteriormente).

En cuanto a otras características como los setos vivos, podría tratar de modelar líneas simples random walk que tienen una mayor tendencia a ir en línea recta, y colocarlas en cualquier lugar al azar en su mapa basado en perlin.

---

muestras

Aquí está una baldosa de 50x50 sample Mapa Forestal. La maleza es de color marrón y los árboles son de color azul (lo siento) para dejar en claro cuál es cuál.

Sparse Forest http://img688.imageshack.us/img688/7005/forestmap.png

Para este mapa no hice umbrales exactos para que coincida con el 50%; Solo configuro el umbral al 50% del máximo. Estadísticamente, esto promediará exactamente el 50% cada vez. Pero puede no ser lo suficientemente exacto para tus propósitos; ver la nota anterior de cómo hacer esto.

---

Aquí es una demostración de sus características Marsh (sin incluir la maleza, para mayor claridad), con poco profundo pantano en pantano gris y profunda en la parte trasera:

Marshes http://img202.imageshack.us/img202/5092/marshdemo.png

esto es sólo 50x50, por lo hay algunos artefactos de eso, pero se puede ver con qué facilidad se puede hacer que el pantano poco profundo "crezca" desde el pantano profundo, simplemente ajustando el umbral en el mismo mapa de Perlin. Para este, miré el nivel de umbral para obtener los resultados más agradables a la vista, pero para sus propios fines, podría hacer lo que se mencionó anteriormente.

Aquí está un mapa Marsh generada desde el mismo mapa de ruido Perlin, pero en extendía a lo largo de 250x250 mapa de baldosas en su lugar:

Marshes 250x250 http://img251.imageshack.us/img251/2867/marshdemo250.png

Answer 2

que nunca he hecho este tipo de cosas, pero aquí hay algunas ideas.

Puede obtener clústeres polarizando la selección aleatoria a las ubicaciones de la cuadrícula que están cerca de los elementos existentes de ese tipo. Asigne un valor predeterminado de 1 a todos los cuadrados. Para los cuadrados con elementos agrupados existentes, agregue el valor de agrupamiento a los cuadrados adyacentes (cuanto mayor sea el valor del agrupamiento, más fuerte será el agrupamiento). Luego haga una selección aleatoria para el siguiente elemento de ese tipo en la función de distribución de probabilidad de todos los cuadrados.

Para las rutas, podría tener un procedimiento similar, excepto que las rutas se extenderían paso a paso (la probabilidad de ruta es finita en cuadrados próximos al final de la ruta y cero en todos los demás). Las rutas direccionales se pueden hacer aumentando la probabilidad de selección en la dirección de la ruta. Las rutas serpenteantes pueden tener una dirección que cambia en el transcurso de la extensión aleatoria (new_direction = mf * old_direction + (1-mf) * rand_direction, donde mf es un factor de momento entre 0 y 1).

Answer 3

Puede comenzar a leer los enlaces here. Recuerdo haber visto un documento mucho mejor. Lo publicaré si lo encuentro (también se basó en L-systems).

Pero eso es en general; en particular, el problema que se enfrenta Creo que se debe modelar en términos de

• porcentajes
• otras reglas (clusters y caminos)

El punto es que a pesar de que no sabe cómo para construir el mapa con las propiedades dadas, si puede evaluar las propiedades (proporción de agrupamiento, bondad de camino) y puntuarlas, puede aplicar fuerza bruta o hacer otro espacio de problema transversal.

Si aún desea hacer un acercamiento generativo, entonces tendrá que examinar las reglas generativas un poco más cerca; He aquí una idea que iba a perseguir

• crear patrones de diferentes terrenos y cubiertas de terreno que han requerido propiedades de 'clusterness', 'pathness' o la uniformidad
• crear los patrones de tal manera que los valores de profundidad el pantano no es discreto, sino que asigna un valor de probabilidad; después de que el patrón se había creado se puede normalizar esta probabilidad de tal manera que producirá porcentaje requerido de la cubierta
• mezcla de diferentes patrones juntos

Answer 4

Es posible que tenga cierto éxito para ciertos tipos de área con un patrón Voronoi . Nunca lo he visto usar para crear mapas, pero lo he visto usado en una cantidad de campos similares.

Answer 5

Para ampliar los comentarios de academicRobot, puede comenzar con un pantano predeterminado o semilla de bosque en algunas de las celdas de la grilla y dejar que crezcan desde la fuente utilizando un número aleatorio correlacionado. Por ejemplo, un pantano puede tener ocho celdas de cuadrícula adyacentes, cada una de las cuales tiene un 90% de probabilidad de ser también un pantano, pero una probabilidad del 10% de ser otra cosa. Puedes dejar que el ecosistema se forme desde la semilla y ajustar la correlación hasta que obtengas algo que se vea bien. Probablemente sea bastante fácil de implementar incluso en una hoja de cálculo.