السلام عليكم،
 
قرأتُ مقالة ياسر جفال عن محركات الألعاب متعددة المسارات، وقد استفدتُ منها كثيراً... لذلك وجب الشكر والامتنان 😄
 
أنا حالياً أقوم بدراسة أكاديمية عن هذا الموضوع أيضاً، لذلك فإن أية أفكار نتداولها هنا ستكون ذات فائدة مباشرة لي... لذلك أودّ دعوة الجميع ولا سيما الأخ ياسر جفال لنقاش هذا الموضوع وتبادل المعلومات والخبرات والأفكار... وسأبدأ أنا هنا إن شاء الله...
 
 
مما لا شك فيه هو أن المحركات متعددة المسارات أصبحت ضرورية للألعاب التي تحوي حسابات معقدة ناجمة عما تحاول تقديمه وإظهاره للاعبين. ومن خبرتي الشخصية بالتعامل مع عدد من المحركات حتى الآن القديمة منها والحديثة، وجدتُ أن السمة العامة هي أن التعقيد يزداد في أغلب نواحي البرمجة عند إدخال عامل تعدد المسارات.
 
فبدءاً من التنسيق بين المهمات وإدارة الوصول إلى الموارد المشتركة، ومروراً بتتبع الكود وفهمه، وانتهاءً بعملية التنقيح وتتبع الأخطاء ومحاولة إعادة توليدها لكشفها... كل هذا يتحول إلى كابوس مقيم.
 
البعض يضع اللوم على لغة البرمجة، وقد بدأت الأنظار بالفعل تتطلع للغات برمجة بديلة (كاللغات الوظيفية مثل هاسكل وإف شارب) تعين على كتابة كود مفهوم وسهل التنفيذ على مسارات متعددة... لكن كل ذلك هو مجرد آمال حتى الآن، ولم أجد لعبة تجارية واحدة حتى الآن كـُتبت بغير سي بلس بلس أو سي البحتة... فهذا يبقى احتمال: إن لغة برمجة بديلة ستعين على تحسين الوضع. وأعتقد أن هناك أبحاثاً في هذا الصدد في مجال محركات الألعاب حصراً (أحدها ضمن قائمة المراجع في مقالة ياسر جفال).
 
ما رأيكم؟ أرجو أن يشاركنا الجميع خبرتهم في عوالم تعدد المسارات.. سواء الأكاديمية منها أو المهنية...
 
والسلام عليكم ورحمة الله

و عليكم السلام و رحمة الله،

لقد قرأت المقالة أيضاََ ووجدتها مفيدة و تُقدّم للقارىء موضوعاََ معقداََ بشكل يسير و شرح وافي. الشكر للأخ ياسر.

خبرتي مع البرمجة المتوازية محدودة. تعلمنا بعض الخوارزميات المتوازية في الجامعة، كما تعلمنا عن القطاعات الحرجة و الاستثناء التبادل في مادة نظم التشغيل. خلال دراسة الماجستير قمت بتسجيل مادة عن البرمجة المتوازية و لكنها ركزت أكثر على الحوسبة الموزعة على عدة حواسيب مرتبطة بشبكة، و لم تركز على البرمجة متعددة المسارات بشكل محدد. أطروحة الدراسات العليا التي أقوم بالعمل عليها حالياََ تتمحور حول استخدام معالج الرسوميات لأغراض متعددة (GPGPU)، و لذا فأنا أقوم بتعلم المزيد عن الحوسبة المتجهة، و لكنها مختلفة عن البرمجة متعددة المسارات لأن معالج الرسوميات مصمم للقيام بعملية واحدة على بيانات كثيرة في نفس الوقت، و لذا فأن هذا النوع من البرمجة أسهل قليلا حيث أن كل برنامج يتم معالجته على رأس أو بكسل على حدة دون القلق بشأن التواصل و التزامن بين وحدات المعالجة المختلفة. لقد قمت بكتابة خوارزمية A* بشكل متوازي باستخدام واجهة MPI كمشروع لمادة البرمجة المتوازية و لكن لم أستطع الحصول على نتائج جيدة لأن طبيعة الخوارزمية لا تستفيد كثيراََ من البرمجة المتوازية (العثور على طريق معين إلى نقطة ما) و لو كنت كتبت البرنامج بشكل إستكشافي (العثور على طريق إلى أقرب نقطة من عدة نقاط) بحيث كل مسار يبحث في طريق مختلف لكنت حصلت على نتائج أفضل.

المشروع الثاني الذي إستخدمت فيه البرمجة متعددة المسار هو محرك اللعبة التي أقوم بتصمميها لهواتف غوغل أندرويد Android المحمول. في نظام أندرويد دالة قلب الإطارات buffer swap توقف البرنامج حتى يتم معالجة جميع أوامر الأوبن جي أل OpenGL و إرسالها لمعالج الرسوميات. لقد وجدت أنه خلال الوقت الذي يقف المسار و ينتظر انتهاء الدالة، أستطيع القيام بأشياء أخرى في مسار مختلف كتحديث الكائنات و حساب الإطار التالي. للقيام بذلك إحتجت أن أقسم المحرك لثلاثة مسارات: مسار واجهة المستخدم الذي يستقبل أوامر المستخدم، مسار المنطق حيث يتم قراءة ملفات الإعدادات و حساب و تحديث حالة اللعبة لكل إطار، إضافة لمسار الرسوميات و الذي يحتوي أوامر أوبن جي أل و دالة قلب الإطارات. طبعاََ المشكلة أنك تحتاج طريقة للتخاطب بين المسارات المختلفة. بشكل خاص، تحتاج أن تجد طريقة لبناء مجموعة من الأوامر في مسار المنطق و نقل هذه الأوامر لمسار الرسوميات. لقد قمت باستعمال طابور queue من أوامر الرسم. مسار المنطق يقوم بإضافة الأوامر إلى نهاية الطابور يينما مسار الرسوميات يقوم بمعالجة هذه الأوامر واحداََ تلو الآخر. هناك بعض التأخير لأنني لا أستطيع السماح لمسارين أن يستعملا الطابور في وقت واحد و لكن بشكل عام فإن النتيجة أفضل كثيراََ من استعمال مسار واحد. كما أنني أحب كيف أن الفصل بين المنطق و الرسوميات قد جعل تصميم المحرك أكثر... وحدوية (هل هذا هو المصطلح المناسب ل  ؟modular design). عموما لا أريد أن أنسب الفضل كله لنفسي، فالفكرة جائت بشكل مباشر من هذه المقالة http://replicaisland.blogspot.com/2009/10/rendering-with-two-threads.html التي كتبها أحد موظفي شركة غوغل. إلا أنني لم أستعمل ما كتبه و قمت بكتابة كل شيء بنفسي لأنني أحب أن أفهم أي جزئية أساسية من تصميم محرك اللعبة. بشكل عام فإن برمجة هذا النظام متعدد المسارات أخذ الكثير من الوقت و المحاولات (و تتبع أخطاء غريبة جداََ) و لكن التجربة كانت مفيدة و علمتني المزيد عن الموضوع.

اللغات الدالية مناسبة للبرمجة المتوازية لأن الدوال أو الوظائف في هذه اللغات تقابل الدوال الحسابية و ليس لها آثار جانبية. في C++ أي دالة قد تقوم بتغيير قيمة متغير عالمي أو كائن وحيد singleton و هذه الآثار الجانبية من الصعب التعامل معها في البرمجة المتوازية (تحتاج قطاعاََ حرجاََ حول كل تغيير). مع هذا، فإنني لا أعتقد أن هذا كاف لجعل الشركات تستعمل اللغات الدالية. حسب ويكيبيديا، فشركة ناوتي دوغ Naughty Dog  المعروفة بسلسلة كراش بانديكوت قد استعملت لغة ليسب LISP في السابق و لكن مع انتقالهم إلى الجيل الحالي بلعبة Uncharted قاموا باستعمال C++ لأن من الصعب الحصول على أفضل النتائج من نظام معقد كالبلايستيشن 3 بدون كتابة كود بلغة مثل C أو C++. البلايستيشن 3 مثال على نظام يتطلب البرمجة المتوازية حيث معالج الخلية أو سل Cell Processor يحتوي 8 أو 7 معالجات متخصصة كما أتذكر مما قرأت و تحتاج لتوزيع العمل على هذه المعالجات للحصول على نتائج جيدة (يقولون أن لعبة غران توريزمو 5 تقوم برسم 60 إطار بحجم 1080 في كل ثانية، هذا شيء مخيف!). إكس بوكس 360 لديه 3 معالجات و يستفيد من البرمجة متعددة المسارات أيضاََ.

لقد كنت أقرأ نقاشاََ حول حلقة الألعاب game loop هنا http://www.reddit.com/r/programming/comments/akmli/ask_proggit_how_do_professional_game_loops_work/ و شدت انتباهي المشاركة التالية:

There is no such thing a 'game loop' in contemporary game architectures.
A modern game more resembles a real-time operating system than a
typical program. It has a kernel, scheduler, multiple memory managers,
multiple processes (each with multiple micro-threads), static and
dynamic services, and asynchronous/lazy communications. There isn't a
single main loop, or even really a concept of one; just as there is no
'mainloop' in windows or linux.
The days of the for (;;) { input(); network(); ai(); physics();
render(); } are well and truly over for professional game systems.
كم ترون فالكاتب يقول أن محركات الألعاب الحديثة أشبه بأنظمة التشغيل من حيث التعقيد و تقسيم المهام. قانون مور Moore's Law و الذي وضعه في ستينات القرن الماضي تنبأ بتضاعف سرعة الحواسب كل سنة، و لكن هذا التضاعف لم يعد عملياََ حيث مع زيادة عدد الموصلات في الشريحة تزداد الحرارة و يصعب تبريد المعالج. لذا فالشركات مثل إنتل و أي إم دي تقوم بإنتاج معالجات مزدوجة و رباعية الآن. كما أشار الأخ ياسر جفال، هناك العديد من الأبحاث التي تحاول العثور على طرق لجعل البرمجة المتوازية أسهل للمبرمج العادي (المساكين مثلي و مثلك الذين يصابون بالصداع عند تتبع مسار واحد، ناهيك عن عدة مسارات 😢 ). المستقبليات و الوعود Futures and Promises* هي أحد هذه الطرق التي قد تلقى نجاحا في المستقبل. المتغير المستقبلي لا يحوي قيمة و إنما هو عبارة عن وعد أنه ستكون هناك قيمة في المتغير عندما تنتهي معالجة مسار آخر. النسخة القادمة من لغة C++ تدعم هذا النوع من البرمجة بالإضافة إلى ميزات أخرى ستسهل البرمجة المتوازية. لغة غو Go من غوغل أيضا لديها أسلوب مبتكر للتعامل مع هذا النوع من البرمجة http://en.wikipedia.org/wiki/Go_language#Concurrency . إذا كنت من المهتمين بهذه المواضيع فأني أقترح قراءة سلسلة مقالات هرب سوتر Herb Sutter عن البرمجة المتوازية: http://herbsutter.com/2010/09/24/effective-concurrency-know-when-to-use-an-active-object-instead-of-a-mutex/ ، هذه أحدث مقالة و لكن إذا نزلت لآخر الصفحة ستجد وصلات إلى كل مقالاته عن الموضوع.

لقد كتبت الكثير لأن الموضوع كبير و شيق (كما أنه تدريب جيد لمسابقة الخليفة المأمون ☺ )، و لا أريد أشعركم بالملل. لذا سأتوقف الآن، و أنتظر المزيد من مشاركاتكم و أفكاركم و خبراتكم. شكراََ على المقالة مجدداََ أخ ياسر جفال، و شكراََ على طرح الموضوع أخ وسام البهنسي. و كل عام و أنتم بخير 😄

* http://en.wikipedia.org/wiki/Future_%28programming%29

هذا مثير للاهتمام. ربما خوارزمية "المحيط-أولاً" (breadth-first) أنسب للتطبيق في هذه الحالة؟
 



هذا مشابه للحل الذي استخدمتُه في مشروع وحدة رسم الخرائط (مشابهة لجوجل إيرث). حيث يجب أن يستمر الرسم وتستمر الحركة أثناء تحميل الموارد والصور وتحسين جودتها. لكن الطابور في حالتي لم يكن مؤلفاً من أوامر، وإنما من "أسطر برمجية" يتم تكديسها في طابور يستهلكه مسار الرسم. الميزة الجميلة في هذا الأسلوب هي أن الكود الذي تريد أن تنفذه في المسار الثاني يقبع مع نفس كود الإجراء الذي يولد الأمر، وبالتالي فإن متابعة الكود سهلة وواضحة. 



وحدوية... ممم... كنتُ في جلسة مع بعض الأصدقاء اليوم وسألتهم عن المقابل العربي لهذا المصطلح... واحدٌ منهم أعطى نفس الكلمة "وحدوية" ☺   البقية لم يعطوا أي مقابل!



لا تغرنك الأرقام. الكثير من الألعاب ترسم بدقة أقل وتقوم بتحجيم الصورة النهائية لتغطي 1080 بيكسل ارتفاعاً. بين البلايستيشن 3 والإكس بوكس 360، في EA (والكثير من الشركات الأخرى) توجد إشاعة تقول: برمج لعبتك لتعمل بالسرعة المطلوبة على البلايستيشن 3 ونحن نضمن لك أن تعمل بسرعة مكافئة أو أسرع على الإكس بوكس 360. تحقق هذا في لعبة بيرن آوت بارادايس Burnout Paradise وكانت النتيجة مرضية. 



أوافقه وبشدة. 
 
شكراً جزيلاً على الروابط... بعضها يستحق القراءة فعلاً!
 
السلام عليكم...

هذا صحيح. أعتقد أن خوارزمية A* وحيدة المسار ممتازة كما هي لهدف العثور على طريق إلى نقطة محددة، جعلها متوازية لا يفيد كثيراََ إلا اذا كان مساعد الاستكشاف heuristic (أي أفكار لترجمة هذا المصطلح؟) سيئاََ أو اذا أردت العثور على أكثر من طريق في وقت واحد، و لكن استعمال خوارزمية المحيط أولاََ أو خوارزمية ديكسترا له بعض التطبيقات مثل العثور على أقرب عدو حول اللاعب أو العثور على أقرب نقطة تغطية cover لتطبيقات الذكاء الصناعي في بعض الألعاب. هذا النوع من البحث من الأسهل ترجمته إلى خوارزمية متعددة المسار.




مما فهمته من كلامك فأعتقد أننا نتحدث عن شيء مشابه. الأوامر التي تكلمتُ عنها هي كائنات تنحدر من واجهة DrawCommand و التي لديها وظيفة معالجة process(). الفكرة أنك لكل أمر تكتب كائناََ يعبر عن الأمر و يحتوي على كل المعلومات اللازمة لتنفيذ الأمر. مسار الرسوميات يقوم بمناداة وظيفة المعالجة على كل كائن في طابور الأوامر. بدورها الوظيفة تحتوي على أسطر برمجية يتم تنفيذها. معظم كائنات الأوامر معزولة عن نظام الرسم و الممثل بكائن آخر للرسوميات Graphics و الاسطر في وظيفة المعالجة تنادي وظائف في هذا الكائن، و الذي يتم تخصيصه إلى رسوميات اللوحة CanvasGraphics و رسوميات أوبن جي إل OpenGLGraphics ليسمح بأكثر من واجهة واحدة للرسم (Canvas في أندرويد شبيه بGDI في وندوز). قد يبدو الأمر معقداََ و لكن كائنات الأوامر بسيطة بشكل عام و لا أحتاج لكتابة أكثر من نسخة اعتماداََ على نوعية واجهه الرسوميات المستخدمة.





 هذا مثير للإهتمام جداََ. أنا أعترف أنني من المعجبين بجهاز البلايستيشن 3، و إن كنت محقاََ بشأن أن معظم الألعاب متعددة المنصات بنفس السرعة أو أسرع على الإكس بوكس 360. و لكن في حالة لعبة غران توريزمو أعتقد أنهم يقومون بالاستفادة من قدرات البلايستيشن أكثر من الألعاب التي تصدر على أكثر من جهاز. من المحتمل كثيراََ أنهم يحجمون الصورة، لقد فعلوا ذلك في نسخة prologue، و لكن حتى هذه النسخة كانت 1280x1080 (المصدر http://forum.beyond3d.com/showpost.php?p=1078611&postcount=583) و في هذا الفيديو http://www.gametrailers.com/video/e3-2010-gran-turismo/700195 أحد المنتجين يقول أن حتى عند اللعب على تلفاز ثلاثي الأبعاد فأن الدقة (و إن كانت محجمة) هي 1080 أيضاََ. عموماََ، هذا خارج نطاق الموضوع و لكن النقطة التي أحببت توضيحها هي أنك لا تستطيع نقل لعبة ذات مسار واحد كما هي للبلايستيشن 3 (أو حتى الإكس بوكس 360) و تتوقع أن تحصل على نتائج جيدة، نرى ذلك في كثير من الألعاب القديمة للجهاز و التي لم تستفد من القدرات المتوازية للمعالج مقارنة بألعاب مثل غران توريزمو، أنتشارتد 2 أو كِلزون. طبعاََ هذا رأيي كلاعب و قد يكون الأمر مختلفاََ من منظورك كمبرمج ذو خبرة بالتعامل مع هذه الأجهزة. 😄

ماذا عنك يا أخ وسام. هلا حدثتنا المزيد عن خبرتك الشخصية مع المحركات متعددة المسار. الأمر يتحول إلى كابوس كما قلت و لكن لا مفر من التعامل مع المسارات المتعددة. لقد قرأت أن العديد من الألعاب تستخدم مساراََ خاصاََ بالفيزياء، إضافة إلى حوض للمسارات thread pool حيث يتم اضافة أوامر إليه ليتم تنفيذها في نفس الوقت. مكتبة OpenMP مستخدمة في بعض البرامج حيث يمكنك استعمال أوامر قبل المعالجة preprocessor directives لتقول مثلا أن حلقة for القادمة يجب تنفيذها بشكل متوازي و ستقوم المكتبة ببناء مسارات قد تصل الى مسار واحد لكل تكرير iteration جاعلاََ الحلقة التي تأخذ س من العمليات تنتهي في عملية واحدة (بافتراض توفر عدد كافي من وحدات المعالجة طبعاََ). هذا مختلف عن أسلوب مكتبة MPI حيث تستعمل بعض الوظائف و الدوال لتبعث و تستقبل الرسائل بين نسخ متعددة من نفس التطبيق، و هذا الأمر بشكل عام أسهل من استخدام تطبيق واحد بمسارات متعددة (لا تتم مشاركة المتغيرات) و لكنه قد يكون ابطأ و ملائم أكثر للحوسبة الموزعة و ليس متعددة المسارات على حاسوب واحد (مع أنك يمكنك استخدامها على حاسوب واحد إذا أردت و كل تطبيق سينفذ على وحدة معالجة مركزية مختلفة).

نعم صحيح. الفارق في التنفيذ فقط. كمثال:

// هذا الحدث يتم نداؤه عند الانتهاء من تحميل بيانات من الإنترنت
void StreamManager::OnDataLoaded(int streamID)
{
  // جلب خصائص البيانات المحملة
  void *data = getStreamData(streamID);
  uint dataSize = getStreamSize(streamID);
  DataType type = getStreamType(streamID);
 
  if (type == Type_Image)
  {
     // تم تحميل صورة. أرسلها لمسار الرسم كي يتم إنشاؤها على جهاز دايركت ثري دي
     BEGIN_RENDER_COMMAND_3PARAM(int,streamID,void*,data,uint,dataSize)
     {
       // نحن الآن في مسار الرسم. فلننشئ الإكساء الذي سيحفظ الصورة
       Texture *texture = renderer->createSquareTexture(dataSize);
       void *textureData = texture->lock(); // قفل الإكساء
       memcpy(textureData,data,dataSize); // ملؤه بالبيانات
       texture->unlock(); // فك القفل
       renderer->setGlobePatchImage(streamID,texture); // تسجيل الصورة مع نظام الرسم لتظهر في اللقطة القادمة


     }
     END_RENDER_COMMAND;
 
     // نحن في المسار الرئيسي هنا... عند هذا السطر تكون الأسطر أعلاه قد دخلت في طابور التنفيذ
     // لكنها لم تنفذ بعد بالضرورة...

  }
}

 
 
والماكرو BEGIN_RENDER_COMMAND_3PARAM يقوم بإنشاء صنف وكائن من هذا الصنف وإضافته في طابور الرسم للتنفيذ. الفكرة فقط تكمن في أن الصنف ليس ظاهراً ولا يحتاج المبرمج لأن يشغل باله بهذه التفاصيل "الميكانيكية" وإنما فقط يكتب السطور التي يود أن ينفذها في مسار الرسم.




الحالة القائمة الآن في البرمجة المتوازية في الألعاب تعتمد على نظام شبيه بذلك الذي ذكرته في إحدى مراجعك... كود يقوم بتوليد مهام، وهذه المهام قد تعتمد على بعضها البعض، ويوجد منظــّم يقوم بتنفيذ هذه المهام على المعالجات الغير مشغولة. في كل الحالات التي تعاملتُ معها كان هذا المنظم مبنياً وفقاً لمبدأ "سرقة العمل" (work stealing). حيث أن كل معالج له طابور من المهمات الخاصة به، وفي حال أنهى مهامه قبل الآخرين، فإنه "يسرق" مهام من طوابير المعالجات الأخرى. تقدم سوني مكتبة SPURS لتنفيذ هذا النظام من العمل على البليستيشن 3. 
 
هو أسلوب لطيف للبرمجة، لكن عند النظر إلى الكود ستجد العديد من التعقيدات الميكانيكية الخاصة بإنشاء هذه المهام وتجهيزها للعمل. ثم إن تقرير أي الأجزاء من الكود يجب أن ينقل إلى "مهمة" هو أمر غير واضح هو الآخر. هذه حالة خاصة في البليستيشن 3، حيث أنك تجد أنهم ينقلون جزءاً من الحسابات ليعمل على المعالجات المساعدة (SPUs) لكنه سيعمل ببطء أكثر بسبب خصائص هذه المعالجات. النتيجة أن العائد من التنفيذ على التوازي ليس مجدياً، وقد تحصل على سرعة مضاعفة فقط مقابل تشغيل 6 معالجات مساعدة في نفس الوقت لإنجاز الحسابات، مما يعتبر هدراً في الطاقة لو سألتني رأيي.. لكن النتيجة النهائية طبعاً زيادة في سرعة الأداء.  يجب وضع مبادئ لتحديد هذه العملية، وهذا يقع على عاتق الجانب الأكاديمي.