Aulas e o jogo de aprendizado

Grafos e busca de caminhos

Guie um rover de Marte com os algoritmos por trás de todo app de mapas e jogo: BFS, DFS, Dijkstra e A*, escritos do zero em Python num Raspberry Pi.

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.

  1. 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.
  2. BFS: uma fila que explora em anéis, distância em saltos, parents que reconstroem a rota, uma única função route para as estações e para a grade, o caminho desenhado no mapa, e uma lâmpada vermelha quando um desabamento isola o objetivo.
  3. 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.
  4. Dijkstra: tempos de viagem como pesos das arestas, heapq como 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.
  5. 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.
  6. 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.
  7. 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:

  • heapq tem heappush, heappop e heapify, que é tudo de que Dijkstra e A* precisam; collections.deque está 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.