توليد العوالم باستخدام خوارزمية "انطباق الدالة الموجية"

توليد عام متقدم

من قبل Joseph Parker

توليد العوالم باستخدام خوارزمية "انطباق الدالة الموجية"

"انطباق الدالة الموجية" Wave Function Collapse (WFC) من قبل exutumno@ هي خوارزمية جديدة يمكنها توليد الأنماط الإجرائية ابتداءاً من صورة نموذجية. إنها أداة مثيرة للغاية بخاصة من أجل مصممي الألعاب، لأنها تدعنا أن نرسم أفكارنا بدلاً من أن نقوم ببنائها يدوياً. سنقوم بإلقاء نظرة على أنواع المخرجات التي يمكن توليدها باستخدام الخوارزمية وعن معنى كل وسيط "Parameter" من مدخلات الخوارزمية. ثم سنأخذ جولة حول كيفية إعداد الخوارزمية في JavaScript وفي محرك Unity.

الطريقة التقليدية لصنع هذا النوع من المخرجات هو إنشاء خوارزميات عدة بشكل يدوي لتوليد المعالم، ثم ضمها مع بعضها البعض لتحويل خريطة اللعبة. على سبيل المثال، يمكننا رش شجرات في مواقع عشوائية ورسم طرقات باستخدام خوارزمية الحركة البراونية "Brownian Motion" وإضافة الغرف باستخدام تقسيم الثنائي للفضاء "Binary Space Partition". ذلك الأسلوب قوي لكنه يستهلك وقتاً طويلاً، وقد تضيع فكرتك الأصلية من طول العملية.

استخدام انطباق الدالة الموجية (وخاصة نموذج التداخل) يجعل هذا النوع من التوليد بديهياً، هنا أنت تقوم برسم مثال ثم تحصل على عدد لانهائي من التنويعات المختلفة. هناك أيضاً عاملٌ من التعاون مع الآلة، أي أن المنتج الصادر قد يكون مفاجئاً وأحياناً تقودك لتغيير تصميمك.

انطباق الدالة الموجية مثيرة خصوصاً من أجل مصممي ألعاب الزنقة "game jam"، حيث يكون الوقت محدوداً من أجل تصميم لعبة كاملة. عندما ننشأ الخوارزمية في مشروعنا، سيمكننا صنع تشكيلة متنوعة من أنواع الأنماط الإجرائية في دقائق.

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

تتألف خوارمية انطباق الدالة الموجية من قسمين: نموذج إدخال "input Model"، ومصلح قيود "constraint Solver".

• نموذج الرقع البسيطة Simple Tiled Model يستخدم ملف xml يعرّف الارتباطات المسموحة بين الرقع المختلفة.
• نموذج التداخل Overlap Model يقسم نمط الإدخال إلى كتل من الأنماط، الأمر يشبه سلسلة ماركوف ثنائية الأبعاد "2D markov chain".

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

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

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

ملاحظة: هذا الاستعراض التفاعلي على الويب من قبل أوسكار ستالبرغ هو طريقة رائعة لفهم كيفية عمل الخوارزمية. تمكنك من لعب دور مرحلة المراقبة وترسم اللعبة مرحلة البث بعد اختيارك لقيم شبكة الخريطة.

استخدام انطباق الدالة الموجية

إن المهمة الأولى هي إيجاد نسخة من الخوارزمية في لغة البرمجة التي تستعملها. الخوارزمية الأصلية مكتوبة في C#، ولكن يوجد العديد من الترجمات إلى لغات برمجة أخرى. (إن كنت مهتماً بترجمة الخوارزمية إلى لغة برمجة أخرى وأردت معلماً فاتصل بي)

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

يتألف عادة أسلوب العمل من:

• إنشاء نموذج مثيل جديد من الإدخال والوسطاء Parameters
• نداء model.Run لحل نمط الإخراج المراد
• حفظ أو قراءة الصورة المخرجة واستخدامها

شرح الوسطاء

دالة بناء النموذج Model Constructor

• name/input الاسم أو المدخل بيانات الإدخال. هذا النوع من الوسطاء يعتمد على ترجمة الخوارزمية المستخدمة. من أجل النسخة الأصلية من الخوارزمية فهي سلسلة محرفية string تمثل اسم الملف ($"samples/{name}.png")
• width,depth (int) العرض،العمق أبعاد بيانات الإخراج
• N (int) يمثل عرض وارتفاع الأنماط التي يقسم نموذج التداخل بيانات الإدخال إليها. عندما يقوم نموذج التداخل بالحل، فهو يحاول مطابقة الأنماط الفرعية تلك ببعضها. عند قيمة أعلى لـ N ستقبض على معالم أكثر من بيانات الإدخال، لكنها ستستهلك قدرات حسابية أكثر من الحاسوب، وقد تحتاج إلى عينة بيانات إدخال أكبر لتحقيق حلول موثوقة.
• periodic input (bool) إدخال دوري يمثل فيما إذا كان نمط الإدخال ذوي رقع قابلة للتكرار Tilable. إن كانت القيمة إيجابية، عندما توزع الخوارزمية بيانات الإدخال إلى كتل من أنماط N فإنها ستنشئ أنماطاً تربط الحواف اليمنى والسفلى باليسرى والعلوية. إن اخترت تفعيل هذا الخيار فعليك أن تتأكد أن بيانات الإدخال تبدو جيدة عندما تكون مرتبطة الحواف.
• periodic output (bool) إخراج دوري تحدد فيما إذا كانت حلول الإخراج ذات رقع قابلة للتكرار. إن هذا الخيار مفيد من أجل صنع أشياء مثل رسم الإكساء المتكرر tileable textures. ولكن له أثر مفاجئ على المنتج. عندما نستخدم خوازمية انطباق الدالة الموجية فيفضل أن نجرب التغيير بين وضعي الإخراج الدوري المفعل والمطفأ، ونتحقق فيما إذا كان أي من الخيارين يؤثر على نتائج بشكل جيد.
• symmetry (int) التناظر يمثل التناظرات الإضافية من نمط الإدخال التي سيتم توزيعها. 0 يعني فقط بيانات الإدخال الأصلية، يضيف ١ إلى ٨ تنويعات معكوسة التناظر وأخرى مدورة بزاويا قائمة. قد تحسن هذه التنويعات الأنماط في بيانات الإدخال، ولكنها ليست ضرورية. وهي تعمل فقط مع الرقع ذات الاتجاه الوحيد، وهي غير مرغوبة في اللعبة النهائية إذا كان رسم أو وظيفة الرقعة مرتبطة باتجاهها.
• ground (int) الأرض عندما لا يساوي 0، فهذا الوسيط يعين نمطاً من أجل الصف الأسفل من المخرج. يفيد عادة من أجل العوالم "العمودية"، حيث نريد أرضاً وسماءً منفصلتين. توافق القيمة مراتب أنماط المصفوفة داخلياً في نموذج التداخل، لذا يفضل القيام بعدة تجارب في هذا الوسيط لإيجاد قيمة مناسبة.

model.generate

• seed (int) البذرة يتم أخذ جميع القيم العشوائية الداخلية من هذه البذرة، إعطاء القيمة 0 سينتج بعدد عشوائي للبذرة.
• limit (int) الحد الأقصى عدد التكرارات التي سيتم القيام بها. إعطاء القيمة 0 سيجعل الخوارزمية تعمل حتى الانتهاء أو التناقض.

درس: كيفية إنشاء الخوارزمية في JavaScript

نزل نسخة من wfc.js ثم ضع الملف في مجلد مشروعك. نحن نستخدم نسخة معدلة من ترجمة تشابليير في JavaScript التي عدلت لتصبح ملفاً واحداً، مما يجعل التعامل معها أسهل من ناحية إضافتها إلى مشروع جديد.

الآن، أنشئ ملف index.html كالتالي:

<!DOCTYPE html>
<html>
  <head>
    <script src='wfc.js'></script>
    <style>
      canvas{
        border:1px solid black;
        image-rendering: pixelated;}
    </style>
  </head>
  <body>
    <canvas id="output" width="48" height="48"></canvas>
    <script>

    </script>
  </body>
</html>

تستخدم نسخة الـ ImageData JavaScript من أجل الإدخال والإخراج. سنبدأ بكتابة دالة تقوم بتحميل عنصر صورة، ورسمها على canvas مؤقت، واستخراج الـ ImageData من الصورة. لأن تحميل صورة لن يكون فورياً، سوف نستخدم رد callback function الذي سيصدر عند تحميل البيانات.

var img_url_to_data = function(path, callback){
  var img = document.createElement("img")
  img.src = path
  img.onload = function(e){
    console.log(this.width, this.height)
    var c = document.createElement("canvas")
    c.width = this.width
    c.height = this.height
    var ctx = c.getContext("2d")
    ctx.drawImage(this,0,0)
    callback(ctx.getImageData(0,0,this.width,this.height))
  }
}

باستخدام برنامج رسم، قم بإنشاء صورة صغيرة ثم احفظها باسم test.png، في مجلد مشروعك، تلك الصورة ستكون "بيانات الإدخال". مثال للصورة هو كالشكل التالي:

شغل صفحة index في المتصفح، ثم فعّل واجهة سطر الأوامر بالضغط على زر f12 واختبر دالة img_url_to_data التي صنعناها بكتابة التالي:

> img_url_to_data("test.png", console.log)
ImageData {data: Uint8ClampedArray(1024), width: 16, height: 16}

إن فتحت ملف index.html مباشرة في المتصفح، فسترى رسالة خطأ كالتالي:

index.html:25 Uncaught DOMException: Failed to execute 'getImageData' on 'CanvasRenderingContext2D':
The canvas has been tainted by cross-origin data.

ذلك لأن السماح لـ JavaScript بالوصول لمصادر خارج النطاق "domain" نفسه هو انتهاك لأمن الحواسيب، فلا يسمح المتصفح بتشغيل الدالة. يمكنك حل هذه المشكلة إما بتحميل مشروعك إلى سرفر ما، أو بتشغيل سرفر محلي على حاسوبك. يمكنك القيام بالخيار الثاني ببساطة عن طريق فتح واجهة سطر أوامر لـ python في مجلد المشروع وكتابة python3 -m http.server 8999 أو python2 -m SimpleHTTPServer 8999. يمكنك الآن تحميل صفحة index من الرابط التالي: http://localhost:8999

تشغيل نموذج التداخل

الآن، أدخل ImageData في نموذج OverlappingModel.

var start = function(id){
  output = document.getElementById("output")
  ctx = output.getContext("2d")
  imgData = ctx.createImageData(48, 48)
  // input, width, height, N, outputWidth, outputHeight, periodicInput, periodicOutput, symmetry, ground
  model = new OverlappingModel(id.data, id.width, id.height, 2, 48, 48, true, false, 1, 0)
  //seed, limit
  var success = model.generate(Math.random, 0)
  model.graphics(imgData.data)
  ctx.putImageData(imgData, 0, 0)
  console.log(success)
}

وأخيراً، استدعي دالة img_url_to_data مع رابط صورة الإدخال و "start" callback:

img_url_to_data("test.png", start)

إن سار كل شيء بشكل طبيعي، فسترى المخرج مرسوماً على الcanvas:

ملاحظة: قد يكون ممكناً حسب نمط الإدخال ألا تستطيع الخوارزمية من حل المخرج. في مشروع درسنا هذا، ذلك سينتج بـ canvas فارغ، وقيمة متغير success ستكون false. بينما يمكنك القيام بتعديل المدخل لزيادة فرص النجاح التام، فاستراتيجية أخرى هي بإعادة محاولة الخوارزمية حتى النجاح. يمكننا إضافة هذه ميزة عن طريق إضافة السطر التالي في آخر دالة start:

if (success == false){start(id)}

استخدام المخرَج

ستصنع خوارزمية انطباق الدالة الموجية مخرج بصيغة صورة (أياً كان نوع بيانات تلك الصورة). هذا الأمر مناسب من أجل إلقاء نظرة سريعة أو توليد إكساء صوري، ولكن من أجل مشروع لعبة لدينا صيغة بيانات محددة لتشكيل عوالمنا. سنجرب ذلك في مشروعنا الحالي: سنقوم بتحويل ImageData إلى مصفوفة من المصفوفات array of arrays تحمل قيمة رقم مفرد يمثل نوع الرقعة.

أولاً، ضف هذه الدالة للحصول على قيمة لون بكسل ما في ImageData:

function get_pixel(imgData, x, y) {
  var index = y*imgData.width+x
  var i = index*4, d = imgData.data
  return [d[i],d[i+1],d[i+2],d[i+3]]
}

سنصنع الآن جدول بحث للتحويل من قيمة اللون إلى رقم مفرد. لأن جداول JavaScript يمكنها فقط الاحتواء على مفتاح من نوع string، سنفترض أيضاً أن معلومات مصفوفة اللون مجتمعة ببعضها عبر حرف ":"

var colormap = {
  "0:0:0:255":1, //black
  "255:255:255:255":0 //white
}

وأخيراً، في دالة start سننشأ مصفوفة من المصفوفات بنفس أبعاد ImageData التي أنشأناها سابقاً، مضيفين للمصفوفة معلومات لكل بكسل:

  if (success == false){
    start(id)
  } else {
    var world = []
    for (var y = 0; y < 48; y++) {
      var row = []
      for (var x = 0; x < 48; x++) {
        var color = get_pixel(imgData, x, y).join(":")
        row.push(colormap[color])
      }
      world.push(row)
    }
    console.log(world)
  }

درس: إنشاء الخوارزمية في Unity

لنلقي نظرة سريعة على استخدام الخوارزمية في محرك ألعاب Unity باستخدام ملحق unity-wave-function-collapse. بدلاً من استخدام ملفات صور للإدخال والإخراج، فإن الخوارزمية تعمل مع ترتيبات من كائنات prefab GameObjects. إن الملحق مجهز للعمل باستخدام المكونات "components"، لذا لا داعي لكتابة أي سطر برمجي عند الاستخدام البسيط.

أنشئ مشروع Unity جديد، ثم لك الخيار إما تحميل ملف .unitypackage للملحق إلى المشروع، أو استنساخ كود المشروع من موقعه على github ووضعه في مجلد Assets المحلي في مشروعنا. سنقوم أيضاً بإنشاء مجلد فارغ اسمه Resources وسيحوي كائنات الرقع التي سنستخدمها.

سنحتاج الآن إلى قالب من الرقع tileset. من أجل تبسيط الأمور، سوف نصنع مكعباً ونسحبه بالفأرة إلى مجلد Resources لتحويله إلى prefeb. الملحق الذي نستخدمه يتطلب إعطاء الرقع توجيهاً بحيث يكون الاتجاه العامودي هو الحرف Y والاتجاه الأفقي هو الحرف X. لذا إن كنت تحمل مجسمات ثلاثية الأبعاد إلى المشروع، فيجب أن تقوم بتغيير إعدادات الـ export في برنامج النمذجة.

انشئ كائن GameObject فارغ في المشهد وسميه input، ثم ألحق مكون Training الذي نزلته من ملحق الخوارزمية إليه. ستقوم الخوارزمية باستيعاب الـ prefabs الأبناء لهذا الكائن المتواجدين في حدود أبعاد مكون Training. اسحب بالفأرة الـ prefabs إلى الكائن الجديد في نافذة heirarchy. قد تضطرّ إلى تغيير قيمة Gridsize في مكون Training تبعاً لأبعاد رقعك. عندما تكون أي رقعة ضمن الحدود فسترى كرة شفافة زرقاء في منتصفها.

ملاحظة: يوجد مكون يمكنه تسريع عملية صنع بيانات الإدخال اسمه Tile Painter، وهو يسمح للمستخدم باختيار مجسم ما من نوع prefab ثم رسمه على لوح الإدخال (مثل برنامج الرسام). عند إضافة prefabs داخل مصفوفة palette في المكون، سيظهر الـ prefab أسفل منطقة الرسم حيث يمكن تغيير الرقعة المختارة بسرعة عن طريق متابعة الضغط على زر S ثم الضغط على الprefab المراد بالفأرة. يمكنك أيضاً سحب مجلد من الـ prefabs إلى مصفوفة palette لتحميلهم جميعاً دفعة واحدة.

أنشئ كائن GameObjects فارغ وضف إليه مكون Overlap WFC، سيتم لحاق المكون تلقائياً ببيانات الإدخال التي صنعتها. يمكنك الآن الدخول في وضع اللعب عبر ضغط زر Play في يونتي وسيتم توليد مخرج من أجل الأبعاد المعطاة. يمكنك أيضاً ضغط زر توليد generate أو زر تفعيل RUN لرؤية المخرج في وضع العمل.

نصائح وخدع

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

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

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

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

---