Como dividir a grade hexadecimal uniformemente entre n jogadores?

15

Estou criando um jogo simples baseado em grade hexagonal e quero que o mapa seja dividido igualmente entre os jogadores. O mapa é criado aleatoriamente, e eu quero que os jogadores tenham uma quantidade igual de células, com áreas relativamente pequenas. Por exemplo, se houver quatro jogadores e 80 células no mapa, cada um deles terá cerca de 20 células (não precisa ser preciso). Além disso, cada jogador deve ter no máximo quatro células adjacentes. Ou seja, quando o mapa é gerado, os maiores "pedaços" não podem ter mais de quatro células cada.

Eu sei que isso nem sempre é possível para dois ou três jogadores (como isso se assemelha ao problema "colorir o mapa"), e eu estou bem em fazer outras soluções para eles (como criar mapas que resolvem o problema). Mas, para quatro a oito jogadores, como eu poderia abordar esse problema?

manabreak
fonte
Autômatos celulares é uma maneira simples, semelhante a este: Um mapa simples, quatro biomas, e como distribuí-los
Michaelhouse

Respostas:

3

Isto é o que eu faria:

  1. Atribua todas as células a jogadores aleatórios. Em mapas grandes, é muito provável que produza um número bastante uniforme de peças para todos os jogadores; em mapas menores, você provavelmente precisará fazer algumas correções.
  2. Divida pedaços muito grandes. A coisa mais fácil a fazer seria pegar todos os blocos em pedaços e atribuir novamente cada bloco aleatoriamente.
  3. No caso de um número desequilibrado de células (por exemplo, o jogador A tem 24 células, o jogador B tem 16), redesigne algumas células de jogadores super-representados para jogadores sub-representados.
  4. Verifique novamente se há pedaços. Se a etapa 3 introduziu novos blocos, volte para a etapa 2. Caso contrário, bom mapa!
Junuxx
fonte
PS: Eu não acho que esse problema seja impossível, o problema de coloração do mapa é bem diferente (por um lado, é o contrário, formas-> cores em vez de cores-> atribuições de ladrilhos).
Junuxx
Eu gosto bastante dessa abordagem, mas não existe a possibilidade de funcionar por um longo tempo, tentando equilibrar os tamanhos da área?
manabreak
11
@manabreak: Eu fiz algo para experimentar. Com uma pequena alteração no passo 2 (reatribuir alternando entre todos os jogadores, em vez de reatribuir aleatoriamente), funciona muito bem. Vou tentar escrever quando tiver tempo.
Junuxx
11
Parece exatamente o que eu estava procurando. :)
manabreak
1

Supondo que você tenha um mapa hexadecimal de ncélulas e pjogadores, onde p <= n, a melhor maneira de resolver isso é através da distribuição round-robin via autômatos celulares (CA).

Inicialização

Aleatoriamente (e / ou usando algumas ou outras heurísticas, como a distância do centro do mapa), escolha uma célula inicial para cada jogador. Desde então p <= n, isso não deve ser um problema.

Autômatos celulares

Você precisa de conectividade completa entre suas células hexadecimais. Eu sugeriria uma matriz de 6 vizinhos por célula:

class Cell
{
   //... other members...
   Cell[6] neighbours = new Cell[6];
}

O uso de matrizes de tamanho fixo permite que exista o conceito de direções topográficas entre células, o que uma lista ou vetor não existiria. Eu recomendo isso, pois pode facilitar algumas operações de navegação.

Você também pode armazenar seu hexmap em uma matriz 2D, com deslocamentos por linha. No entanto, isso pode ser um pouco menos intuitivo do que armazenar uma matriz vizinha por célula, apenas devido ao deslocamento geométrico em todas as outras linhas.

Verifique se todas as células estão conectadas a tudo que é vizinho. Você pode fazer isso linha por linha, célula por célula, ao gerar o mapa hexadecimal completo. PS Se você quiser um mapa hexadecimal não retangularmente delimitado, poderá simplesmente remover células e referências individuais a essas células, para formar espaços negativos, permitindo criar um esboço de mapa orgânico.

Distribuição round-robin

Pseudo-código:

count number of neutral cells in entire map, minus those starting cells taken by players
while neutral cells remain (or while true)
   for each player
      if player has not yet reached expected territory size in cells
         for each cell already constituting this player's territory
           if territory can grow by one cell into a neutral neighbour
              grow into neighbour
              reduce neutral cell count for entire map by one
              if no more neutral cells remain in map
                 break out of outermost while loop immediately
              else
                 continue to next player immediately
begin game

Esse algoritmo dará a cada jogador a chance de aumentar seu território por um, de maneira round robin, desde que o território do jogador ainda tenha um espaço de cultivo válido. Se alguns jogadores são impedidos de crescer ainda mais, o algoritmo irá apesar deste continuar a crescer nos territórios de jogadores que não têm ainda espaço crescente válido. Você pode restringir facilmente todos os jogadores ao mesmo número de células assim que um deles atingir um limite, mas isso deve ser fácil o suficiente para você descobrir, se desejar.

Isso fornecerá "territórios domésticos" de tamanho máximo para cada jogador. Se você deseja ter territórios de "ilha", além disso, para cumprir a cota de contagem de células para esse jogador, depois que um jogador ficar sem espaço local para crescer, você poderá escolher uma nova célula de início na lista de células neutras e prossiga com o mesmo processo de "crescimento" a partir daí. Dessa forma, você acabará com conjuntos de ilhas coerentes e de bom tamanho para cada jogador, em vez de ruído aleatório.

Engenheiro
fonte
Embora você forneça excelente documentação e pseudocódigo para seu algoritmo, não tenho certeza se isso corresponde ao que o questionador pergunta. A pergunta menciona que "os maiores" blocos "não podem ter mais de quatro células cada", enquanto seu algoritmo cria o maior grupo conectado possível.
Fnord 17/10
@ fnord Não, não. Você não leu minha resposta corretamente. Eu coloquei explicitamente um limite no pseudocódigo: "se o jogador ainda não atingiu o tamanho esperado do território nas células". Por favor, remova o seu voto negativo. Sinta-se à vontade para verificar o histórico de revisões da pergunta para se certificar de que esse era o caso desde antes do seu comentário e voto negativo.
Engenheiro de
A pergunta pede para ter "não mais que quatro células adjacentes", mas para cada usuário ter uma parte esperada do mapa. Isso, para mim, implica que algo está mais parecido com a forma como os jogos de risco distribuem aleatoriamente o mapa para todos os jogadores. Sua resposta divide o mapa em "territórios domésticos de tamanho máximo". É verdade que seu algoritmo para quando o limite de tamanho de território esperado é atingido, mas não vejo uma maneira de o jogador obter novas "ilhas", embora você o mencione no texto posterior.
Fnord 17/10
@fnord Sua lógica está errada. Em sua sentença final, você admite que meu algoritmo para no tamanho de uma ilha ne, a partir de então, se contradiz dizendo que "ainda não vê um caminho" e que eu "mencione [como obter ilhas] em texto posterior". Respondi ou não respondi à pergunta? Esse algoritmo generalizado pode ser usado para espalhar células (limitando na 1) ou para criar ilhas (configurando n> 1). Então você tem, em um único algoritmo, não apenas a capacidade de dispersar, mas também agrupar. Como isso não responde à pergunta do OP? Como é digno de um voto negativo?
Engenheiro de
Gostaria de editar meu comentário acima, mas é tarde demais. "Não vejo uma maneira no seu algoritmo ". embora você mencione o conceito em texto posterior.
Fnord 17/10
0

Outra abordagem seria começar com uma distribuição 'justa', mas regular e, em seguida, usar uma abordagem semelhante ao Simulated Annealing para interromper a regularidade sem perder a imparcialidade:

  • Comece atribuindo cores a todas as células da grade em um padrão regular (por exemplo, tenha um padrão '123412341234' repetido na primeira linha, seguido de '341234123412' na próxima, etc.). Isso pode levar a uma distribuição não uniforme de cores, se o seu mapa estiver com uma forma particularmente ruim, mas presumo que você esteja começando com um mapa fixo, portanto, você poderá encontrar algumas cores regulares equidistribuídas.
  • Em seguida, repita o seguinte para o número de etapas que desejar (não há um critério real de 'doneness', para que a experiência lhe diga qual é o número mínimo razoável de etapas):
    • Escolha dois elementos da grade aleatoriamente
    • Se eles tiverem a mesma cor, tente novamente (não há sentido em contrário, pois a troca será um não-op. Você só tem 1/4 de chance de atingir a mesma cor e 1/16 de chance de atingir a mesma cor duas vezes seguidas, para que você nunca precise tentar demais)
    • Troque provisoriamente as cores desses dois elementos
    • Teste os tamanhos das regiões recém-formadas nos locais dos elementos após a troca:
      • faça um preenchimento simples a partir do novo local de cada elemento para determinar o tamanho de uma região dessa cor que a troca faria.
    • Se uma dessas duas regiões for maior que o seu limite, desfaça a troca provisória; caso contrário, 'finalize' a troca das cores dos dois elementos.

As chaves aqui são que o fato de você estar trocando dois pontos significa que você nunca desequilibra as cores e, da mesma forma, o teste que você faz antes de finalizar sua troca garante que você nunca crie regiões muito grandes. Se você tem algum meio de exibir sua grade, pode até visualizar esse processo para observar como ele 'constrói' suas regiões através de trocas repetidas.

Se você não pode começar com uma coloração regular com distribuição equidistante, aliás, ainda assim poderá fazer algo semelhante para distribuir a coloração: enquanto sua coloração não for distribuída com equidistribuição, escolha um elemento aleatoriamente; se for uma das cores super-representadas, defina provisoriamente sua cor para uma das cores sub-representadas e verifique se não cria uma região muito grande da nova cor.

Steven Stadnicki
fonte
Abordagens estocásticas são ineficientes. Para uma abordagem como a minha que executa etapas consideradas, o tempo de execução se aproxima de O (n) para n células de mapa. Para o seu algoritmo, é O (n * m), onde m é o número de células desejado por ilha (na verdade, para cada ilha em potencial). Sempre é melhor apontar para algoritmos que tenham um tempo de execução prontamente estimado. Em vez de consertar um mapa gerado aleatoriamente, é melhor gerar um mapa que não esteja quebrado ou aleatório, em n etapas, mantendo assim um processo controlado e eficiente.
Engenheiro