Procurando um bom algoritmo de geração de mapa mundial [fechado]

Estou trabalhando em um jogo semelhante ao da Civilização e procurando um bom algoritmo para gerar mapas mundiais semelhantes à Terra. Experimentei algumas alternativas, mas ainda não achei um vencedor real.

Uma opção é gerar um mapa de altura usando o ruído Perlin e adicionar água em um nível de forma que cerca de 30% do mundo seja terra. Embora o ruído Perlin (ou técnicas baseadas em fractais semelhantes) seja frequentemente usado para terrenos e seja razoavelmente realista, ele não oferece muito controle sobre o número, tamanho e posição dos continentes resultantes, o que eu gostaria de tem de uma perspectiva de jogo.

Uma segunda opção é começar com uma semente de um ladrilho posicionada aleatoriamente (estou trabalhando em uma grade de ladrilhos), determinar o tamanho desejado para o continente e a cada vez adicionar um ladrilho que seja horizontal ou verticalmente adjacente ao continente existente até você atingiu o tamanho desejado. Repita para os outros continentes. Essa técnica faz parte do algoritmo usado em Civilization 4. O problema é que depois de colocar os primeiros continentes, é possível escolher um local de partida que está rodeado por outros continentes e, portanto, não caberá no novo. Além disso, tem a tendência de gerar continentes muito próximos, resultando em algo que se parece mais com um rio do que com continentes.

Alguém conhece um bom algoritmo para gerar continentes realistas em um mapa baseado em grade, mantendo o controle sobre seu número e tamanhos relativos?

Você pode seguir uma sugestão da natureza e modificar sua segunda ideia. Depois de gerar seus continentes (que têm quase o mesmo tamanho), faça com que eles se movam e girem aleatoriamente e colidam e deformam uns aos outros e se afastam uns dos outros. (Observação: isso pode não ser a coisa mais fácil de implementar.)

Edit: Aqui está outra maneira de fazer isso, completa com uma implementação - Polygonal Map Generation for Games .

Eu sugiro que você volte e

1. Pense no que faz continentes "bons".
2. Escreva um algoritmo que possa diferenciar um bom layout continental de um ruim.
3. Refine o algoritmo para que você possa quantificar o quão bom é um bom layout.

Depois de fazer isso, você pode começar a implementar um algoritmo que deve ter a seguinte forma:

• Gere continentes ruins e depois melhore-os.

Para melhoria, você pode tentar todos os tipos de truques de otimização padrão, seja recozimento simulado, programação genética ou algo completamente ad hoc , como mover um quadrado de aresta escolhido aleatoriamente de onde quer que esteja no continente para a aresta oposta ao centro de massa do continente. Mas a chave é ser capaz de escrever um programa que possa distinguir continentes bons dos ruins. Comece com continentes desenhados à mão, bem como seus continentes de teste, até obter algo de que goste.

Escrevi algo semelhante ao que você está procurando para um clone do Civilization 1. estilo protetor de tela automatizado. Para registro, escrevi isso em VB.net, mas como você não mencionou nada sobre linguagem ou plataforma em sua pergunta, vou manter é abstrato.

O "mapa" especifica o número de continentes, a variância do tamanho do continente (por exemplo, 1,0 manteria todos os continentes com a mesma área de terra aproximada, até 0,1 permitiria que os continentes existissem com 1/10 da massa do maior continente), área máxima de terra (como uma porcentagem) para gerar, e o viés central da terra. Uma "semente" é distribuída aleatoriamente ao redor do mapa para cada continente, ponderada em direção ao centro do mapa de acordo com o viés central (por exemplo, um viés baixo produz continentes distribuídos mais semelhantes à Terra, onde como um viés central alto se parecerá mais com um Pangea). Então, para cada iteração de crescimento, as "sementes" atribuem blocos de terreno de acordo com um algoritmo de distribuição (mais sobre isso mais tarde) até que uma área de terreno máxima seja atingida.

O algoritmo de distribuição de terras pode ser tão preciso quanto você quiser, mas encontrei resultados mais interessantes aplicando vários algoritmos genéticos e jogando os dados. O "Jogo da Vida" de Conway é realmente fácil de começar. Você precisará adicionar ALGUMA lógica globalmente ciente para evitar coisas como continentes crescendo uns nos outros, mas na maioria das vezes as coisas cuidam de si mesmas. O problema que encontrei com abordagens mais baseadas em fractais (que foi minha primeira inclinação) foi que os resultados pareciam muito padronizados ou levavam a muitos cenários que exigiam regras de solução alternativa parecidas com hacky para obter um resultado que ainda não parecia dinâmico o suficiente. Dependendo do algoritmo que você usa, você pode querer aplicar uma passagem de "desfoque" sobre o resultado para eliminar coisas como ladrilhos oceânicos de um único quadrado abundantes e linhas costeiras quadriculadas. No caso de algo como um continente sendo gerado cercado por vários outros e sem nenhum lugar para crescer, realoque a semente para um novo ponto no mapa e continue as passagens de crescimento. Sim, pode significar que às vezes você acaba com mais continentes do que o planejado, mas se for realmente algo que você não deseja firmemente, então outra maneira de ajudar a evitar é enviesar os algoritmos de crescimento para que favoreçam o crescimento na direção com menos proximidade de outras sementes. Na pior das hipóteses (pelo menos na minha opinião), você pode sinalizar uma série como inválida quando uma semente não sobrou nenhum lugar para crescer e gerar um novo mapa. Apenas certifique-se de definir um número máximo de tentativas para que se algo irrealista for especificado (como encaixar 50 continentes de peso igual em uma placa de 10x10) não perca a eternidade tentando encontrar uma solução válida.

Não posso garantir como o Civ etc. faz isso e, claro, não cobre coisas como clima, idade da terra, etc., mas brincando com o algoritmo de crescimento de sementes você pode obter resultados muito interessantes que lembram continentes, arquipélagos etc. use a mesma abordagem para produzir rios, cadeias de montanhas, etc. de aparência 'orgânica' também.

Criei algo semelhante à sua primeira imagem em JavaScript. Não é super sofisticado, mas 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>

O artigo sobre geração de mapa poligonal descreve a geração de mapas passo a passo de polígonos de Voronoi.

Esse cara também dá todos os códigos-fonte. É Flash (ActionScript 3 / ECMAScript), mas pode ser transposto para qualquer outra linguagem orientada a objetos

Ou tente usar algoritmos implementados em alguns softwares de ambiente fractal como TerraJ

Só pensando de improviso aqui:

Escolha alguns pontos de partida e atribua a cada um um tamanho (esperado) desenhado aleatoriamente. Você pode manter um desenho de tamanho separado para continentes planejados e ilhas planejadas, se desejar.

Faça um loop sobre os elementos de terreno e, onde eles ainda não estiverem no tamanho planejado, adicione um quadrado. Mas a parte divertida é pesar a chance de que cada elemento vizinho seja o único. Alguma coisa sugerida que pode incluir:

1. Distância até a "outra" terra mais próxima. Além disso, é melhor gerar amplos espaços oceânicos. Quanto mais próximo, melhor torna os canais estreitos. Você tem que decidir se vai permitir que os bits se fundam também.
2. Distância da semente. Mais perto é melhor significa massas de terra compactas, mais longe é melhor significa pedaços longos estendidos
3. Número de quadrados de terreno existentes adjacentes. A ponderação em favor de muitos quadrados adjacentes proporciona uma costa suave, ao passo que preferir poucos proporciona muitas enseadas e penínsulas.
4. Presença de praças de "recursos" nas proximidades? Depende das regras do jogo, quando você gera o quadrado de recursos e se deseja torná-lo mais fácil.
5. Você permitirá que os bits se aproximem ou se juntem aos pólos?
6. ??? não sei o que mais

Continue até que todas as massas de terra tenham atingido o tamanho planejado ou não possam mais crescer por algum motivo.

Observe que alterar o parâmetro para esses fatores de ponderação permite ajustar o tipo de mundo gerado, que é um recurso que gostei em alguns dos Civs.

Dessa forma, você precisará fazer a geração do terreno em cada bit separadamente.

Você pode tentar um algoritmo de diamante quadrado ou ruído perlin para gerar algo como um mapa de altura. Em seguida, atribua valores de intervalos para o que aparece no mapa. Se a sua "altura" for de 0 a 100, faça 0 - 20 água, 20 - 30 praia, 30 - 80 grama, 80 - 100 montanhas. Acho que o notch fez algo semelhante a isso no minicraft, mas não sou um especialista, estou apenas em uma mentalidade de quadrado de diamante depois de finalmente fazê-lo funcionar.

Acho que você pode usar a abordagem de estilo de "programação dinâmica" aqui.

Resolva os pequenos problemas primeiro e combine as soluções de maneira inteligente para resolver os problemas maiores.

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á muito bom dar uma olhada em alguns "Algoritmos de Layout de Gráfico"

• Algoritmos baseados em força
• Algoritmo Genético para Layout de Gráfico

Você pode modificá-los para se adequar ao seu propósito.

Tive uma ideia para a criação de um mapa semelhante à resposta das placas tectônicas. Aconteceu mais ou menos assim:

1. varra os quadrados da grade dando a cada quadrado um quadrado de "terra" se rnd <= 0,292 (a porcentagem real de terra seca no planeta Terra).
2. Migre cada pedaço de terreno um quadrado em direção ao seu vizinho maior mais próximo. Se os vizinhos forem equidistantes, vá em direção ao pedaço maior. Se os pedaços forem iguais, escolha um aleatoriamente.
3. se dois quadrados de terreno se tocarem, agrupe-os em um pedaço, movendo todos os quadrados como um a partir de agora.
4. repita a partir da etapa 2. Pare quando todos os blocos estiverem conectados.

Isso é semelhante a como a gravidade funciona em um espaço 3D. É muito complicado. Um algoritmo mais simples para suas necessidades funcionaria da seguinte maneira:

1. Coloque n quadrados iniciais aleatórios em posições x, y e distâncias aceitáveis ​​entre si. Estas são sementes para seus continentes. (Use o teorema de Pitágoras para garantir que as sementes tenham uma distância mínima entre elas e todas as outras.)
2. gerar um quadrado de terreno a partir de um quadrado de terreno existente em uma direção aleatória, se essa direção for um quadrado de oceano.
3. repita a etapa 2. Pare quando os quadrados de terreno preencherem 30% do tamanho total do mapa.
4. se os continentes estiverem próximos o suficiente uns dos outros, coloque pontes de terra conforme desejado para simular um efeito do tipo Panamá.
5. Desça em ilhas menores e aleatórias, conforme desejado, para uma aparência mais natural.
6. para cada quadrado de "ilha" extra que você adicionar, corte os mares interiores e os quadrados dos lagos dos continentes usando o mesmo algoritmo ao contrário. Isso manterá a porcentagem do terreno no valor desejado.

Deixe-me saber como isso funciona. Eu nunca experimentei.

PS. Vejo que é semelhante ao que você tentou. Exceto que ele configura todas as sementes de uma vez, antes de começar, então os continentes estarão distantes o suficiente e irão parar quando o mapa estiver suficientemente preenchido.

Na verdade, não tentei fazer isso, mas foi inspirado pela resposta de David Johnstone sobre as placas tectônicas. Tentei implementá-lo sozinho em meu antigo projeto Civ e, quando se tratava de lidar com colisões, tive outra ideia. Em vez de gerar blocos diretamente, cada continente consiste em nós. Distribua a massa para cada nó e, em seguida, gere uma série de continentes "blob" usando uma abordagem metaball 2D. A tectônica e a deriva continental seriam ridiculamente fáceis de "falsificar" simplesmente movendo os nós ao redor. Dependendo de quão complexo você deseja ir, você pode até mesmo aplicar coisas como correntes para lidar com o movimento do nó e gerar cadeias de montanhas que correspondem à sobreposição dos limites das placas. Provavelmente não acrescentaria muito ao lado da jogabilidade das coisas,

Uma boa explicação sobre metaballs se você nunca trabalhou com eles antes:

http://www.gamedev.net/page/resources/_//feature/fprogramming/exploring-metaballs-and-isosurfaces-in-2d-r2556

Aqui está o que estou pensando, já que estou prestes a implementar algo como isso que tenho para um jogo em desenvolvimento. :

O mundo dividido em regiões. dependendo do tamanho do mundo, ele determinará quantas regiões. Para este exemplo, vamos supor um mundo de tamanho médio, com 6 regiões. Cada zona da grade se divide em 9 zonas da grade. essas zonas de grade se dividem em 9 grades cada. (isso não é para o movimento do personagem, mas apenas para a criação do mapa) As grades são para biomas, as zonas da grade são para características terrestres mais arqueadas (continente x oceano) e as regiões são para o clima geral. As grades se dividem em ladrilhos.

Geradas aleatoriamente, as regiões recebem conjuntos lógicos de clima. Zonas de grade são atribuídas aleatoriamente, por exemplo; oceano ou terra. As grades recebem biomas aleatoriamente com modificadores baseados em suas zonas de grade e clima, sendo eles floresta, deserto, planície, glacial, pântano ou vulcânico. Depois que todos os princípios básicos forem atribuídos, é hora de combiná-los, usando uma função baseada em porcentagem aleatória que preenche conjuntos de blocos. Por exemplo; se você tem um bioma de floresta, próximo a um bioma de deserto, você tem um algoritmo que diminui a probabilidade de um bloco ser "florestal" e aumenta que ele será "deserto". Então, a meio caminho entre eles, você verá um tipo de efeito mesclado combinando os dois biomas para criar uma transição um tanto suave entre eles. A transição de uma zona da grade para a próxima provavelmente exigiria um pouco mais de trabalho para garantir formações lógicas de massa terrestre. Como, por exemplo, um bioma de uma zona da grade que toca o bioma de outra, em vez de ter uma porcentagem de troca simples com base na proximidade. Por exemplo, existem 50 blocos do centro do bioma até a borda do bioma, ou seja, existem 50 blocos da borda que toca até o centro do próximo bioma. Isso logicamente deixaria uma mudança de 100% de um bioma para o outro. Assim, à medida que os ladrilhos se aproximam da fronteira dos dois biomas, a porcentagem diminui para cerca de 60% ou mais. Acho que não seria sensato dar muita probabilidade de cruzar biomas longe da fronteira, mas você vai querer que a fronteira seja um tanto mesclada. Para as zonas de grade, a mudança percentual será muito mais pronunciada. Em vez de a% cair para cerca de 60%, cairia apenas para cerca de 80%. E uma verificação secundária teria que ser realizada para garantir que não haja um bloco de água aleatório no meio de um bioma terrestre próximo ao oceano sem alguma lógica. Portanto, conecte esse bloco d'água à massa do oceano para fazer um canal para explicar o bloco d'água, ou remova-o completamente. Terra em um bioma de base hídrica é mais fácil de explicar usando afloramentos rochosos e outros.

Oh, meio idiota, desculpe.

Eu colocaria o terreno fractal de acordo com algum layout que você sabe que "funciona" (por exemplo, grade 2x2, diamante, etc, com algum jitter), mas com uma distribuição gaussiana com picos de amortecimento em direção às bordas dos centros do continente. Coloque o nível da água mais baixo de forma que a maior parte seja terra até chegar perto das margens.