طريقة للمسارات المتخصصة؟

Question

أنا أعمل على روجويليك في وقت فراغي (القليل جدا). سيكون كل مستوى أساسا بعض الغرف المستطيلة المتصلة بالمسارات. أريد أن تكون المسارات بين الغرف مظهرا طبيعيا وريحا. على سبيل المثال، لن أفكر في المظهر الطبيعي التالي:

       B       
       X       
       X       
       X       
      XX       
     XX        
    XX         
  AXX          

أريد حقا شيئا أكثر مثل هذا:

       B       
       X       
       XXXX    
          X    
          X    
          X    
          X    
  AXXXXXXXX    

يجب أن تلبي هذه المسارات بعض الخصائص:

1. يجب أن أكون قادرا على تحديد منطقة داخلها،
2. يجب أن أكون قادرا على تحديد عدد العاصفة وطويلة،
3. يجب أن تبدو الخطوط كما لو أنها بدأت في طريق واحد وانتهت في الآخر. على سبيل المثال، يبدو المثال الأول أعلاه كما لو بدأ في A وينتهي في B، لأنه غير مؤشرات بشكل أساسي مرارا وتكرارا حتى تصطف ب B، ثم ذهب فقط إلى هناك.

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

سؤالي هو، ما هو وسيلة جيدة للحصول على النتائج التي أريدها؟ يرجى عدم تحديد طريقة مثل "A *" أو "خوارزمية Dijkstra"، لأنني أحتاج أيضا إلى مساعدة مع إرشادية جيدة.

Answer 1

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

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

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

فيما يلي بعض الخطوات التالية جيدة:

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

ثم ستكون مستعدا للتفكير في خوارزميات البحث.

Answer 2

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

أقترح، بالنظر إلى أنك تفضل أن تفضل أن تتحول المسارات الأفقية والرأسية بالزوايا الصحيحة، للبدء بمسار مستقيم وشرعة من A إلى B. (A * مع Manhattan Very Heuristic يمكن أن تجد هذا من أجلك، لكن الأمر كذلك من السهل أن تخطئ نفسك). ثم خذ نقطة عشوائية على طول أحد الشريحة وواحدة من النقاط الطرفين لهذا القطاع، ونقل هذا القسم الفرعي للخط بالتوازي مع نفسه من قبل بعض المسافة العشوائية. ثم قم بإضافة شرائح الخط الإضافية 2 للانضمام إلى الموضع الجديد للخط إلى نقاط الاتصال القديمة. يوضح مثالك الثاني تكرارا من هذه الخوارزمية: إذا كان A هو (0،0) و B (5، 7)، فأنت قد اخترت قطاع الخط الثاني (المرتبة الأولى) في عشوائي، اختار نقطة النهاية في (0،5 ) ونقطة الوسط عند (5،5)، ودفعت هذا القسم إلى اليمين بنسبة 3 وحدات، قبل الانضمام إليها احتياطيا.

Answer 3

وهنا فكرة ---

ابدأ في A واتخاذ خطوة في اتجاه عشوائي - اليسار أو لأعلى أو لأسفل. بعد كل حركة، لفة رقم عشوائي لمعرفة ما إذا كنت تتحول. دعونا نقول أن 75٪ من الوقت تستمر في السفر في نفس الاتجاه، و 25٪ من الوقت الذي ستحول فيه. عندما تقوم بدورها، قم دائما بدوره في اتجاه يقترب من B. هذا يعني أنه إذا كنت تتحرك إلى اليسار أو اليمين، فسيتعين عليك تشغيله، وإذا كنت تتحرك لأعلى، قم باختيار يمين / يسار بناء على مدى ما تقم به حاليا على اليمين أو يسار الهدف. أيضا، إذا ضربت واحدة من حدود العالم، بدوره!

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