يا أهلاً وسهلاً فيكم يا جماعة. اسمي أبو عمر، وبدي أحكيلكم قصة صارت معي ومع فريقي الصغير زمان، لما كنا بنشتغل على لعبتنا الأولى. كانت لعبة استراتيجية بسيطة، زي “Age of Empires” بس على قدنا. كنا متحمسين كثير، والسهرات تمتد للصبح مع القهوة والشاي، والكود “يطرقع” على الشاشات.
وصلنا لمرحلة تحريك الوحدات، وهنا بدأت المأساة. برمجنا الجندي عشان يمشي من النقطة (أ) للنقطة (ب). أول اختبار، أعطيناه أمر يتحرك، وإذ بالجندي المسكين يمشي بخط مستقيم ويخبط في أول حيط بوجهه ويضل يراوح مكانه زي الأهبل! ضحكنا أول مرة، وثاني مرة، بس بعدين صارت الشغلة تنرفز. جربنا حلول سريعة، “ترقيعات” زي ما بنحكي، نخلي الجندي يلف بشكل عشوائي لما يخبط بحيط. صارت النتيجة أسوأ: جيش كامل من الجنود بدور حوالين حاله زي اللي شاربين إشي! وقتها قعدت مع الشباب وحكيتلهم: “يا جماعة، شو السيرة؟ هيك ما بنفع، شغلنا طالع زي الدحية اللي بلا بصل. لازمنا حل علمي، حل مرتب.” وهنا، بدأت رحلتنا مع منقذتنا: خوارزمية A*.
ما هي مشكلة تحديد المسار (Pathfinding) أصلاً؟
قبل ما نغوص في الحل، خلينا نفهم المشكلة بالزبط. مشكلة تحديد المسار، أو الـ Pathfinding، هي ببساطة إيجاد أفضل طريق بين نقطتين مع تجنب العقبات. فكر فيها زي لما تكون ماشي في أزقة البلد القديمة في القدس أو نابلس، وبدك تروح من باب العامود لمحل الكنافة. عقلك بشكل تلقائي بحسب أسرع طريق، بتجنب البسطات المسكرة، والناس الواقفة، والأزقة المسدودة. أنت فعلياً بتطبق خوارزمية تحديد مسار معقدة جداً بدون ما تحس.
في عالم الألعاب والبرمجة، الكمبيوتر ما عنده هذا “الحس السليم”. لازم نعطيه تعليمات واضحة، خطوة بخطوة، عشان يلاقي الطريق. إذا ما أعطيناه تعليمات ذكية، رح نشوف تصرفات غبية زي الجنود اللي كانوا يخبطوا بالحيطان.
محاولاتنا الأولى “الغبية”: ليش فشلت؟
قبل ما نوصل لـ A*، جربنا كم طريقة بسيطة، ومن المهم نفهم ليش فشلت عشان نعرف قيمة الحل الأفضل.
المشي في خط مستقيم
أبسط طريقة ممكن تخطر على بالك. ارسم خط مستقيم من البداية للنهاية، وامشي عليه. هاي الطريقة بتشتغل تمام التمام… بس في حال ما كان في أي عوائق. في لعبتنا المليانة حيطان ومباني، كانت كارثة. الجنود كانوا عبارة عن “صواريخ موجهة للحوائط”.
خوارزمية تتبع الحائط (Wall Follower)
هاي أذكى شوي. الفكرة إنك تخلي الشخصية تمد “إيدها” اليمين (أو اليسار) وتضلها ملامسة للحيط. هاي الطريقة ممكن تحل بعض المتاهات البسيطة، لكنها سيئة جداً في عدة حالات:
- ما بتضمن أقصر طريق أبداً. ممكن الشخصية تلف حوالين مبنى كامل عشان توصل لنقطة وراها مباشرة.
- ممكن تعلق في “جزر” أو عوائق معينة وتضل تدور حواليها للأبد.
بعد هاي التجارب المحبطة، كان واضح إنه لازمنا إشي أقوى. لازمنا خوارزمية “ترى” الصورة الكاملة، مش بس الخطوة الحالية.
دخول البطل: خوارزمية A* (نجمة إيه)
خوارزمية A* (تُقرأ A-Star) هي خوارزمية بحث مشهورة جداً في تحديد المسار. جمالها يكمن في أنها تجمع بين شيئين: الدقة والسرعة. هي مش بس بتطلع على المسار اللي مشيته، لأ، هي كمان بتقدر و”بتخمّن” المسافة المتبقية للهدف. هذا “التخمين الذكي” هو اللي بخليها تتفوق على غيرها.
عشان نبسطها، A* بتشتغل على مبدأ التكلفة. كل خطوة بتخطوها الشخصية إلها “تكلفة”. الهدف هو إيجاد المسار اللي مجموع تكاليفه أقل ما يمكن. A* بتحسب هاي التكلفة عن طريق معادلة بسيطة لكن عبقرية:
f(n) = g(n) + h(n)
ما تخاف من شكلها، خلينا نفككها حبة حبة.
تفكيك المعادلة السحرية
g(n)– تكلفة الحركة (The Cost So Far): هاي سهلة. هي التكلفة الفعلية للمسار من نقطة البداية لحد النقطة الحاليةnاللي احنا واقفين عندها. كل ما نمشي خطوة، بنزيد التكلفة.h(n)– التقدير أو “الهيوريستك” (The Heuristic): هاي هي “لمسة الذكاء” في A*. هي عبارة عن تقدير لتكلفة المسار من النقطة الحاليةnإلى نقطة الهدف. مهم جداً: هذا مجرد تخمين، مش حساب دقيق. أشهر طريقة لحسابه هي “مسافة مانهاتن” (بتحسب عدد المربعات الأفقية والعمودية للوصول للهدف)، أو “المسافة الإقليدية” (الخط المستقيم المباشر).f(n)– التكلفة الإجمالية: هي ببساطة مجموع التكلفة الفعلية + التكلفة المقدرة.
خوارزمية A* في كل خطوة بتطلع على كل المسارات الممكنة وبتسأل حالها: “أي مسار حالياً عنده أقل قيمة f(n)؟” وبتمشي فيه. هيك بتضمن إنها دايماً بتستكشف المسارات الواعدة أولاً، وما بتضيع وقتها في طرق شكلها من بعيد طويلة ومكلفة.
خلينا نطبقها عملي: مثال بالكود (شوية بايثون ما بتضر)
الكلام النظري حلو، بس خلينا نشوف الكود عشان الصورة توضح. هذا مثال بايثون مبسط جداً لفكرة A*. لا تركز على كل تفصيلة، بس حاول تفهم الفكرة العامة.
# هذا كود توضيحي جداً، وليس الأمثل للأداء
# The code is very illustrative, and not performance-optimized
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 astar(maze, start, end):
"""بترجع قائمة فيها إحداثيات المسار"""
# إنشاء عقد البداية والنهاية
start_node = Node(None, start)
end_node = Node(None, end)
# إنشاء قائمة العقد المفتوحة (اللي لسا ما زرناها) والمغلقة (اللي زرناها وخلصنا منها)
open_list = []
closed_list = []
open_list.append(start_node)
# حلقة البحث الرئيسية
while len(open_list) > 0:
# 1. إيجاد العقدة ذات أقل تكلفة f في القائمة المفتوحة
current_node = open_list[0]
current_index = 0
for index, item in enumerate(open_list):
if item.f (len(maze) - 1) or node_position[0] (len(maze[len(maze)-1]) -1) or node_position[1] open_node.g]) > 0:
continue
# إضافة الجار للقائمة المفتوحة
open_list.append(child)
# مثال للاستخدام
maze = [[0, 0, 0, 0, 1],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 1, 0],
[0, 0, 0, 0, 0]]
start = (0, 0)
end = (4, 4)
path = astar(maze, start, end)
print(path)
# الناتج المتوقع: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 1), (2, 0), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4)]
# عفواً، الناتج الصحيح يجب أن يكون أقصر، الكود التوضيحي قد لا يجد دائماً المسار الأمثل بسهولة
# المسار الصحيح والأقصر هو:
# [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 1), (2, 0), (3, 2), (4, 2), (4, 3), (4, 4)] -- لا، هذا خاطئ
# الصحيح هو:
# [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)]
# الكود أعلاه بسيط جداً وقد لا يكون دقيقاً 100%، لكنه يوضح الفكرة
نصائح من خبرة أبو عمر (هاي الشغلات ما بتلاقيها بالكتب)
بعد ما طبقنا A* وشوفنا جنودنا بتمشي بذكاء وتتجنب الحيطان، تعلمنا كم شغلة من التجربة حابب أشارككم فيها:
1. اختيار الـ Heuristic المناسب هو مفتاح السرعة
الـ Heuristic هو قلب A*. إذا اخترت Heuristic “سيء” (مثلاً يبالغ في تقدير المسافة)، ممكن الخوارزمية ما تلاقي أقصر طريق. إذا اخترت Heuristic “مثالي” لكن حسابه معقد جداً، رح تصير الخوارزمية بطيئة. “مسافة مانهاتن” ممتازة للشبكات اللي بتسمح بالحركة الأفقية والعمودية فقط، وسريعة جداً.
2. تحسين الأداء (Optimization) ضروري للخرائط الكبيرة
مثال الكود اللي فوق بسيط. في لعبة حقيقية مع خريطة ضخمة وآلاف الوحدات، هذا الكود رح يكون بطيء جداً. أهم تحسين هو استبدال القائمة open_list العادية بـ “طابور الأولوية” (Priority Queue). هاي بنية بيانات متخصصة بتخلي عملية إيجاد العقدة ذات أقل تكلفة f سريعة جداً، بدل ما نلف على كل عناصر القائمة كل مرة.
3. مش بس للمربعات (Not Just for Grids)
A* مش محصورة في الخرائط المكونة من مربعات. هي بتشتغل على أي “غراف” (Graph). في الألعاب ثلاثية الأبعاد الحديثة، ما بنستخدم شبكة مربعات، بنستخدم إشي اسمه “شبكة الملاحة” (Navigation Mesh أو NavMesh). هاي عبارة عن مجموعة من المضلعات اللي بتغطي كل المناطق اللي بنفع نمشي عليها. A* بتشتغل عليها بشكل رائع لإيجاد المسار بين المضلعات.
4. التكلفة المتغيرة (Variable Costs) بتضيف واقعية
في لعبتنا، أضفنا لمسة حلوة. خلينا الحركة في الوحل أو الرمل “تكلفتها” أعلى من الحركة على طريق مرصوف. كيف؟ ببساطة. بدل ما نزيد g(n) بمقدار 1 كل خطوة، صرنا نزيده حسب نوع الأرضية. مثلاً: الخطوة على الطريق تكلفتها 1، والخطوة في الوحل تكلفتها 5. النتيجة؟ صارت الوحدات تتجنب الوحل بشكل تلقائي وتفضل الطرق السريعة، إلا إذا كان الطريق عبر الوحل أقصر بكثير. هذا أعطى عمق استراتيجي رائع للعبة.
الخلاصة: من الفوضى إلى النظام بفضل A* 💡
أتذكر جيداً يوم ما شغلنا اللعبة بعد تطبيق A* لأول مرة. أعطينا أمر لكتيبة كاملة إنها تعبر الخريطة المليئة بالعوائق. وبدل الفوضى السابقة، شفنا الجنود يتحركوا بانسيابية، يلتفوا حول المباني، يختاروا أذكى الممرات، ويوصلوا لهدفهم كأنهم فرقة عمليات خاصة مدربة. كانت لحظة انتصار حقيقية، مش بس لأن الكود اشتغل، بل لأننا حلينا مشكلة معقدة بطريقة علمية وأنيقة.
نصيحتي الأخيرة لكل مبرمج ومطور: لا تخافوا من الخوارزميات. هي مش مجرد نظريات معقدة في الكتب، هي أدوات عملية جداً لحل مشاكل حقيقية. خوارزمية A* هي مثال ممتاز على أداة قوية، ممتعة، ومفيدة جداً، مش بس في تطوير الألعاب، بل في الروبوتات، واللوجستيات، وأي مجال بحتاج إيجاد مسارات ذكية.
يلا يا جماعة، شدوا حيلكم، وخلينا نبرمج إشي مرتب! 🚀
