Kursusnya
Graphs and pathfinding adalah kursus Coding tingkat lanjut dalam tujuh pelajaran. Setiap pelajaran berjalan di rangkaian yang sama: sebuah Raspberry Pi 4 dengan modul lampu lalu lintas (merah di GPIO17, kuning di GPIO27, hijau di GPIO22), yang menjadi lampu status rover. Peta dan rute dicetak ke Serial Monitor, dan setiap langkah diperiksa terhadap apa yang dicetak Pi atau lampu mana yang menyala.
- Graf sebagai data: stasiun dan jalan Base Jezero sebagai dict of lists, derajat dan hub tersibuk, pemeriksa yang menemukan jalan satu arah, lemma jabat tangan, dan peta medan yang diubah menjadi graf sel.
- BFS: antrian yang menjelajah dalam cincin, jarak dalam lompatan, parent yang menyusun ulang rutenya, satu fungsi
routeuntuk stasiun dan untuk grid, jalur yang digambar di peta, dan lampu merah ketika longsoran batu menutup satu-satunya jalan menuju tujuan. - DFS: rekursi dan stack eksplisit, stasiun yang terputus oleh badai debu, jalur pertama yang 32 langkah di mana BFS menemukan 24, dan batas rekursi yang dijumpai oleh ladang 30 x 30.
- Dijkstra: waktu berkendara sebagai bobot sisi,
heapqsebagai priority queue, rute 30 menit yang memakai satu jalan lebih banyak daripada rute 40 menit, dan pasir lunak di peta medan. - A: prioritas f = g + h, jarak Manhattan dan heuristik yang admissible, rute yang sama dari 25 kotak alih-alih 42, dataran 600 kotak di mana A memperluas 54 kotak dibanding 570 milik Dijkstra, dan rute yang lebih buruk yang dipilih oleh tebakan yang terlalu percaya diri.
- Labirin: DFS acak memahat labirin sempurna (39 lorong untuk 40 sel), BFS menyelesaikannya, solusinya digambar, jalan buntu dihitung, dan seed baru menghasilkan labirin baru.
- Boss: robot yang menyelesaikan labirin: babak final.
Katalog juga mencantumkan ESP32-C3 dan sasis dua roda. Kursus ini dibangun hanya di atas Pi, dengan gerak rover sebagai perintah berkendara yang dicetak, sehingga setiap langkah bisa diperiksa di browser.
Babak 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."
Apa yang berbeda di engine Pi
Pi menjalankan MicroPython 1.29, bukan CPython. Untuk kursus ini hal itu terlihat di beberapa tempat:
heapqpunyaheappush,heappopdanheapify, yang semuanya dibutuhkan Dijkstra dan A*;collections.dequejuga ada untuk BFS.- Dict tidak menyimpan urutan masuknya kunci, jadi tabel-tabel melakukan loop lewat
sorted(...). List menyimpan urutannya, jadi list tetangga aman. - Rekursi berhenti di sekitar 800 frame dengan
RuntimeError: pystack exhausted. Batas CPython adalah 1.000 dan error-nyaRecursionError. Pelajaran DFS sengaja menabrak tembok ini lalu memperbaikinya dengan stack. random.seed(2026)menghasilkan labirin yang sama setiap kali dijalankan di engine ini. CPython mengambil angka acaknya dari generator yang berbeda, jadi seed yang sama di sana bisa memahat labirin berbeda yang sama sempurnanya.input()membaca satu baris yang diketik di Serial Monitor.