O que é um bom algoritmo para gerar um labirinto?

https://stackoverflow.com/questions/38502

09-06-2019
|

Pergunta

Digamos que você queira um labirinto simples em um N por M grelha, com um caminho do meio, e um bom número de becos sem saída, mas que parece "certo" (i.é.como alguém feito à mão, sem muitos pequenos impasses e todas outras).Há uma maneira conhecida para fazer isso?

Solução

A partir de http://www.astrolog.org/labyrnth/algrithm.htm

Recursiva backtracker:Este é um pouco relacionado com o recursiva backtracker método de solução descrita abaixo, e requer pilha até o tamanho do Labirinto.Quando a escultura, ser tão ganancioso quanto possível, e sempre esculpir em uma desfeita seção se, junto à célula atual.Cada vez que você move para uma nova célula, pressione o ex-célula na pilha.Se não há desfeita células avançar para a posição atual, pop pilha para a posição anterior.O Labirinto é feito quando você pop tudo na pilha.Este algoritmo resulta em Labirintos com cerca de uma alta "rio" fator como possível, com menos, mas mais becos sem saída, e, geralmente, um longo e sinuoso solução.Ele funciona muito rápido, apesar de Prim algoritmo é um pouco mais rápido.Recursiva retrocesso não funciona como uma parede adder, porque isso tende a resultar em uma solução caminho que segue a borda externa, onde todo o interior do Labirinto, que é ligado ao limite de um único tronco.

Eles produzem apenas 10% becos sem saída

é um exemplo de um labirinto gerados por esse método.

Outras dicas

Acontece que há 12 algoritmos clássicos para gerar "perfeito" labirintos.Um labirinto é perfeito se ele tiver uma, e apenas uma, solução.Aqui estão alguns links para cada algoritmo, em ordem aproximada de minha preferência.

Para mais informações, confira mazelib no GitHub, uma biblioteca em Python implementação de todo o padrão labirinto de geração/algoritmos de solução de problemas.

Um bem simples solução pode ser aleatória atribuir pesos para as arestas do grafo e aplicar De Kruskal algoritmo para encontrar uma árvore geradora mínima.

Melhor discussão já no labirinto de geração de algoritmos: http://www.jamisbuck.org/presentations/rubyconf2011/index.html (foi no HN um par de dias atrás).

Estranhamente, mudando ligeiramente o 'canônico' regras e a partir de uma configuração aleatória, Conway Jogo da Vida parece gerar muito bom labirintos!

(Não me lembro o exato regra, mas é muito simples modificação que tende a "densificar" a população de células...)

Minha maneira favorita é a utilização de Kruskal algoritmo, mas quando a escolha aleatória de borda e de remover, peso a escolha com base nos tipos de bordas é conectado para.

Variando-se os pesos para diferentes tipos de borda, você pode gerar labirintos com lotes de características distintas, ou "personalidades".Veja o meu exemplo aqui:

https://mtimmerm.github.io/webStuff/maze.html

Um dos métodos para gerar um labirinto é o randomizados versão de Prim algoritmo.

Começa com uma grade completa de paredes.Escolha uma célula, marque-a como parte do labirinto.Adicione as paredes da célula para a parede lista.Enquanto não há paredes na lista:

Escolha aleatória de parede a partir da lista.Se a célula do lado oposto, não no labirinto ainda:

(i) Fazer a parede de uma passagem e marcar a célula no lado oposto, como parte do labirinto.

(ii) Adicionar vizinhos paredes da célula para a parede lista.

Se a célula no lado oposto, já foi em labirinto, de remover a parede da lista.

Para mais compreensão clique aqui

Aqui está o DFS algoritmo escrito como pseudocódigo:

criar um CellStack (LIFO) para manter uma lista de localizações de célula
conjunto TotalCells = número de células na grade
escolher um celular no aleatório e chamá-lo CurrentCell
conjunto VisitedCells = 1

enquanto VisitedCells < TotalCells encontrar todos os vizinhos de CurrentCell com todas as paredes intactas
se um ou mais encontrado escolher um aleatoriamente
derrubar o muro entre ele e CurrentCell
empurre CurrentCell localização no CellStack
fazer a nova célula CurrentCell
adicione 1 para VisitedCells mais pop a mais recente entrada de célula fora da CellStack
torná-lo CurrentCell endIf endWhile

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow