Gerador de labirintos de backtracker recursivo

O algoritmo backtracker recursivo é, na verdade, uma pesquisa em profundidade de propósito geral. Quando utilizado para a geração de labirintos, é ligeiramente modificado para escolher o caminho de forma aleatória, enquanto que se utilizado para fins de pesquisa reais, normalmente seria apenas necessário procurar cada nível por ordem linear. Tem tendência a produzir 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 backtracker recursivo é um método de busca em profundidade para gerar labirintos perfeitos (labirintos sem loops e um único caminho entre dois pontos quaisquer). É simples, eficiente e produz labirintos visualmente atraentes com corredores longos e sinuosos.

Apesar do nome, não tem necessariamente de ser implementado usando recursão. É geralmente implementado numa abordagem iterativa usando uma fila LIFO (ou seja, uma pilha). Para labirintos muito grandes, o uso de recursão tem maior probabilidade de resultar em overflow da 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 numa base de dados se a memória disponível for insuficiente.

Como funciona

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

1. Escolha uma célula inicial e marque-a como visitada.
2. Enquanto existirem células não visitadas:
   • Note 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.
     • Dirija-se ao vizinho escolhido e marque-o como visitado.
     • Empurre a célula atual para a pilha.
   • Se não existirem vizinhos não visitados:
     • Retroceda removendo a última célula da pilha.
3. Continue este processo até que a pilha esteja vazia.

Um facto interessante sobre este algoritmo é que funciona tanto como um gerador de labirintos como um solucionador de labirintos. Se o executar num labirinto já gerado e parar quando chegar ao ponto final definido, a pilha conterá a solução para o labirinto.

Na verdade, tenho duas versões deste algoritmo em uso neste site: uma baseada na fila LIFO para gerar labirintos nesta página e uma baseada na recursão para resolver labirintos, também labirintos gerados por outros algoritmos (é assim que se fazem os mapas com as soluções). Ter duas versões diferentes é só por desporto, porque eu sou um nerd que acha isto interessante, qualquer uma delas podia ter funcionado para ambas ;-)