algorithm - sistemas - Buscando un buen algoritmo de generación de mapas mundiales
planificacion de procesos sistemas operativos (12)
Colocaría el terreno fractal de acuerdo con un diseño que usted sabe que "funciona" (p. Ej., Rejilla 2x2, diamante, etc., con cierta inestabilidad) pero con una distribución Gaussiana que amortigua los picos hacia los bordes de los centros continentales. Coloque el nivel del agua más bajo, de modo que la mayor parte del terreno quede hasta que se acerque a los bordes.
Estoy trabajando en un juego parecido a Civilization y estoy buscando un buen algoritmo para generar mapas mundiales similares a Earth. He experimentado con algunas alternativas, pero aún no he logrado un verdadero ganador.
Una opción es generar un mapa de alturas utilizando el ruido Perlin y agregar agua a un nivel tal que aproximadamente el 30% del mundo sea tierra. Si bien el ruido Perlin (o técnicas similares basadas en fractales) se utiliza con frecuencia para el terreno y es razonablemente realista, no ofrece mucho control sobre el número, el tamaño y la posición de los continentes resultantes, lo que me gustaría tener desde una perspectiva de juego.
Una segunda opción es comenzar con una semilla de una sola casilla colocada al azar (estoy trabajando en una cuadrícula de fichas), determinar el tamaño deseado para el continente y cada turno agregar una ficha que esté horizontal o verticalmente adyacente al continente existente hasta has alcanzado el tamaño deseado Repita para los otros continentes. Esta técnica es parte del algoritmo utilizado en Civilization 4. El problema es que después de colocar los primeros continentes, es posible elegir una ubicación de inicio que esté rodeada por otros continentes, y por lo tanto no se ajustará a la nueva. Además, tiene una tendencia a engendrar continentes muy juntos, dando como resultado algo que se parece más a un río que a los continentes.
¿Alguien sabe un buen algoritmo para generar continentes realistas en un mapa basado en cuadrícula mientras mantiene el control sobre su número y tamaño relativo?
Creé algo similar a tu primera imagen en JavaScript. No es muy sofisticado pero funciona:
http://jsfiddle.net/AyexeM/zMZ9y/
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Untitled Document</title>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.7.2/jquery.min.js"></script>
<style type="text/css">
#stage{
font-family: Courier New, monospace;
}
span{
display: none;
}
.tile{
float:left;
height:10px;
width:10px;
}
.water{
background-color: #55F;
}
.earth{
background-color: #273;
}
</style>
</head>
<body>
<div id="stage">
</div>
<script type="text/javascript">
var tileArray = new Array();
var probabilityModifier = 0;
var mapWidth=135;
var mapheight=65;
var tileSize=10;
var landMassAmount=2; // scale of 1 to 5
var landMassSize=3; // scale of 1 to 5
$(''#stage'').css(''width'',(mapWidth*tileSize)+''px'');
for (var i = 0; i < mapWidth*mapheight; i++) {
var probability = 0;
var probabilityModifier = 0;
if (i<(mapWidth*2)||i%mapWidth<2||i%mapWidth>(mapWidth-3)||i>(mapWidth*mapheight)-((mapWidth*2)+1)){
// make the edges of the map water
probability=0;
}
else {
probability = 15 + landMassAmount;
if (i>(mapWidth*2)+2){
// Conform the tile upwards and to the left to its surroundings
var conformity =
(tileArray[i-mapWidth-1]==(tileArray[i-(mapWidth*2)-1]))+
(tileArray[i-mapWidth-1]==(tileArray[i-mapWidth]))+
(tileArray[i-mapWidth-1]==(tileArray[i-1]))+
(tileArray[i-mapWidth-1]==(tileArray[i-mapWidth-2]));
if (conformity<2)
{
tileArray[i-mapWidth-1]=!tileArray[i-mapWidth-1];
}
}
// get the probability of what type of tile this would be based on its surroundings
probabilityModifier = (tileArray[i-1]+tileArray[i-mapWidth]+tileArray[i-mapWidth+1])*(19+(landMassSize*1.4));
}
rndm=(Math.random()*101);
tileArray[i]=(rndm<(probability+probabilityModifier));
}
for (var i = 0; i < tileArray.length; i++) {
if (tileArray[i]){
$(''#stage'').append(''<div class="tile earth ''+i+''"> </div>'');
}
else{
$(''#stage'').append(''<div class="tile water ''+i+''"> </div>'');
}
}
</script>
</body>
</html>
Creo que puedes usar el enfoque de "programación dinámica" aquí.
Resuelva primero los problemas pequeños y combine las soluciones de manera inteligente para resolver un problema mayor.
A1= [elliptical rectangular random ... ]// list of continents with area A1 approx.
A2= [elliptical rectangular random ... ]// list of continents with area A2 approx.
A3= [elliptical rectangular random ... ]// list of continents with area A3 approx.
...
An= [elliptical rectangular random ... ]// list of continents with area An approx.
// note that elliptical is approximately elliptical in shape and same for the other shapes.
Choose one/more randomly from each of the lists (An).
Now you have control over number and area of continents.
You can use genetic algorithm for positioning them
as you see "fit" ;)
Será muy bueno echar un vistazo a algunos "Algoritmos de diseño de gráficos"
Puede modificar estos para adaptarse a su propósito.
Escribí algo similar a lo que buscas para un clon automatizado de estilo de protector de pantalla de Civilization 1. Para el registro lo escribí en VB.net pero como no mencionas nada sobre el lenguaje o la plataforma en tu pregunta, me quedaré es abstracto
El "mapa" especifica el número de continentes, la variación del tamaño del continente (ej. 1.0 mantendría todos los continentes con la misma superficie aproximada, hasta 0.1 permitiría la existencia de continentes con 1/10 de la masa del continente más grande), área de tierra máxima (como porcentaje) para generar, y el sesgo central de la tierra. Una "semilla" se distribuye aleatoriamente alrededor del mapa para cada continente, ponderada hacia el centro del mapa según el sesgo central (por ejemplo, un sesgo bajo produce continentes distribuidos más similares a la Tierra, donde un sesgo central alto se parecerá más a un Pangea). Luego, para cada iteración de crecimiento, las "semillas" asignan las baldosas de tierra de acuerdo con un algoritmo de distribución (más sobre esto más adelante) hasta que se haya alcanzado un área de tierra máxima.
El algoritmo de distribución de tierras puede ser tan preciso como lo desee, pero encontré resultados más interesantes aplicando varios algoritmos genéticos y tirando los dados. El "Juego de la vida" de Conway es realmente fácil de empezar. Tendrá que agregar ALGUNA lógica con conciencia global para evitar que cosas como los continentes se desarrollen entre sí, pero en su mayor parte las cosas se cuidan a sí mismas. El problema que encontré con más enfoques basados en fractales (que fue mi primera inclinación) fue que los resultados parecían demasiado modelados o conducen a demasiados escenarios que requieren reglas alternativas para obtener un resultado que todavía no se sentía lo suficientemente dinámico. Dependiendo del algoritmo que utilice, es posible que desee aplicar un pase "difuminado" sobre el resultado para eliminar elementos como abundantes mosaicos oceánicos de una sola casilla y costas a cuadros. En el caso de que algo así como un continente se engendre rodeado de varios otros y no tener ningún lugar para crecer, trasladar la semilla a un nuevo punto en el mapa y continuar con los pasos de crecimiento. Sí, puede significar que a veces terminas con más continentes de lo planeado, pero si realmente es algo que definitivamente no quieres, otra forma de evitarlo es sesgar los algoritmos de crecimiento, por lo que favorecen el crecimiento en la dirección con la menor proximidad a otros semillas En el peor de los casos (en mi opinión, de todos modos), puede marcar una serie como no válida cuando una semilla no tiene ningún lugar para crecer y generar un nuevo mapa. Solo asegúrate de establecer un número máximo de intentos, de modo que si se especifica algo poco realista (como ajustar 50 continentes pares en una placa de 10x10), no pasará una eternidad tratando de encontrar una solución válida.
No puedo responder cómo lo hace Civ, y por supuesto no cubre cosas como el clima, la edad de la tierra, etc., pero jugando con el algoritmo de crecimiento de semillas puede obtener resultados bastante interesantes que se asemejan a continentes, archipiélagos, etc. utilice el mismo enfoque para producir ríos, cadenas montañosas, etc. de aspecto "orgánico".
Esto es lo que estoy pensando, ya que estoy a punto de implementar algo como esto que tengo para un juego en desarrollo. :
El mundo dividido en regiones dependiendo del tamaño del mundo, determinará cuántas regiones. Para este ejemplo, asumiremos un mundo de tamaño mediano, con 6 regiones. Cada zona de cuadrícula se divide en 9 zonas de cuadrícula. esas zonas de cuadrícula se dividen en 9 cuadrículas cada una. (Esto no es para el movimiento de personajes, sino simplemente para la creación de mapas) Las rejillas son para biomas, las zonas de grillas son para las características del terreno arqueado (continente contra océano) y las regiones son para el clima general. Las cuadrículas se dividen en azulejos.
Generados aleatoriamente, las regiones reciben conjuntos climáticos lógicos asignados. Las zonas de cuadrícula se asignan aleatoriamente, por ejemplo; océano o tierra. A las grillas se les asignan biomas aleatoriamente con modificadores basados en sus zonas de grillas y clima, estos son bosques, desiertos, llanuras, glaciares, pantanosos o volcánicos. Una vez que se hayan asignado todos los elementos básicos, es hora de combinarlos, utilizando una función aleatoria basada en el porcentaje que rellene los conjuntos de mosaicos. Por ejemplo; si tienes un bioma forestal, al lado de un bioma del desierto, tienes un algoritmo que disminuye la posibilidad de que un mosaico sea "forestal" y aumenta que será "desierto". Por lo tanto, a mitad de camino entre ellos, verás una especie de efecto combinado que combina los dos biomas a una transición bastante suave entre ellos. La transición de una zona de grilla a la siguiente probablemente requeriría un poco más de trabajo para asegurar formaciones lógicas de masas terrestres. Como, por ejemplo, un bioma de una zona de grilla que toque el bioma de otra, en lugar de tener un porcentaje de conmutación simple basado en la proximidad. Por ejemplo, hay 50 fichas desde el centro del bioma hasta el borde del bioma, lo que significa que hay 50 desde el borde que toca hasta el centro del siguiente bioma. Eso lógicamente dejaría un cambio del 100% de un bioma al siguiente. A medida que las fichas se acercan al borde de los dos biomas, el porcentaje se reduce a alrededor del 60% más o menos. Creo que sería imprudente dar demasiada probabilidad de cruzar biomas lejos de la frontera, pero querrás que el borde se mezcle un tanto. Para las zonas de cuadrícula, el cambio porcentual será mucho más pronunciado. En lugar de que el% baje a alrededor del 60%, solo bajará a alrededor del 80%. Y luego se tendría que realizar una verificación secundaria para asegurarse de que no haya una baldosa de agua aleatoria en el medio de un bioma terrestre junto al océano sin alguna lógica. Entonces, o bien, conecte esa baldosa de agua a la masa del océano para hacer un canal que explique la baldosa de agua o elimínela por completo. La tierra en un bioma basado en agua es más fácil de explicar usando afloramientos rocosos y cosas similares.
Oh, algo tonto, lo siento.
No lo he intentado, pero está inspirado en la respuesta de David Johnstone sobre las placas tectónicas. Intenté implementarlo yo mismo en mi antiguo proyecto Civ y cuando se trataba de manejar colisiones tuve otra idea. En lugar de generar mosaicos directamente, cada continente consiste en nodos. Distribuya masa a cada nodo y luego genere una serie de continentes "blob" utilizando un enfoque de metaball en 2D. La tectónica y la deriva continental serían ridículamente fáciles de "falsificar" simplemente moviendo los nodos. Dependiendo de cuán complejo quieras ir, incluso podrías aplicar cosas como las corrientes para manejar el movimiento del nodo y generar cordilleras que correspondan a los límites de las placas que se superponen. Probablemente no agregaría mucho al lado del juego, pero podría generar una interesante generación de mapas desde una perspectiva puramente académica :)
Una buena explicación de metaballs si no has trabajado con ellos antes:
Podría intentar con un algoritmo cuadrado de diamante o ruido perlin para generar algo así como un mapa de altura. Luego, asigne valores de rangos a lo que aparece en el mapa. Si su "altura" va de 0 a 100, entonces haga 0 - 20 agua, 20 - 30 playa, 30 - 80 hierba, 80 - 100 montañas. Creo que notch hizo algo similar a esto en minifurgonetas, pero yo no soy un experto, solo estoy en una mentalidad de cuadrado de diamantes después de finalmente ponerlo en funcionamiento.
Podrías seguir el ejemplo de la nature y modificar tu segunda idea. Una vez que genere sus continentes (que son aproximadamente del mismo tamaño), haga que se muevan aleatoriamente, roten y choquen y se deformen unos a otros y se separen unos de otros. (Nota: esto puede no ser lo más fácil de implementar).
Editar: Aquí hay otra forma de hacerlo, completa con una implementación: Generación de mapas poligonales para juegos .
Solo pensando en el brazalete aquí:
Elija algunos puntos de inicio y asigne a cada uno un tamaño dibujado aleatoriamente (esperado). Puede mantener un sorteo de tamaño separado para los continentes planificados y las islas planificadas si lo desea.
Pasa el cursor sobre los elementos de la tierra, y si aún no están en el tamaño planificado, agrega un cuadrado. Pero la parte divertida es sopesar la posibilidad de que cada elemento vecino sea el elegido. Alguna cosa sugerida que podría tener en cuenta:
- Distancia al "otro" terreno más cercano. Además, es mejor generar amplios espacios oceánicos. Más cerca está mejor hacer canales angostos. Tienes que decidir si vas a dejar que los bits se fusionen también.
- Distancia de la semilla Más cerca es mejor significa masas de tierra compactas, más lejos es mejor significa largas cadenas de bits
- Número de cuadrados de tierra adyacentes. La ponderación a favor de muchos cuadrados adyacentes le da una costa suave, y prefiere pocos que le proporcione muchas entradas y penínsulas.
- ¿Presencia de cuadrados de "recursos" cerca? Depende de las reglas del juego, cuando generas recursos cuadrados, y si quieres hacerlo más fácil.
- ¿Permitirá que los bits se acerquen o se unan a los polos?
- ??? no sé qué más
Continúe hasta que todas las masas de tierra hayan alcanzado el tamaño planificado o ya no puedan crecer por alguna razón.
Tenga en cuenta que modificar el parámetro de estos factores de ponderación le permite ajustar el tipo de mundo generado, que es una característica que me gustó de algunos de los Civs.
De esta manera necesitarás hacer generación de terreno en cada bit por separado.
Te sugiero que vuelvas y
- Piensa en qué hace los continentes "buenos".
- Escribe un algoritmo que pueda distinguir un buen diseño continental de uno malo.
- Refine el algoritmo para que pueda cuantificar qué tan bueno es un buen diseño.
Una vez que tenga eso en su lugar, puede comenzar a implementar un algoritmo que debe tener la forma siguiente:
- Genera continentes repugnantes y luego mejoralos.
Para mejorar puede probar todo tipo de trucos de optimización estándar, ya sea recocido simulado, programación genética o algo completamente ad hoc , como mover un cuadrado de borde elegido al azar desde donde se encuentre en el continente hasta el borde opuesto al centro de masa del continente. Pero la clave es poder escribir un programa que pueda distinguir buenos continentes de los malos. Comience con continentes dibujados a mano, así como con sus continentes de prueba, hasta que obtenga algo que le guste.
Tuve una idea para la creación de mapas similar a la respuesta de las placas tectónicas. Fue algo como ésto:
- barrer a través de los cuadrados de la cuadrícula dando a cada cuadrado un cuadrado de "tierra" si rnd <= 0.292 (el porcentaje real de tierra seca en el planeta tierra).
- Migra cada pedazo de tierra un cuadrado hacia su vecino más grande más cercano. Si los vecinos son equidistantes, ve hacia el trozo más grande. Si los trozos son del mismo tamaño, elija uno al azar.
- si tocan dos cuadrados terrestres, agrúpelos en un trozo, moviendo todos los cuadrados como uno a partir de ahora.
- repita desde el paso 2. Pare cuando todos los trozos están conectados.
Esto es similar a cómo funciona la gravedad en un espacio tridimensional. Es bastante complicado. Un algoritmo más simple para sus necesidades funcionaría de la siguiente manera:
- Coloca n cuadrados cuadrados iniciales en posiciones X, Y aleatorias y distancias aceptables entre sí. Estas son semillas para tus continentes. (Use el teorema de Pitágoras para asegurarse de que las semillas tengan una distancia mínima entre ellas y todas las demás).
- engendrar un cuadrado de tierra desde un cuadrado de tierra existente en una dirección aleatoria, si esa dirección es un cuadrado oceánico.
- repita el paso 2. Detenga cuando los recuadros cuadrados llenen el 30% del tamaño total del mapa.
- si los continentes están lo suficientemente cerca uno del otro, coloque puentes terrestres como desee para simular un efecto de tipo Panamá.
- Suelta en islas más pequeñas y aleatorias según lo desees para un aspecto más natural.
- por cada casilla adicional de "isla" que agregue, recorte los mares interiores y las plazas de los lagos de los continentes utilizando el mismo algoritmo en reversa. Esto mantendrá el porcentaje de la tierra en la cantidad deseada.
Déjame saber cómo funciona esto. Nunca lo intenté yo mismo.
PD. Veo que esto es similar a lo que probaste. Excepto que establece todas las semillas a la vez, antes de comenzar, por lo que los continentes estarán lo suficientemente separados y se detendrán cuando el mapa esté suficientemente lleno.
El artículo de generación de mapas poligonales describe la generación de mapas paso a paso en los polígonos de Voronoi.
Este chico también da todos los códigos fuente. Es Flash (ActionScript 3 / ECMAScript) pero transponible a cualquier otro lenguaje orientado a objetos
O intente utilizar algoritmos implementados en algunos softwares de entorno fractales como TerraJ