Advertisement
  1. Game Development
  2. Pathfinding
Gamedevelopment

كيفية التكيف A * Pathfinding لمنصة على أساس الشبكة 2D: النظرية

by
Difficulty:IntermediateLength:MediumLanguages:
This post is part of a series called How to Adapt A* Pathfinding to a 2D Grid-Based Platformer.
How to Adapt A* Pathfinding to a 2D Grid-Based Platformer: Implementation

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

A * شبكة القاعدة اﻻستطﻻعية يعمل جيدا للألعاب التي الأحرف يمكن أن تتحرك بحرية على طول x--وياكسيس. المشكلة مع تطبيق ذلك على platformers أن الحركة على المحور الصادي مقيدة بشدة، بسبب قوي الجاذبية محاكاة.

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

وافترض هنا أن كنت بالفعل على دراية مع A * اﻻستطﻻعية، ولكن إذا كنت بحاجة إلى مقدمة، Patrick Lester's A * Pathfinding for Beginners هو ممتاز.

عرض

يمكنك تشغيل عرض الوحدة، أو(the WebGL version (64MB، لمعرفة النتيجة النهائية في العمل. استخدام WASD لنقل الحرف، والزر الأيسر على الفور للعثور على مسار يمكنك اتباعها للوصول إلى هناك، وزر الماوس الأيمن فوق خلية لتبديل الأرض في تلك المرحلة.

بنهاية هذه السلسلة، سنقوم أيضا قد أضاف منصات أحادية الاتجاه، تمديد التعليمة البرمجية للتعامل مع أحجام مختلفة من الأحرف، وترميز بوت أن يمكن تلقائياً اتبع المسار! تحقق من أن عرض الوحدة هنا (أو نسخة WebGL 100 ميغا بايت).

تعريف القواعد

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

ما يمكن القيام به الحرف؟

لنفترض أن شخصيتنا يستغرق خلية واحدة، ويمكن أن تقفز ثلاث خلايا عالية.

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

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

استناداً إلى هذه القواعد، هنا هو مثال على مسار الحرف ستتخذ خلال القفز المسافة القصوى:

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

تمثل مسارات الانتقال مع قيم القفز

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

دعونا نبدأ بتعيين القيمة كل خلية القفز بزيادة من جانب واحد، كل خلية، لطالما تواصل القفز. وبطبيعة الحال، عندما يكون الحرف على أرض الواقع، يجب أن تكون القيمة القفز 0.

هنا هو أن القاعدة المطبقة على نفس المسار القفز المسافة القصوى من قبل:

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

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

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

هنا ما يجب أن يبدو وكأنه للقفز التوالي:

وهنا قضية أكثر تعقيداً:

هنا كيف يتم حساب قيم الانتقال:

  1. ابدأ على أرض الواقع: القيمة القفز هو 0.
  2. الانتقال أفقياً: زيادة القيمة القفز من 1، حيث القيمة القفز هو 1.
  3. القفز عمودياً: زيادة قيمة الانتقال إلى رقم زوجي المقبل: 2.
  4. القفز عمودياً: زيادة قيمة الانتقال إلى رقم زوجي المقبل: 4.
  5. الانتقال أفقياً: زيادة القيمة القفز 1؛ القيمة القفز الآن 5.
  6. القفز عمودياً: زيادة القيمة إلى رقم زوجي المقبل: 6. (الحرف يمكن لم تعد تتحرك صعودا، حيث فقط متبقي، تتوفر العقد اليمنى والسفلي.)
  7. تقع أفقياً: زيادة القيمة القفز 1؛ القيمة القفز الآن 7.
  8. تقع عمودياً: زيادة قيمة الانتقال إلى رقم زوجي المقبل: 8.
  9. تقع عمودياً: زيادة القيمة إلى رقم زوجي المقبل: 10.
  10. تقع عمودياً: نظراً للحرف الآن على أرض الواقع. تعيين القيمة القفز إلى 0.

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

إضافة الإحداثيات

الآن أن نحن على علم بهذا نوع الحركات التي يمكن أن تجعل الحرف على الشبكة، دعونا النظر في الإعداد التالية:

الخلية الخضراء في الموضع (3، 1) هو الحرف؛ خلية أزرق في موضع (2، 5) هو الهدف. دعونا رسم طريق التي قد تختار الخوارزمية A * أولاً في محاولة للوصول إلى الهدف@

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

قد نجد أكثر حظاً مع مسار آخر، والترجيع سعينا لذلك دعونا والبدء مرة أخرى من عقده (3، 2).

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

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

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

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

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

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

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

نقاط القوة والضعف لاستخدام شبكة القاعدة اﻻستطﻻعية

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

نقاط القوة

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

نقاط الضعف

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

المحرك ومتطلبات الفيزياء

حرف الحرية مقابل الحرية الخوارزمية

من المهم أن تتمتع الشخصية بقدر من حرية الحركة على الأقل كما تتوقع الخوارزمية - ويفضل أكثر قليلاً من ذلك.

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

الطريقة التي أتخذها في هذا البرنامج التعليمي هي ملائمة الخوارزمية لفيزياء اللعبة ، وليس العكس.

تحدث المشاكل الرئيسية في الحالات الحرجة عندما لا تتطابق الحرية المتوقعة في حرية الحركة مع الخوارزمية مع حرية الحركة الحقيقية في اللعبة.

عندما يكون الحرف أكثر حرية من الخوارزمية تتوقع

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

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

عندما الخوارزمية تتوقع المزيد من الحرية من حرف له

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

(من بين هاتين المشكلتين ، من الأفضل السماح لفيزياء اللعبة بالسماح بحرية حركة أكبر مما تتوقعه الخوارزمية.)

حل هذه المشاكل

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

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

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

خاتمة

عند هذه النقطة ، يجب أن يكون لديك فهم مفاهيمي لائق لكيفية تأقلم A * pathfinding مع المنصة. في البرنامج التعليمي القادم ، سوف نجعل هذا ملموسًا ، من خلال تعديل خوارزمية Pathfinding A الحالية من أجل تنفيذ ذلك في لعبة!

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.