Labirintos perfeitos numa grade 40×28: percurso recursivo, Wilson, Eller ou Prim aleatório; resolve-se com A* (Manhattan, 4-vizinhança). Dá para desenhar paredes e mover o início e a meta.
Sobre o modelo
Os geradores de labirinto constroem um labirinto perfeito — árvore geradora na grade de salas: um só caminho entre células, enquanto o campo não é editado. Constrói-se na mesma grade 40×28 que engineering/astar-dijkstra-grid. As «salas» são as células de índices ímpares (1,1)…; as passagens abrem tanto as salas quanto a parede entre salas vizinhas, então o labirinto fica conexo e sem ciclos até que se comece a editar. Estão o percurso recursivo (pilha DFS), Wilson (passeios ao acaso com apagamento de laços), Eller (fusão de conjuntos por linhas com verticais ao acaso) e Prim aleatório (a árvore cresce a partir de uma frente de arestas). Depois de gerar, lança-se **A* com heurística de Manhattan e 4-vizinhança** — o mesmo modelo discreto do laboratório de A*, sem diagonais nem células «caras». Dá para acrescentar paredes, apagar passagens e mover S/G; ao movê-los, as pontas são forçadas a ser transitáveis.
Para quem: Matemática discreta e computação: geradores de labirinto e caminho mais curto numa grade, ao lado de A*/Dijkstra.
Conceitos-chave
labirinto perfeito
árvore geradora
percurso recursivo
algoritmo de Wilson
algoritmo de Eller
Prim aleatório
busca A*
heurística de Manhattan
Como funciona
Labirinto perfeito em 40×28: salas na grade ímpar, as passagens abrem as paredes entre elas — uma árvore sem ciclos. Percurso recursivo / Wilson / Eller / Prim dão árvores aleatórias diferentes; depois o mesmo A* de aula (4-vizinhança, Manhattan) busca o caminho mais curto sobre as paredes já feitas.
Perguntas frequentes
Por que os labirintos de Wilson e de Eller «parecem» diferentes?
Os dois constroem árvores geradoras aleatórias na mesma grade, mas outra aleatoriedade local (a raiz de Wilson, as decisões horizontais de Eller) dá um desenho distinto em tamanho finito.
É o mesmo A* da página A* / Dijkstra?
Os mesmos quatro rumos, a heurística de Manhattan e o custo unitário do passo por células livres. Aqui não há diagonais, células com peso nem modos Dijkstra ou guloso: só o A* de aula.
Dá para quebrar a «perfeição» do labirinto?
Sim: a borracha cria um ciclo (um segundo caminho entre regiões); paredes a mais podem romper a conexidade. A* mostrará a topologia nova; se não houver caminho até G, sem caminho.