Multi-threaded Recast-Based A* Pathfinding for Scalable Navigation in Dynamic Game Environments
تقدم هذه الورقة إطار عمل متعدد الخيوط يدمج بين توليد الشبكات القائم على تقنية Recast، وتنعيم منحنيات بيزييه (Bezier-curve)، والتنسيق المدرك للكثافة لتعزيز خوارزمية البحث عن المسار A* القياسية، مما يتيح ملاحة قابلة للتوسع وخالية من الاصطدامات لأكثر من 1,000 وكيل في بيئات ثلاثية الأبعاد ديناميكية مع الحفاظ على معدلات إطارات عالية.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
تخيل أنك مخرج في موقع تصوير سينمائي ضخم وفوضوي. لديك آلاف الممثلين (الوكلاء) الذين يحتاجون إلى الانتقال من مكان إلى آخر دون الاصطدام ببعضهم البعض، أو التعثر بالديكورات، أو العلوق في الجدران. في عالم ألعاب الفيديو، يسمى هذا "تحديد المسار" (Pathfinding).
تقدم هذه الورقة البحثية "حقيبة أدوات للمخرج" لمساعدة هؤلاء الآلاف من الممثلين على التحرك بسلاسة وكفاءة، حتى عندما يتغير موقع التصوير باستمرار. إليك كيف فعلوا ذلك، مقسماً إلى مفاهيم بسيطة:
1. المشكلة: "الشبكة" مقابل "العالم الحقيقي"
تقليدياً، تتحرك شخصيات الألعاب على شبكة غير مرئية ضخمة (مثل رقعة الشطرنج).
- المشكلة: إذا حاولت السير بشكل قطري على رقعة شطرنج، فسيتعين عليك التحرك بشكل متعرج (زيجزاج). هذا يجعلك تبدو آلياً ومتقطع الحركة. وأيضاً، إذا كان موقع التصوير ضخماً، فسيصاب الكمبيوتر بالإرهاق وهو يحاول حساب كل مربع لكل آلاف الممثلين في وقت واحد، مما يؤدي إلى بطء اللعبة (اللاغ/Lag).
2. الحل: خريطة أكثر ذكاءً (رسوم Recast البيانية)
بدلاً من الشبكة الجامدة، قام المؤلفون ببناء "شبكة ملاحة" (Navigation Mesh - NavMesh).
- التشبيه: تخيل أن أرضية منزلك ليست بلاطاً مكوناً من مربعات، بل سجادة ناعمة ومستمرة. الكمبيوتر لا يهتم بـ "المربعات"؛ هو فقط يرى المساحة الأرضية المفتوحة.
- السحر: استخدموا أداة تسمى Recast لمسح العالم ثلاثي الأبعاد تلقائياً ورسم هذه "السجادة" فقط في الأماكن التي يمكن للشخصيات السير فيها فعلياً. إنها تفهم السلالم، والمنحدرات، والأسقف، محولةً عالماً معقداً ثلاثي الأبعاد إلى خريطة بسيطة وسهلة القراءة.
3. المحرك: "خط التجميع" (تعدد الخيوط - Multi-threading)
حساب مسار لشخص واحد أمر سهل. لكن حساب مسار لـ 1,000 شخص في نفس الوقت يشبه محاولة حل 1,000 مسألة رياضية بقلم رصاص واحد.
- الطريقة القديمة: يحاول عقل واحد (خيط المعالجة الرئيسي للكمبيوتر) حل جميع المسارات واحداً تلو الآخر. هذا يجعله يتعب، وتتجمد اللعبة.
- الطريقة الجديدة: بنى المؤلفون "خط تجميع". لقد وظفوا فريقاً من العمال (تعدد الخيوط). بينما يقوم عامل واحد بحساب مسار الممثل الأول، يكون هناك عامل آخر يعمل بالفعل على الممثل الثاني، وثالث يعمل على الثالث.
- النتيجة: اللعبة لا تنتظر. بل تستمر في العمل بسلاسة (محافظة على أكثر من 350 إطاراً في الثانية) حتى مع تحرك 1,000 ممثل في آن واحد.
4. الحركة: من "روبوت" إلى "بشر"
حتى مع وجود خريطة جيدة، يبدو المسار الخام الذي ينتجه الكمبيوتر كخط متعرج بزوايا حادة.
- الإصلاح: أضافوا خطوة "تنعيم".
- القمع (The Funnel): أولاً، يقومون بشد المسار عبر "الممرات" في الخريطة لإزالة التوقفات غير الضرورية.
- منحنى بيزييه (The Bezier Curve): ثم، يحولون تلك الزوايا الحادة إلى خطوط منحنية ناعمة (مثل رسم قوس مثالي باستخدام مسطرة مرنة).
- النتي النتيجة: بدلاً من أن يلتفت الروبوت برأسه بزوايا 90 درجة، تنساب الشخصيات بشكل طبيعي، وتنعطف بسلاسة كما يفعل البشر.
5. التحكم في الحشود: "العين الصقرية" (تحليل الكثافة)
عندما يحاول الكثير من الناس التدافع عبر باب، تحدث الفوضى.
- الابتكار: يمتلك النظام "عيناً صقرية" تراقب مدى ازدحام منطقة ما قبل أن يصل إليها الممثلون.
- كيف يعمل: إذا رأى الممثل أن المسار أمامه أصبح مزدحماً جداً (مثل تشكل ازدحام مروري)، فإنه لا ينتظر حتى يصطدم بالحائط ليتوقف. بل يطلب فوراً من "خط التجميع" مساراً آخر أقل ازدحاماً. هذا يمنع تأثير "التكتل" حيث يتوقف الجميع في وقت واحد.
النتائج: ماذا أثبتوا؟
اختبر المؤلفون هذا النظام في 10 "مراحل" مختلفة، بدءاً من متاهة ثنائية الأبعاد بسيطة وصولاً إلى عالم ثلاثي الأبعاد معقد يحتوي على قوارب متحركة، وأبواب متأرجحة، وآلاف الممثلين.
- السرعة: مع تحرك 1,000 ممثل في نفس الوقت، حافظ النظام على تشغيل اللعبة بسرعة 350 إطاراً في الثانية (سريع وسلس للغاية). أما النظام القياسي فقد كان سينهار ليصل إلى سرعة بطيئة جداً (أقل من 20 إطاراً في الثانية) مع 200 ممثل فقط.
- الواقعية: لم تكن الشخصيات تمشي فحسب؛ بل كانت تتدفق. لقد تجنبوا العقبات، وانتظروا فتح الأبواب، وتنقلوا عبر المنصات المتحركة (مثل قارب يتمايل) دون السقوط.
- الكفاءة: كان النظام ذكياً بما يكفي لمعرفة متى يعيد حساب المسار ومتى يستمر في المضي قدماً، مما وفر طاقة الكمبيوتر.
باخت de مختصر: تصف هذه الورقة طريقة للسماح لآلاف الشخصيات في ألعاب الفيديو بالتحرك عبر عوالم معقدة ومتغيرة دون أن تتباطأ اللعبة أو تبدو الشخصيات كأنها روبوتات خرقاء. لقد فعلوا ذلك من خلال منح الكمبيوتر خريطة أفضل، وتوظيف فريق من العمال للقيام بالعمليات الحسابية، وتعليم الشخصيات كيفية النظر للأمام لتجنب الازدحامات المرورية.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.