Pelajaran dan game belajarnya

Graf dan pencarian jalur

Kendarai sebuah rover Mars dengan algoritme di balik setiap aplikasi peta dan game: BFS, DFS, Dijkstra dan A*, ditulis dari nol dengan Python di Raspberry Pi.

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.

  1. 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.
  2. BFS: antrian yang menjelajah dalam cincin, jarak dalam lompatan, parent yang menyusun ulang rutenya, satu fungsi route untuk stasiun dan untuk grid, jalur yang digambar di peta, dan lampu merah ketika longsoran batu menutup satu-satunya jalan menuju tujuan.
  3. 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.
  4. Dijkstra: waktu berkendara sebagai bobot sisi, heapq sebagai priority queue, rute 30 menit yang memakai satu jalan lebih banyak daripada rute 40 menit, dan pasir lunak di peta medan.
  5. 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.
  6. Labirin: DFS acak memahat labirin sempurna (39 lorong untuk 40 sel), BFS menyelesaikannya, solusinya digambar, jalan buntu dihitung, dan seed baru menghasilkan labirin baru.
  7. 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:

  • heapq punya heappush, heappop dan heapify, yang semuanya dibutuhkan Dijkstra dan A*; collections.deque juga 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-nya RecursionError. 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.