كيفية تسريع * Pathfinding مع خوارزمية البحث السريع

Pathfinding هو موجود في كل مكان في الألعاب. لذلك من المهم فهم الدلالات الموجودة عند استخدام الخوارزميات مثل A *. سنقوم في هذا البرنامج التعليمي بتغطية طريقة جديدة نسبياً للبحث في العوالم القائمة على الشبكة: Jump Point Search ، والتي يمكنها تسريع A * بأوامر من الحجم.

ملاحظة: على الرغم من كتابة هذا البرنامج التعليمي باستخدام AS3 و Flash ، يجب أن تكون قادرًا على استخدام نفس الأساليب والمفاهيم في أي بيئة تطوير ألعاب.

يعتمد هذا التطبيق على الورقة الأصلية والمادة على JPS التي تم العثور عليها هنا: Jump Point Search. ال
الاستُخدم تطبيق Lua ، وهو تطبيق Jumper ، للمساعدة في بعض أجزاء التطبيق.al

قفزة نقطة بحث تجريبي

انقر على رمز SWF لمنحه التركيز ، ثم حرك الماوس على المناطق غير المحظورة في الخريطة لجعل محاكي NPC يحاول الوصول إليها. اضغط على مفتاح المسافة للتبديل بين A * و Jump Point Search وكلتاهما.

لا يوجد فلاش؟ تحقق من فيديو يوتيوب بدلا من ذلك:

Faster A* Pathfinding With Jump Point Search (Demo)

اقامة

يستخدم تطبيق العرض التوضيحي أعلاه AS3 و Flash مع إطار Starling لرسالة GPU المتسرعة ومكتبة المضلع ds لهياكل البيانات.

الاستطلاعية

غالبًا ما يستخدم Pathfinding في ألعاب الفيديو ، ومن المؤكد أنك ستصطدم بها في مرحلة ما أثناء مسيرتك في تطوير اللعبة. استخدامه الأساسي هو إعطاء سلوك حركة ذكي المظهر للكيانات الاصطناعية (NPCs) ، لتجنبها تتصادم مع الأشياء (في كثير من الأحيان).

في بعض الألعاب ، تتعرض الصورة الرمزية للاعب أيضًا لتوجيه المسار (ألعاب استراتيجية ، والعديد من ألعاب RPG وألعاب المغامرة من شخص ثالث). لذا قد تفترض أن مشكلة مسار الطريق قد تم حلها ، ولكن للأسف ليس هذا هو الحال ؛ لا يوجد رصاصة فضية يمكنك استخدامها فقط.

وحتى في ألعاب AAA الكبيرة ، ستظل تجد أشياءً مضحكة مثل هذه:

L.A. Noire (PS3) - Glitch - Pathfinding FAIL

قد لا يكون هناك رصاصة فضية ، لكن هناك رصاصة: خوارزمية A * (نجم). في هذا البرنامج التعليمي ، سنشاهد نظرة عامة موجزة عن A * وكيفية تسريعها باستخدام خوارزمية أخرى ، Jump Point Search.

أولاً ، نحتاج إلى طريقة لتمثيل عالم الألعاب بطريقة يمكن لخوارزمية pathfinding استخدامها.

ممثلات العالم

واحدة من أهم الأشياء التي يجب مراعاتها عند التفكير في تحديد مسار لعبتك هو تمثيل عالمي. كيف يتم تنظيم البيانات الخاصة بالمناطق والعقبات المقبولة مع هياكل البرمجة في الذاكرة؟

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

تمثل البكسلات السوداء في الصورة الخلايا المحظورة.

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

البيانات الأخرى التي يمكن تخزينها في تمثيل الخريطة هي تكاليف: ما هي تكلفة السفر من عقدة إلى أخرى. يمكن استخدام هذا لـ AI لتحديد المسار الذي يفضل على سبيل المثال ، الطرق على التضاريس العادية (مما يجعل تكلفة الطريق أقل من التضاريس).

تم تصميم Jump Point Search خصيصًا لتمثيل الخريطة على أساس الشبكة الثماني بحيث نستخدم ذلك. أيضا ، في شكله الفانيليا لا يدعم الخرائط المرجحة. (في القسم الأخير سأناقش طريقة ممكنة لعلاج هذا.)

A * Pathfinding تنشيطية

الآن لدينا تمثيل عالمي دعونا نلقي نظرة سريعة على تنفيذ A *. هي خوارزمية بحث رسم بياني مرجحة تستخدم أساليب البحث ("تلميحات" صغيرة) عن أفضل طريقة للبحث في المنطقة من نقطة البداية إلى عقدة النهاية.

أوصي بشدة بالاطلاع على هذا التمثيل البصري لخوارزميات مسار البحث:
PathFinding.js - مرئي. اللعب بها يمكن أن يعزز حدسك لما تقوم به الخوارزمية بالفعل - بالإضافة إلى أنه ممتع!

بالنسبة لميزة Pathfinding باستخدام A * في شبكات مستطيلة ، نقوم بما يلي:

1. Find node closest to your position and declare it start node and put it on 
   the open list. 
2. While there are nodes in the open list:
   3. Pick the node from the open list having the smallest F score. Put it on 
      the closed list (you don't want to consider it again).
   4. For each neighbor (adjacent cell) which isn't in the closed list:
      5. Set its parent to current node.
      6. Calculate G score (distance from starting node to this neighbor) and 
         add it to the open list
      7. Calculate F score by adding heuristics to the G value.

الاستدلال هو أساسا تخمين في فرصة أن العقدة التي يجري تقييمها ستؤدي إلى الهدف. يمكن للاستدلال أن يُحدث فرقًا كبيرًا في كفاءة خوارزميات Pathfinding لأنها تميل إلى الحد من عدد العقد التي تحتاج إلى زيارتها. سنستخدم مسافة مانهاتن لأغراضنا (بمعنى أن العقد الأقرب إلى الهدف سيكون لها عدد أقل):

private function manhattanDistance(start:Node, end:Node):int {
    return Math.abs(end.x - start.x) + Math.abs(end.y - start.y);
}

هذا أكثر أو أقل من ذلك. نوقف الخوارزمية عندما نجد عقدة الهدف ، ثم نتبعها مرة أخرى باستخدام المتغير الرئيسي للعقدة لإنشاء المسار.

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

في تطوير اللعبة ، نحتاج إلى القيام بالأمور بسرعة ، عند تحديث ألعابنا بمعدل 60 إطارًا في الثانية لكل ميلي ثانية. على الرغم من أن أداء A * جيد بشكل معقول بالنسبة لبعض الاستخدامات ، فهناك حاجة لجعله أسرع أو استخدام ذاكرة أقل.

تحسينات

اختيار التمثيل هو الشيء الأول الذي سيكون له تأثير على أداء المسار وإختيارك لخوارزمية تحديد المسار. سيكون لحجم الرسم البياني الذي يتم البحث عنه ارتباط كبير حول كيفية أداء المسار الخاص بك (وهو أمر منطقي ؛ فمن الأسهل العثور على طريقك في غرفتك أكثر من مدينة كبيرة).

ثم قد تفكر في إجراء تحسينات على مستوى أعلى والتي تتضمن عادة تجميع البيانات إلى مناطق أصغر ثم البحث عن تلك التحسينات لاحقًا أثناء تنقيح المسارات في مناطق أصغر تنقلها. على سبيل المثال ، إذا كنت ترغب في الذهاب إلى أحد المطاعم في مدينة مجاورة ، فيجب عليك أولاً التفكير في كيفية الوصول من مدينتك إلى تلك المدينة ، وبمجرد أن تكون في تلك المدينة فإنك تقيد "البحث" الخاص بك في المنطقة التي يقع فيها المطعم. بتجاهل الباقي. سيشمل أشياء مثل المستنقعات ، القضاء على طريق مسدود و HPA *.

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

القفز نقطة البحث

نظرًا لأن هذا البرنامج التعليمي يتعلق بتطبيق Jump Point Search ، فسيتم تمثيل الرسم البياني لمسار المسار بشبكة. ويجب أن يكون تحديدًا شبكة ذات ثمانية اتجاهات نظرًا لأن الخوارزمية تستخدمها بشكل مباشر.

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

كما هو الحال مع A * ، نختار من المشهد المفتوح العقدة التي تحتوي على أدنى درجة F. لكن هذا هو المكان الذي تبدأ الأمور في إثرائه. بدلاً من اختيار العقد المجاورة ، سوف ندعو هذه الوظيفة للقيام بذلك من أجلنا:

function identifySuccessors(current:Node, start:Node, end:Node):Vector.<Node> {
    var successors:Vector.<Node> = new Vector.<Node>();
    var neighbours:Vector.<Node> = nodeNeighbours(current);
   
    for each (var neighbour:Node in neighbours) {
        // Direction from current node to neighbor:
        var dX:int = clamp(neighbour.x - current.x, -1, 1);
        var dY:int = clamp(neighbour.y - current.y, -1, 1);


        // Try to find a node to jump to:
        var jumpPoint:Node = jump(current.x, current.y, dX, dY, start, end);


        // If found add it to the list:
        if (jumpPoint) successors.push(jumpPoint);
    }
   
    return successors;
}

ما يفعله هذا هو إزالة العقد التي ليست مثيرة للاهتمام لمسارنا. لهذا نستخدم الاتجاه من الوالد باعتباره المبدأ التوجيهي الرئيسي. فيما يلي أمثلة تقليم العقد التي سنقوم بتجاهلها للحصول على الاتجاهات الأفقية والرأسية:

مثال على واحدة من حالات التقليم الأفقي.

في رمز هذا سوف ينتهي كسلسلة من إذا كانت البيانات التحقق من هذه الحالات. يمكنك رؤية المثال هنا ، مع وصف الحالة الصحيحة من الصورة:

               if(directionY == 0) {
                    if (!_world.isBlocked(current.x + directionX, current.y)) {
                        if (_world.isBlocked(current.x, current.y + 1)) {
                              // create a node with the new position
                            neighbours.push(
                                  Node.pooledNode(current.x + directionX, current.y + 1));
                        }
                    }
                }

مثال على حالات التقليم القطرية.

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

سبيل المثال التماثل.

لذا ، بالنسبة إلى المساحات المفتوحة الكبيرة ، يمكننا تحقيق انتصارات ضخمة. إليك طريقة عمل طريقة القفزة:

function jump(cX:int, cY:int, dX:int, dY:int, start:Node, end:Node):Node {
    // cX, cY - Current Node Position,  dX, dY - Direction

    // Position of new node we are going to consider:
    var nextX:int = cX + dX;
    var nextY:int = cY + dY;
   
    // If it's blocked we can't jump here
    if (_world.isBlocked(nextX, nextY)) return null;

    // If the node is the goal return it
    if (nextX == end.x && nextY == end.y) return new Node(nextX, nextY);

    // Diagonal Case   
    if (dX != 0 && dY != 0) {
        if (/*... Diagonal Forced Neighbor Check ...*/) {
            return Node.pooledNode(nextX, nextY);
        }
       
        // Check in horizontal and vertical directions for forced neighbors
        // This is a special case for diagonal direction
        if (jump(nextX, nextY, dX, 0, start, end) != null ||
            jump(nextX, nextY, 0, dY, start, end) != null)
        {
            return Node.pooledNode(nextX, nextY);
        }
    } else {
        // Horizontal case
        if (dX != 0) {
            if (/*... Horizontal Forced Neighbor Check ...*/) {
                return Node.pooledNode(nextX, nextY);
            }
        /// Vertical case
        } else {
            if (/*... Vertical Forced Neighbor Check ...*/) {
                return Node.pooledNode(nextX, nextY);
            }
        }
    }
   
    /// If forced neighbor was not found try next jump point
    return jump(nextX, nextY, dX, dY, start, end);
}

أزلت عمليات التدقيق المجبرة القسري من عبارات if إذا كانت كبيرة جدًا. وهي تتكون أساسا من الشيكات التي تشبه تلك التي اخترناها لأول مرة الجيران لعقدة جديدة (الكثير من الشيكات لمعرفة ما إذا تم حظر الخلايا). إنها تخدم غرض اكتشاف متى يُسمح لنا بتطبيق افتراضاتنا على التناظر.

مثال على سلوك وظيفة القفز.

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

في الوقت نفسه لا نجد عقدة بحث نسميها وظيفة الانتقال بشكل متكرر في الاتجاه المحدد. في العرض التجريبي قمت في الواقع بالكشف عن هذه الدعوة العودية لأن هذا سوف يطلق عليه الكثير. (في الاختبار الخاص بي ، هذا الأداء المحسّن بواسطة عامل اثنين.)

هذا ما تفعله JPS ؛ النتيجة النهائية هي عقد جديدة لـ A * للتحقق من ذلك ونتابع الخوارزمية عند العثور على عقدة الهدف ، نعيد إنشاء المسار وإعادته.

الخصائص

يمكن لـ JPS تخطي الكثير من العقد عند البحث ، الأمر الذي يمكن أن يمنح تحسينات للسرعة لطيفة (في مشروعي يكون حوالي 30x أكثر من A *) ، ولكنه يأتي بتكلفة.

وهو يعمل بشكل أفضل على شبكة موحدة ، ولكن يمكن جعله يعمل مع غير الزي الرسمي باستخدام تغييرات جانبية إضافية ، ووضع علامات على الجيران حيث يتم الانتقال إلى عقدة ذات تكاليف مختلفة (الأفضل لاستخدام التكاليف المنفصلة).

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

التصحيح

ملاحظة سريعة حول تصحيح الأخطاء. قد يكون تصحيح هذه الأنواع من الخوارزميات أمراً صعباً للغاية ، ومن شبه المؤكد أن التطبيق الأول سيكون به بعض الأخطاء التي يصعب العثور عليها. يمكنك أن تقدم لنفسك معروفًا وأن تبني نوعًا ما من التصور وظيفيًا وارسم ما يحدث عند تشغيل الخوارزمية.

إذا حصلت على خطأ ، يجب عليك تقليل النطاق (حجم الشبكة) إلى الحد الأدنى الذي يسمح لك بإعادة إظهار المشكلة والاختبار من هناك. كما يمكن أن تخمّن ، لم ينفذ عملي الأول لتطبيق JPS على الفور!