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?
fonte
Respostas:
Isto é o que eu faria:
fonte
Supondo que você tenha um mapa hexadecimal de
n
células ep
jogadores, ondep <= 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:
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:
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.
fonte
n
e, 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 (limitandon
a 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?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:
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.
fonte