Gerador de labirintos de backtracker recursivo

O algoritmo recursive backtracker é, na verdade, uma pesquisa em profundidade de propósito geral. Quando usado para geração de labirintos, é ligeiramente modificado para escolher o caminho ao acaso, enquanto que, se usado para fins de pesquisa real, normalmente procura-se cada nível por ordem linear. Tende a criar labirintos com corredores longos e sinuosos e uma solução muito longa e sinuosa.

Um labirinto perfeito é um labirinto em que existe exatamente um caminho de qualquer ponto do labirinto para qualquer outro ponto. Isto significa que não pode acabar por andar em círculos, mas encontrará frequentemente becos sem saída, obrigando-o a dar meia volta e regressar.

Os mapas de labirinto gerados aqui incluem uma versão predefinida sem posições de início e fim, para que possas decidir por ti próprio: haverá uma solução de qualquer ponto do labirinto para qualquer outro ponto. Se quiseres inspiração, podes ativar uma posição de início e de fim sugerida - e até ver a solução entre as duas.

O algoritmo recursivo backtracker é um método de pesquisa 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 apelativos com corredores longos e sinuosos.

Apesar do nome, não tem necessariamente de ter sido implementado usando recursão. É frequentemente implementado numa abordagem iterativa usando uma fila LIFO (ou seja, uma pilha). Para labirintos muito grandes, usar recursão é mais provável que resulte em excesso de chamadas de pilha, 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, mantendo mesmo a fila em disco ou numa base de dados se a memória disponível for insuficiente.

Como Funciona

O algoritmo opera usando uma abordagem de pesquisa em profundidade baseada em pilha. Aqui está a explicação passo a passo:

1. Escolhe uma célula inicial e marca-a como visitada.
2. Embora existam celas não visitadas: Observe as celas vizinhas que ainda não foram visitadas. Se existir pelo menos um vizinho não visitado: Escolha aleatoriamente um dos vizinhos não visitados. Remove a parede entre a célula atual e o vizinho escolhido. Muda-te para o vizinho escolhido e marca-o como visitado. Empurra a célula de corrente para a pilha. Se não existirem vizinhos não visitados: Recuar removendo a última célula da pilha.
3. Continue este processo até a pilha ficar vazia.

Um facto interessante sobre este algoritmo é que funciona tanto como gerador de labirintos como como solucionador de labirintos. Se o executares num labirinto já gerado e parares assim que chegares ao ponto final decidido, a pilha vai conter a solução do labirinto.

Na verdade, tenho duas versões deste algoritmo em jogo neste site: uma baseada numa fila LIFO para gerar labirintos nesta página e outra 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ó para desporto porque sou um nerd que acha interessante, qualquer uma poderia ter funcionado para ambas ;-)

Leitura adicional

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

• Gerador de labirintos de caça e matança
• Gerador de labirintos do algoritmo de Wilson
• Gerador de labirintos do algoritmo de Kruskal