Gerar processualmente regiões na ilha

Atualmente, tenho ilhas que se parecem com isso:

E eu quero subdividi-lo processualmente em regiões, assim:

Qual algoritmo faz o que estou procurando? Você tem sugestões sobre como criar regiões coerentes, como na figura inferior. Sua ajuda é apreciada.

No mundo real, essas fronteiras provinciais geralmente seguem características geológicas como rios.

Então, talvez uma boa abordagem seria modelar a geologia da ilha e fazer com que as fronteiras caiam fora disso?

A Red Blob Games tem alguns bons artigos sobre esse assunto, com bons resultados.

Sua abordagem parece envolver o uso do mosaico de Voronoi e define os rios como os limites entre as células.

Confira os outros artigos em seu site, ele escreveu bastante sobre o assunto de geração de mapas .

Eu resolveria esse problema com duas passagens dos diagramas de Voronoi:

Primeira passagem: particionamento de região

A primeira passagem usaria uma distribuição um pouco esparsa de pontos (ou seja, a distância entre os pontos deve ser relativamente grande) para dividir aproximadamente a ilha em regiões (veja a nota abaixo sobre a geração de pontos). Em seguida, gere um diagrama Voronoi com base nesses pontos. Isso dividirá a ilha em regiões poligonais em torno de cada ponto, como mostrado abaixo:

Segunda passagem: randomização de borda

Agora que a ilha foi dividida em regiões, o próximo passo é 'aproximar' os limites entre elas. Para fazer isso, gere uma nova camada de pontos usando uma distribuição mais compacta de pontos (ou seja, a distância entre os pontos deve ser pequena) e use novamente esses pontos para criar outro diagrama de Voronoi. Em seguida, para cada região menor, atribua-a a uma região maior, verificando seu ponto de 'semente'. Isso resultará em limites mais irregulares entre as subdivisões maiores. Aqui está um close do que parece com os dois diagramas de Voronoi:

E aqui está a mesma área mostrando apenas os limites finais:

Comentários sobre Point Generation

Em relação à geração de pontos, eu gosto de usar uma distribuição de discos Poisson para obter uma distribuição relativamente agradável e uniforme de pontos. A outra opção comum é obter uma distribuição igualmente uniforme é usar o algoritmo de Lloyd em um conjunto de pontos aleatórios 'regulares'. O LLoyd's é mais fácil de codificar, mas pode levar algumas tentativas e erros para determinar quantas passagens são necessárias para obter o resultado desejado.

Um problema potencial com essa abordagem é que o particionamento da primeira passagem pode gerar algumas regiões muito pequenas. Se você não os quiser no resultado final, eu simplesmente os fundirei com uma região adjacente aleatória.

Notas Finais

As ilustrações que forneci são imagens rasterizadas, mas essa técnica também funciona com representações poligonais / vetoriais.

O MineCraft faz isso muito bem, e seu algoritmo de geração mundial foi analisado e documentado minuciosamente.

Existem várias descrições do algoritmo, uma delas aqui: https://github.com/UnknownShadow200/ClassiCube/wiki/Minecraft-Classic-map-generation-algorithm

O núcleo do algoritmo é um gerador de ruído Perlin . Isso controla a elevação diretamente (mais ou menos, pois a etapa subsequente de escavar cavernas também pode alterar a superfície), bem como a geração de biomas. Algo como o gerador de biomas é provavelmente o que você deseja usar para criar suas áreas.

(Uma versão antiga) está documentada , basicamente funciona usando dois geradores Perlin Noise diferentes, um para "temperatura", um para "precipitação" e, em seguida, escolhendo o bioma dentre esses dois. As variáveis ​​em si (temperatura e precipitação) não são realmente usadas no jogo posteriormente; por exemplo, desertos não têm chuva, mas o jogo determina isso na propriedade "deserto", não no valor original da precipitação.

Existem várias ferramentas online para gerar um mapa do bioma a partir de uma semente aleatória, uma delas é mineatlas.com . Eu acho que, internamente, eles usam um servidor java que usa as classes internas do próprio MineCraft; Não sei se algum código fonte está disponível diretamente.

Um algoritmo típico usado, por exemplo, pelo Azgaar ( código fonte ). É mais ou menos assim:

1. divida sua massa terrestre em áreas menores, por exemplo, através da triangulação delauny ou células voronoi.
2. determine (aleatoriamente ou não) locais "iniciais" para suas culturas, reinos, religiões ou qualquer outra coisa que você queira simular.
3. determinar (aleatoriamente ou não) um "fator de crescimento" para cada um deles. Quanto maior a diferença nos fatores de crescimento, menos uniforme será o seu mapa final.
4. Agora itere sobre seus reinos (etc) e, dependendo do fator de crescimento, espalhe-os pelos ladrilhos vazios circundantes até que todo o mapa seja preenchido.
5. Provavelmente, você deseja terminar um pouco o alinhamento das bordas, alternando as células que possuem apenas um vizinho em sua própria cor e, caso contrário, são cercadas por outro diferente daquela cor.

Se você está interessado em fazer isso em formato vetorial, em vez de abordagens baseadas em varredura, escrevi um post de blog há um tempo atrás sobre praticamente exatamente isso.

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

A idéia é começar com uma malha (geralmente baseada em Voronoi) e crescer as regiões concentricamente a partir de pontos semeados aleatoriamente e suficientemente espaçados.

Que pergunta divertida :) Essa abordagem é baseada nas células de Vornoi, mas a métrica da distância não é bem euclidiana (usei o poder de 1,5 em vez de 2,0) e tem alguma aleatoriedade incorporada. Pode pular sobre a água, o que não é o ideal.

As regiões próximas podem ser mescladas para obter formas mais interessantes; aqui eu meio que usei os N vizinhos mais próximos para determinar isso.

Se você estiver interessado, posso entrar em mais detalhes e compartilhar o código Python.