Qual é um bom método para gerar arestas aleatoriamente entre nós do gráfico?

Estou fazendo um gerador de mapas aleatórios para um jogo espacial de 4X.

Cada nó no jogo é colocado em uma coordenada aleatória (x, y) em uma grade 2D. Um nó pode ter uma ou mais arestas bidirecionais para outro nó (representando buracos de minhoca). Todos os nós devem ter pelo menos um buraco de minhoca e todos os nós devem pertencer ao mesmo gráfico.

Idealmente, um buraco de minhoca não deve exceder o comprimento máximo e, se possível, os buracos de minhoca não devem se cruzar.

Minha implementação ingênua é iterar por todos os nós e fazer com que o nó se vincule aos 3 nós mais próximos. No entanto, acabo com vários subgráficos. Qual é um bom método para gerar as arestas para os nós?

Aqui está uma boa resposta para uma pergunta semelhante.

Primeiro faça um gráfico conectado, talvez usando uma árvore de abrangência mínima, como no link acima. Ele sugere o uso de pesos aleatórios na borda para tornar a árvore "mínima" aleatória. Em seguida, você pode adicionar aleatoriamente mais arestas para que não seja apenas a árvore mínima. Como exatamente você adiciona as arestas aleatórias depende do tipo de gráfico que você deseja.

De fato, se o problema é apenas garantir que todos os nós pertençam ao mesmo gráfico, você pode usar seu método atual de geração aleatória (ou qualquer outro) e aplicar o algoritmo de Prim sobre ele. Se você quiser fazer alterações mínimas no gráfico apenas para garantir que todos os subgráficos estejam conectados, defina o custo da borda como 0 para as que já estão lá.

As principais restrições do seu problema são duas: criar um gráfico conectado 1; e criá-lo com conexões proximais. A resposta de Philip, embora valiosa, não trata de todas as restrições do seu problema

Idealmente, um buraco de minhoca não deve exceder o comprimento máximo e, se possível, os buracos de minhoca não devem se cruzar.

Quando você ingenuamente conecta pontos em uma nuvem, corre o risco (e alto) de que essas condições não sejam cumpridas.

Como vê, o problema não é tanto a conectividade, mas a proximidade nessas conexões. É trivial conectar todos os nós de um gráfico a todos os outros nós, mas conectar-se apenas àqueles mais próximos, mantendo a conexão 1 do gráfico geral, é um pouco mais complicado.

É isso que uma triangulação de Delaunay cria, em n dimensões. A primeira razão para usar a triangulação de Delaunay é que ela cumpre ambas implicitamente. A segunda razão é que é muito mais fácil trabalhar para trás a partir de um gráfico desse tipo (subtraindo arestas e vértices que você não deseja), do que tentar criá-lo de outras maneiras.

1. Crie aleatoriamente sua nuvem de pontos completa.
2. Delaunay-triangular.
3. Construa o gráfico (conexão de pontos). Neste, você pode gerar o gráfico inteiro (cada estrela) primeiro e, em seguida, derivar o gráfico como menores representando suas regiões conectadas por buracos de minhoca, ao executar a etapa 4. Como alternativa, você pode trabalhar ao contrário, gerando apenas as regiões conectadas por buracos de minhoca primeiro como nós do supergrafo e, em seguida, em uma segunda fase, gerar estrelas individuais dentro dos volumes delimitadores dessas regiões (para essas derivaria o gráfico da triangulação de Delaunay dual - o diagrama de Voronoi em 3 dimensões) como subgráficos. Agora você tem aglomerados de estrelas conectados proximalmente e todos os aglomerados são conectados por buracos de minhoca mais raros: sua topologia e topografia fazem sentido para o jogador.
4. Aplique métodos inteligentes para modelar os super e subgráficos, dependendo de como você escolheu tratá-lo na etapa 3.

É importante ver que esse é um processo hierárquico. O primeiro nível lida com a conectividade do buraco de minhoca; o segundo lida com distâncias presumivelmente percorríveis usando uma unidade de navio padrão. Você pode aplicar o Delaunay em um ou nos dois níveis para satisfazer suas restrições.

Fazer isso puramente topologicamente deixará você com buracos de minhoca que não fazem sentido, pois eles podem conectar um lado da galáxia a outro, apesar de uma alta densidade de estrelas entre elas (e talvez até cair na rota direta do buraco de minhoca). Topologia não é topografia; o último é uma consideração além do anterior. Você está preocupado com a proximidade e, portanto, com a topografia.