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?
Respostas:
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 .
fonte
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
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.
fonte