Simulador de solucionador de labirintos com flood fill

Controles

Escolha um modo — Explorar e depois percorrer rapidamente ou Percorrer rapidamente apenas — e pressione Iniciar para vê-lo resolver, ou execute um movimento por vez com Passo. Novo labirinto cria um labirinto aleatório novo; Reiniciar repete o mesmo. Três velocidades, atalhos de teclado e Tela cheia mantêm a execução controlável. As linhas grossas são as paredes do labirinto, os corredores sombreados são todos os lugares que o robô explorou (incluindo becos sem saída) e a linha grossa é o caminho mais curto que o flood fill encontrou.

Teoria

Um labirinto em grade é formado por células unidas por arestas abertas, com paredes entre as demais. Para encontrar a rota mais curta, o robô precisa primeiro conhecer o labirinto — portanto este laboratório executa duas fases.

Explorar. O robô percorre o labirinto em profundidade com a regra da mão esquerda: em cada interseção, vira à esquerda se puder; caso contrário, segue em frente e depois vira à direita. Quando encontra um beco sem saída, retorna até a última interseção e pega o próximo ramo. Repetir isso até visitar todas as células mapeia o labirinto inteiro — incluindo todos os caminhos errados que ele precisou descartar.

Otimizar. Com o mapa completo, o flood fill atribui distância zero ao objetivo e propaga valores crescentes para fora por cada aresta aberta. Agora cada célula contém sua distância até o objetivo, portanto o caminho mais curto é simplesmente este: a partir do início, avance sempre para uma célula vizinha com número um menor. O robô percorre rapidamente esse caminho — muito mais curto que a exploração com desvios.

Algoritmo

1. Explore o labirinto em profundidade com a regra da mão esquerda, retornando de cada beco sem saída até todas as células serem visitadas.
2. Registre cada aresta aberta dos dois lados para que o mapa concluído conheça todas as paredes.
3. Faça flood fill a partir do objetivo: rotule-o como 0 e propague distâncias crescentes para fora por cada aresta aberta.
4. Leia o caminho mais curto no campo: a partir do início, avance repetidamente para uma célula vizinha cuja distância seja uma unidade menor.
5. Percorra rapidamente esse caminho até o objetivo.
6. Compare o comprimento da exploração com o comprimento do caminho mais curto para ver quanto o mapa economizou ao evitar desvios.

Código-fonte

Mantenha exploração, mapeamento, planejamento e movimento como funções separadas:

// Phase 1 — map the whole maze, backtracking out of dead ends
exploreDepthFirst(map, robot);        // left-hand rule until every cell is visited

// Phase 2 — flood-fill the finished map and run the shortest path
map.floodFill(goal);                  // goal = 0, distances ripple outward
for (Cell c = start; c != goal; c = map.lowerNeighbor(c))
  robot.driveTo(c);                   // always step one distance lower

Essa fronteira permite testar o mesmo planejador neste laboratório de navegador, em um computador e no controlador final baseado no ESP32.

Premissas e diferenças do hardware

O laboratório torna o mapeamento limpo removendo a parte difícil de um Micromouse real: a odometria. O robô simulado se move exatamente uma célula por passo, sem derrapagem nas rodas, sem viés do giroscópio e sem erro de curva de 90°, e seus três sensores de distância relatam paredes perfeitamente, sem falsos positivos. Uma construção física com ESP32 acumula erros de orientação e distância a cada movimento, precisa se realinhar às paredes e precisa filtrar as leituras de ToF para compensar a luz do sol e a queda de tensão — por isso o tutorial de curvas precisas e o guia de flood fill gastam mais tempo com movimento do que com planejamento. Use este simulador para aprender por que o flood fill replaneja, não para provar sua camada de movimento.

Diagrama do circuito

Use um regulador externo dimensionado para a corrente de travamento do motor. O ESP32 e os sensores precisam de um trilho lógico estável, mesmo quando os motores invertem o sentido de rotação.