Tendo uma lista de salas com a conexão entre si, como encontro grupos de salas isoladas?

9

Estou tentando criar um pequeno roguelike e foi tão longe quanto gerar aleatoriamente salas e corredores. Cada sala é um objeto instanciado e contém uma lista de matrizes das outras salas conectadas por um corredor.

Posso destacar salas não conectadas, mas como posso conhecer as salas que estão conectadas apenas umas às outras, mas não à maioria das outras, formando uma ilha?

Para ilustrar melhor o problema, aqui está uma imagem do console em um nível atolado. Os quartos 5 e 6 são conectados apenas um ao outro. Que algoritmo posso usar para detectar isso?

insira a descrição da imagem aqui

petervaz
fonte
Problema com o uso da imagem? Esse link pastebin durará apenas um mês.
MichaelHouse
Sim, eu não entendi direito o que você fez aqui. Desculpe, reverti sua alteração.
petervaz
11
Por que você não o constrói para que não possa haver salas separadas? Ou você quer que haja conjuntos isolados?
AlbeyAmakiir
@AlbeyAmakiir, como eu disse em outro comentário abaixo, eu gero as salas separadamente por tentativa e erro até preencher o mapa, só então eu corro uma rotina para conectar e depois corro outra para conectar essas ilhas. Eu sei que é provavelmente muito complicado, mas não consegui descobrir outra maneira.
31412 petervaz

Respostas:

14

Comece com uma lista completa de quartos. Escolha uma sala inicial. Navegue dessa sala para todas as salas conectadas. Para cada quarto que você visita, removê-lo da lista de quartos e adicionar a uma lista A . Uma vez que você visitou todas as suas conexões, quartos restantes na lista não estão conectados à sala inicial ou qualquer um dos quartos na lista A .

Você pode continuar selecionando uma sala do que resta da lista completa e navegando novamente. Desta vez, acrescentando à lista B . Continue esse processo até não ter mais quartos na lista original. Agora você tem listas de todos os conjuntos de salas conectados.

Problemas como esse são facilmente adaptados aos problemas da teoria dos grafos. Por exemplo, o problema que você descreveu acima está diretamente relacionado à conectividade .

MichaelHouse
fonte
11
qualquer algoritmo da árvore de pesquisa deve funcionar. Isso ou você pode alterar o algoritmo de geração para evitar esse problema. Se você alterar o algoritmo de geração, basta gerar um número aleatório de salas anexadas à sua sala inicial, depois um número aleatório de salas anexadas a cada uma das seguintes opções, em seguida, você pode adicionar algumas conexões aleatórias entre salas existentes para apimentar um pouco as coisas com atalhos e tal. Pessoalmente, eu faria apenas um algoritmo de árvore de pesquisa.
Benjamin Danger Johnson
Isso é muito lógico. Eu devo estar cansado. Obrigado pela ajuda. Aceitará assim que permitir.
31412 petervaz
@BenjaminDangerJohnson Seu comentário parece mais apropriado para a pergunta e não para esta resposta.
MichaelHouse
@petervaz Sem problemas. Eu acho que meu diploma de CS tem seus usos, afinal.
MichaelHouse
@BenjaminDangerJohnson meu algoritmo de geração é apenas colocar salas aleatórias até preencher o espaço e procurar conexões mais tarde. = P Tentará corrigir as conexões antes de mudar a criação.
31412 petervaz
9

Sua coleção de salas é essencialmente um gráfico e seu problema se resume em encontrar os componentes conectados ("ilhas") nesse gráfico.

Uma maneira simples de encontrar componentes conectados é fazer o BFS (pesquisa pela primeira vez) de cada vértice. Fazer BFS a partir de um vértice A obterá todos os vértices no componente conectado ao qual o vértice A pertence.

Então, basicamente, você começa com um vértice arbitrário, executa um BFS e marca cada vértice encontrado como membro da 1ª "ilha". Em seguida, você passa para o próximo vértice não marcado e faz um BFS novamente, desta vez, identificando vértices como membros da 2ª "ilha" e assim por diante.


fonte
4

Você pode imaginar as salas como vértices em um gráfico direcionado . Ao fazer isso, você poderá aplicar algoritmos conhecidos para resolver seu problema.

O algoritmo de Dijkstra , por exemplo, produz uma árvore de caminho mais curto para um dado vértice inicial em um gráfico. Esta árvore conterá todos os vértices alcançáveis ​​desde o ponto inicial. Você pode deduzir que os vértices que não estão presentes na árvore fazem parte de outras ilhas. Você pode aplicar o algoritmo a esses vértices para obter árvores que representam todas as ilhas.

Asakeron
fonte
11
Mesmo um gráfico não direcionado faria isso ... exceto que você tem rotas unidirecionais.
Aron_dc 19/10/12
@Aron_dc, você está certo, pode visualizar as salas como vértices em um gráfico não direcionado e obter resultados semelhantes usando o algoritmo de Kruskal. Eu apenas sugeri imaginá-lo como gráficos direcionados por causa da maneira como petervaz representava as conexões - ou seja, Sala 1> 3
Asakeron