Esses dias eu estava numa fila chata, com o celular quase sem bateria, e fiz a coisa mais analógica que existe: peguei o caderninho que ando sempre comigo e comecei a rabiscar um labirinto à mão. Sabe, daqueles de revistinha de passatempo. E aí veio a frustração de sempre: ou eu deixava um beco sem saída no meio do nada, ou — pior — desenhava sem querer um caminho tão óbvio que dava pra resolver o labirinto antes de terminar de desenhar. Fiquei encarando aquilo e pensei: "como é que um computador faz isso certinho, toda vez, sem trapacear?"
Cheguei em casa e não consegui largar a ideia. Fui atrás, reescrevi o algoritmo do zero, e o resultado tá logo aqui embaixo — você vai ver o computador derrubando as paredes uma a uma, ao vivo. Mas antes deixa eu te contar o pulo do gato, porque é mais simples (e mais bonito) do que parece.
O que é um labirinto "perfeito"
Em teoria de labirintos existe um termo específico pra aquilo que eu tentava (e falhava em) desenhar à mão: o labirinto perfeito. A definição é elegante: entre quaisquer dois pontos do labirinto existe exatamente um caminho. Nem zero (nada de áreas isoladas, inacessíveis), nem dois ou mais (nada de atalhos ou loops). Um, e só um.
Isso tem uma consequência linda: um labirinto perfeito não tem ciclos e não tem becos isolados. Se você é de exatas, já sentiu o cheiro — isso é literalmente uma árvore. Cada célula é um nó, e as passagens são as arestas que ligam os nós sem nunca fechar um loop. O problema "desenhar um labirinto perfeito" é, no fundo, o problema "gerar uma árvore que cobre todas as células". Os matemáticos chamam isso de spanning tree, uma árvore geradora.
Quando eu desenhava à mão, eu errava justamente aqui: sem perceber, eu fechava um loop (criando dois caminhos pro mesmo lugar) ou deixava uma região solta. O computador não "tem mais cuidado" — ele só segue uma regra que torna impossível errar.
A ideia: comece com tudo bloqueado e vá cavando
O jeito mais intuitivo de gerar um labirinto perfeito é começar pelo avesso do que a gente imagina. Em vez de desenhar caminhos, você começa com uma grade onde todas as paredes existem — cada célula é uma cela fechada, cercada por paredes em todos os lados. Nada se conecta a nada.
Aí você "cava". O algoritmo mais charmoso pra isso é o backtracking recursivo (uma busca em profundidade, ou DFS). Funciona assim:
- Escolha uma célula pra começar e marque como visitada.
- Olhe os vizinhos dela que ainda não foram visitados.
- Se existe pelo menos um, sorteie um deles, derrube a parede entre as duas células, mova-se pra lá e empilhe a célula anterior.
- Se não existe nenhum vizinho não-visitado (você está num beco), volte (faça backtrack) desempilhando até achar uma célula que ainda tenha caminho novo a explorar.
- Repita até a pilha esvaziar. Quando ela esvazia, todas as células foram visitadas — e o labirinto está pronto.
O segredo que garante a perfeição é uma única regra: você só derruba a parede em direção a uma célula ainda não visitada. Como cada célula é visitada uma única vez, você nunca cria um segundo caminho pra ela. Sem segundo caminho, sem loop. Sem loop, árvore. Árvore = labirinto perfeito. É quase impossível de errar — e foi exatamente isso que faltou no meu caderno.
É contraintuitivo, mas funciona: para garantir um caminho entre dois pontos quaisquer, você nunca pensa nos dois pontos. Você só segue a regra local "não revisite ninguém" — e a propriedade global aparece de graça.
Por que "recursivo", mas com pilha?
A versão de livro é recursiva: a função chama a si mesma pra cada célula nova. Bonito no papel, mas em labirintos grandes a pilha de chamadas do navegador estoura (Maximum call stack size exceeded — já tomei essa na cara). A solução que usei aqui é trocar a recursão do JavaScript por uma pilha explícita (um array). É o mesmo algoritmo, a mesma ordem de visitação, só que eu controlo a pilha na mão — e de quebra fica fácil animar: a cada quadro eu dou um passinho e desenho onde estão a célula atual e a pilha.
Duas curiosidades que eu achei demais
- O "viés" do algoritmo tem cara. O backtracking recursivo produz labirintos com corredores longos e sinuosos e poucas bifurcações — um visual bem característico. Outros métodos têm outras "assinaturas": o algoritmo de Prim faz labirintos cheios de becos curtos; o de Wilson gera labirintos perfeitamente "imparciais", sem viés nenhum. Dá pra reconhecer qual algoritmo gerou um labirinto só de olhar a textura dele. Achei isso lindo.
- Resolver é mais fácil que gerar. Como o labirinto perfeito é uma árvore, achar o caminho da entrada à saída é trivial: não existe escolha errada que custe caro, porque não há loops pra te prender andando em círculos. Uma simples busca acha o único caminho. Coloquei um botão "resolver" no brinquedo pra você ver — ele acende exatamente a única rota.
Minha opinião honesta
Esse é, de longe, um dos meus algoritmos favoritos pra mostrar pra quem está começando — e olha que não tem nada de matemática pesada. Ele captura uma ideia que eu uso o tempo todo no trabalho de verdade: regras locais simples geram estruturas globais corretas. Você não precisa orquestrar o resultado inteiro de cima; você define bem o passo pequeno e a garantia emerge. É o mesmo princípio por trás de coisas como geração procedural de fases em jogos, layout automático de circuitos e até roteamento de redes.
E tem o lado humano: eu falhava à mão não por falta de inteligência, mas por falta de uma regra que me impedisse de trapacear sem querer. Boa parte de programar bem é exatamente isso — desenhar restrições que tornam o erro impossível, em vez de torcer pra não errar.
Chega de conversa, gera aí 👇
Abaixo está o gerador que escrevi: JavaScript puro, num <canvas>, sem nenhuma biblioteca. Mexe nos sliders de tamanho e de velocidade, aperta "gerar de novo" quantas vezes quiser, e — se quiser ver o algoritmo trabalhando — deixe no modo animado pra acompanhar a célula atual (em destaque) e a pilha (o rastro) derrubando parede por parede. Quando terminar, clica em "resolver" pra ver o caminho único acender.