Quais são os bons algoritmos para gerar bordas / áreas de estado em mapas em estrela 2D?

Estou tentando gerar um mapa estelar bidimensional bastante grande que mostra diferentes facções / estados, cada um possuindo um ou mais sistemas estelares. Eu gostaria de criar automaticamente bordas / áreas para as facções.

A idéia é basicamente partir de algo assim (os pontos representam sistemas estelares em um plano 2D, cores são afiliações de facções)

para isso

Gerar mapas como esse parece ser um requisito bastante comum, então minha pergunta real é a seguinte: Existem algoritmos padrão para gerar áreas de estado, como mostrado? Se sim, você poderia apontar para mim? Caso contrário, você pode pensar em um bom algoritmo (ideia básica ou pseudo-código estão corretos)?

O desempenho do algoritmo não é uma preocupação principal para mim, portanto, prefiro ter um mapa "mais bonito" do que um mais rápido para gerar. Essa pergunta semelhante oferece uma abordagem que provavelmente é aplicável ao meu problema, embora com algumas "prettificações" necessárias: Como criar um mapa a partir do gráfico

Deixe-me explicar o que quero dizer quando digo mais bonita: na parte inferior da pergunta vinculada, a pessoa que pergunta apresenta seu resultado final após implementar a resposta aceita. Minha primeira edição aqui: as áreas dos nós # 6, # 9 e # 12 são muito pequenas e de formato estranho. Além disso, em vez das bordas afiadas, eu preferiria uma aparência mais suave e curvada.

Minhas próprias idéias até agora, incluindo as respectivas desvantagens / perguntas que vejo com elas:

• Gere um polígono "casco convexo" para cada facção e depois expanda-o um pouco. Problemas: Sem recursos côncavos. Além disso, como você lida com sobreposições?
• Gere um gráfico de voronoi para os pontos e use as bordas do polígono de voronoi entre sistemas vizinhos de facções diferentes como bordas. Problema: polígonos grandes nas bordas do mapa - como identifico e corrijo esses?
• Gere um polígono de tamanho fixo para cada ponto, unindo todos os polígonos para uma única facção (resultando em um "polígono de facção" grande e potencialmente complexo). Em seguida, faça algo para reconciliar áreas sobrepostas entre duas facções. Problemas: Como eu faria exatamente isso? Não é exatamente um processo trivial. E se houver sobreposição entre mais de duas facções?

Sua ajuda é apreciada.

Adendo: Depois de pensar nas duas primeiras respostas e suas respectivas abordagens para resolver o problema, percebi que meus requisitos acima estão incompletos.

Devo acrescentar que o mapa pode ter áreas pouco povoadas, o que significa que pode haver uma estrela isolada ou um aglomerado de estrelas. Gostaria de exibir cada um desses clusters com sua própria área colorida contígua. Algo assim:

Percebo que isso pode exigir uma primeira etapa que identifique os clusters e, em seguida, execute o algoritmo real de cada um dos clusters.

Eu acho que a ideia de Voronoi é boa. Cada estrela se torna um ponto inicial para Voronoi e, em seguida, as regiões de Voronoi mostram as áreas pertencentes a cada facção. No entanto, existem algumas mudanças que o farão funcionar melhor:

1. Como você mencionou, existem áreas vazias que não devem ser atribuídas a uma facção. Voronoi criará polígonos grandes que se estendem para áreas onde a facção não deve alcançar. Para corrigir isso, use um algoritmo de ruído azul, como o disco de Poisson, para preencher o espaço desocupado com estrelas "pertencentes a ninguém". O ruído azul é aleatório, mas distribuído uniformemente (também pode ser útil para gerar a localização das suas estrelas).
2. Voronoi produz regiões em blocos. Para produzir células mais redondas, substitua o cálculo do circuncentro de Voronoi por um cálculo de centróide. Eu escrevi um pouco sobre isso aqui com algumas imagens de comparação.
3. Voronoi produz polígonos, mas você deseja áreas redondas. Em cada canto, há três polígonos. Quando todas as três são da mesma facção, você pode deixá-la em paz. Quando duas são da mesma facção, introduza uma curva quadrática de bezier que desloque o limite em direção à outra facção. Quando todas as três facções são diferentes, você pode deixar a esquina em paz ou pode introduzir três curvas de bezier para afastar todas as fronteiras uma da outra. Não tenho certeza do que parece melhor.

Aqui está a saída:

Também escrevi uma página que permite pintar as regiões para ver como elas seriam.

Um dos muitos métodos é um mapa de influência . Você pode procurar implementações de código específicas, mas o algoritmo básico é bastante simples.

Para cada objeto de facção (por exemplo, sistema estrela), atribua um valor positivo (quente). Para os objetos de todas as outras facções, atribua um valor negativo (frio). A magnitude do calor ou do frio deve basear-se em quanta influência você acha que o objeto exerce sobre seus arredores e vizinhos. Esses valores não precisam ser proporcionais se você quiser manter um "dmz" entre facções.

Use esses detalhes para criar uma grade temporária (por exemplo, matriz) que se aproxime dos pixels do seu mapa. Você pode criar uma grade com a resolução desejada, incluindo 1: 1.

Em seguida, use a equação de transferência de calor / campo para iterar e propagar as forças dos objetos da facção (calor) contra as forças dos objetos dos adversários (frio) para cada célula vizinha na grade.

Enxágüe e repita para cada facção em seu mapa, criando grades de facção separadas para cada uma.

Por fim, interpole as grades da facção para produzir um contorno de influência para cada facção. Em seguida, transfira essa grade de volta para o seu mapa de pixels, dada a resolução que você usou para a grade (adicionando cores específicas de facção etc.).

A arte deste processo é determinar quanta influência cada objeto deve ter e quais elementos do jogo você usa para quantificar esse valor.

Como um aparte, os produtos desse método podem ser usados ​​para todos os tipos de outras coisas, como a tomada de decisão do seu ai.

Referência adicional: tópico de discussão sobre origens do mapeamento de influência .

Você deve examinar os diagramas de Voronoi. Aqui está a definição na wikipedia:

Em matemática, um diagrama de Voronoi é uma partição de um plano em regiões com base na distância a pontos em um subconjunto específico do plano.

Os pontos básicos são geralmente gerados aleatoriamente e geralmente são chamados de nós. No seu caso, cada nó pode ser sua estrela. Dessa forma, a facção associada às estrelas pode ser associada à célula voronoi que circunda a estrela e, quando todas as células foram calculadas, você junta aquelas com a mesma facção e deve ter uma borda bem organizada em torno de suas estrelas.

A biblioteca FastNoise suporta os diagramas de Voronoi, então talvez você deva dar uma olhada.

• Diagramas de Voronoi na Wikipedia
• Biblioteca FastNoise no GitHub

Suavização das regiões

Mantenha suas estrelas em uma "matriz segura" e use uma cópia dela, na qual você adiciona mais pontos via interpolação dos vizinhos mais próximos e gera o diagrama a partir desses pontos. Deve dar-lhe regiões mais suaves.

Outras idéias O algoritmo da sorte é baseado em uma linha reta que varre o plano cartesiano. Uma idéia interessante seria usar um círculo para varrer o avião do centro de sua galáxia / espaço, talvez isso também possa levar a algumas formas interessantes.

Manipulação de geometria

Sua última idéia de combinar polígonos menores em outros maiores e depois fixar as arestas exigirá algoritmos avançados de spline para modificar as formas. Não tenho certeza se isso o tornaria eficiente ou bonito. Tenho certeza de que o diagrama de voronoi com mosaico extra é o caminho a seguir, pois corrige o problema de borda sozinho e pode até oferecer alguns dados extras por si só, como a distância das bordas (que pode ser usada para determinar as zonas de conflito entre as diferentes facções, a probabilidade de encontrar diferentes tipos de navios, etc.)