مستكشف المتاهة
AI Maze Explorer
متاهة عشوائية ببذرة قابلة للتكرار: شاهد كل خوارزمية تستكشف، ثم ارسم مسارك وتحدَّ أقصر طريق، وقارن الخوارزميات على المتاهة نفسها.
تعمل اللعبة كاملة في متصفحك. لا يُرسل شيء إلى خدمة خارجية.
تُحمَّل اللعبة…
التلميحات
ثلاثة مستويات: الأول يوجّه فقط، والثالث أقرب إلى الحل. اكشفها واحداً واحداً.
وضع التعلم
- التلميح 1: ابدأ بـ BFS على متاهة بلا حلقات ثم زد نسبة الحلقات وراقب الفرق.
- التلميح 2: لوّن الخلايا الموسَّعة: BFS ينتشر كموجة، وDFS يندفع في ممر واحد.
- التلميح 3: قارن A* بـ Greedy: الفرق كله في g (الكلفة المقطوعة).
وضع التحدي
- التلميح 1: لست مضطراً للمرور بكل الممرات: ابحث عن الحلقات التي تختصر الطريق.
- التلميح 2: تتبّع الطريق من الهدف إلى الوراء: غالباً أسهل.
- التلميح 3: أقصر طريق هو ما يجده BFS: نقاطك = 1000 × الطول الأقصر ÷ طول مسارك.
كيف تعمل؟ How It Works
تعريف المشكلة
إيجاد مسار من البداية إلى الهدف في متاهة شبكية، حيث كل خطوة إلى خلية مجاورة مفتوحة كلفتها 1.
الخوارزمية
أربع خوارزميات منفذة فعلياً: BFS (طابور)، DFS (مكدس)، A* (أولوية = g + h، مع h مسافة مانهاتن)، والبحث الجشع Greedy Best-First (أولوية = h فقط).
المدخلات
المتاهة (من بذرة عشوائية قابلة للتكرار)، البداية، الهدف، الخوارزمية.
المخرجات
ترتيب العقد الموسَّعة، المسار النهائي، طوله، أكبر حجم للحافة (Frontier).
خطوات التنفيذ
- تُولَّد المتاهة بخوارزمية Recursive Backtracker ثم تُفتح نسبة من الجدران لتظهر طرق بديلة.
- تأخذ الخوارزمية عقدة من الحافة (Frontier) وتوسّعها: تضيف جيرانها بالترتيب أعلى، يمين، أسفل، يسار.
- تُكسر التعادلات في طوابير الأولوية بترتيب الإدخال (FIFO).
- عند الوصول إلى الهدف يُعاد بناء المسار من مؤشرات الأب.
المعلمات
- الحجم: صغير 15×11، متوسط 25×17، كبير 41×27
- نسبة الحلقات (الطرق البديلة) 0–40%
- سرعة المحاكاة
مثال
في متاهة بحلقات: BFS وA* يجدان أقصر مسار دائماً، وA* يوسّع عادة عقداً أقل من BFS لأن مسافة مانهاتن توجّهه نحو الهدف. Greedy قد يكون أسرع لكنه قد يعطي مساراً أطول.
المزايا
- BFS: أقصر مسار مضمون عند تساوي الكلف.
- A*: أقصر مسار مضمون مع دالة تقدير مقبولة (Admissible) مثل مانهاتن هنا، وعادة باستكشاف أقل.
- DFS: ذاكرة قليلة.
- Greedy: سريع غالباً.
القيود
- DFS وGreedy لا يضمنان أقصر مسار.
- BFS يستكشف في كل الاتجاهات بالتساوي.
- جودة A* تعتمد على دالة التقدير.
التعقيد الحسابي
BFS وDFS: O(V + E). A* وGreedy مع كومة ثنائية: O(E log V) في أسوأ الحالات، حيث V عدد الخلايا المفتوحة وE عدد الوصلات.
مقاييس التقييم
- عدد العقد الموسَّعة
- طول المسار مقارنة بالأقصر
- أكبر حجم للحافة
التطبيقات الواقعية
- تخطيط مسارات الروبوتات
- الألعاب
- الملاحة والخرائط
المراجع
- Hart, P. E., Nilsson, N. J. & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Trans. SSC 4(2).
- Russell, S. & Norvig, P. Artificial Intelligence: A Modern Approach (4th ed., 2020), chapters on search and adversarial search.
