Como eu geraria um mapa em estrela?

8

Estou tentando gerar um mapa em estrela.

Minha tentativa seria:

  1. Tenha uma largura e altura para o mapa.
  2. Coloque os pontos (estrelas) aleatoriamente na área de largura e altura.

Uma abordagem simples, mas tem o problema de colocar aleatoriamente estrelas extremamente próximas umas das outras.

Para resolver esse problema, uma abordagem seria ter uma distância mínima e, ao gerar uma estrela, você compara a distância da nova estrela a cada estrela gerada e, se estiver abaixo da distância mínima, você gera uma nova, mas não sei se isso é eficiente. Alguma dica?

zebleckDAMM
fonte
3
Pode haver maneiras mais eficientes de fazer isso, mas por que não funciona para você? Você tem problemas com esta implementação? Você está otimizando prematuramente?
Vaillancourt
Qual é o objetivo do mapa estelar? É um plano de fundo ou mais como um campo de jogo?
Erik
@AlexandreVaillancourt Sim, eu ainda não sei quantas estrelas quero gerar e parece que é uma maneira muito ineficiente.
precisa saber é o seguinte
@Erik não um fundo, as estrelas você pode interagir com
zebleckDAMM
E ... você fará isso em tempo de execução ou offline?
Vaillancourt

Respostas:

13

Uma distribuição de amostragem Poisson-Disk permitirá que você selecione pontos aleatórios a uma distância mínima; o algoritmo de Bridson pode resolver com eficiência o problema em O (n) - rápido o suficiente para tempo real, desde que sua contagem de estrelas não seja muito grande.

O algoritmo de Bridson divide a região de saída em uma grade de células dimensionadas em relação à distância mínima permitida, de modo que apenas um ponto possa aparecer em cada célula. Então, ao considerar adicionar um novo ponto, você só precisa verificar uma coleção em forma de disco de células vizinhas, em oposição a toda a lista de pontos. Por exemplo, considere a seguinte imagem:

insira a descrição da imagem aqui

Ao verificar se o ponto azul candidato está muito próximo dos pontos existentes, não é necessário verificar em todos os pontos existentes. Em vez disso, você pode restringir a pesquisa aos pontos nas células vizinhas (que você pode encontrar rapidamente usando uma tabela de pesquisa). Mike Bostock tem uma bela animação mostrando o algoritmo em andamento.

A implementação padrão refere-se apenas a uma distância mínima fixa entre pontos. O artigo de amostragem Poisson Disk de Herman Tulleken (inclui código fonte) cobre uma adaptação para variar a distância mínima em diferentes partes da imagem; basicamente como um algoritmo de pontilhamento . O uso de ruído perlin / ruído simplex, como mostrado nas nuvens de artigos, pode fornecer um mapa estelar com aparência mais natural. Por exemplo, usei a imagem à esquerda para gerar a direita:

insira a descrição da imagem aqui insira a descrição da imagem aqui

Para fazer isso, ao considerar um ponto candidato, primeiro verifico o valor da imagem de entrada, que gera um valor de 0 a 1. Em seguida, escalono isso para a distância mínima e máxima desejada entre os pontos; neste caso, selecionei 5 e 20 pixels. Portanto, ao colocar um ponto nas regiões escuras, minhas estrelas podem ter até 5 pixels uma da outra e ao colocar estrelas nas regiões claras, elas podem ter até 20 pixels de distância.

Vale ressaltar que a velocidade de Bridson não funciona exatamente com a amostragem de distância variável, porque os pontos de saída não estão usando uma distância mínima uniforme. No entanto, você ainda pode usar uma grade de saída para reduzir a pesquisa. Quanto menor a grade, mais rápida é a busca pelos vizinhos mais próximos à custa de maior memória para uma tabela de pesquisa maior.

Pikalek
fonte
2
Os links são muito legais. No entanto, eles podem se perder com o tempo. Pode ser ainda melhor incluir mais detalhes aqui.
precisa saber é o seguinte
Adicionado um pouco mais de explicação e ilustração para se proteger contra isso.
Pikalek
1

Uma solução muito ingênua, mas simples, seria simplesmente sempre pular a distância "mínima" e, em seguida, acrescentar uma quantia aleatória. Isso significa que as estrelas nunca terão amigos demais, e você terá pelo menos um pouco de desvio.

por exemplo

for (int x = 0; x < MAX_WIDTH; x+= MIN_SEPERATION_X)
{
  x += generateRandom();

  for (int y = 0; y < MAX_HEIGHT; y+= MIN_SEPERATION_Y)
  {
    y += generateRandom();

    if (x < MAX_WIDTH && y < MAX_HEIGHT)
    {
      image[x + y * width] = STAR;
    }
  }
}

(Inserir sua função favorita de geração de números aleatórios)

Huxellberger
fonte
Mas e se você acertar outra estrela lá? (Também suas estrelas deve estar em uma banda inclinada se fazer assim.)
Trilarion
11
É possível acertar outra estrela? Estou assumindo apenas uma iteração sobre toda a imagem. Os dois números sempre mudando por uma separação mínima não param isso? Eu ouço fusões estelares são muito complicadas, então eu concordo que é bom garantir que elas não aconteçam. Causar uma supernova seria um erro muito imprudente.
Huxellberger
Eu quis dizer que o min_separation não é garantido (não pode ser com esse algoritmo) porque você sempre adiciona números aleatórios. Pelo menos, verifique se os números aleatórios não podem ser maiores que min_separation. A distância mínima garantida é então min_separation - max (generate_Random). Mas não é uma abordagem muito ruim. +1
Trilarion
Essa abordagem tenderá a produzir colunas de estrelas em linhas verticais organizadas, pois você não varia a coordenada x à medida que y muda. É improvável que pareça aleatório ou natural para coleções densas.
DMGregory
0

Se você souber o tamanho XYZ do seu espaço de jogo, poderá escolher um local aleatório nesse espaço

e faça um SphereCast para verificar se já existe algo muito próximo.

//pseudo code

SpawnStar(){
 Vector3 spot = new vector3(random(0,world size),random(0,world size,random(0,world size)

  while(true){
  SphereCast(spot, radius)
   if(hit something){
      spot = get new random spot
    }else{
     SpawnStar();
     brake;
    }
  } 
}

O problema é que provavelmente não será muito bom em tempo real, no entanto, para pré-gerado, é bom e muito rápido.

Josh Kirkpatrick
fonte
11
Qualquer que seja o SphereCast, essa não é exatamente a solução mencionada na pergunta e considerada ineficiente?
precisa saber é o seguinte
11
Eu acho que você quer dizer OverlapSphere. O SphereCast dispara uma esfera ao longo de uma linha, para ter uma pegada de detecção em forma de cápsula.
DMGregory