السلام عليكم

موضوع ال path finding (ايجاد الطرق) الذي لا يزال يحيرني 🙁 :

في البدابة المح انني هنا لا اود الدخول في انواع التطبيقات الاخري للزكاء الاصطناعي  وانما أفضل ان يكون الحديث كاملا في منظور
برمجة الالعاب والزكاء الاصطناعي للالعاب game AI

حسنا البداية اظنها كالاتي:
انني احاول ان افهم كيف يتم عمل نظام التحكم في ايجاد الطرق لمثال لبيئة معقدة نوعا ما مثل المعروضة في الفيديو الاتي:

حيث اننا نلاحظ ان البيئة تهدف الي ايجاد الطرق لعدد كبير من الوحدات المتحركة بطريقة عشوائية او في مجموعات منظمة مثل طرق
ال flocking and movement coordination

لكني قرأت انه لتحديد وايجاد الطرق هناك عدة عوامل مثل
1- البيئة التي تريد ايجاد الطريق فيها وكيفية تمثيلها برمجيا -- علي هيئة grid ام باستخدام انواع اخري مثل الـ way points والتي
تعتبر ايضا graph ام باستخدام هياكل بيانات اخري مثل navigation mesh 
عموما تم مناقشة موضوع اختيار ال NM بدلا من ال WP في هذا المقال المميز
http://www.ai-blog.net/archives/000152.html
2- نوع البيئة التي سيتم البحث فيها; هل هي ديناميكية ام بيئة لا تتغير؟ هل البيئة متعددة التكلفة للانتقال من مكان لاخر ام ان تكلفة
الانتقال بين اي نقطتين في البيئة تكلفة ثابتة
3- نوع الخوارزم المستخدم للبحث وهنا نري الكثير من الخوارزميات - لكن بالطبع يفضل استخدام الخوارزم حسب الموقف والحالة
التي نريد تطبيق البحث فيها ( يعني حسب نوع التطبيق ).

لكن هناك افكار اخري مثل ايجاد الطرق باستخدام اكثر من طريقة او خوارزم معا وذلك بتقسيم العمل بطريقة هيكلية
راجع البحث Hierarchical Pathfinding and AI-Based Learning Approach in Strategy Game Design
4- عوامل اخري ... للمزيد راجع  http://theory.stanford.edu/~amitp/GameProgramming/

جدير بالذكر ان الاخ وسام ذكر ان هناك طريقة ال points of visibility ؟
اتمني ان يفيدنا احد بالمزيد عنها؟

بعد هذه المقدمة الطويلة (اعتقد اني ذكرت الكثير منها سابقا) اتمني ان تكونوا ما زلتم معي لندخل الي المشكلة التي تواجهني:-
المشكلة هي انه كيف يتم برمجيا اختيار هيكل بيانات مناسب data structure لوصف مثل هذه البيئة terrain متغيرة ال cost
وكيف يتم وضع ان البيئة من المفترض ان تدعم ال multi units وتكون ديناميكية في نفس الوقت بجانب ان خوازرم a star الشهير كان معظم شرحه يعتمد علي دالة H لحساب التكلفة المتوقعة من النقطة الحالية الي لهدف لكن في  بيئة ذات تكلفة ثابتة بين اي نقطتين فكيف يمكن حل هذه المشكلة مع البيئة المذكورة اعلاه او مع graph عادي وغير منتظم بشرط مراعاة ان مكان اللاعب الابتدائي والنهائي متغير بدرجة كبيرة
اثناء ال run time مثل العاب  RTS ؟؟؟؟؟


اتمني لو يقوم احد بذكر كيف تقوم الالعاب الاسترتيجية RTS بعمل طرق البحث الخاصة بها مثل Red Alert مثلا او هذه الانواع
من السلاسل وايضا مثل لعبة قريش ؟


في انتظار الافكار والملاحظات 😒
وجزاكم الله خيرا

ضمن المراجع التي لدي أعتقد أن الـ Visibility Points ماهي الا تسمية أخرى للـ Visibility Graph والتي تعتبر الحالة المبسطة من الـ Visibility Maps.
تستخدم طريقة الـ Visibility Graph عادة في حل المسائل التي يمكن التعبير فيها عن العوائق ضمن فراغ الوضعيات (Configuration Space) على شكل مضلعات (Polygons) ذات عدد محدود من الأضلاع.
أي في حال كانت لديك عوائق بعدد لانهائي من المضلعات - أو ببساطة عوائق ذات اشكال دائرية - عندها لا تعتبر هذه الطريقة من الطرائق المناسبة لانشاء مخطط البحث (Graph).
يعتمد مبدأ عمل هذه الطريقة بداية على اعتبار عقد (vertices) المضلعات المشكلة للعوائق هي عقد في الـ Graph المطلوب البحث ضمنه. وبناءً عليها يتم الوصل بين هذه العقد بحواف (edges) في حال كانت العقد مرئية بشكل مباشر فيما بينها. أي لابد من يكون المستقيم المنتهي الواصل بين أي عقدتين غير قاطع لأي من المضلاعات الأخرى المشكلة للعوائق.
الأشكال التالية توضح هذه الفكرة:







طبعاً كما هو واضح من الأشكال السابقة، تولد هذه الطريقة عدد لا بأس من المسارات (الحواف) الغير مفيدة في عملية إيجاد المسار، لذلك أنت بحاجة للقيام بعملية تنظيف للنتائج التي حصلت عليها. بالطبع يمكنك يمكنك تطوير خوارزمية بسيطة للقيام بعملية إزالة هذه الشوائب ولكن هناك عدد جيد من الطرق الفعالة والجاهزة التي تقوم أولاً بتصنيف المسارات ثم إزالتها للحصول على مخطط بحث نظيف. أحد طرق التصنيف المشهورة والمستخدمة مع طريقة الـ Visibility Graphs هي تصنيف الحواف الى صنفين كالتالي:
- حواف داعمة (Supporting Edges): وهي الحواف التي تشكل مماس مع مضلعين من نفس الجهة.
- حواف فاصلة (Separating Edges): وهي الحواف التس تشكل مماس مع مضلعين من جهتين متقابلتين.
الشكل التالي يوضح الفرق بين التصنيفين:



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







الآن يمكنك استخدام أي خوارزمية بحث تناسبك (A*, Breadth First, … etc) للقيام بعملية ايجاد المسار ضمن مخطط البحث الناتج لديك من طريقة الـ Visibility Graphs والذي يعتبر Graph قياسي.
بقي لدينا نقطة صغيرة في طريقة الـ Visibility Graphs ولكنها هامة وأساسية بالنسبة للأداء وهي كيفية الطريقة الأفضل لتحديد العقد المرئية فيما بينها للوصل بينها؟
طبعاً يمكننا استغلال الآلة وجعلها تختبر التقاطع بين جميع القطع المستقيمة v-vi المنطلقة من العقدة المدروسة v لباقي العقد vi مع جميع أضلاع العوائق الموجودة لدينا O(n)، وتكرار العمل على جميع العقد v1,v2,…vn. ولكننا بهذه الطريقة سنواجه مسألة من الدرجة O(n^3) والتي تعتبر مسألة مملة حتى بالنسبة للأجهزة الصبورة التي لا تبادر بالاحتجاج.
لذلك من المفيد أيضاً هنا محاولة البحث عن خوارزمية للقيام بهذا الاختبار ولكن بشيء من الذكاء. سأترك لك هذه المسألة التفصيلية للحل في حال أعجبك مبدأ الـ Visibility Graphs بشكل عام.
 
* مرجع الصور التوضيحية:
Principles of Robot Motion: Theory, Algorithms, and Implementations (Intelligent Robotics and Autonomous Agents)
من نشر MIT Press وتأليف: Howie Choset, Kevin M. Lynch, Seth Hutchinson, George Kantor, Wolfram Burgard, Lydia E. Kavraki, Sebastian Thrun

السلام عليكم

اولا: كل عام وانتم بخير 😄
شكرا استاذ همام علي الشرح الرائع


اعتقد انها تشبه جدا ال Navigation Mesh ولكنها بذلك ايضا تعبر بديل مقارب جدا لل: Way Points
او قل انها طريقة لانشاء ال  way points graph
هذا المقال يقوم بذكر مميزات مثل طريقة ال navigation mesh عن طريقة ال Way Points
http://www.ai-blog.net/archives/000152.html

لكن ماذا عن البيئات الكبيرة جدا مثل terrain للعبة RTS ؟
هل تعتقد ان افضل طريقة لمعالجة مثل هذه البيئات هي ال hierarchical path finding والتي ربما تكون هذه الطريقة احدي خطواتها ؟

بصراحة مازلت اجد ان طرق البحث التقليدية والمشهورة مثل a star معقدة نوعا ما للبحث بها اذا اعتمدنا علي graph
لوصف البيئة وخصوصا اذا كانت هذه ال graph غير منتظمة في شكلها فيصعب تحويلها الي grid
وذلك ليتم استخدامها في مصفوفة من ال nodes

اتمني ان تكون هناك طريقة لوصف البيئات الكبري مثل terrain في شبكة grid بسيطة التكوين وياريت لو يتم وصف كل عقدة nodes
فيها بشكل مبسط ويكون واقعي للاستخدام في بيئات ال RTS
؟؟؟؟؟؟؟؟؟؟؟؟؟

شكرا لك اخي همام واعتذر عن الازعاج لكن كما تري حضرتك من الفيديو المذكور في اعلي الصفحة
وهو ما اريد عمل مثله لمشروع التخرج فهو بيئة كبيرة جدا وسيكون الاداء مهم جدا
اعتقد ان طريقة  visibility points المذكورة محل اهتمام كبير من ناحية البحث بطريقة high level بين المدن المختلفة مثلا
لكن الا تعتقد انه ان كانت الخريطة التي تصف البيئة المراد عملها محددة مسبقا فلا داعي لعمل خوارزم يقوم باستنتاج النقط ويقوم بانشاء
ال  visibility map حيث ان ذلك ربما يكون مهم في برنامج محرر يستخدمه مبرمج الذكاء الاصطناعي.

حاليا انا سأذاكر كورس ال  game institute
والخاص بالذكاء الاصطناعي

جزاك الله خيرا وشكرا لكم 😄

 
كلا، هي ليست الـ Way Points Graph (والتي لا تنفع أساساً لبيئة ديناميكية كما هو الحال في لعبة RTS)، التشابه الوحيد بين الـ Points of Visibility والـ Way Points Graph هو أن الـ Points of Visibility أيضاً تعمل على مبدأ العقد وليس الخلايا.
وهي تماماً الخوارزمية التي شرحها همام (visibility graph).
 
يمكنك القراءة عنها في كتاب Game Programming Gems 2 (المقالات 3.9 و 3.10 للمؤلف Thomas Young):
 
http://www.amazon.com/gp/reader/1584500549/ref=sib_dp_bod_toc?ie=UTF8&p=S002#reader-link
 
في حالة قريش كان استخدام هذه الخوارزمية أسرع من تطبيق A* على الخلايا بشكل مباشر، حيث أن المساحات شاسعة والأبنية لها محيط مستطيل دائماً، وبالتالي سهل جداً توليد العقد حول الأبنية وربطها ببقية المخطط (للأسف لا أملك نسخة debug من اللعبة، حيث كنت أستطيع إظهار مخطط العقد أثناء اللعب).
 
من أهم مزايا هذه الطريقة أنها غير متعلقة بمساحة الأرض، فيمكنك ببضعة عقد إيجاد الطريق في مساحات شاسعة. في الحقيقة تزداد كلفة الحسابات مع انتثار الزوايا في الموقع. بينما في بنية شبكة منتظمة من الخلايا، فإن الكلفة تزداد مع اتساع المساحة.
 
نقطة هامة أخرى هي أن هذه الخوارزمية قادرة على الإجابة فقط عن السؤال: أعطني طريقاً من هذه العقدة إلى تلك.
أما عن كيفية معرفة إن اصطدمت الوحدة بمكان مسدود، فهذا لا يدخل ضمن عملها.
 
 
 


لاحظ أن في هذه الألعاب (الجيل الجديد من C&C و Age of Empires) فإن اللاعب يضع الأبنية بشكل حر تماماً ومستمر، وليس مكمماً على خلايا، مما يجعل التعبير عن العالم ببنية خليوية أمراً غير مفيد. 
في Age of Empires 2 وقريش، تم استخدام ما تدعوه hierarchical path finding، وإن كان على طبقتين فقط، الطبقة الأولى توجد الطريق دون الأخذ بعين الاعتبار العوائق المتحركة (الوحدات الأخرى)، أما الطبقة الثانية فتعمل لحل الطرق مع العوائق المتحركة (وحل هذه المشكلة ليس بالأمر السهل على الإطلاق).
 
أما C&C فإن إيجاد الطرق بها لم يشتهر بالنجاح أساساً، لذلك لا أنصح باتخاذه قدوة في العمل. يظهر هذا الضعف خصوصاً في الأجزاء الأخيرة (Tiberium Wars و Kane's Wrath)، وهو أمر معيب بالنسبة لسلسلة عريقة مثل C&C.
 
أخيراً، فإن WarCraft3 كانت تطبيقاً كلاسيكياً على بنية خليوية، ونتائج إيجاد الطرق فيها ناجحة للغاية، إلا أن اللعبة لا تقوم بتحريك أعداد غفيرة من الشخصيات إذا قورنت مثلاً بـ Age of Empires.
 
 
 


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




كما ذكرت، في هذه الحال أنت تحتاج إلى وصف للبيئة غير مرتبط بمساحتها، وفي هذا المضمار تستطيع استخدام points of visibility أو أي بديل له نفس المزايا.

تعقيباً على تطبيق خوارزمية (Waypoints) مع A*، مقطع الفيديو التالي يوضح مثال تطبيقي مشروح لكيفية تطبيق كل من A* والـ Waypoints في بيئة ثنائية البعد لعدد غير محدد من الشخصيات.
 
http://webrel2.softimage.com/open/video/xsi7/01_Crowds_Navigating_Waypoint_Graphs.flv
 
الجميل في هذا المقطع التعليمي أنه جميع مراحل تطوير الخوارزمية يتم ضمن بيئة (Interactive Creative Environment) الجديدة في الـ XSI 7 والتي تمثل بيئة البرمجة المرئية (Visual Programming Language)، لذلك فإن عملية تتبع آلية عمل الخوارزمية للأكاديميين غير المبرمجين أسهل عليهم من رؤية مئات الأسطر من الكود البرمجي 😒
 
النقطة المميزة في هذا المقطع التعليمي أنه يعالج حالة أكثر من هدف بطريقة مرنة مميزة ولكنه لا يعالج مشكلة مسألة كشف تصادم الشخصيات فيما بينها، ولكنه يبقى في رأيي مفيد كبداية لأخذ فكرة عملية عن كيفية تطبيق مثل هذه الخوارزميات.