Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Game Development
  2. Programming
Gamedevelopment

فهم المسار الموجه القائم على الهدف الهدف Pathfinding

by
Difficulty:IntermediateLength:MediumLanguages:

Arabic (العربية/عربي) translation by Hamdan Veerlax (you can also view the original English article)

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


مقدمة

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

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

ملاحظة: يمكن استخلاص مسار مسار الحقل الموجه إلى العقد والرسومات البيانية بشكل عام ؛ لمجرد أن أشرح ذلك باستخدام النهج القائم على بلادي والبلاط لا يعني أن هذه الخوارزمية تقتصر على عوالم تستند إلى البلاط!


نظرة عامة على الفيديو

يتكون حقل pathfinding Vector من ثلاث خطوات.

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

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



توليد الحرارة

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

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

تُظهر الأرقام الموجودة في أعلى يسار كل مربع مسافة المسار إلى الهدف محسوبة بواسطة خوارزمية توليد heatmap. لاحظ أن هناك أكثر من مسار مسار ممكن بين نقطتين ؛ في هذه المقالة ، نحن مهتمون فقط بأقصر واحد.

Efficient_Pathing_Path_vs_Linear_Distance

خوارزمية توليد heatmap هي خوارزمية جبهة الموجة. يبدأ عند الهدف بقيمة 0 ، ثم يتدفق للخارج لملء المنطقة القابلة للعبور بالكامل. هناك خطوتان لخوارزمية موجة الموجة:

  • أولاً ، تبدأ الخوارزمية عند الهدف ، وتضع علامة عليها بمسافة مسافة 0.
  • بعد ذلك ، يحصل على كل الجيران غير المميزين في علامة التمييز ، ويميزها بمسار مسار البلاطة السابقة + 1.
  • يستمر هذا حتى يتم وضع علامة على الخريطة التي يمكن الوصول إليها بالكامل.

ملاحظة: تعمل خوارزمية واجهة الموجة ببساطة على تشغيل أول بحث شامل على الشبكة وتخزين عدد الخطوات اللازمة للوصول إلى كل مربع على طول الطريق. تسمى هذه الخوارزمية أحيانًا خوارزمية brushfire.


جيل ناقل المجال

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

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

Efficient_Pathing_Vector_Field_Visualization

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

ملاحظة: يخزن متغير المسافة لكل مسار مسافة المسار إلى الهدف كما تم حسابه بواسطة خوارزمية واجهة الموجة أعلاه.

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


حركة باثفايندر

والآن بعد أن تم حساب حقل المتجه ، يكون من السهل جدًا حساب الحركة لواحد من محددات المسارات. بافتراض أن vector_field (x، y) تقوم بإرجاع المتجه الذي قمنا بحسابه في وقت سابق على التجانب (x، y) ، وأن value_velocity هو عددي ، فإن pseudocode لحساب سرعة الجسيم على البلاط (x، y) يشبه هذا:

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

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

أوبتيما المحلية

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

يمكن رؤية هذه المشكلة في الصورة أدناه. تحتوي البلاطة (المبينة باللون الوردي) على يسار مركز الجدار مباشرةً على متجه للمسار الذي تساوي مكوناته (س و ص) 0.

Efficient_Pathing_Local_Optima

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

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

الخدعة الحقيقية التي تحل مشكلة Optima المحلية هي إضافة أربع نقاط هدف بدلاً من واحدة فقط. للقيام بذلك علينا ببساطة تعديل الخطوة الأولى لخوارزمية توليد heatmap. عندما اعتدنا على إضافة هدف واحد فقط بمسافة مسار 0 ، نقوم الآن بإضافة الأربعة مربعات الأقرب إلى الهدف.

هناك عدة طرق لاختيار البلاط الأربعة ، ولكن الطريقة التي يتم اختيارها بها غير ذات صلة إلى حد كبير - طالما أن القرميدات الأربعة متاخمة (وعابرة) ، يجب أن تعمل هذه التقنية.

هنا هو pseudocode تغيير لتوليد heatmap:

  1. أولاً ، تبدأ الخوارزمية في مربعات الأهداف الأربعة ، وتضع كل مربعات الأهداف الأربعة بمسافة للمسار تساوي 0.
  2. بعد ذلك ، يحصل على كل الجيران غير المميزين في علامة التمييز ، ويميزها بمسار مسار البلاطة السابقة + 1.
  3. يستمر هذا حتى يتم وضع علامة على الخريطة التي يمكن الوصول إليها بالكامل.

والآن ، وهنا النتائج النهائية ، والتي تبين بوضوح أن تم حل مشكلة optima المحلية:

Efficient_Pathing_Local_Optima_Solved

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

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


خاتمة

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

التنفيذ أكثر تعقيدًا ، ولكن يمكن تقسيمه إلى ثلاث خطوات يمكن إدارتها بسهولة:

  1. توليد الحرارة
  2. جيل ناقل المجال
  3. حركة الجسيمات

آمل أن أرى الناس يتوسعون في الأفكار المقدمة هنا. كما هو الحال دائمًا ، إذا كانت لديك أسئلة ، فلا تتردد في طرحها في التعليقات أدناه!

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.