Qual algoritmo você usou no passado para gerar um simples labirinto 2D?
algorithm
procedural-generation
jdeseno
fonte
fonte
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:
E a partir desses, obtemos:
fonte
A Wikipedia tem um ótimo recurso na geração de labirintos . Eu usei o algoritmo prims randomizado com ótimos resultados. O algoritmo de divisão parece interessante, mas eu nunca o usei.
Aqui está um exemplo da wikipedia de prim no trabalho.
fonte
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
Eu também daria uma olhada em alguns dos algoritmos usados no desenvolvimento do Roguelike. Há um bom recurso inicial na Rogue Basin
fonte
Há uma boa execução aqui: https://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/
As etapas básicas foram:
Código aqui: https://github.com/munificent/hauberk/blob/db360d9efa714efb6d937c31953ef849c7394a39/lib/src/content/dungeon.dart
fonte
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.
fonte