في الأسبوع الماضي ، تحدثنا في مدونتنا عن التغييرات التي من شأنها أن تسمح للأعداء (biters) ألا يصطدموا ببعضهم البعض ، لكن هذا لم يكن التحديث الوحيد المتعلق بالمتجرّين. من قبيل الصدفة ، تضمنت تحديثات هذا الأسبوع ما عملنا عليه خلال الأسابيع القليلة الماضية - تحديث نظام البحث عن الأعداء.
البحث عن وسيلة
عندما تريد الوحدة الانتقال إلى مكان ما ، يجب أولاً فهم كيفية الوصول إلى هناك. في أبسط الحالات ، يمكنك الانتقال مباشرة إلى الهدف ، ولكن في بعض الأحيان تنشأ عقبات في الطريق - الصخور ، الأشجار ، أعشاش العدو (المخاضون) ، وحدات اللاعبين. لتمهيد الطريق ، نحتاج إلى إخبار وظائف باثفايندر بالمواقع الحالية والأخيرة ، وسيعود باثفايندر إلينا (ربما بعد العديد من التدابير) ، وهو
مسار يمثل ببساطة مجموعة من نقاط الطريق التي يجب أن تتحركها الوحدة للوصول إلى الوجهة.
لإنجاز عملها ، يستخدم باثفايندر خوارزمية تدعى A * (وضوحا "A star"). يتم عرض مثال بسيط لإيجاد مسار باستخدام A * في الفيديو: يريد biter إيجاد مسار حول الصخور. تبدأ وظيفة البحث عن المسار في استكشاف الخريطة المحيطة بالبيتار (تظهر الدراسة بالنقاط البيضاء). في البداية تحاول الوصول مباشرة إلى الهدف ، ولكن بمجرد وصولها إلى المنحدرات ، "تتسرب" في كلا الاتجاهين ، في محاولة لإيجاد موقع يمكن من خلالها الانتقال إلى الهدف مرة أخرى.
يتم تباطؤ الخوارزمية في هذا الفيديو بحيث يمكنك رؤية كيفية عمله بشكل أفضل.كل نقطة في الرسوم المتحركة تمثل
عقدة . تتذكر كل عقدة المسافة من بداية البحث وتقدير المسافة من هذه العقدة إلى الهدف (يتم حساب هذا التقدير من خلال
وظيفة الكشف عن
مجريات الأمور ). بفضل الوظيفة الاستكشافية التي تعمل بها A * - تقوم بتوجيه الخوارزمية في الاتجاه الصحيح.
في أبسط الحالات ، تقوم هذه الوظيفة ببساطة بحساب المسافة في خط مستقيم من العقدة إلى الموضع المستهدف - وهذا هو النهج الذي استخدمناه في Factorio من بداية التطوير ، وبفضله ، تنتقل الخوارزمية مبدئيًا في خط مستقيم. ومع ذلك ، ليس هذا هو الخيار الوحيد - إذا كانت الوظيفة الإرشادية تعرف ببعض العقبات ، فيمكنها توجيه الخوارزمية المحيطة بها ، والتي من شأنها تسريع عملية البحث ، لأنها لن تضطر إلى فحص العقد الإضافية. من الواضح أنه كلما كانت إرشادية أكثر ذكاءً ، زاد صعوبة تنفيذها.
إن وظيفة تقدير المسافة على الخطوط المستقيمة البسيطة هي طريقة جيدة لإيجاد مسارات عبر مسافات قصيرة نسبيًا. لقد كان مناسبًا لنا في الإصدارات السابقة من Factorio - دائمًا ما تنتقل ال biters لمسافات طويلة فقط لأنهم كانوا غاضبين من التلوث ، وهذا لم يحدث كثيرًا. ومع ذلك ، لدينا الآن المدفعية. يمكن للمدفعية أن تطلق النار بسهولة على أعداد هائلة من البتر على الجانب الآخر من بحيرة كبيرة (و "تضربهم") ، وبعد ذلك يحاولون تمهيد الطريق حول البحيرة. يوضح الفيديو أدناه كيف تحاول الخوارزمية A * البسيطة التي استخدمناها في وقت سابق الالتفاف على البحيرة.
يوضح هذا الفيديو سرعة الخوارزمية في الواقع ؛ انه لا يتباطأ.تخفيض كتلة
يعد العثور على مسار مهمة تاريخية طويلة ، وهناك العديد من التقنيات لتحسينه. تنتمي بعض هذه التقنيات إلى فئة
البحث عن المسار الهرمي : في هذه الحالة ، الخريطة مبسطة في البداية ، المسار يقع على هذه الخريطة المبسطة ، والتي تستخدم بعد ذلك للعثور على المسار الحقيقي. أكرر ، هناك العديد من التطبيقات المحددة لهذه التقنية ، ولكن كلها تتطلب تبسيط مساحة البحث.
كيف يمكنك تبسيط عالم Factorio؟ يتم إنشاء خرائطنا بشكل عشوائي وتتغير باستمرار: وضع وحذف الكيانات (على سبيل المثال ، المجمعون أو الجدران أو الأبراج) - ربما هذا هو الميكانيكا الأساسية للعبة بأكملها. لا نريد إعادة فرز الخريطة المبسطة بأكملها في كل مرة نضيف أو نزيل كيانًا. في الوقت نفسه ، إذا قمنا بتبسيط الخريطة من جديد في كل مرة نحتاج فيها إلى إيجاد طريقة ، فيمكننا أن نفقد بسهولة كل مكاسب الأداء.
جاء أحد الأشخاص الذين لديهم إمكانية الوصول إلى الكود المصدري للعبة (Allaizn) بفكرة. الذي نفذته نتيجة لذلك. الآن هذه الفكرة تبدو واضحة.
وتستند اللعبة على كتل من البلاط 32x32. تستبدل عملية التبسيط كل كتلة بواحد أو أكثر من
العقد المجردة . نظرًا لأن هدفنا هو تحسين البحث عن مسار حول البحيرات ، يمكننا تجاهل جميع الكيانات والنظر في البلاط فقط: لا يمكنك التحرك على الماء ، على الأرض التي يمكنك. نحن فصل كل كتلة في
مكونات منفصلة. المكون هو منطقة تجانب يمكن للوحدة الحصول عليها من بلاطة واحدة داخل مكون إلى أي تجانب آخر من نفس المكون. في الصورة أدناه ، يتم تقسيم الكتلة إلى مكونين منفصلين ، الأحمر والأخضر. سيصبح كل من هذه المكونات عقدة تجريدية واحدة - في الواقع ، يتم تقليل الكتلة بأكملها إلى "نقطتين".
كانت الفكرة الأكثر أهمية في Allaizn هي أننا لسنا بحاجة إلى تخزين مكون لكل بلاطة خريطة - فقط تذكر مكونات البلاطة على طول محيط كل قطعة ، لأننا مهتمون فقط بالمكونات الأخرى المرتبطة (في الكتل المجاورة) لكل مكون ، وهذا يعتمد فقط على البلاط التي تقع على حدود الكتلة.
مسار البحث الهرمي
لذلك ، اكتشفنا كيفية تبسيط الخريطة ، ولكن كيفية استخدام هذا للعثور على مسارات؟ كما قلت ، هناك العديد من تقنيات البحث عن المسار الهرمي. أبسط فكرة هي العثور على المسار باستخدام العقد المجردة من البداية إلى الهدف ، أي أن المسار سيكون قائمة بمكونات الكتل التي تحتاج إلى زيارتها. بعد ذلك ، نستخدم سلسلة عمليات البحث القديمة الجيدة A * لمعرفة كيفية الانتقال من أحد مكونات الكتلة إلى آخر على وجه التحديد.
المشكلة هنا هي أننا قمنا بتبسيط الخريطة كثيرًا: ماذا لو كان الانتقال من كتلة إلى أخرى أمرًا مستحيلًا ، لأن بعض الكيانات (على سبيل المثال ، الصخور) تسد المسار؟ عند تقليص الكتل ، نتجاهل جميع الكيانات ، لذلك نحن نعرف فقط أن المربعات بين الكتل مرتبطة بطريقة أو بأخرى ، لكننا لا نعرف مطلقًا ما إذا كان من الممكن الانتقال من واحدة إلى أخرى.
الحل هو استخدام التبسيط ببساطة ك "توصية" لإجراء بحث حقيقي. على وجه الخصوص ، سوف نستخدمها لإنشاء نسخة ذكية من وظيفة البحث التجريبي.
نتيجة لذلك ، حصلنا على المخطط التالي: لدينا اثنين من باثفايندر: باثفايندر
الأساسي ، الذي يجد المسار الحقيقي ، و
باثفايندر المجرد ، الذي يوفر الوظيفة الاستكشافية إلى باثفايندر الأساسي. في كل مرة يقوم فيها باثفايندر الأساسي بإنشاء عقدة أساسية جديدة ، فإنه يستدعي باثفايندر مجردة للحصول على تقدير للمسافة إلى الهدف. يعمل مسار المسار التجريدي بالترتيب المعاكس - حيث يبدأ بهدف البحث ويمهد الطريق إلى البداية ، وينتقل من مكون واحد من العنصر إلى آخر. عندما يعثر البحث المجرد على الكتلة والمكون الذي يتم فيه إنشاء عقدة أساسية جديدة ، فإنه يستخدم المسافة من بداية البحث التجريدي (والتي ، كما قلت ، هي موضع الهدف من البحث بأكمله) لحساب تقدير المسافة من العقدة الأساسية الجديدة إلى الهدف العام.
ومع ذلك ، فإن تنفيذ باثفايندر بالكامل لكل عقدة فردية سيكون بعيدًا عن الصيام ، حتى لو كان باثفايندر مجردة ينتقل من كتلة إلى أخرى. لذلك ، بدلاً من ذلك ، نستخدم نظامًا يسمى "Reverse Resumable A *". "عكس" يعني أنه ، كما قلت أعلاه ، يتم تنفيذه من الهدف إلى البداية. "المتجددة" تعني أنه بعد العثور على كتلة مثيرة للاهتمام لباثفايندر الأساس ، فإننا نحفظ جميع العقد في الذاكرة. في المرة التالية التي ينشئ فيها مستكشف المسار الأساسي عقدة جديدة ويحتاج إلى تقدير المسافة ، نلقي نظرة فقط على العقد المجردة المحفوظة من البحث السابق. في الوقت نفسه ، هناك احتمال كبير أن تظل العقدة المجردة المطلوبة في الذاكرة (في النهاية ، تغطي عقدة مجردة واحدة معظم الكتلة ، وغالبًا ما تكون الكتلة بأكملها).
حتى إذا كان باثفايندر الأساس يخلق عقدة تقع في كتلة لا تغطيها أي من العقد المجردة ، فإننا لسنا بحاجة إلى إجراء البحث المجرد بأكمله مرة أخرى. من الميزات الملائمة لخوارزمية A * أنه حتى بعد "الانتهاء من العمل" والعثور على المسار ، فإنه يستمر في التنفيذ ، ويستكشف العقد حول العقد التي تمت دراستها بالفعل. وهذا هو بالضبط ما نفعله إذا كنا بحاجة إلى تقدير المسافة لعقدة قاعدة موجودة في كتلة لم تتم تغطيتها بعد من البحث المجرد: نستأنف البحث التجريدي من العقد المخزنة في الذاكرة حتى يتم توسيعه إلى العقدة التي نحتاج إليها.
يُظهر مقطع الفيديو أدناه نظامًا جديدًا لربط المسار قيد التنفيذ. الدوائر الزرقاء هي عقد مجردة. النقاط البيضاء - البحث الأساسي. يعد مستكشف المسار في الفيديو أبطأ بكثير من اللعبة لإظهار كيفية عمله. في السرعة العادية ، يستغرق البحث بأكمله بضع علامات فقط. لاحظ أن البحث الأساسي ، الذي لا يزال يستخدم الخوارزمية القديمة التي استخدمناها دائمًا ، ببساطة يعرف "كيفية" التنقل في البحيرة.
نظرًا لاستخدام محدد المسار التجريدي فقط للحصول على تقدير إرشادي للمسافة ، فإن البحث الأساسي يمكن أن يبتعد بسهولة عن المسار المقترح بواسطة البحث التجريدي. هذا يعني أنه على الرغم من أن مخطط الحد من الكتلة يتجاهل جميع الكيانات ، إلا أن باثفايندر الأساسي يمكنه تجاوزها بدون مشاكل. نظرًا لتجاهل الكيانات في عملية تبسيط الخريطة ، لا نحتاج إلى تكرارها مرة أخرى في كل مرة تتم فيها إضافة أو إزالة كيان ، يكفي فقط تغطية تلك البلاطات التي تم تغييرها (على سبيل المثال ، كما هو الحال مع مكب النفايات) والذي يحدث كثيرًا أقل من وضع الكيانات.
بالإضافة إلى ذلك ، يعني هذا أننا نستخدم أساسًا نفس مُعرِّف المسار الذي نستخدمه لسنوات ، وقد تم تحديث الوظيفة الاستكشافية فقط. أي أن هذا التغيير لن يؤثر على العديد من الأنظمة الأخرى ، وسيؤثر فقط على سرعة البحث.