Lecciones y el juego de aprendizaje

Grafos y búsqueda de rutas

Guía un rover de Marte con los algoritmos detrás de cada app de mapas y cada juego: BFS, DFS, Dijkstra y A*, escritos desde cero en Python en una Raspberry Pi.

El curso

Grafos y búsqueda de rutas es un curso avanzado de Programación en siete lecciones. Cada lección usa el mismo circuito: una Raspberry Pi 4 con un módulo de semáforo (rojo en GPIO17, ámbar en GPIO27, verde en GPIO22), que es la lámpara de estado del rover. Los mapas y las rutas se imprimen en el monitor serie, y cada paso se comprueba contra lo que la Pi imprime o qué lámpara enciende.

  1. Grafos como datos: las estaciones y caminos de la Base Jezero como un dict de listas, grados y el nodo con más conexiones, un verificador que encuentra un camino de sentido único, el lema del apretón de manos, y un mapa de terreno convertido en un grafo de celdas.
  2. BFS: una cola que explora en anillos, distancia en saltos, padres que reconstruyen la ruta, una sola función route para las estaciones y para la cuadrícula, el camino dibujado en el mapa, y una lámpara roja cuando un derrumbe encierra la meta.
  3. DFS: recursión y una pila explícita, las estaciones que una tormenta de polvo aísla, un primer camino de 32 pasos donde BFS encontró 24, y el límite de recursión con que choca un campo de 30 por 30.
  4. Dijkstra: tiempos de viaje como pesos de las aristas, heapq como cola de prioridad, la ruta de 30 minutos que toma un camino más que la de 40, y arena blanda en el mapa de terreno.
  5. A: la prioridad f = g + h, la distancia Manhattan y las heurísticas admisibles, la misma ruta recorriendo 25 casillas en lugar de 42, una llanura de 600 casillas donde A expande 54 casillas contra las 570 de Dijkstra, y la peor ruta que elige una suposición demasiado confiada.
  6. Laberintos: un DFS aleatorizado talla un laberinto perfecto (39 pasajes para 40 celdas), BFS lo resuelve, la solución se dibuja, se cuentan los callejones sin salida, y una nueva semilla crea un nuevo laberinto.
  7. Jefe final: un robot que resuelve un laberinto: el gran final.

El catálogo también lista una ESP32-C3 y un chasis de dos ruedas. Este curso está construido solo con la Pi, con el movimiento del rover como comandos de manejo impresos, así cada paso se puede comprobar en el navegador.

El gran final

Rover 7's console reads commands typed in the Serial Monitor. Its canyon is the maze from lesson 6 with six extra walls knocked out, because a real canyon has loops. solve plans with A*, amber lamp on while it searches, then green, and prints the route as drive commands: R F L F F F F R F L F R F L F F R F for the 11 cell route, worked out from the change in compass heading at each cell. rock 4 9 drops a boulder on the route and the next solve finds a 13 cell way around. rock 8 15 blocks the goal's only way in, and the red lamp says so. drive plans and plays the commands out, one move at a time, until "arrived at the goal. Science time."

Qué hace distinto el motor de la Pi

La Pi ejecuta MicroPython 1.29, no CPython. Para este curso eso se nota en algunos puntos:

  • heapq tiene heappush, heappop y heapify, que es todo lo que Dijkstra y A* necesitan; collections.deque está ahí para BFS.
  • Un dict no conserva el orden en que entraron las llaves, así que las tablas recorren sorted(...). Las listas sí conservan su orden, así que las listas de vecinos están a salvo.
  • La recursión se detiene cerca de 800 marcos con RuntimeError: pystack exhausted. El límite de CPython es 1,000 y su error es RecursionError. La lección de DFS choca contra el muro a propósito y luego lo arregla con una pila.
  • random.seed(2026) da el mismo laberinto en cada ejecución en este motor. CPython saca sus números aleatorios de un generador distinto, así que la misma semilla allí puede tallar un laberinto diferente e igualmente perfecto.
  • input() lee una línea escrita en el monitor serie.