مرحبًا بكم في فريق الخوارزميات الرشيقة!
كتجربة ، قررنا الاحتفاظ بـ "مذكرات" للمطورين التي سنشارك فيها الخبرة ونبرز بعض النتائج المهمة لتجاربنا. هذه مقالنا الأول عن مشروع Pathfinder 3D ، أحد أصول محرك ألعاب Unity ، والذي يسمح لك بالبحث عن مسارات في مساحة ثلاثية الأبعاد. سوف نتحدث فيه عن المسار من أصل الفكرة إلى منتج متكامل وبعض المشكلات التي واجهناها. ستكون هذه المادة مفيدة للأشخاص الذين يرغبون في بدء مشروعهم ودعمه في المستقبل ، وكذلك لأولئك الذين يرغبون في تنفيذ عملية بحث عن مسار في الفضاء.
بدأ فريق من شخصين العمل على الأصول. تضمنت الأولى بعض التطورات التي سمحت بتسريع عملية العثور على أقصر طريق على الرسوم البيانية المعقدة بما يكفي للعمل في الوقت الحقيقي ، والرغبة في العثور على تطبيق عملي لهم ، والثاني لديه بعض الخبرة في العمل مع الوحدة وكان يبحث عن فكرة لبدء التشغيل. نظرًا لأنهم غالبًا ما يتواصلون مع بعضهم البعض ، فليس من المستغرب أن تكون الفكرة قد نشأت في مرحلة ما عن إمكانية إنشاء أصل للبحث عن مسار في الفضاء ثلاثي الأبعاد.
عند دراسة كتالوج أصول Unity ، تم العثور على العديد من الحلول للعثور على المسار في الفضاء ثنائي الأبعاد ، ولكن ليس في ثلاثي الأبعاد. أصبح من الواضح أن هذه كانت فرصة عظيمة لدخول سوق الوظائف الإضافية لبرامج Unity ، خاصة بالنظر إلى مدى الرؤية والنتيجة المتوقعة للنتيجة المتوقعة.
كان الهدف هو التنفيذ المباشر للبحث عن مسار في الفضاء ثلاثي الأبعاد والقدرات النموذجية للحلول الحالية لإيجاد مسار في الفضاء ثنائي الأبعاد. لقد بدأنا العمل: أحدهما طور مباشرة آلية البحث عن المسار ، والفئات والطرق الثانية لإدارة عملية البحث عن المسار ، وواجهات التكوين ، ومشاهد الاختبار ، والوثائق ، وموقع المشروع ، وشارك أيضًا في تسجيل وإعداد حسابات الخدمة اللازمة لبيع الأصل.
بعد وقت قصير من بدء العمل ، أصبح من الواضح أن هناك حاجة إلى بعض الموارد المشتركة للفريق لتدوين الملاحظات: قائمة المهام والمشاكل التي تحتاج إلى حل ، معلومات حول القرارات المتخذة والأفكار ونتائج البحوث التي كانت مثيرة للاهتمام في المستقبل. بعد تحليل الحلول الحالية ، توقفنا في
Trello ، بسبب وظائفه وبساطته
وراحته ومظهره الجميل. كما أظهرت الممارسة ، هذه الخدمة مريحة للغاية للفرق الصغيرة. إذا كان لدى الفريق أكثر من 5 أشخاص ، فإننا نوصي باستخدام نظام متكامل لإدارة المشاريع.
بعد ذلك ، نصف القرارات التي تم اتخاذها أثناء تطوير الإصدار الأول من الأصل ، والمنطق الذي اتبعناه عند صنعها. سوف يتفهم الأشخاص الذين لديهم خبرة مع Unity والذين لديهم دراية بخوارزميات البحث عن المسار على الفور أين ستظهر المشاكل في المستقبل. في هذه الأماكن ، استخدمنا حلاً بسيطًا من أجل تقليل وقت التطوير حتى يتم استلام الإصدار الأول من الأصل ، حتى لا نتعطل ، لأن الحماس محدود وغير مستقر. وبالتالي ، تعاملنا مع أحد الأسباب الأكثر شيوعًا لإغلاق هذه الشركات الناشئة ، والتي بسببها تموت العديد من المشاريع دون أن تولد. تم تصحيح جميع مجالات المشكلات بعد نشر الأصل.
للعثور على المسار ، تم اختيار خوارزمية
A * (A star) بسبب سرعتها العالية في التشغيل في المساحات المفتوحة الكبيرة. تعمل معظم خوارزميات البحث عن المسار على الرسوم البيانية التي تمثلها مصفوفة منفصلة. قد يكون من الممكن بناء هذه المصفوفة مقدمًا ، لكن عملية إنشاءها لمرة واحدة في حيز ثلاثي الأبعاد مع وجود عقبات نظرت إلى ذلك الوقت على أنها مهمة صعبة إلى حد ما. بالإضافة إلى ذلك ، لم يكن من الواضح كيفية القيام بذلك دون التضحية بالأداء ، لأنه في وقت بدء العمل على الأصل لم تكن هناك خبرة في عمليات الخلفية وتعدد مؤشرات التوحيد في الوحدة ، وكذلك مع تعدد العمليات بشكل عام. تم تكوين الرسم البياني في الوقت الفعلي عن طريق البحث في المساحة بالأشعة المادية (Physics.BoxCast) في اتجاه البحث. تم تخفيض المسارات التي تم العثور عليها إلى مسارات مقطوعة بنقاط وسيطة أقل ، ثم تم تنعيمها بواسطة شرائح.
كانت الصعوبة الرئيسية تتمثل في استحالة استخدام الأساليب الفيزيائية للمحرك بشكل غير متزامن ، حيث يمكن أن تعمل بشكل حصري في الخيط الرئيسي. في المشاهد غير المعقدة ، لم يؤثر استخدام وظيفة البحث في نفس الوقت من قبل أكثر من عشرين وكيلًا بشكل كبير على معدل الإطارات. للتخلص من عمليات السحب القوية النادرة من FPS ، تم تباعد الحمل الحسابي في الوقت المناسب باستخدام coroutines. تباطأ هذا البحث ، ولكن ليس بشكل كبير.
قبل تقديم مادة عرض للإشراف ، تحتاج إلى وضع الكود في ترتيب وإعداد وثائق مفصلة ، وفقًا
للمتطلبات ، والتسجيل وتكوين بريد الدعم. يُنصح أيضًا بإنشاء موقع ويب للمشروع حيث سيتم عرض أخبار التطوير والعروض التوضيحية بشكل ملائم. ستكون هذه إضافة كبيرة خلال مرور فترة الاعتدال ، وعند دراسة الأصول الخاصة بك من قبل المستخدم قبل الشراء. تم طلب خدمات الاستضافة والبريد من قبلنا من
BeGet ، لأنها في ذلك الوقت كانت تقدم العروض الأكثر فائدة ، وتكلفنا 1000r / year.
استغرقت مدة الإشراف على الأصول 22 يومًا وتخطت المرة الأولى ، نظرًا لأننا اقتربنا بعناية فائقة من الوثائق وتصميم صفحة الأصول في متجر الوحدة. بعد النشر ، سقط الأصل في الحال في المرتبة الأولى في فئة Scripting / AI. منذ تلك اللحظة ، بدأت الرسائل تصل إلى بريد الدعم لطلب المساعدة في حل بعض المشكلات. أحيانا قليلة في اليوم ، وأحيانا لا شهر. إذا كنت في المتوسط ، ثم لمدة شهر واحد طرح الأسئلة ، والمراسلات التي استغرقت ما مجموعه 2-3 ساعات. ليس كثيرًا ، ولكن يجب أن يؤخذ في الاعتبار أنه بغض النظر عن عبء العمل الحالي الخاص بك ، تحتاج إلى الاستجابة بسرعة كبيرة حتى لا يكتب المستخدمون الغاضبون تعليقات سيئة عن المنتج ، ولكن على العكس من ذلك ، فإنهم متحمسون لدعم الجودة ، ويتركون تعليقات إيجابية. أيضًا ، هناك الكثير من الأسئلة التي تصل إلى البريد مثل "هل ستعمل أصولك إذا ...". كما يجب عدم تجاهل هذه الرسائل ، لأن هذا هو المشتري المحتمل الذي يمكنه المغادرة.
عند تلقي شكاوى من المشترين الأوائل ، أصبح من الواضح أن العديد من المستخدمين يستخدمون الأصول في المشاهد المعقدة التي تحتوي على تكوين متاهة أو تجويف آخر متصل. في مثل هذه المشروعات ، لم يكن مخطط اكتشاف المسار ، القائم على التحقق من التصادم ، وحتى في المسار الرئيسي ، فعالًا بدرجة كافية. لذلك ، بدأنا في تطبيق الإنشاء المبكر للرسم البياني بحيث يكون من الممكن البحث عن المسار في الدفق الجانبي دون استخدام الفيزياء والوصول إلى كائنات المشهد.
تقديرية الفضاء ثلاثي الأبعاد يقسمها إلى مكعبات. تخزين المعلومات حول كافة مكعبات التقسيم زائدة ومكثفة للغاية في الذاكرة. لذلك ، من المنطقي تخزين إحداثيات الخلايا غير السالكة فقط ، والتي تم القيام بها.
عقبات اللعبة هي أشكال مضلعة وتتألف من مثلثات. لحساب العقبات في الرسم البياني للبحث ، يجب أن تجد كل مكعبات القسم التي تتقاطع مع أي مثلث من أي عقبة. بالفعل في هذه المرحلة ، تم وضع إمكانية إزالة العقبات وإضافتها إلى المرحلة بشكل ديناميكي ، ولم يتم حفظ إحداثيات المكعبات المحتلة فقط ، ولكن أيضًا محددات العقبات التي كانت موجودة فيها. أصبح من الممكن الآن إنشاء رسم بياني للملاحة قبل بدء عملية اللعبة ، وبسبب القضاء على عدد كبير من العمليات الحسابية المعقدة أثناء البحث عن مسار ، يمكن لأكثر من مائتي وكيل إجراء ذلك في وقت واحد دون المساس بالأداء.
مشكلة أخرى معروفة لنا جعلت نفسها تشعر: خوارزمية A * وتعديلاته تعمل بشكل سيئ للغاية في الأماكن الضيقة على الرسوم البيانية عالية الطاقة. نظرًا لأن الخوارزمية تفضل اتجاه المسار نحو الاقتراب من نقطة الهدف ، فإن أي طريق مسدود يؤدي إلى الهدف يؤدي إلى تباطؤ كبير في البحث عن المسار ، لأنه قبل اختيار اتجاه مختلف من "الإنبات" ، تقوم الخوارزمية أولاً بملء الفراغ بأكمله داخل النهاية المسدودة.
في مثل هذه الحالات ، تثبت
خوارزمية البحث عن الموجة (Lee Algorithm) أنها فعالة جدًا نظرًا
لصغر عدد العمليات المطلوبة "لملء" المساحة. لذلك ، تمت إضافته إلى الأصل كبديل. عند الاختبار على مرحلة تمثل متاهة ، تم تقليل وقت البحث عن المسار بأكثر من 30 مرة.
لتسريع المعالجة الأولية للمشهد وإيجاد الطريق إلى الأصل ، تمت إضافة إمكانية التنفيذ المتوازي للعمليات ، لكن كفاءة التوازي كانت منخفضة للغاية ، نظرًا لحقيقة أنه عند العمل مع حاوية تخزن إحداثيات الخلايا المشغولة ، من الضروري مزامنة التدفقات التي تم تنفيذها باستخدام mutexes ، نظرًا لأن المجموعات التنافسية والعديد من الأدوات الأخرى لضمان التزامن الفعال
تم تنفيذها فقط في .NET Framework 4.5 القياسي ، وفي Unity ، تم استخدام إصدار .NE حتى إصدار 2018. تي الإطار 3.5. لقد حاولنا حل هذه المشكلة باستخدام الأدوات المتاحة ، ولكن كان أداءها متواضعًا جدًا ، ولم نحصل على النتيجة المرجوة إلا بعد التحول إلى إصدار الوحدة 2018. فتح استخدام المجموعات التنافسية أيضًا إمكانية تحقيق التغيير الديناميكي للعقبات في المشهد.
في مرحلة معينة ، بدأت الخلافات تظهر في الفريق فيما يتعلق بتوزيع الأرباح ، وانضم شخص ثالث إلى الفريق ، الذي قدم نظامًا لتقييم وقت استثمار كل عضو من أعضاء الفريق ، وبدأ أيضًا الانخراط في فحص الكود واختباره ، مما أدى إلى تحسين جودة المنتج بشكل كبير.
يتكون نظام تقدير تكاليف الوقت في الوقت الحالي في شكل جدول Excel وهو نظام آلي يتم فيه إدخال معلومات حول المبيعات والمهام المنجزة خلال الشهر الماضي مرة كل شهر. يحتاج أعضاء الفريق إلى تقييم مقدار الوقت الذي سيحتاجون إليه لحل مشكلة معينة. وبالتالي ، عند تقييم التعقيد الزمني للمهام ، تؤخذ سرعة كل مشارك في الاعتبار. إن المبالغة في تقدير تقدير أحد المشاركين أو المبالغة فيه على نحو غير طبيعي على الفور يصبح واضحًا من الإحصائيات المتراكمة في تقييماته السابقة. وفي حالة عدم وجود تفسير مرض ، يقرر الفريق بأكمله هذه المشكلة. أثبت هذا النهج أنه جيد لمدة ستة أشهر من الاستخدام وسمح لجمع إحصاءات مثيرة للاهتمام. لم نجد حلاً مجانيًا جاهزًا يوفر الميزات الموصوفة. لذلك ، في الوقت الحالي ، بالنسبة للفرق الصغيرة ، فإن التنفيذ في شكل جداول Excel يبدو لنا هو الأفضل. بالنسبة للفرق الكبيرة نسبيًا ، سيكون عليك على الأرجح تصميم قاعدة البيانات الخاصة بك أو تطوير جزء الخادم والعميل أو تنفيذ ملحق لأحد أنظمة إدارة المشاريع الحالية.
لتلخيص. لقد مر عام منذ بداية التطوير إلى الإصدار الأول مع الحد الأدنى من الوظائف اللازمة والأداء الكافي للاستخدام في المشاريع الحقيقية. أمضيت ستة أشهر أخرى في تحسين الأداء وتنفيذ العمل متعدد الخيوط للأصل. في الوقت الحالي ، قدّرنا تكاليف الوقت لهذا المشروع بـ 1065 ساعة عمل (وهذا تقدير متفائل إلى حد ما) ، ومتوسط ربح الشهر هو 9.5 أضعاف. من السهل حساب أن متوسط تكلفة ساعة العمل في الوقت الحالي يبلغ حوالي 160 روبل ، وهذا ليس كثيرًا. ومع ذلك ، فإن الشيء الرئيسي في هذا الحدث هو الخبرة التي اكتسبها كل مشارك. بما في ذلك تجربة العمل الجماعي وتجربة دعم منتجات البرمجيات. يمكن اعتبار المشروع ناجحًا.
بدأ فريقنا الآن في تنفيذ وظائف إضافية مفيدة: التحقق من إمكانية الوصول إلى الخوارزمية ؛ القدرة على تعيين كائنات اللعبة إلى البوابات ؛ دعم عقبة ديناميكية. التنقل المحلي بين الوكلاء لمنع الاصطدامات وخطة الطرق المحلية.
نأمل أن تساعد هذه المواد شخص ما في الوصول بمشروعه إلى خط النهاية.