كيفية ترميز مولد خريطة الأبراج المحصنة الإجرائية باستخدام خوارزمية المشي العشوائي

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

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

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

هناك العديد من أنواع الخرائط ثنائية الأبعاد ، ولكل منها الخصائص التالية:

1. المناطق التي يمكن الوصول إليها والتي يتعذر الوصول إليها (الأنفاق والجدران).

2. مسار متصل يمكن للاعب التنقل فيه.

تأتي الخوارزمية في هذا البرنامج التعليمي من Random Walk Algorithm ، أحد أبسط الحلول لإنشاء الخرائط.

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

لمشاهدة عرض توضيحي ، افتح مشروع CodePen أدناه ، وانقر فوق الخريطة لإنشاء خريطة جديدة ، وتغيير القيم التالية:

  1. الأبعاد: عرض الخريطة وارتفاعها.
  2. MaxTunnels: أكبر عدد من الأدوار التي يمكن أن تأخذها الخوارزمية أثناء عمل الخريطة.
  3. MaxLength: أقصى طول لكل نفق ستختاره الخوارزمية قبل عمل منعطف أفقي أو عمودي.

ملاحظة: كلما تمت مقارنة maxTurn بالأبعاد ، كلما زادت كثافة الخريطة. كلما قورنت الطول الأقصى بالأبعاد ، كلما بدا "النفق ص".

بعد ذلك ، دعنا نذهب إلى خوارزمية إنشاء الخريطة لنرى كيف:

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

تستمر هذه الحلقة حتى يصبح عدد الأنفاق صفراً.

الخوارزمية في الكود

نظرًا لأن الخريطة تتكون من خلايا النفق والجدران ، فيمكننا وصفها بأنها أصفار وتلك الموجودة في صفيف ثنائي الأبعاد كما يلي:

الخريطة = [[1،1،1،1،0] ،
       [1،0،0،0،0]،
       [1،0،1،1،1]،
       [1،0،0،0،1]،
       [1،1،1،0،1]]

نظرًا لأن كل خلية في صفيف ثنائي الأبعاد ، يمكننا الوصول إلى قيمتها من خلال معرفة صفها وعمودها مثل الخريطة [صف] [عمود].

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

createArray (الأسطوانات والأبعاد) {
    فار مجموعة = [] ؛
    لـ (var i = 0 ؛ أنا <الأبعاد ؛ i ++) {
      array.push ([])؛
      لـ (var j = 0 ؛ j <بعاد ؛ j ++) {
         مجموعة [أنا]. دفع (الأسطوانات)؛
      }
    }
    مجموعة العودة ؛
}

لتطبيق خوارزمية المشي العشوائي ، عيّن أبعاد الخريطة (العرض والارتفاع) ، ومتغيرات themaxTunnels ، ومتغير الطول.

createMap () {
 دع الأبعاد = 5 ،
 maxTunnels = 3 ،
 الطول الأقصى = 3 ؛

بعد ذلك ، قم بعمل صفيف ثنائي الأبعاد باستخدام وظيفة المساعد المحددة مسبقًا (صفيف ثنائي الأبعاد من تلك).

اسمحوا الخريطة = createArray (1 ، الأبعاد) ؛

قم بإعداد عمود عشوائي وصفي عشوائي لإنشاء نقطة بداية عشوائية للنفق الأول.

دع currentRow = Math.floor (Math.random () * الأبعاد) ،
    currentColumn = Math.floor (Math.random () * الأبعاد) ؛

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

على سبيل المثال ، للانتقال إلى خلية حول الخلية [2] [2] ، يمكنك إجراء العمليات التالية:

  • للصعود ، اطرح 1 من صفها [1] [2]
  • للنزول ، أضف 1 إلى صفها [3] [2]
  • للانتقال إلى اليمين ، أضف 1 إلى العمود [2] [3]
  • للذهاب إلى اليسار ، قم بطرح 1 من العمود [2] [1]

توضح الخريطة التالية هذه العمليات:

عرض الاتجاهات على الخريطة.

الآن ، قم بتعيين متغير الاتجاهات على القيم التالية التي ستختارها الخوارزمية قبل إنشاء كل نفق:

اسمحوا الاتجاهات = [[-1 ، 0] ، [1 ، 0] ، [0 ، -1] ، [0 ، 1]] ؛

أخيرًا ، قم ببدء متغير randomDirection للاحتفاظ بقيمة عشوائية من صفيف الاتجاهات ، وقم بتعيين متغير lastDirection على صفيف فارغ سيحتوي على قيمة randomDirection الأقدم.

ملاحظة: صفيف lastDirection فارغ في الحلقة الأولى لأنه لا توجد قيمة randomDirection قديمة.

دع lastDirection = [] ،
    randomDirection.

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

على سبيل المثال ، إذا كان lastTurn الخاص بك هو [0 ، 1] ، فإن حلقة التنفيذ أثناء العمل تمنع الوظيفة من التحرك للأمام حتى يتم ضبط randomDirection على قيمة ليست [0 ، 1] أو العكس [0 ، -1].

فعل {
randomDirection = direction [Math.floor (Math.random () * direction.length)] ؛
} في حين ((randomDirection [0] === -lastDirection [0] &&
          randomDirection [1] === -lastDirection [1]) ||
         (randomDirection [0] === lastDirection [0] &&
          randomDirection [1] === lastDirection [1])) ؛

في حلقة العمل أثناء القيام ، هناك شرطان أساسيان مقسومان على | (OR) علامة. يتكون الجزء الأول من الشرط أيضًا من شرطين. يتحقق الأول من أن العنصر الأول لـ randomDirection هو عكس العنصر الأول lastDirection. يتحقق العنصر الثاني إذا كان العنصر randomDirection الثاني هو عكس العنصر lastTurn الثاني.

للتوضيح ، إذا كان lastDirection هو [0،1] و randomDirection هو [0 ، -1] ، فإن الجزء الأول من الشرط يتحقق إذا كان randomDirection [0] === - lastDirection [0]) ، والذي يعادل 0 == = - 0 ، وهذا صحيح.

ثم ، يتحقق إذا كان (randomDirection [1] === - lastDirection [1]) والذي يعادل (-1 === -1) وصحيح أيضًا. نظرًا لأن كلا الشرطين صحيحين ، تعود الخوارزمية للعثور على اتجاه عشوائي آخر.

يتحقق الجزء الثاني من الشرط من أن القيمتين الأولى والثانية لكلتا الصفيفتين متماثلتان.

بعد اختيار randomDirection الذي يفي بالشروط ، قم بتعيين متغير لاختيار طول عشوائيًا من الطول الأقصى. قم بتعيين متغير tunnelLength على صفر للخادم كمكرر.

دع randomLength = Math.ceil (Math.random () * maxLength) ،
    tunnelLength = 0؛

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

بينما (tunnelLength 

عدا ذلك ، قم بتعيين الخلية الحالية للخريطة على صفر باستخدام currentRow و currentColumn. أضف القيم في مصفوفة randomDirection عن طريق تحديد currentRow و currentColumn حيث يجب أن تكون في التكرار القادم للحلقة. الآن ، زيادة التكرار tunnelLength.

آخر{
  map [currentRow] [currentColumn] = 0 ؛
  currentRow + = randomDirection [0]؛
  currentColumn + = randomDirection [1]؛
  tunnelLength ++؛
 }
}

بعد أن تقوم الحلقة بإنشاء نفق أو انكسار عن طريق ضرب حافة الخريطة ، تحقق مما إذا كان النفق بطول كتلة واحدة على الأقل. إذا كان الأمر كذلك ، فاضبط lastDirection على maxTunnels randomDirection وتناقص والعودة لإنشاء نفق آخر مع randomDirection آخر.

if (tunnelLength) {
 lastDirection = randomDirection؛
 maxTunnels--.
}

تمنع عبارة IF هذه الحلقة التي وصلت إلى حافة الخريطة ولم تنشئ نفقًا من خلية واحدة على الأقل لتقليل حجم maxTunnel وتغيير lastDirection. عندما يحدث ذلك ، تذهب الخوارزمية للعثور على اتجاه عشوائي آخر للمتابعة.

عندما تنتهي من رسم الأنفاق و maxTunnels هي صفر ، أعد الخريطة الناتجة بكل المنعطفات والأنفاق.

}
 خريطة العودة
}؛

يمكنك رؤية الخوارزمية الكاملة في المقتطف التالي:

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

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

شكر خاص لـ Tom (@ moT01 on Gitter) لمشاركته في كتابة هذا المقال.