Reduza o número de arestas de um gráfico, mantendo-o conectado

10

Estou criando um jogo com masmorras geradas aleatoriamente. Gostaria de ver isso como um gráfico conectado e não direcionado, no qual os nós são salas e as bordas são portas ou corredores. Depois, escolho um nó "lateral" como entrada da masmorra, calculo a distância entre essa entrada e todos os outros nós e decido que um dos nós mais distantes é o "objetivo" da masmorra (a localização do tesouro, chefe, princesa, etc.).

Vi duas maneiras de gerar a topografia final da masmorra:

  • Gere primeiro um gráfico aleatório e tente preencher o mundo 2D com salas em locais aleatórios, respeitando as conexões de borda. Imaginei que isso às vezes seria difícil porque a geração de salas poderia ser "trancada" tentando caber em salas em lugares impossíveis.
  • Gere as primeiras salas, colocando-as aleatoriamente onde cabem, e mapeie o resultado para nós e arestas. Eu decidi tentar isso.

Minha ideia consiste em:

  • Primeiro gere uma grande sala que contenha toda a masmorra.
  • Coloque uma parede dentro da sala grande, em um local aleatório, dividindo a sala grande em 2 salas menores de área diferente.
  • Então, continuo dividindo cada quarto em 2, até que eles sejam muito pequenos, ou o número total de quartos atinja o máximo (ou qualquer outra condição). Cada nova sala é um nó.
  • Depois de terminar, verifico cada sala e encontro todas as outras salas adjacentes, marcando os 2 nós como conectados por uma borda.

Dessa forma, garanto que todas as salas tenham uma possível localização no mundo 2D e sejam mapeadas corretamente por um gráfico conectado.

Meu problema é que existem muitas portas e corredores conectando os quartos.

Então, eu gostaria de um algoritmo que reduz o número de arestas de um gráfico não direcionado conectado , mas mantendo-o conectado (todos os nós permanecem acessíveis) no final.

algorithm procedural-generation random topography graphs Splo
fonte
Sua ideia é basicamente uma árvore de pesquisa binária, se você quiser saber. Eu usei; faz masmorras bastante agradáveis ​​e é fácil. :)
O Pato Comunista
2
FYI: Um gráfico completo possui arestas entre todos os pares de vértices, portanto (supondo que arestas duplicadas não sejam permitidas), você não pode remover nenhuma aresta e ainda possui um gráfico completo. O termo certo é um gráfico conectado .
Michael Madsen
Árvore de pesquisa binária, gráfico conectado, à direita. Eu sou tão ruim com o nome convencional das coisas.
Splo

Respostas:

13

Use o algoritmo Prim para obter a árvore de abrangência mínima para o seu gráfico (adicione pesos aleatórios ou pesos mais altos perto da entrada ou faça um algoritmo de sua escolha) e adicione novamente algumas portas / bordas aleatoriamente. Dessa forma, você terá todos os quartos conectados e alguns caminhos redundantes extras.

r2d2rigo
fonte
1
Ah, claro, a árvore de abrangência mínima, é claro! Boa ideia, obrigado.
Splo
1

Você também pode tentar o algoritmo de Kruskal

Gastón
fonte
0

Alguns dos geradores de masmorra nesta lista da Inkwell Ideas são de código aberto ou fornecem documentação sobre seus algoritmos. O Google também fornecerá muitas pesquisas por 'gerador de masmorra [nome da linguagem de programação]'. Infelizmente, meu favorito não é encontrado por nenhum desses métodos, apesar de ser o mais bem documentado que já encontrei, e não consigo me lembrar do nome, pois perdi-o recentemente devido a uma falha no disco rígido. Vou atualizar esta resposta depois de executar a recuperação nessa unidade.

Sparr
fonte