خوارزمية A*: كيف أنقذتني من جحيم المسارات الغبية وشخصياتي التي تصطدم بالجدران

حكايتي مع الجدران: عندما كانت شخصياتي “بتلطّش”

يا جماعة الخير، اسمحوا لي أرجع بالزمن لورا كم سنة. كنت قاعد في مكتبي الصغير، فنجان القهوة جنبي، وشغال على لعبة بسيطة. كانت الفكرة إنو في شخصية صغيرة، خلينا نسميها “حمدان”، لازم يوصل لقطعة كنافة في آخر الخريطة. الخريطة عبارة عن متاهة مليانة جدران وعوائق.

كتبت أول كود لحركة حمدان، كان أشي بسيط جداً، يمشي خطوة بخطوة باتجاه الكنافة. وشغّلت اللعبة… وإذ بحمدان المسكين يمشي بخط مستقيم ويخبط بأول حيط قدامه! ويضل يحاول يمشي من خلاله، “يلطّش” فيه زي الأعمى. عدّلت الكود شوي، صار حمدان يغير اتجاهه بشكل عشوائي لما يخبط بحيط. النتيجة؟ صار حمدان يدور حولين حاله في حلقة مفرغة، والكنافة بتستناه وهو مش عارف يوصلها. وقتها قلت لحالي: “يا زلمة شو هالحكي! لازم في طريقة أذكى من هيك”.

هذه الحادثة البسيطة كانت مدخلي لعالم ممتع ومعقد اسمه “إيجاد المسار” (Pathfinding)، وكانت البداية لقصة حبي مع خوارزمية عظيمة أنقذتني وأنقذت حمدان من جحيم المسارات الغبية: خوارزمية A* (تُنطق A-Star أو نجمة ألفا).

ما هو “إيجاد المسار” (Pathfinding) وليش هو مهم؟

ببساطة، إيجاد المسار هو عملية إيجاد أقصر أو أفضل طريق بين نقطتين في خريطة أو مخطط (Graph). الموضوع أكبر بكثير من مجرد ألعاب فيديو. فكر فيها:

• تطبيقات الخرائط (GPS): كيف يجد Google Maps أو Waze أسرع طريق من بيتك لشغلك، مع الأخذ بالاعتبار الازدحام وإشارات المرور؟ هذا إيجاد مسار.
• الروبوتات والمستودعات: كيف يتحرك الروبوت في مستودع أمازون ليحضر سلعة معينة دون الاصطدام بالروبوتات الأخرى أو الأرفف؟ هذا إيجاد مسار.
• شبكات الحاسوب: كيف تنتقل حزمة البيانات (Data Packet) من جهازك إلى سيرفر في أمريكا عبر شبكة الإنترنت المعقدة؟ نعم، هذا أيضاً إيجاد مسار.
• الذكاء الاصطناعي في الألعاب: كيف يجد الأعداء في لعبة استراتيجية الطريق إليك ليقوموا بالهجوم؟ أو كيف تجد وحداتك الطريق لتنفيذ أوامرك؟

المشكلة واضحة، لكن الحلول تتفاوت في ذكائها وكفاءتها. خلينا نشوف المحاولات الفاشلة اللي مريت فيها قبل ما أهتدي للحل الأمثل.

المحاولات الأولى: رحلة البحث عن الذكاء

قبل ما نصل للبطل A*، من المهم نفهم الخيارات الأخرى وليش هي مش دايماً الحل الأفضل. زي ما بنحكي، “لولا الخطأ ما عرفنا الصح”.

خوارزمية البحث بأولوية العرض (BFS): سيلٌ يغمر الخريطة

خوارزمية Breadth-First Search أو BFS كانت أول محاولة جادة. فكرتها مثل صب الماء في نقطة البداية على الخريطة. الماء ينتشر بالتساوي في كل الاتجاهات، طبقة بعد طبقة، حتى يصل إلى نقطة النهاية.

ميزتها: تضمن لك إيجاد أقصر مسار إذا كانت تكلفة الحركة بين كل خطوة وأخرى متساوية (مثلاً، كل مربع يكلف 1).
عيبها: غبية جداً! هي لا “ترى” الهدف، بل تبحث في كل الاتجاهات الممكنة. لو كانت الخريطة كبيرة والهدف في زاوية بعيدة، ستقوم BFS باستكشاف أجزاء ضخمة من الخريطة لا علاقة لها بالحل، مما يستهلك وقتاً وذاكرة هائلة.

تخيل أنك تبحث عن محل في مدينة كبيرة، وبدل أن تسير في الشارع الذي يؤدي إليه، قررت أن تستكشف كل شارع يبعد عنك مسافة 1 كم، ثم كل شارع يبعد 2 كم، وهكذا. هذا هو BFS، فعال لكنه غير كفؤ.

خوارزمية دَيكسترا (Dijkstra): المستكشف الحذر ولكنه بطيء

هنا بدأنا ندخل في الحلول الأذكى شوي. خوارزمية دَيكسترا (Dijkstra’s Algorithm) تشبه BFS، لكنها تأخذ في الاعتبار “تكلفة” الحركة. يعني لو الحركة في الوحل تكلف 5 نقاط والحركة على الشارع تكلف 1 نقطة، دَيكسترا ستفضل الشارع.

ميزتها: تجد المسار الأقل تكلفة من نقطة البداية إلى كل النقاط الأخرى في الخريطة.
عيبها: مثل BFS، هي لا تعرف أين يقع الهدف. هي تستكشف دائماً النقطة الأقرب إلى نقطة البداية، حتى لو كانت هذه النقطة في الاتجاه المعاكس تماماً للهدف. هي لا تملك أي “حدس” أو “بصيرة” للمستقبل.

البطل المنتظر: خوارزمية A* (نجمة ألفا)

بعد المعاناة مع الخوارزميات السابقة، كان اكتشاف A* بمثابة ” eureka moment”. خوارزمية A* هي الحل السحري الذي يجمع بين دقة دَيكسترا (الأخذ بالتكلفة الفعلية) وبين “حدس” ذكي يوجهها نحو الهدف.

المعادلة السحرية: f(n) = g(n) + h(n)

جمال A* يكمن في هذه المعادلة البسيطة التي تقيّم كل مربع (أو عقدة) في الخريطة. خلينا نفصّلها:

• n: هو المربع أو العقدة الحالية التي نقوم بتقييمها.
• g(n): هي التكلفة الفعلية للمسار من نقطة البداية إلى العقدة الحالية n. هذا هو الجزء الذي ورثته A* من دَيكسترا.
• h(n): هي التكلفة التقديرية أو “الحدسية” (Heuristic) من العقدة الحالية n إلى نقطة النهاية. هذا هو السحر! هذا هو الجزء الذي يجعل A* ذكية. هي “تخمّن” كم تبعد عن الهدف.
• f(n): هي التكلفة الإجمالية التقديرية للمسار إذا مررنا عبر العقدة n. A* دائماً تختار استكشاف العقدة التي تملك أقل قيمة f(n).

بفضل الدالة h(n)، خوارزمية A* تفضل استكشاف المربعات التي لا تبدو قريبة من البداية فحسب، بل تبدو قريبة من النهاية أيضاً. هذا يمنعها من التجول في مسارات بعيدة عن الهدف، ويوجه بحثها بشكل فعال.

كيف تعمل A* خطوة بخطوة؟ (مع مثال بسيط)

لتبسيط الفكرة، الخوارزمية تحتفظ بقائمتين:

1. القائمة المفتوحة (Open List): تحتوي على العقد (المربعات) التي تم اكتشافها ولكن لم يتم زيارتها بعد. هذه هي العقد المرشحة للاستكشاف.
2. القائمة المغلقة (Closed List): تحتوي على العقد التي تمت زيارتها وتقييمها بالفعل. لن نعود إليها مرة أخرى.

والخطوات هي كالتالي:

1. ضع عقدة البداية في القائمة المفتوحة.
2. طالما أن القائمة المفتوحة ليست فارغة، كرر التالي:
3. أ. اختر العقدة التي تملك أقل قيمة f من القائمة المفتوحة. سنسميها “العقدة الحالية”.
4. ب. انقل “العقدة الحالية” من القائمة المفتوحة إلى القائمة المغلقة.
5. ج. إذا كانت “العقدة الحالية” هي عقدة الهدف، فقد انتهينا! يمكنك الآن تتبع المسار للخلف من الهدف إلى البداية باستخدام “الآباء” (Parents) الذين قمت بتسجيلهم لكل عقدة.
6. د. لكل “عقدة مجاورة” للعقدة الحالية:
   • إذا كانت العقدة المجاورة جداراً أو موجودة في القائمة المغلقة، تجاهلها.
   • احسب تكلفتها g الجديدة (تكلفة العقدة الحالية + تكلفة الحركة إلى المجاورة).
   • إذا كانت هذه التكلفة الجديدة أفضل (أقل) من تكلفتها القديمة، أو إذا لم تكن موجودة في القائمة المفتوحة، فقم بتحديثها: سجل “العقدة الحالية” كـ “أب” لها، واحسب قيم g, h, f الجديدة، ثم أضفها إلى القائمة المفتوحة.
7. إذا انتهت الحلقة ولم نجد الهدف (القائمة المفتوحة أصبحت فارغة)، فهذا يعني أنه لا يوجد مسار.

مثال برمجي بلغة بايثون (Python)

الكلام النظري جميل، لكن الكود يوضح كل شيء. هذا مثال مبسط جداً لخوارزمية A* باستخدام بايثون لإيجاد مسار في شبكة (Grid).

import heapq

# تعريف العقدة (المربع)
class Node:
    def __init__(self, parent=None, position=None):
        self.parent = parent
        self.position = position
        self.g = 0
        self.h = 0
        self.f = 0

    def __eq__(self, other):
        return self.position == other.position

    def __lt__(self, other):
        return self.f  0:
        # استخراج العقدة ذات أقل f_cost
        current_node = heapq.heappop(open_list)
        closed_list.add(current_node.position)

        # وصلنا للهدف
        if current_node == end_node:
            path = []
            current = current_node
            while current is not None:
                path.append(current.position)
                current = current.parent
            return path[::-1]  # عكس المسار ليكون من البداية للنهاية

        # استكشاف الجيران
        (x, y) = current_node.position
        for new_position in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]: # حركة في 4 اتجاهات

            # التأكد من أن الجار داخل حدود الخريطة
            if not (0 <= new_position[0] < len(maze) and 0 <= new_position[1] = open_node.g):
                continue

            # إضافة الجار إلى القائمة المفتوحة
            heapq.heappush(open_list, neighbor)

    return None # لم يتم العثور على مسار

# --- مثال للاستخدام ---
maze = [[0, 0, 0, 0, 1, 0, 0, 0],
        [0, 0, 1, 0, 1, 0, 1, 0],
        [0, 0, 1, 0, 0, 0, 1, 0],
        [0, 0, 1, 1, 1, 0, 1, 0],
        [0, 0, 0, 0, 1, 0, 0, 0],
        [0, 1, 1, 0, 1, 1, 1, 1],
        [0, 0, 0, 0, 1, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0]]

start = (0, 0)
end = (7, 6)

path = astar(maze, start, end)
print(path)
# سيطبع: [(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3), (5, 3), (6, 3), (7, 3), (7, 4), (7, 5), (7, 6)]

نصائح أبو عمر الذهبية لإتقان A*

بعد سنوات من التعامل مع هذه الخوارزمية، تعلمت بعض الدروس التي أحب أن أشاركها معكم:

فن اختيار الدالة الحدسية (Heuristic)

الدالة h(n) هي قلب وروح A*. اختيارك لها يحدد أداء الخوارزمية:

• مسافة مانهاتن (Manhattan Distance): |x1 - x2| + |y1 - y2|. ممتازة للخرائط الشبكية التي تسمح بالحركة في 4 اتجاهات فقط (أعلى، أسفل، يمين، يسار). هي سريعة الحساب وتضمن أقصر مسار.
• المسافة الإقليدية (Euclidean Distance): sqrt((x1-x2)^2 + (y1-y2)^2). مناسبة إذا كانت الحركة ممكنة في أي اتجاه. لكن حساب الجذر التربيعي مكلف نسبياً، لذا أحياناً نستخدم “المسافة الإقليدية المربعة” لتجنب ذلك أثناء المقارنات.
• قاعدة مهمة: يجب أن تكون دالة الحدس “مقبولة” (Admissible)، أي أنها لا تبالغ أبداً في تقدير التكلفة الحقيقية للوصول إلى الهدف. إذا بالغت في التقدير، قد لا تجد A* أقصر مسار.

أهمية هياكل البيانات الصحيحة (Priority Queue)

في كل خطوة، تحتاج A* إلى إيجاد العقدة ذات أقل قيمة f في القائمة المفتوحة. لو استخدمت قائمة عادية، ستحتاج للبحث في كل عناصرها في كل مرة (عملية O(n)). هذا بطيء جداً.

الحل هو استخدام “طابور الأولوية” (Priority Queue)، والذي يتم تنفيذه عادةً باستخدام هيكل بيانات يسمى “الكومة الثنائية” (Binary Heap). هذا الهيكل يضمن أن عملية إيجاد وإزالة العنصر الأصغر تكون سريعة جداً (عملية O(log n)). في مثال بايثون أعلاه، مكتبة heapq تقوم بهذا الدور.

ماذا بعد A*؟ لمحة عن المستقبل

خوارزمية A* رائعة، لكنها ليست نهاية المطاف. في بعض الحالات، خاصة في الألعاب ذات الخرائط الضخمة والمفتوحة، قد تكون A* بطيئة. هنا تظهر خوارزميات أكثر تقدماً مثل:

• Jump Point Search (JPS): تحسين هائل على A* للخرائط الشبكية المنتظمة. تقوم “بالقفز” فوق المربعات غير المهمة بدلاً من تقييمها واحداً تلو الآخر، مما يقلل بشكل كبير من عدد العقد التي يتم استكشافها.
• Hierarchical A*: تقوم بتقسيم الخريطة الكبيرة إلى مناطق، وتجد المسار على مستوى عالٍ بين المناطق أولاً، ثم تجد المسار التفصيلي داخل كل منطقة.

الخلاصة: من الجدران إلى أذكى المسارات 🚀

رحلتي مع “حمدان” وشخصياتي التي كانت تصطدم بالجدران علمتني درساً قيّماً: فهم المبادئ الأساسية للخوارزميات هو ما يفصل بين المبرمج العادي والمبرمج الذي يصنع حلولاً ذكية وأنيقة. خوارزمية A* لم تكن مجرد كود أضفته لمشروعي، بل كانت نقلة نوعية في طريقة تفكيري بحل المشاكل.

نصيحتي الأخيرة لك: لا تكتفِ بنسخ ولصق الكود. تعمق في فهم لماذا تعمل هذه الخوارزمية. جربها بنفسك، غيّر في دالة الحدس، ارسم الخطوات على ورقة. عندما تفهم “السر” وراء f(n) = g(n) + h(n)، ستتمكن من حل مجموعة واسعة من المشاكل التي تتجاوز بكثير مجرد تحريك شخصية في لعبة.

أتمنى أن تكون هذه المقالة قد أنارت لكم الطريق، تماماً كما أنارت A* الطريق لشخصياتي. بالتوفيق في رحلتكم البرمجية!