الدروس ولعبة التعلّم

المخططات البيانية والبحث عن المسار

قِد مركبة استكشاف المريخ بالخوارزميات التي تقف خلف كل تطبيق خرائط وكل لعبة: BFS وDFS وDijkstra وA*، مكتوبة من الصفر بلغة Python على Raspberry Pi.

الدورة

دورة المخططات البيانية والبحث عن المسار هي دورة برمجة متقدمة في سبعة دروس. يعمل كل درس على الدائرة نفسها: لوحة Raspberry Pi 4 مع وحدة إشارة مرور (أحمر على GPIO17، وأصفر على GPIO27، وأخضر على GPIO22)، وهي مصباح حالة المركبة. تُطبع الخرائط والمسارات في الشاشة التسلسلية، ويُتحقق من كل خطوة مقابل ما يطبعه Pi أو أي مصباح يضيء.

  1. المخططات كبيانات: محطات قاعدة Jezero وطرقها كقاموس من قوائم، والدرجات وأكثر محطة ازدحامًا، وفاحص يجد طريقًا باتجاه واحد، ومبرهنة المصافحات، وخريطة تضاريس تتحول إلى مخطط من خلايا.
  2. خوارزمية BFS: طابور يستكشف على شكل حلقات، والمسافة بالقفزات، وأسلاف يعيدون بناء المسار، ودالة مسار واحدة للمحطات وللشبكة، والمسار مرسوم على الخريطة، ومصباح أحمر عندما يحاصر انهيار صخري الهدف.
  3. خوارزمية DFS: الاستدعاء الذاتي ومكدّس صريح، والمحطات التي تقطعها عاصفة غبار، ومسار أول بطول 32 خطوة حيث وجدت BFS مسارًا من 24، وحد الاستدعاء الذاتي الذي تصطدم به حقل بمقاس 30 في 30.
  4. خوارزمية Dijkstra: أزمنة القيادة كأوزان للحواف، وheapq كطابور أولويات، ومسار الـ 30 دقيقة الذي يأخذ طريقًا واحدًا أكثر من مسار الـ 40 دقيقة، والرمل الناعم على خريطة التضاريس.
  5. خوارزمية A: أولوية f = g + h، ومسافة Manhattan والاستدلالات المقبولة، والمسار نفسه من 25 مربعًا بدل 42، وسهل من 600 مربع تتوسع فيه A في 54 مربعًا مقابل 570 لخوارزمية Dijkstra، والمسار الأسوأ الذي يختاره تخمين متعجرف.
  6. المتاهات: DFS عشوائي ينحت متاهة كاملة (39 ممرًا لـ 40 خلية)، وBFS تحلها، ويُرسم الحل، وتُعدّ الممرات المسدودة، وبذرة جديدة تصنع متاهة جديدة.
  7. المهمة الكبرى: روبوت يحل متاهة: الخاتمة.

يسرد الفهرس ESP32-C3 وهيكلًا بعجلتين أيضًا. هذه الدورة مبنية على Pi وحده، مع حركة المركبة كأوامر قيادة مطبوعة، بحيث يمكن التحقق من كل خطوة في المتصفح.

الخاتمة

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 بشكل مختلف

يعمل Pi على MicroPython 1.29، وليس CPython. في هذه الدورة يظهر ذلك في مواضع قليلة:

  • heapq يتضمن heappush وheappop وheapify، وهي كل ما يحتاجه خوارزميا Dijkstra و A*؛ كما تتوفر collections.deque لخوارزمية BFS.
  • القاموس لا يحفظ ترتيب إدخال المفاتيح، لذا تمرّ الجداول على sorted(...). القوائم تحفظ ترتيبها، لذا فقوائم الجيران آمنة.
  • يتوقف الاستدعاء الذاتي قرب 800 إطار مع RuntimeError: pystack exhausted. حد CPython هو 1,000 وخطؤه RecursionError. درس DFS يصطدم بالجدار عمدًا ثم يصلحه بمكدّس.
  • random.seed(2026) يعطي المتاهة نفسها في كل تشغيل على هذا المحرك. يسحب CPython أرقامه العشوائية من مولّد مختلف، لذا قد تنحت البذرة نفسها هناك متاهة مختلفة، لكنها كاملة بالقدر نفسه.
  • input() يقرأ سطرًا مكتوبًا في الشاشة التسلسلية.