geração de mapa espacial

Question

Estou no início da criação de um espaço 4x e antes de tudo preciso gerar uma galáxia de estrelas unidas por linhas conectantes que mudam a cada novo jogo, vou adicionar algumas fotos para mostrar o que quero

Então, como posso ter um mapa 2D simples com pontos conectados como essas imagens? Pensei em programar cada linha com um comprimento aleatório e um ângulo aleatório ou programar polígonos por polígonos, mas ainda não está claro.

Answer 1

Você pode espalhar pontos usando ...

• coordenadas aleatórias uniformes (sujeito a clusters desiguais e lacunas)

• ou uma grade abalada ou instável, onde você começa com uma rede regular de pontos e, em seguida, adiciona um pequeno deslocamento aleatório a cada um (evita grandes lacunas / clusters, mas pode revelar sua estrutura)

• ou uma distribuição de Poisson ( alguns algoritmos inteligentes para gerar isso podem ser encontrados aqui )

Red Blob Games tem uma página que permite que você jogue com diferentes distribuições de grade jittered e Poisson para ter uma ideia das compensações nesses algoritmos.

Se você achar que seu resultado é muito irregular, você pode formar o diagrama de Voronoi de seus pontos - gerando o polígono convexo que está mais próximo de cada ponto do que qualquer outro - e mover cada um de seus pontos em direção ao centroide de seu polígono. Isso tende a diminuir um pouco o espaçamento, enquanto mantém as coisas orgânicas.

Se você achar que seu resultado é muito uniforme, pode excluir aleatoriamente alguns pontos para introduzir lacunas ou inserir aleatoriamente alguns com critérios de espaçamento mais fracos para criar clusters.

Você também pode variar o espaçamento de sua grade ou amostras de Poisson com base em um mapa de densidade subjacente que você gera primeiro usando ruído.

Agora, para as conexões:

Para garantir que todas as estrelas estejam conectadas à rede, de modo que você não possa ter uma ilha inacessível do resto da galáxia, você pode usar um algoritmo de árvore estendida.

Uma árvore geradora mínima fornecerá o esqueleto de uma constelação que toca todas as estrelas, usando os links mais curtos que puder. Então elaboramos nessa base, sem violar a garantia de conexão.

• Se você usar o algoritmo de Prim (que adiciona links um por um), você pode adicionar alguns links extras depois que o algoritmo terminar para criar ciclos e caminhos alternativos.

• Se você usar o algoritmo de Kruskal (que começa com um gráfico denso e remove links um por um), você pode interromper o algoritmo antes que seja eliminado mais de x% dos links redundantes ou dar a ele uma probabilidade de manter links redundantes como ele vai.