Dersler ve öğrenme oyunu

Graflar ve yol bulma

Bir Mars gezginini, her harita uygulamasının ve oyunun arkasındaki algoritmalarla yönet: BFS, DFS, Dijkstra ve A*, bir Raspberry Pi üzerinde Python ile sıfırdan yazılmış.

Kurs

Graflar ve yol bulma, yedi derslik ileri seviye bir Kodlama kursudur. Her ders aynı devre üzerinde çalışır: GPIO17'de kırmızı, GPIO27'de sarı, GPIO22'de yeşil lambası olan bir trafik ışığı modülüne sahip Raspberry Pi 4, bu da gezginin durum lambasıdır. Haritalar ve rotalar seri monitöre yazdırılır ve her adım, Pi'nin yazdırdıkları veya yaktığı lambayla karşılaştırılarak kontrol edilir.

  1. Graf verileri: Base Jezero'nun istasyonları ve yolları listelerden oluşan bir dict olarak, dereceler ve en yoğun merkez, tek yönlü bir yol bulan bir denetleyici, el sıkışma lemması ve bir arazi haritasının hücrelerden oluşan bir grafa dönüştürülmesi.
  2. BFS: halkalar halinde keşfeden bir kuyruk, adım cinsinden uzaklık, rotayı yeniden kurmak için ebeveynler, istasyonlar ve ızgara için tek bir route fonksiyonu, harita üzerine çizilen yol ve bir çöküş hedefi duvarlarla çevirdiğinde yanan kırmızı lamba.
  3. DFS: özyineleme ve açık bir yığın, bir kum fırtınasının kestiği istasyonlar, BFS'nin 24 bulduğu yerde 32 adımlık bir ilk yol ve 30'a 30'luk bir alanın çarptığı özyineleme sınırı.
  4. Dijkstra: kenar ağırlığı olarak sürüş süreleri, öncelik kuyruğu olarak heapq, 40 dakikalık rotadan bir yol fazla alan 30 dakikalık rota ve arazi haritasındaki yumuşak kum.
  5. A: f = g + h önceliği, Manhattan uzaklığı ve kabul edilebilir sezgiseller, 42 yerine 25 kareden aynı rota, A'nın Dijkstra'nın 570'ine karşılık yalnızca 54 kare açtığı 600 karelik bir düzlük ve aşırı kendinden emin bir tahminin seçtiği daha kötü rota.
  6. Labirentler: rastgele bir DFS kusursuz bir labirent oyuyor (40 hücre için 39 geçit), BFS çözer, çözüm çizilir, çıkmaz sokaklar sayılır ve yeni bir seed yeni bir labirent yapar.
  7. Boss: labirenti çözen bir robot: final.

Katalogda bir ESP32-C3 ve iki tekerlekli bir şasi de var. Bu kurs yalnızca Pi üzerine kuruludur, gezginin hareketi yazdırılmış sürüş komutları olarak gösterilir, böylece her adım tarayıcıda kontrol edilebilir.

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."

Pi'nin motoru neyi farklı yapar

Pi, CPython değil MicroPython 1.29 çalıştırır. Bu kurs için bu birkaç yerde kendini gösterir:

  • heapq modülünde heappush, heappop ve heapify var; Dijkstra ve A* için gereken her şey bunlar; BFS için de collections.deque mevcut.
  • Bir dict, anahtarların girildiği sırayı tutmaz, bu yüzden tablolar sorted(...) üzerinde döner. Listeler sıralarını korur, bu yüzden komşu listeleri güvenlidir.
  • Özyineleme yaklaşık 800 çerçevede RuntimeError: pystack exhausted ile durur. CPython'un sınırı 1.000'dir ve hatası RecursionError'dur. DFS dersi bilerek bu duvara çarpar ve sonra bir yığınla düzeltir.
  • random.seed(2026) bu motorda her çalıştırmada aynı labirenti verir. CPython rastgele sayılarını farklı bir üreteçten aldığı için aynı seed orada farklı ama yine kusursuz bir labirent oyabilir.
  • input() seri monitöre yazılan bir satırı okur.