Simulador de robot de laberintos con flood-fill

Controles

Selecciona un modo (Explorar y carrera rápida o Solo carrera rápida) y pulsa Iniciar para ver la resolución, o usa el botón Paso para avanzar celda a celda. Nuevo laberinto genera una configuración procedural aleatoria; Restablecer repite el escenario actual. Tres velocidades de ejecución, atajos de teclado y vista en pantalla completa facilitan el análisis. Las líneas gruesas delimitan las paredes, las zonas sombreadas señalan los pasillos explorados (incluyendo fondos de saco) y el trazo destacado exhibe la ruta mínima hallada por flood-fill.

Teoría

Un laberinto en cuadrícula está formado por celdas interconectadas por pasos abiertos, separadas por paredes en las aristas restantes. Para hallar el camino más corto, el robot debe mapear primero el entorno en dos fases secuenciales:

Exploración. El robot recorre la cuadrícula en profundidad guiándose por la regla de la mano izquierda: en cada encrucijada gira a la izquierda si el paso está abierto, de lo contrario avanza de frente, y si no, hacia la derecha. Ante un callejón cerrado, retrocede hasta la bifurcación anterior y explora la rama restante. La iteración exhaustiva permite registrar todos los muros del laberinto.

Optimización. Con el mapa consolidado, el algoritmo flood-fill asigna distancia cero a la meta y propaga valores numéricos crecientes a través de cada arista transitable. Cada celda almacena así su distancia métrica a la meta; la ruta más corta consiste simplemente en desplazarse en cada celda hacia un vecino con valor numérico inferior.

Algoritmo

1. Explorar el laberinto en profundidad aplicando la regla de la mano izquierda y retrocediendo de los callejones sin salida hasta visitar todas las celdas.
2. Registrar cada arista abierta bidireccionalmente para consolidar el mapa de obstáculos.
3. Ejecutar flood-fill desde la meta: fijar su potencial en 0 e irradiar distancias crecientes a través de los pasos libres.
4. Trazar la ruta óptima: partiendo del inicio, seleccionar reiteradamente la celda contigua de menor valor numérico.
5. Ejecutar la carrera rápida recorriendo dicha trayectoria calculada.
6. Comparar la longitud del trayecto exploratorio frente a la ruta óptima para constatar la eficiencia del algoritmo.

Código fuente

Estructura el software separando con claridad exploración, mapeo, planificación y control cinemático:

// 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

Esta modularidad permite evaluar el mismo algoritmo de planificación en este simulador de navegador, en pruebas sobre escritorio y finalmente en el microcontrolador ESP32 físico.

Suposiciones y diferencias con el hardware

El simulador aísla la lógica de planificación eliminando el mayor obstáculo de un robot físico: los errores de odometría. El modelo virtual avanza exactamente una celda por paso sin derrape de ruedas, deriva angular ni desviaciones en giros ortogonales, y sus tres telémetros reportan muros con precisión binaria perfecta. Un chasis físico con ESP32 acumula errores de rumbo y traslación en cada maniobra, debiendo realinearse contra los muros y filtrar las lecturas de los sensores ToF frente a reflejos y variaciones lumínicas; aspectos tratados en el tutorial de giros precisos y en la guía de flood-fill.

Diagrama de circuito

Emplea un regulador de tensión externo dimensionado para soportar la corriente de calado de los motores. El microcontrolador ESP32 y los sensores de proximidad demandan un riel de alimentación lógica inmune a las caídas de tensión inducidas por las conmutaciones del puente H.