Gerador de labirintos de backtracker recursivo

O algoritmo de backtracking recursivo é, na verdade, 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 buscas propriamente ditas, normalmente se busca em cada nível em ordem linear. Ele tende a produzir labirintos com corredores longos e sinuosos e uma solução muito longa e complexa.

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.

Algoritmo de backtracking recursivo é um método de busca em profundidade para gerar labirintos perfeitos (labirintos sem laços e com 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. Muitas vezes, é implementado de forma iterativa usando uma fila LIFO (ou seja, uma pilha). Para labirintos muito grandes, o uso de recursão tem maior probabilidade de resultar em estouro de pilha, dependendo da linguagem de programação e da memória disponível. Uma fila LIFO pode ser adaptada mais facilmente para lidar com grandes quantidades de dados, podendo inclusive ser armazenada em disco ou em um banco de dados caso a memória disponível seja insuficiente.

Como funciona

O algoritmo opera usando uma abordagem de busca em profundidade baseada em pilha. Aqui está a descrição 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 houver pelo menos uma célula vizinha não visitada: Escolha aleatoriamente uma das células vizinhas não visitadas. Remova a parede entre a célula atual e a célula vizinha escolhida. Mova-se para a célula vizinha escolhida e marque-a como visitada. Empurre a célula atual para a pilha. Se não houver células vizinhas não visitadas: 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 simplesmente parar ao atingir o ponto final predefinido, a pilha conterá a solução do labirinto.

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

Leitura adicional

Se você gostou deste post, você também pode gostar destas sugestões:

• Gerador de labirinto de algoritmo de Eller
• Gerador de labirintos do algoritmo de Wilson
• Algoritmo de Árvore Crescente Gerador de Labirinto