Algoritmo para gerar um labirinto 2D [fechado]

Respostas:

21

Existem várias maneiras de criar labirintos. Há uma lista enorme deles e suas descrições aqui: http://www.astrolog.org/labyrnth/algrithm.htm

Eu acho que usei o descrito em "Perfeito".

Tetrad
fonte
Um recurso muito bom, exatamente o que eu estava procurando.
jdeseno
Adoro esse site, usado há muitos anos.
Zanlok
8

Prefiro os labirintos que o Algoritmo de Kruskal cria.

A descrição padrão do algoritmo de Kruskal é inadequada, pois falha em distinguir localizações no gráfico de grupos de localizações, enquanto se baseia em um trocadilho com a escolha da estrutura de dados, levando a ambiguidades de descrição que confundem os novatos. Por isso, rejeito a termonologia de Kruskal.

Vou usar os seguintes termos:

  • Gráfico
    • o próprio labirinto.
    • um local no labirinto. Em um labirinto quadrado, esta é uma célula quadrada.
  • Beira
    • a conexão entre dois nós. Em um labirinto quadrado, esta é uma barra de um comprimento.
  • Grupo de árvores
    • um conjunto de nós, que podem estar vazios, organizados como uma árvore

E a partir desses, obtemos:

  1. Crie um grupo GTG , para o Graph Tree Group , contendo grupos de árvores
  2. Preencher GTG com um grupo de árvores contendo um nó, para cada local no seu labirinto
  3. Criar um conjunto de arestas E
  4. Preencher E com todas as bordas válidas no seu labirinto
  5. Enquanto houver mais de um grupo no GTG e enquanto E não estiver vazio:
  6. Escolha uma borda aleatória rE de E
  7. Identifique os pontos de extremidade p1 e p2 de rE
  8. Remover rE de E
  9. Verifique a quais grupos p1 e p2 pertencem ( p1g e p2g respectivamente).
  10. Se p1g e p2g forem diferentes, junte-se ao grupo de árvores p1g e p2g em p1 -> p2 e reescreva toda a propriedade do grupo de uma árvore na outra, juntando assim as árvores.
  11. Volte para a etapa 5.
  12. Se você não tiver mais arestas, mas houver mais de uma árvore, o gráfico não está conectado ou há um erro.
  13. Se você tem apenas uma árvore, você tem um labirinto completo sem loop.
John Haugeland
fonte
11
Tínhamos um projeto de GUI e tivemos que construir um labirinto 2D aleatório na GUI. Foi exatamente assim que eu fiz e nunca percebi que estava usando o Kruskals. Eu definitivamente percebi que tinha usado um gráfico.
Bryan Harrington
1

Uma maneira fácil é fazer uma lista das muralhas norte e oeste e depois permutá-las. Dê um número a cada quarto. Depois, exploda uma das paredes da lista, desde que as duas salas não tenham o mesmo número, depois propague um dos números para todas as outras salas com o mesmo número. Continue indo até você ficar sem paredes. Isso funciona para labirintos retangulares ou, na verdade, qualquer outro labirinto onde você pode dar uma lista de "salas potencialmente conectadas". Além disso, é bastante simples de programar.


fonte
1

Eu também daria uma olhada em alguns dos algoritmos usados ​​no desenvolvimento do Roguelike. Há um bom recurso inicial na Rogue Basin

Casey
fonte
0

Você perguntou qual eu usei, por isso vou me certificar de responder. Eu usei o algoritmo do Backtracker recursivo no meu jogo de labirinto nos jogos Rootbeer .

Isso é prova de que eu usei o algoritmo, por favor, não o veja como um anúncio do meu trabalho.

BenMaddox
fonte