O que é um bom algoritmo para gerar um labirinto?

Digamos que você queira um labirinto simples em uma grade N por M, com um caminho, e um bom número de becos sem saída, mas que parece “certo” (ou seja, como alguém fez com a mão sem muitos pequenos becos sem saída e tudo isso ). Existe uma maneira conhecida de fazer isso?

    De http://www.astrolog.org/labyrnth/algrithm.htm

    Backtracker recursivo: Isso é um pouco relacionado ao método de solução de recursiva backtracker descrito abaixo e requer o empilhamento até o tamanho do Maze. Ao esculpir, seja o mais ganancioso possível e sempre esculpido em uma seção desfeita se estiver ao lado da célula atual. Cada vez que você move para uma nova célula, empurre a antiga célula na pilha. Se não houver células desfeitas perto da posição atual, coloque a pilha na posição anterior. O labirinto é feito quando você tira tudo da pilha. Esse algoritmo resulta em Mazes com um fator “rio” tão alto quanto possível, com menos deadends, mas mais longos, e geralmente uma solução muito longa e sinuosa. Ele corre muito rápido, embora o algoritmo de Prim seja um pouco mais rápido. Backtracking recursivo não funciona como um sumdor de parede, porque isso tende a resultar em um caminho de solução que segue a borda externa, onde todo o interior do labirinto é anexado ao limite por um único tronco.

    Eles produzem apenas 10% de becos sem saída

    http://sofpt.miximages.com/maze/recursiv.gif

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

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

    1. De Kruskal
    2. De Prim
    3. Backtracker Recursivo
    4. Aldous-Broder
    5. Árvore em crescimento
    6. Caça-e-mate
    7. Wilson’s
    8. Eller
    9. Autômato Celular (Fácil)
    10. Divisão Recursiva (Muito Fácil)
    11. Sidewinder (previsível)
    12. Árvore Binária (Inoperante)

    Para mais informações, confira mazelib no GitHub, uma biblioteca Python que implementa todos os algoritmos padrão de geração / resolução de labirintos.

    Uma solução bastante simples poderia ser atribuir pesos randoms às arestas do gráfico e aplicar o algoritmo de Kruskal para encontrar uma tree de abrangência mínima.

    Melhor discussão sobre algoritmos de geração de labirintos: http://www.jamisbuck.org/presentations/rubyconf2011/index.html (estava na HN há alguns dias).

    Estranhamente, mudando ligeiramente as regras ‘canônicas’ e partindo de uma configuração aleatória, o Game of Life de Conway parece gerar labirintos muito bons!

    (Não me lembro da regra exata, mas é uma modificação muito simples que tende a “densificar” a população de células …)

    Minha maneira favorita é usar o algoritmo de Kruskal, mas ao escolher aleatoriamente e remover a borda, pondere a escolha com base nos tipos de arestas às quais ela está conectada.

    Ao variar os pesos para diferentes tipos de arestas, você pode gerar labirintos com muitas características distintas ou “personalidades”. Veja meu exemplo aqui:

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

    Um dos methods para gerar um labirinto é a versão aleatória do algoritmo de Prim.

    Comece com uma grade cheia de paredes. Escolha uma célula, marque-a como parte do labirinto. Adicione as paredes da célula à lista de parede. Enquanto houver paredes na lista:

    Escolha uma parede aleatória na lista. Se a célula do lado oposto ainda não estiver no labirinto:

    (i) Faça da parede uma passagem e marque a célula no lado oposto como parte do labirinto.

    (ii) Adicione as paredes vizinhas da célula à lista de parede.

    Se a célula do lado oposto já estava no labirinto, remova a parede da lista.

    Para mais compreensão clique aqui

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

    criar um CellStack (LIFO) para manter uma lista de localizações de células
    set TotalCells = número de células na grade
    escolha uma célula aleatoriamente e chame-a de CurrentCell
    definir VisitadosCélulas = 1

    enquanto o VisitatedCells se um ou mais encontrados escolher um aleatoriamente
    derrubar a parede entre ele e o CurrentCell
    Empurre o local do CurrentCell no CellStack
    faça a nova célula CurrentCell
    adicione 1 a VisitedCells, caso contrário, insira a input de célula mais recente no CellStack
    torná-lo CurrentCell endIf endWhile