كيفية بناء مولّد خرائط متاهات إجرائي باستخدام خوارزمية المشي العشوائي في JavaScript

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

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

• مناطق يمكن الوصول إليها (أنفاق) ومناطق غير قابلة للوصول (جدران).
• مسار متصل يمكن للاعب التنقل عبره.

فهم خوارزمية المشي العشوائي لتوليد الخرائط

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

تجربة عملية: استكشاف مولد الخرائط

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

• Dimensions: يحدد عرض وارتفاع الخريطة (مثلاً، خريطة 5×5).
• MaxTunnels: يمثل الحد الأقصى لعدد الأنفاق أو المنعطفات التي يمكن للخوارزمية اتخاذها أثناء بناء الخريطة.
• MaxLength: يحدد أقصى طول لكل نفق تختاره الخوارزمية قبل اتخاذ منعطف أفقي أو عمودي.

See the Pen CreatMap by Ahmad Abdolsa (@abdolsa) on CodePen.

ملاحظة هامة: كلما زادت قيمة MaxTunnels مقارنة بـ Dimensions، أصبحت الخريطة أكثر كثافة وتشابكًا. وبالمثل، كلما زادت قيمة MaxLength مقارنة بـ Dimensions، بدت الخريطة وكأنها تحتوي على أنفاق أطول وأكثر امتدادًا.

آلية عمل الخوارزمية خطوة بخطوة

دعنا نستعرض الآن الخطوات الأساسية التي تتبعها خوارزمية توليد الخرائط:

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

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

تطبيق الخوارزمية برمجياً باستخدام JavaScript

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

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

map = [[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]]

بما أن كل خلية تقع ضمن مصفوفة ثنائية الأبعاد، يمكننا الوصول إلى قيمتها بمعرفة رقم الصف (row) والعمود (column) الخاص بها، مثل map[row][column]. قبل الشروع في كتابة الخوارزمية الرئيسية، سنحتاج إلى دالة مساعدة (helper function) تستقبل قيمة أولية (num) وبعدًا (dimensions) كمعاملات، وتقوم بإرجاع مصفوفة ثنائية الأبعاد مملوءة بتلك القيمة.

الدالة المساعدة createArray()

هذه الدالة تُنشئ مصفوفة ثنائية الأبعاد بالحجم المحدد وتملأها بقيمة ابتدائية:

createArray(num, dimensions) {
    var array = [];
    for (var i = 0; i < dimensions; i++) {
        array.push([]);
        for (var j = 0; j < dimensions; j++) {
            array[i].push(num);
        }
    }
    return array;
}

تهيئة المتغيرات الأساسية

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

createMap() {
    let dimensions = 5,
        maxTunnels = 3,
        maxLength = 3;

بعد ذلك، نقوم بإنشاء مصفوفة ثنائية الأبعاد تمثل الخريطة باستخدام الدالة المساعدة createArray() التي عرفناها سابقًا، مع ملئها بالرقم 1 لتمثيل الجدران.

إنشاء الخريطة وتحديد نقطة البداية

    let map = createArray(1, dimensions);

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

تحديد الموضع الحالي ونقاط الاتجاه

    let currentRow = Math.floor(Math.random() * dimensions),
        currentColumn = Math.floor(Math.random() * dimensions);

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

• للانتقال للأعلى: اطرح 1 من رقم الصف [1][2].
• للانتقال للأسفل: أضف 1 إلى رقم الصف [3][2].
• للانتقال لليمين: أضف 1 إلى رقم العمود [2][3].
• للانتقال لليسار: اطرح 1 من رقم العمود [2][1].

توضح الصورة التالية هذه العمليات بشكل مرئي:

تعريف الاتجاهات ومتغيرات التتبع

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

    let directions = [
        [-1, 0], // أعلى
        [1, 0],  // أسفل
        [0, -1], // يسار
        [0, 1]   // يمين
    ];

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

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

تهيئة متغيرات الاتجاه

    let lastDirection = [],
        randomDirection;

بعد ذلك، يجب التأكد من أن قيمة maxTunnels ليست صفرًا، وأن قيم الأبعاد (dimensions) و maxLength قد تم استلامها بشكل صحيح. ستستمر الخوارزمية في البحث عن اتجاهات عشوائية حتى تجد اتجاهًا ليس عكسيًا أو مطابقًا لـ lastDirection.

تساعد حلقة do while هذه في منع الكتابة فوق النفق الذي تم رسمه للتو أو رسم نفقين متتاليين في نفس الاتجاه أو عكسه. على سبيل المثال، إذا كان lastDirection هو [0, 1] (يمين)، فإن حلقة do while تمنع الدالة من المضي قدمًا حتى يتم تعيين randomDirection إلى قيمة ليست [0, 1] (يمين) ولا [0, -1] (يسار).

منطق حلقة do while لتجنب التكرار العكسي أو المطابق

    do {
        randomDirection = directions[Math.floor(Math.random() * directions.length)];
    } while ((randomDirection[0] === -lastDirection[0] && randomDirection[1] === -lastDirection[1]) ||
             (randomDirection[0] === lastDirection[0] && randomDirection[1] === lastDirection[1]));

تتكون حلقة do while من شرطين رئيسيين يفصل بينهما عامل التشغيل المنطقي || (أو). الجزء الأول من الشرط يتكون أيضًا من شرطين فرعيين:

1. يتحقق الشرط الأول مما إذا كان العنصر الأول من randomDirection هو عكس العنصر الأول من lastDirection.
2. يتحقق الشرط الثاني مما إذا كان العنصر الثاني من randomDirection هو عكس العنصر الثاني من lastDirection.

لتوضيح ذلك، إذا كان lastDirection هو [0, 1] (يمين) و randomDirection هو [0, -1] (يسار)، فإن الجزء الأول من الشرط يتحقق مما إذا كان randomDirection[0] === -lastDirection[0]، وهو ما يعادل 0 === -0، وهذا صحيح (true). ثم يتحقق مما إذا كان randomDirection[1] === -lastDirection[1]، وهو ما يعادل -1 === -1، وهذا صحيح أيضًا (true). بما أن كلا الشرطين صحيحان، تعود الخوارزمية للبحث عن randomDirection آخر.

أما الجزء الثاني من الشرط، فيتحقق مما إذا كانت القيمتان الأولى والثانية لكلتا المصفوفتين (randomDirection و lastDirection) متطابقتين تمامًا.

بعد اختيار randomDirection الذي يفي بهذه الشروط، نقوم بتعيين متغير لاختيار طول عشوائي للنفق من قيمة maxLength. كما نقوم بتهيئة المتغير tunnelLength إلى الصفر ليعمل كمؤشر تكراري (iterator).

تحديد طول النفق وبدء الحفر

    let randomLength = Math.ceil(Math.random() * maxLength),
        tunnelLength = 0;

الآن، سنقوم بإنشاء نفق عن طريق تغيير قيمة الخلايا من 1 (جدار) إلى 0 (نفق) طالما أن قيمة tunnelLength أصغر من randomLength. إذا وصل النفق إلى حواف الخريطة أثناء هذه العملية، يجب أن تتوقف الحلقة (break).

حلقة while لإنشاء الأنفاق وتجنب الحواف

    while (tunnelLength < randomLength) {
        if (((currentRow === 0) && (randomDirection[0] === -1)) ||
            ((currentColumn === 0) && (randomDirection[1] === -1)) ||
            ((currentRow === dimensions - 1) && (randomDirection[0] === 1)) ||
            ((currentColumn === dimensions - 1) && (randomDirection[1] === 1))) {
            break;
        }

خلاف ذلك (else)، نقوم بتعيين الخلية الحالية في الخريطة إلى 0 (نفق) باستخدام قيم currentRow و currentColumn. ثم نضيف قيم مصفوفة randomDirection إلى currentRow و currentColumn لتحديد موقعهما في التكرار التالي للحلقة. أخيرًا، نزيد قيمة المؤشر tunnelLength.

تحديث الخريطة والموقع

        else {
            map[currentRow][currentColumn] = 0;
            currentRow += randomDirection[0];
            currentColumn += randomDirection[1];
            tunnelLength++;
        }
    }

بعد أن تُنهي الحلقة إنشاء نفق أو تتوقف بسبب الوصول إلى حافة الخريطة، نتحقق مما إذا كان النفق قد تم إنشاؤه بطول لا يقل عن خلية واحدة. إذا كان الأمر كذلك، نقوم بتعيين lastDirection ليكون هو randomDirection الحالي، ونُقلل قيمة maxTunnels، ثم نعود لإنشاء نفق آخر باتجاه عشوائي جديد (randomDirection).

التحقق من طول النفق وتحديث الحالة

    if (tunnelLength) {
        lastDirection = randomDirection;
        maxTunnels--;
    }
} // End of while (maxTunnels) loop (implicit from original)
return map;
}; // End of createMap function

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

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

createArray(num, dimensions) {
    var array = [];
    for (var i = 0; i < dimensions; i++) {
        array.push([]);
        for (var j = 0; j < dimensions; j++) {
            array[i].push(num);
        }
    }
    return array;
}

createMap() {
    let dimensions = 5,
        maxTunnels = 3,
        maxLength = 3;

    let map = createArray(1, dimensions);

    let currentRow = Math.floor(Math.random() * dimensions),
        currentColumn = Math.floor(Math.random() * dimensions);

    let directions = [
        [-1, 0], // Up
        [1, 0],  // Down
        [0, -1], // Left
        [0, 1]   // Right
    ];

    let lastDirection = [],
        randomDirection;

    while (maxTunnels) { // This loop implicitly covers the maxTunnels condition
        do {
            randomDirection = directions[Math.floor(Math.random() * directions.length)];
        } while ((randomDirection[0] === -lastDirection[0] && randomDirection[1] === -lastDirection[1]) ||
                 (randomDirection[0] === lastDirection[0] && randomDirection[1] === lastDirection[1]));

        let randomLength = Math.ceil(Math.random() * maxLength),
            tunnelLength = 0;

        while (tunnelLength < randomLength) {
            if (((currentRow === 0) && (randomDirection[0] === -1)) ||
                ((currentColumn === 0) && (randomDirection[1] === -1)) ||
                ((currentRow === dimensions - 1) && (randomDirection[0] === 1)) ||
                ((currentColumn === dimensions - 1) && (randomDirection[1] === 1))) {
                break;
            } else {
                map[currentRow][currentColumn] = 0;
                currentRow += randomDirection[0];
                currentColumn += randomDirection[1];
                tunnelLength++;
            }
        }

        if (tunnelLength) {
            lastDirection = randomDirection;
            maxTunnels--;
        }
    }
    return map;
};

تهانينا على إتمام قراءة هذا الدليل! أصبحت الآن مجهزًا بالمعرفة اللازمة لإنشاء مولّد خرائط خاص بك أو تحسين هذه النسخة. يمكنك استكشاف المشروع على CodePen وعلى GitHub كتطبيق React. شكرًا لقراءتك! إذا أعجبك هذا المقال، فلا تنسَ مشاركته على وسائل التواصل الاجتماعي. شكر خاص لـ "Tom" على المشاركة في كتابة هذا المقال.

الخلاصة التقنية

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