نتعامل مع خوارزمية انهيار دالة الموجة

منذ ظهور DeBroglie و Tessera ، طُلب مني عدة مرات لشرح كيفية عملهم. قد يبدو التوليد مثل السحر ، لكن القواعد التي تقف وراءه بسيطة بالفعل.

إذن ما هي خوارزمية طي دالة الموجة (WFC)؟ تم تطويره بواسطة Maxim Gumin لإنشاء صور "مبلطة" استنادًا إلى تكوين بسيط أو عينات صورة. يمكن للخوارزمية أن تفعل الكثير: انظر من خلال الأمثلة المقدمة من Maxim و Twitter #wavefunctioncollapse ، شاهد هذا الفيديو . التنوع مذهل.


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

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

ملحوظة:يصف هذا الدليل المفاهيم المختلفة ، وليس الأساليب والتعليمات البرمجية. إذا كنت مهتمًا بالتطبيق ، فيمكنك استخدام مكتبة WFC المفتوحة المصدر ( github ، التوثيق ). على الرغم من أنه من الأفضل أن تبدأ الدراسة بتنفيذ مكسيم . إذا كنت تستخدم Unity ، يمكنك شراء Tessera ، فهذه هي أداتي لتطبيق WFC في هذا المحرك.

سودوكو مصغرة

كمهمة توضيحية ، أخذت ميني سودوكو . هذا لغز يشبه شبكة 4 × 4 مع أرقام في بعض الخلايا.


الهدف هو ملء كل خلية فارغة برقم من 1 إلى 4 وفقًا للقواعد:

• يجب أن يكون كل رقم من 1 إلى 4 موجودًا في كل صف في نسخة واحدة.
• يجب أن يكون كل رقم من 1 إلى 4 موجودًا في كل عمود في نسخة واحدة.
• يجب أن يكون كل رقم من 1 إلى 4 موجودًا في كل مربع زاوية 2 × 2 في نسخة واحدة.

ووفقًا لهذه القواعد ، سيكون الحل كما يلي:


ربما كنت قد حل هذا اللغز بسهولة. لكننا مهتمون بكيفية قيام الكمبيوتر بذلك. يمكن تقسيم المشكلة إلى قسمين: وصف لظروف الكمبيوتر ، ثم حل باستخدام الخوارزمية.

وصف الشروط

عادة ، يتم استخدام لغة برمجة في القيود لهذا الغرض. هناك العديد من هذه اللغات ، ومبادئ عملها متشابهة.

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

ثم لكل متغير نحدد المجال : مجموعة من القيم الممكنة. في سودوكو ، لكل خلية فارغة ، سيكون النطاق {1 ، 2 ، 3 ، 4}. وبالنسبة للخلية التي تم إدخال 1 فيها بالفعل ، سيكون النطاق {1}.

أخيرا ، وضعنا القيود: قواعد ملزمة لمتغيراتنا. في معظم لغات البرمجة ، توجد بالفعل وظيفة ذات قيود all_distinct(..)تحتاج إلى تمرير قيم فريدة. لذا يمكن ترجمة قواعد Sudoku إلى 12 قيود all_distinct- واحدة لكل صف وعمود ، وكذلك لمربعات الزاوية 2 × 2. نحن بحاجة إلى نوع واحد فقط من القيود لحل هذه المشكلة ، ومع ذلك ، عادة ما تأتي أدوات حل المشكلات لإرضاء القيود مع مكتبة كبيرة من أنواع مختلفة من القيود لوصف مشكلتك.

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

خوارزميات لحل مشاكل الرضا بالقيود

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


هذه كلها قيم محتملة في المجالات المتغيرة.

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


كرر هذه العملية مع جميع القيود 12. وهذا ما يسمى نشر القيود ، لأن المعلومات يتم توزيعها من متغير إلى آخر من خلال القيود.


وانظر ، لدينا متغيرات ، في المجالات التي تبقى فيها قيمة واحدة. يجب أن تكون هذه هي الحلول الصحيحة لهذه المتغيرات.


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

نحن نعقد المهمة

لسوء الحظ ، لا يمكن حل جميع الألغاز المنطقية بهذه السرعة. هنا سودوكو كبير ، يعمل بنفس الطريقة ، باستثناء أنه لدينا الآن 9 قيم مختلفة ، 9 صفوف ، 9 أعمدة و 9 3 × 3 مربعات.


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


الآن جميع القيود شائعة ، ولكن لا تزال هناك متغيرات غير محددة.

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

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

الآن يمكننا نشر القيود أكثر قليلاً. إليك ما حصلت عليه في العمود الأوسط:


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

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

في مواجهة مثل هذا التناقض ، نقوم بعملية البحث عن الإرجاع(التراجع). أولاً ، نستعيد الحالة التي كانت قبل افتراضنا. ثم نقوم بإزالة القيمة التي استخدمناها من الافتراض من المجال - لم تعد الإجابة الصحيحة.


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

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

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

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

نعود إلى انهيار الدالة الموجية

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

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

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

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

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

هناك العديد من الإضافات للمبادئ المذكورة أعلاه التي تضيف النعمة والأداء إلى الخوارزمية. لكن دعنا ننظر أولاً إلى الخطوات الموضحة.

مثال

لنفترض أننا بحاجة لملء شبكة 3 في 3 بأربعة أنواع من البلاط:


القيود هي: يجب أن تتطابق ألوان البلاط المجاور مع بعضها البعض.

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

أولاً ، في كل خلية ، يمكن وضع البلاط من أي نوع:


قم بتشغيل حلقة WFC الرئيسية. حدد خلية بشكل عشوائي ، على سبيل المثال ، أعلى اليسار. الآن حدد مربع في المجال وحذف جميع الآخرين.


توزيع القيود. تنطبق القاعدة الوحيدة على المربعات المجاورة ، لذلك نحتاج إلى تحديث خليتين:


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


لم يعد بإمكاننا توزيع القيود ، لذلك نكرر الدورة الرئيسية: اختيار الخلية ، واختيار البلاط والتوزيع. هذه المرة نأخذ الخلية الوسطى العليا:


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


بشكل عام ، أنت تفهم الفكرة. يمكنك ملء بقية الخلايا بنفسك.

إذا كنت ترغب في تجربة مثال تفاعلي أكثر تعقيدًا ، أوصي بهذا .

أصغر الكون

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

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

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

$$

$$entropy = — \sum p_{i}log(p_{i})$$

هذا هو ملخص البلاط في المجال حيث $$$p_{i}$- احتمالية هذا البلاط.

الحوسبة الفعالة

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

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

علاوة على ذلك ، للتحقق من قيود المجاورة ، نحتاج إلى إجابة السؤال: "بالنظر إلى البلاط في مجال الخلية A ، ما هي البلاط الممكنة في مجال الخلية B إذا كانت الخلايا متجاورة؟"

يُطلق على هذا السؤال أحيانًا اسم "دعم" الخلية A. بالنسبة لبلاطة معينة "b" في المجال B ، من السهل حساب دورات المربعات في المجال A. لا يزال مناسبًا ، على الأقل لزوج البلاط المعني. إذا لم يكن هناك مثل هذا المربع في A ، فلا يمكنك وضع المربع "b" من المجال B ، ويمكننا التخلص منه.

الحلقات تجعل من السهل تنفيذ هذا في التعليمات البرمجية ، ولكنها ستعمل ببطء شديد. وإذا قمنا بتخزين المعلومات في بنية بيانات إضافية ، فيمكننا الإجابة على السؤال بسرعة حسب الضرورة. البيانات الجديدة عبارة عن مصفوفة كبيرة مع إدخالات لكل جانب من كل خلية وكل مربع. في مثالنا ، هناك 9 خلايا ، لكل منها 4 جوانب ، و 4 أنواع من البلاط. لذلك نحن بحاجة إلى 9 * 4 * 4 سجلات. سنحفظ عدادات الدعم في المصفوفة: لكل خلية / مربع / جانب ، نحسب عدد المربعات في مجال الخلية المجاورة التي يمكن وضعها بجانب المربع المعني. إذا انخفض العداد إلى الصفر ، فلا يمكن وضع هذا البلاط ، لأنه لا يمكن لأحد أن يكون مجاورًا له.

ملحقات الخوارزمية

نظرًا لأن WFC يعتمد على فهم أكثر عمومية للمشكلات المقيدة ، فهناك العديد من الطرق لتوسيع الخوارزمية عن طريق تغيير القيود المستخدمة.

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




يمكنك إدخال قيود إضافية: إصلاح مربعات معينة ، أو إنشاء "وحدات" من عدة خلايا.

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

في مقال آخر ، تحدثت عن كيفية تحقيق أفضل النتائج من WFC.

تداخل WFC

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

اقترح ماكسيم مفهوم تداخل WFC: استبدلنا قيد المجاور بقيد جديد يؤثر على عدة مربعات في وقت واحد. على سبيل المثال ، بحيث عند الإخراج ، تتوافق كل مجموعة من 3 × 3 خلايا مع مجموعة 3 × 3 من عينة شبكة. سيتم تكرار الأنماط الموجودة في العينة مرارًا وتكرارًا في اختلافات مختلفة عند الإخراج:


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

ماذا بعد؟

يعد حل المشكلات المتعلقة بالقيود مجالًا كبيرًا ومتطورًا لعلوم الكمبيوتر ، ولم أتطرق إليه إلا. WFC - تمامًا مثل أي خوارزمية الجيل الإجرائي الأخرى لحل المشكلات المقيدة - لا يزال جديدًا. أوصي القراءة ص / proceduralgeneration ، #wavefunctioncollapse ، exutumno و osksta للحصول على فكرة من حالات الاستخدام الأخيرة.

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