Resolucion de laberintos por flood fill para robots micromouse

El flood fill es el algoritmo que gana la mayoria de las competiciones de micromouse, y es una gran introduccion a la planificacion bajo incertidumbre. A diferencia de la busqueda de caminos de manual, un robot de laberinto no empieza con el mapa completo: tiene que descubrir las paredes mientras conduce. El flood fill esta hecho exactamente para eso. Miralo funcionar en el simulador de resolucion de laberintos.

Un campo de distancias, no una ruta

El flood fill asigna a cada celda un numero: su distancia a la meta. Las celdas objetivo reciben cero. A partir de ahi, cada celda vecina que no este bloqueada recibe uno mas que su vecino mas bajo, propagandose hacia fuera hasta que todas las celdas alcanzables tengan un valor.

El robot nunca guarda una ruta. Simplemente se situa en una celda, mira a sus vecinos y avanza a cualquiera que tenga un numero exactamente una unidad menor. El campo de distancias es el plan, y por eso se recupera con elegancia cuando el mapa cambia.

Optimismo sobre las paredes desconocidas

El robot no puede ver el laberinto entero, asi que el flood fill trata toda pared que aun no ha sensado como abierta. Ese optimismo produce la estimacion mas corta posible y mantiene al robot avanzando hacia la meta en lugar de explorar sin rumbo.

Cuando un sensor revela una pared que se suponia abierta, el robot la registra (en ambos lados del borde compartido) y recalcula el campo de distancias. El plan se corrige solo, y el robot continua desde donde este.

Por que la primera pasada no es el camino mas corto

Una sorpresa habitual: el flood fill no garantiza la ruta mas corta en la primera pasada. Como actuo con suposiciones optimistas, encontro una forma de llegar a la meta, no necesariamente la mejor. Los robots micromouse reales usan dos fases:

1. Una pasada de busqueda que explora lo suficiente del laberinto para construir un mapa exacto.
2. Una pasada de velocidad por el camino mas corto que revela el mapa ya completo.

Al principio, una exploracion eficiente importa mas que la optimalidad de la primera pasada.

Flood fill frente a BFS y A*

La busqueda en anchura y A* planifican sobre un grafo que ya conoces. El flood fill esta disenado para un laberinto que todavia estas descubriendo: vuelve a inundar cada vez que aparece una pared nueva. Matematicamente el flood es un calculo de distancias en anchura; la diferencia es que el flood fill espera que el mapa siga cambiando y es barato de recalcular.

Tambien supera al simple seguimiento de paredes (mantener siempre una mano sobre una pared), que no puede alcanzar una meta en el centro del laberinto y rara vez encuentra una ruta corta.

El bucle de sensado, planificacion y movimiento

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

Manten el sensado, el mapeo, la planificacion y el movimiento como pasos separados. Esa frontera es lo que permite que el mismo planificador se ejecute en un simulador de navegador, en tu escritorio y en un ESP32 con sensores de distancia y codificadores reales.

El flood, completo

El campo de distancias es una expansion en anchura desde la meta, y es lo bastante corto para escribirlo entero:

const uint8_t N = 16;                       // laberinto de 16 x 16
uint8_t dist[N][N];                         // distancia a la meta, por celda
uint8_t walls[N][N];                        // mascara de bits: 1=N, 2=E, 4=S, 8=O

// Un buffer circular sencillo supera a un std::queue en un microcontrolador.
uint8_t queueR[N * N], queueC[N * N];

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

  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, O
  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;             // hay una pared en medio

      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 significa no visitada
        dist[nr][nc] = dist[r][c] + 1;
        queueR[tail] = nr; queueC[tail] = nc; tail++;
      }
    }
  }
}

Ese es el algoritmo entero. En un laberinto de 16x16 visita como maximo 256 celdas y se ejecuta en bastante menos de un milisegundo en un Arduino, y por eso volver a inundar ante cada pared recien descubierta es perfectamente asumible, y por eso nadie se molesta con actualizaciones incrementales.

Registrar una pared en ambos lados

El fallo mas comun del flood fill no esta en el flood. Una pared es compartida por dos celdas, y registrarla en un solo lado produce un mapa en el que el robot puede atravesarla en una direccion y no en la otra:

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));   // la misma pared, desde el otro lado
}

El (dir + 2) % 4 es la direccion opuesta: norte se convierte en sur y este en oeste. El sintoma de equivocarse aqui es un robot que planifica una ruta directamente a traves de una pared que el mismo registro, algo genuinamente desconcertante de ver.

Memoria, en un Arduino

Un laberinto de 16x16 en los 2 KB de SRAM de un Uno es apretado pero viable, y merece la pena hacer las cuentas antes de descubrirlo por las malas:

La cola es la parte cara y la mas facil de reducir: un unico array de bytes empaquetados r<<4|c la reduce a la mitad, 256 B. Si aun vas justo, empaquetar el mapa de paredes a 2 bits por celda recupera otros 192 B. La mayoria de la gente recurre en este punto a un ESP32 o un Mega, y es una decision razonable, pero el ejercicio de hacerlo caber es instructivo en si mismo.

Elegir las celdas objetivo

Una meta estandar de micromouse es un bloque de 2x2 en el centro, no una sola celda, y eso no es un detalle. Sembrar las cuatro celdas con distancia 0 hace que el robot se dirija a la cara del bloque que pueda alcanzar mas barato, lo que es a la vez mas rapido y mas robusto que comprometerse con una celda concreta a la que quizas tenga que aproximarse desde una direccion incomoda.

El codigo de arriba ya lo maneja: pasa las cuatro celdas en goals y el flood arranca desde todas ellas a la vez. Esta es una ventaja real del enfoque de campo de distancias: varias metas no cuestan nada, mientras que A* necesitaria una heuristica modificada.

Explorar correctamente

El flood fill le dice al robot adonde ir dado lo que sabe. No dice nada sobre lo que deberia aprender, y un robot que solo desciende el gradiente alcanzara la meta sin haber visto la mayor parte del laberinto, lo que hace que el “camino mas corto” de la pasada de velocidad sea el mas corto solo entre los pasillos que resulto recorrer.

El compromiso habitual en competicion es la segunda o la tercera fila: alcanza la meta, luego inunda de vuelta hacia el inicio y recorre ese camino, lo que revela de forma natural un conjunto distinto de pasillos. Dos travesias suelen producir un mapa lo bastante bueno como para que la pasada de velocidad quede a unos pocos puntos porcentuales de lo optimo.

Solucion de problemas

Esa quinta fila es la importante, y merece decirse con claridad: el algoritmo no es la parte dificil de un micromouse. El flood fill son cuarenta lineas y puedes verificarlo por completo en el simulador sin hardware. La parte dificil es que tras diez celdas el robot ya no esta donde cree estar, y un plan perfecto ejecutado desde una posicion ficticia acaba contra una pared.

Pruebalo tu mismo

Avanza paso a paso por el simulador de resolucion de laberintos celda a celda y observa como se recalcula el campo de distancias cada vez que el robot descubre una pared. Ver cambiar los numeros es la forma mas rapida de entender por que el robot siempre tiene un plan.