Gere regiões iguais em um mapa hexadecimal

Tomando, por exemplo, um mapa hexadecimal grande (X por Y), como posso dividi-lo em N regiões de hexágonos conectados para simular países?

O objetivo é gerar um mapa hexadecimal que se parece com um mapa da vida real com países com formas diferentes, mas tamanhos iguais.

Você já experimentou o algoritmo do Lloyd's ? O procedimento é bastante simples e irá gerar regiões com aparência bastante regular (dependendo de quantas iterações você executar).

1. Coloque o mapa com hexágonos em branco para iniciar.
2. Escolha N hexados aleatoriamente. Eles representarão o "centro de massa" de cada país.
3. Identifique cada hexágono com o hexágono central mais próximo ( diagrama de Voronoi ). País i é o conjunto de todos os hexágonos mais próximos do i'ésimo hexágono central.
4. Calcule o novo centro de massa para cada país.
5. Repita as etapas 3 e 4 quantas vezes desejar para suavizar as regiões geradas.

Você não precisa executá-lo por muito tempo para produzir um mapa bonito. Este exemplo requer apenas três iterações.

Uma maneira simples de tentar.

1. Selecione aleatoriamente nhexágonos. Cada um começará um grupo.
2. Para cada grupo, tente expandir o hexágono inicial em uma direção aleatória.
3. Se todos os hexágonos ao redor do hex escolhido estiverem ocupados, marque como tocado, altere hex.
4. Repita até que cada grupo tenha 20 hexadecimais ou não tenha mais espaço para expandir (todos os hexadeclarados).

Eu não testei, mas isso deve gerar ilhas e evitar um pouco de aparelho longo e fino. Além disso, provavelmente haverá fronteiras vizinhas, mas não necessariamente cada uma entrará em contato uma com a outra; essa densidade dependerá do valor de n.
Alguns grupos também podem ser encurralados por outros e atingir menos de 20 tamanhos. Você pode garantir um espaço maior gerando os hexágonos iniciais a uma distância mínima um do outro.
Teste e ajuste conforme necessário.


Além disso, não relacionado a esse problema, mas muito, muito útil para trabalhar com hexágonos, visite esta página: http://www.redblobgames.com/grids/hexagons/#basics
Agrega um monte de informações hexadecimais em um único local com um belo visual.

Definitivamente, acho que algum tipo de estrutura gráfica tornaria isso possível. Basicamente, crie uma aresta entre dois nós hexadecimais se eles estiverem próximos um do outro para simular o mapa inteiro. No entanto, não tenho certeza do algoritmo exato para gerar um "país" dentro desse mapa. O problema é que, dependendo de como você deseja que o país "pareça", você precisará de algoritmos diferentes.

Em cima da minha cabeça, eu recomendaria escolher um ponto e sair daí, escolhendo um ladrilho aleatório dentro do seu "país em crescimento", que tem um ladrilho adjacente que não faz parte do país.

Um padrão de estratégia pode ser usado para alternar algoritmos, dependendo do tipo de país que você deseja. http://en.wikipedia.org/wiki/Strategy_pattern, ou seja, você quer um país fino como o Chile? Ou você quer algo mais redondo e contido?

As propriedades do gráfico também podem permitir que você ajuste a aparência desejada para o "país": http://en.wikipedia.org/wiki/Eccentricity_(graph_theory)

Quer um país grande? Ajuste as propriedades do gráfico e force o país gerado (que é apenas um gráfico) a ter as propriedades que lhe dão uma "aparência" desejada.

Por último, mas não menos importante, o Graphs também será muito útil para definir fronteiras entre países. Você pode criar um gráfico que tenha uma conexão entre dois nós se os países fizerem fronteira entre si. Isso pode ser útil para algum tipo de particionamento no seu jogo e permitirá que você otimize algumas coisas mais adiante no desenvolvimento.

Uma pequena nota: você diz 'parece um mapa da vida real com países de formas diferentes, mas com tamanhos iguais), mas os países' reais 'são muito diferentes em tamanho, mesmo em determinadas regiões - mesmo os países' grandes 'da Europa podem variar bastante, com, por exemplo, a França sendo duas vezes maior que a Itália. Com isso dito, obviamente existem regiões de jogabilidade para tentar manter os tamanhos aproximadamente os mesmos - apenas esteja ciente de que uma pequena variação aqui é provavelmente uma coisa boa !

Minha abordagem inicial para o problema seria 'evoluir' (em vez de 'crescer') suas regiões:

• Comece com uma divisão concreta do mapa em pedaços de tamanho aproximadamente igual por linhas retas (por exemplo, se você quiser 6 países, poderá dividir o mapa em três fatias horizontais e depois dividir cada uma dessas fatias 'na diagonal' em duas partes). Obviamente, isso é fácil de ser programado, principalmente porque não precisa ser muito exato (de fato, provavelmente não deve ser muito exato).
• Faça um passe inicial na divisão, construindo uma estrutura de dados 'limite': um conjunto de hexágonos que têm algum vizinho atualmente pertencente a um país diferente. Este também seria um bom momento para contar quantos hexágonos existem em cada país.

Agora, pelo tempo que desejar, execute o seguinte pseudocódigo:

Pick a random hex A from the boundary list;
Pick a random neighbor B of this hex from a different country;
if (A's country has more hexes than B's country has) {
  change hex A to belong to B's country;
} else if (B's country has more hexes than A's country has) {
  change hex B to belong to A's country;
} else {
  flip a coin to decide which to change;
}
if ( the changed hex's old country has become disconnected ) {
  undo and reject this move;
} else {
  update the boundary list around the changed hex and its neighbors;
}

Isso manterá um equilíbrio aproximado entre o tamanho de dois países vizinhos e a verificação 'desconectada' (que pode ser feita com um algoritmo simples de preenchimento) garante que nenhum país se desmonte em pedaços. Atualizar a lista de limites é uma operação de tempo constante - o hexadecimal alterado obviamente sempre estará no limite, e você pode apenas verificar seus seis vizinhos para ver se algum deles se tornou uma célula de limite (porque seu vizinho está agora em um país diferente) ou deixou de ser uma célula de limite (porque seu vizinho está no mesmo país agora), modificando o conjunto de limites conforme necessário.

Para um refinamento dessa abordagem, você pode até fazer com que a condição de que hex mude um pouco aleatoriamente - em vez de sempre 'equilibrar' os dois países, você sempre pode fazer a troca com uma certa probabilidade e até diminuir essa probabilidade gradualmente. tempo (semelhante ao processo de resfriamento em um Recozimento Simulado algoritmo de ) para começar a forçá-los a ter aproximadamente o mesmo tamanho.

Observe que isso não garante que todas as áreas tenham exatamente o mesmo tamanho (o que é impossível a menos que N divida perfeitamente o tamanho da sua grade) e nem garante que todos os países estejam dentro de um hexágono um do outro na área; ele deve garantir (correr para iterações suficientes) que cada país há mais de um hex maior ou menor do que cada um dos seus vizinhos imediatos é, no entanto.