Preenchimento por inundação para labirintos Micromouse

O preenchimento por inundação é o algoritmo que vence a maioria das competições de Micromouse e é uma ótima introdução ao planejamento sob incerteza. Ao contrário da busca de caminhos de livros didáticos, um robô de labirinto não começa com o mapa completo — precisa descobrir paredes enquanto se desloca. O algoritmo foi projetado exatamente para isso. Veja-o funcionando no simulador solucionador de labirintos.

Um campo de distância, não um caminho

O preenchimento por inundação atribui um número a cada célula: sua distância até o objetivo. As células objetivo recebem zero. A partir daí, cada célula adjacente que não esteja bloqueada recebe um número uma unidade maior que o menor valor já atribuído a uma de suas vizinhas, e o cálculo se espalha até que toda célula alcançável tenha um valor.

O robô nunca armazena uma rota. Ele fica em uma célula, observa as células vizinhas e avança para qualquer uma cujo número seja exatamente um menor. O campo de distância é o plano, e é por isso que ele se recupera de forma natural quando o mapa muda.

Otimismo em relação às paredes desconhecidas

O robô não consegue ver o labirinto inteiro, portanto o preenchimento por inundação trata como aberta toda parede que ainda não percebeu. Esse otimismo produz a menor estimativa possível e mantém o robô avançando em direção ao objetivo em vez de explorar sem propósito.

Quando um sensor revela uma parede que havia sido considerada aberta, o robô a registra — dos dois lados da borda compartilhada — e recalcula o campo de distância. O plano se corrige, e o robô continua de onde está.

Por que a primeira execução não é o caminho mais curto

Uma surpresa comum: o preenchimento por inundação não garante a rota mais curta na primeira execução. Como agiu com base em suposições otimistas, encontrou um caminho até o objetivo, não necessariamente o melhor. Robôs Micromouse reais usam duas fases:

1. Uma fase de busca que explora o suficiente do labirinto para construir um mapa preciso.
2. Uma fase de corrida pelo caminho mais curto que o mapa completo revela.

No início, uma exploração eficiente importa mais que a garantia de optimalidade da primeira execução.

Preenchimento por inundação em comparação com BFS e A*

A busca em largura (BFS) e A* planificam sobre um grafo já conhecido. O preenchimento por inundação foi projetado para um labirinto que ainda está sendo descoberto: ele refaz o cálculo sempre que uma nova parede aparece. Matematicamente, ele é um cálculo de distância por busca em largura — a diferença é que o algoritmo espera que o mapa continue mudando e é barato recalculá-lo.

Ele também supera o seguimento de paredes simples (manter sempre uma mão em uma parede), que não alcança um objetivo no centro do labirinto e raramente encontra uma rota curta.

O ciclo de percepção, planejamento e movimento

void planOneCell(Maze& map, Robot& robot) {
  map.observe(robot.cell(), robot.senseLeftFrontRight());
  map.floodFill(centerGoals);
  Cell next = map.bestDescendingNeighbor(robot.cell());
  robot.turnAndMoveTo(next);
}

Mantenha percepção, mapeamento, planejamento e movimento como etapas separadas. Essa fronteira é o que permite que o mesmo planejador seja executado em um simulador no navegador, em seu computador e em um ESP32 com sensores de distância e encoders reais.

O algoritmo completo

O campo de distância é uma expansão em largura a partir do objetivo, e é curto o suficiente para ser escrito inteiramente:

const uint8_t N = 16;                       // 16 x 16 maze
uint8_t dist[N][N];                         // distance to goal, per cell
uint8_t walls[N][N];                        // bitmask: 1=N, 2=E, 4=S, 8=W

// A simple ring buffer beats a std::queue on a microcontroller.
uint8_t queueR[N * N], queueC[N * N];

void floodFill(const uint8_t goals[][2], uint8_t goalCount) {
  memset(dist, 255, sizeof(dist));          // 255 = unreachable

  uint16_t head = 0, tail = 0;
  for (uint8_t g = 0; g < goalCount; g++) {
    const uint8_t r = goals[g][0], c = goals[g][1];
    dist[r][c] = 0;
    queueR[tail] = r; queueC[tail] = c; tail++;
  }

  const int8_t dr[4] = {-1, 0, 1, 0};       // N, E, S, W
  const int8_t dc[4] = { 0, 1, 0, -1};

  while (head < tail) {
    const uint8_t r = queueR[head], c = queueC[head];
    head++;

    for (uint8_t d = 0; d < 4; d++) {
      if (walls[r][c] & (1 << d)) continue;             // wall in the way

      const int8_t nr = r + dr[d], nc = c + dc[d];
      if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;

      if (dist[nr][nc] > dist[r][c] + 1) {              // 255 means unvisited
        dist[nr][nc] = dist[r][c] + 1;
        queueR[tail] = nr; queueC[tail] = nc; tail++;
      }
    }
  }
}

Esse é todo o algoritmo. Em um labirinto 16×16, ele visita no máximo 256 células e é executado em bem menos de um milissegundo em um Arduino — por isso refazer o preenchimento por inundação a cada parede recém-descoberta é plenamente viável, e por isso ninguém se preocupa com atualizações incrementais. Durante o cálculo, 255 também representa uma célula ainda não visitada, e a fila garante que cada célula elegível entre nela apenas uma vez.

Registrar uma parede nos dois lados

O erro mais comum do preenchimento por inundação não está no próprio cálculo. Uma parede é compartilhada por duas células, e registrá-la apenas de um lado produz um mapa no qual o robô pode atravessá-la em uma direção, mas não na outra:

void setWall(uint8_t r, uint8_t c, uint8_t dir) {
  walls[r][c] |= (1 << dir);

  const int8_t dr[4] = {-1, 0, 1, 0};
  const int8_t dc[4] = { 0, 1, 0, -1};
  const int8_t nr = r + dr[dir], nc = c + dc[dir];
  if (nr < 0 || nr >= N || nc < 0 || nc >= N) return;

  walls[nr][nc] |= (1 << ((dir + 2) % 4));   // the same wall, from the other side
}

O (dir + 2) % 4 representa a direção oposta — norte se torna sul, leste se torna oeste. O sintoma de errar isso é um robô que planeja uma rota atravessando diretamente uma parede que ele próprio registrou, o que é realmente confuso de observar.

Memória em um Arduino

Um labirinto 16×16 nos 2 KB de SRAM de um Uno é apertado, mas viável, e vale fazer a conta antes de descobrir isso da pior maneira:

A fila é a estrutura mais cara e a mais fácil de reduzir: um único array de bytes com r<<4|c compactados reduz sua metade para 256 B. Se o uso de memória ainda for apertado, compactar o mapa de paredes em 2 bits por célula recupera mais 192 B. A essa altura, a maioria escolhe um ESP32 ou um Mega, uma decisão razoável — mas o exercício de fazer tudo caber também é instrutivo.

Escolher as células objetivo

Um objetivo Micromouse padrão é um bloco 2×2 no centro, não uma única célula, e isso não é um detalhe. Inicializar as quatro células com distância 0 significa que o robô segue para a face do bloco que consegue alcançar com mais facilidade — o que é mais rápido e robusto do que se comprometer com uma célula específica que talvez precise ser abordada de uma direção desconfortável.

O código acima já trata disso: passe as quatro células em goals, e o preenchimento por inundação começa simultaneamente a partir de todas elas. Essa é uma vantagem real da abordagem por campo de distância — múltiplos objetivos não custam nada, enquanto A* precisaria de uma heurística modificada.

Explorar de forma adequada

O preenchimento por inundação informa ao robô para onde ir dado o que ele sabe. Não diz nada sobre o que ele deveria aprender, e um robô que apenas desce o gradiente chegará ao objetivo sem ter visto a maior parte do labirinto — o que torna o “caminho mais curto” da corrida rápida curto apenas entre os corredores por onde ele passou.

O compromisso usual nas competições é a segunda ou a terceira linha: alcance o objetivo e depois faça o retrocesso por preenchimento por inundação em direção ao início e percorra esse caminho, o que revela naturalmente um conjunto diferente de corredores. Duas travessias normalmente produzem um mapa suficientemente bom para que a corrida rápida fique a poucos pontos percentuais do ideal.

Solução de problemas

Essa quinta linha é a importante, e vale dizer claramente: o algoritmo não é a parte difícil de um Micromouse. O preenchimento por inundação tem quarenta linhas e você pode verificá-lo completamente no simulador sem equipamento físico. A parte difícil é que, depois de dez células, o robô não está mais onde acredita estar, e um plano perfeito executado a partir de uma posição fictícia faz o robô bater em uma parede.

Experimente

Avance uma célula de cada vez no simulador solucionador de labirintos e observe o campo de distância ser recalculado sempre que o robô descobrir uma parede. Ver os números mudarem é a maneira mais rápida de entender por que o robô sempre tem um plano.