O curso
Grafos e busca de caminhos é um curso avançado de Codificação em sete aulas. Cada aula roda no mesmo circuito: um Raspberry Pi 4 com um módulo de semáforo (vermelho no GPIO17, amarelo no GPIO27, verde no GPIO22), que é a lâmpada de status do rover. Mapas e rotas são impressos no monitor serial, e cada passo é conferido com o que o Pi imprime ou qual lâmpada acende.
- Grafos como dados: estações e estradas da Base Jezero como um dict de listas, graus e o ponto mais movimentado, um verificador que encontra uma via de mão única, o lema do aperto de mãos, e um mapa de terreno transformado num grafo de células.
- BFS: uma fila que explora em anéis, distância em saltos, parents que reconstroem a rota, uma única função
routepara as estações e para a grade, o caminho desenhado no mapa, e uma lâmpada vermelha quando um desabamento isola o objetivo. - DFS: recursão e uma pilha explícita, as estações que uma tempestade de poeira isola, um primeiro caminho de 32 passos onde o BFS achou 24, e o limite de recursão que um campo de 30 por 30 encontra.
- Dijkstra: tempos de viagem como pesos das arestas,
heapqcomo fila de prioridade, a rota de 30 minutos que usa uma estrada a mais que a de 40 minutos, e areia fofa no mapa de terreno. - A: a prioridade f = g + h, distância de Manhattan e heurísticas admissíveis, a mesma rota a partir de 25 quadrados em vez de 42, uma planície de 600 quadrados em que o A expande 54 quadrados contra 570 do Dijkstra, e a rota pior que um palpite confiante demais escolhe.
- Labirintos: um DFS aleatorizado esculpe um labirinto perfeito (39 passagens para 40 células), o BFS o resolve, a solução é desenhada, os becos sem saída são contados, e uma nova seed cria um novo labirinto.
- Chefão: um robô que resolve um labirinto: o grande final.
O catálogo também lista um ESP32-C3 e um chassi de duas rodas. Este curso é construído só no Pi, com o movimento do rover como comandos de direção impressos, então cada passo pode ser conferido no navegador.
O 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."
O que o motor do Pi faz de diferente
O Pi roda MicroPython 1.29, não CPython. Neste curso isso aparece em alguns pontos:
heapqtemheappush,heappopeheapify, que é tudo de que Dijkstra e A* precisam;collections.dequeestá lá para o BFS.- Um dict não mantém a ordem em que as chaves entraram, então as tabelas percorrem
sorted(...). Listas mantêm a ordem, então listas de vizinhos são seguras. - A recursão para perto de 800 quadros com
RuntimeError: pystack exhausted. O limite do CPython é 1.000 e seu erro éRecursionError. A aula de DFS bate no limite de propósito e depois resolve com uma pilha. random.seed(2026)gera o mesmo labirinto em toda execução neste motor. O CPython tira seus números aleatórios de um gerador diferente, então a mesma seed lá pode esculpir um labirinto diferente, igualmente perfeito.input()lê uma linha digitada no monitor serial.