Gerador de labirintos de backtracker recursivo

O algoritmo do backtracker recursivo é realmente uma busca em profundidade de propósito geral. Quando usado para geração de labirintos, ele é ligeiramente modificado para escolher o caminho aleatoriamente, enquanto que se usado para propósitos de busca reais, normalmente alguém apenas buscaria cada nível em ordem linear. Ele tende a produzir labirintos com corredores longos e sinuosos e uma solução muito longa e sinuosa.

Um labirinto perfeito é um labirinto em que há exatamente um caminho de qualquer ponto do labirinto para qualquer outro ponto. Isso significa que você não pode acabar andando em círculos, mas frequentemente encontrará becos sem saída, forçando-o a dar meia-volta e retornar.

Os mapas de labirinto gerados aqui incluem uma versão padrão sem posições de início e fim, para que você possa decidir por si mesmo: haverá uma solução de qualquer ponto do labirinto para qualquer outro ponto. Se quiser se inspirar, você pode ativar uma sugestão de posição inicial e final e até mesmo ver a solução entre as duas.

O algoritmo backtracker recursivo é um método de busca em profundidade para gerar labirintos perfeitos (labirintos sem loops e um único caminho entre quaisquer dois pontos). É simples, eficiente e produz labirintos visualmente atraentes com corredores longos e sinuosos.

Apesar do nome, não precisa necessariamente ser implementado usando recursão. Geralmente é implementado em uma abordagem iterativa usando uma fila LIFO (ou seja, uma pilha). Para labirintos muito grandes, usar recursão tem mais probabilidade de resultar em estouro de pilha de chamadas, dependendo da linguagem de programação e da memória disponível. Uma fila LIFO pode ser mais facilmente adaptada para lidar com grandes quantidades de dados, mesmo mantendo a fila em disco ou em um banco de dados se a memória disponível for insuficiente.

Como funciona

O algoritmo opera usando uma abordagem de busca em profundidade baseada em pilha. Aqui está o detalhamento passo a passo:

1. Escolha uma célula inicial e marque-a como visitada.
2. Enquanto houver células não visitadas:
   • Observe as células vizinhas que ainda não foram visitadas.
   • Se existir pelo menos um vizinho não visitado:
     • Escolha aleatoriamente um dos vizinhos não visitados.
     • Remova a parede entre a célula atual e o vizinho escolhido.
     • Vá até o vizinho escolhido e marque-o como visitado.
     • Empurre a célula atual para a pilha.
   • Se não houver vizinhos não visitados:
     • Retroceda removendo a última célula da pilha.
3. Continue esse processo até que a pilha esteja vazia.

Um fato interessante sobre esse algoritmo é que ele funciona tanto como um gerador de labirintos quanto como um solucionador de labirintos. Se você executá-lo em um labirinto já gerado e apenas parar quando atingir o ponto final decidido, a pilha conterá a solução para o labirinto.

Na verdade, tenho duas versões desse algoritmo em jogo neste site: uma baseada em fila LIFO para gerar labirintos nesta página e uma baseada em recursão para resolver labirintos, também labirintos gerados por outros algoritmos (é assim que os mapas com as soluções são feitos). Ter duas versões diferentes é só por esporte, porque sou um nerd que acha isso interessante, qualquer uma poderia ter funcionado para ambos ;-)