انهيار دالة الموج: خوارزمية مستوحاة من ميكانيكا الكم

تنشئ خوارزمية "طي دالة الموجة" الصور النقطية المتشابهة محليًا مع الصورة النقطية للإدخال.

مظاهر محلية تعني ذلك

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

في الأمثلة ، القيمة القياسية لـ N هي 3.


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

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

في كل مرحلة ، ينخفض ​​إجمالي الانتروبيا ، وفي النهاية نحصل على حالة يمكن ملاحظتها تمامًا ، ينتهي انهيار وظيفة الموجة.

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

يتم تنفيذ خوارزمية انهيار دالة الموجات في C ++ و Python و Kotlin و Rust و Julia و Haxe و JavaScript ومتكيفة مع Unity . يمكن تنزيل الملفات القابلة للتنفيذ الرسمية من itch.io أو تشغيلها في المستعرض . يولد WFC مستويات في Bad North ، Caves of Qud ، والعديد من الألعاب الأصغر ، فضلاً عن العديد من النماذج الأولية. إنشائها أدى إلى دراسة جديدة . للاطلاع على الأعمال الأخرى ذات الصلة ، والشروحات ، والعروض التوضيحية التفاعلية ، والأدلة ، والدروس التعليمية ، والأمثلة ، راجع قسم المنافذ والشوك العرضية .

شاهد عرضًا توضيحيًا لخوارزمية WFC على YouTube: https://youtu.be/DOQTr2Xmlz0

خوارزمية

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

بلاط بطاقة جيل

أبسط حالة غير تافهة للخوارزمية هي النموذج NxN = 1x2 (بتعبير أدق ، NxM). إذا قمنا بتبسيطها أكثر ، مع الحفاظ على احتمالات أزواج الألوان ، ولكن دون احتمالات الألوان نفسها ، فسنحصل على ما يسمى "نموذج تجانب بسيط". مرحلة الانتشار في هذا النموذج هي ببساطة انتشار تبعية الحي. من المناسب تهيئة نموذج تجانب بسيط بقائمة من التجانبات وبيانات الجوار الخاصة بهم (يمكن اعتبار بيانات الجوار عددًا كبيرًا من العينات الصغيرة جدًا) ، بدلاً من صورة نقطية تم أخذ عينات منها.

GIF | GIFV

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


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









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

تجدر الإشارة أيضًا إلى أن مجموعة الدوائر Circuit و Summer و Rooms ليست من بلاط Van. بمعنى ، لا يمكن إنشاء بيانات الحي الخاص بهم من تلوين الحواف. على سبيل المثال ، في مجموعة بلاط الدائرة (الدائرة المتكاملة) ، لا يمكن أن يكون زاويتان متجاورتين ، على الرغم من أنهما يمكن توصيلهما باتصال (اتصال) ، ولا يمكن للمسارات القطرية تغيير الاتجاهات.

أبعاد أعلى

تعمل خوارزمية WFC بأبعاد أعلى تمامًا كما هي الحال في بعدين ، لكن الأداء يصبح مشكلة هنا. تم إنشاء هذه النماذج فوكسل في N = 2 في نموذج البلاط مع التداخل باستخدام كتل 5x5x5 و 5x5x2 والاستدلال إضافية (المرتفعات ، الكثافة ، انحناءات ...).


لقطات ذات أبعاد أعلى: 1 ، 2 ، 3 .

ستكون نماذج Voxel التي تم إنشاؤها باستخدام WFC وغيرها من الخوارزميات في مستودع منفصل.

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

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

إليك كيفية إكمال WFC تلقائيًا لمستوى الشخص الذي بدأه:

GIF | GIFV

تفي خوارزمية ConvChain بالإصدار الصارم للشرط (C2): توزيع حدود أنماط NxN في بيانات المخرجات التي ينشئها هو بالضبط توزيع الأنماط في بيانات الإدخال. ومع ذلك ، فإن ConvChain لا يرضي (C1): غالبًا ما يخلق آثارًا ملحوظة. من المنطقي أن تبدأ ConvChain أولاً للحصول على تكوين جيد العينات ، ثم WFC لتصحيح القطع الأثرية المحلية. هذا مشابه لاستراتيجية شائعة في التحسين: أولاً نقوم بتشغيل طريقة مونت كارلو للعثور على النقطة. بالقرب من المستوى العالمي الأمثل ، ثم قم بإجراء نزول التدرج من هذه النقطة لمزيد من الدقة.

تعد خوارزمية تركيب الأنسجة الخاصة بـ P.F. Harrison أسرع بكثير من WFC ، ولكنها تواجه مشكلات في الارتباطات الطويلة (على سبيل المثال ، يصعب تجميع هذه الخوارزمية مع قوام جدار القرميد بالطوب المدمج بشكل صحيح). في مثل هذه الحالات ، يُظهر WFC تفوقه ، وتدعم خوارزمية هاريسون القيود. من المنطقي أولاً إنشاء مخطط مثالي لجدران الطوب باستخدام WFC ، ثم إجراء خوارزمية تركيب نسيج محدودة لهذا المخطط.

تعليقات

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

يتوافق النموذج المتداخل مع نموذج بسيط بنفس الطريقة التي تتوافق بها سلاسل Markov عالية الترتيب مع سلاسل Markov من الدرجة الأولى.

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

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

لاحظ أن عينات "العقدة البسيطة" و "العقدة الخادعة" لا تحتوي على 2 بل 3 ألوان.

بعد واحد قد يكون الوقت. على وجه الخصوص ، يعرض WFC d الأبعاد الأبعاد سلوك أي تلقائي الخلوية (d-1) الأبعاد.

المراجع

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

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

الجمعية

WFC هو تطبيق وحدة الذي يعتمد فقط على المكتبة القياسية. قم بتنزيل .NET Core لنظام التشغيل Windows أو Linux أو macOS وتشغيله

 dotnet run WaveFunctionCollapse.csproj 

أو يمكنك استخدام إرشادات بناء المجتمع لأنظمة أساسية مختلفة في العدد المقابل . أنشأ Casey Marshall طلب سحب يبسط استخدام برنامج سطر الأوامر ويتضمن حزمة مبكرة.

الموانئ مثيرة للاهتمام ، والشوك العرضية

• أنشأ Emil Ernerfeld منفذًا في C ++ .
• أنشأ ماكس إلير مكتبة Kotlin (JVM) تسمى Kollapse . أنشأ Joseph Roscopf منفذًا تلو الآخر على إصدار Kotlin الأمثل لخوارزمية 2018. أنشأ إدوين جاكوبس مكتبة Kotlin أخرى.
• قام Kevin Chapelier بإنشاء منفذ على JavaScript .
• قام أوسكار ستالبيرج ببرمجة نموذج البلاط ثلاثي الأبعاد ، وهو نموذج البلاط ثنائي الأبعاد للشبكات غير المستوية في المجال. فيما يلي المجموعات ثلاثية الأبعاد الجميلة لهم: 1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 7 ، 8 ، 9 ، 10 ، 11 ، 12 ، 13 ، 14 ، 15 .
• قام جوزيف باركر بتكييف WFC for Unity واستخدمه لإنشاء تزلج على الجليد في لعبة Proc Skater 2016 ، وهضاب رائعة في لعبة Swapland 2017 ومستويات المنصات في 2018 Bug with a Gun .
• قام مارتن أوليري بتطبيق خوارزمية تشبه WFC لتوليد الشعر: 1 ، 2 ، 3 ، 4 .
• أنشأ Nick Nenov مجموعة ثلاثية الأبعاد من وحدات فوكسل استنادًا إلى مجموعة البلاط الخاصة بـ Castle. يستخدم Nick خيار إخراج النص إلى نموذج التجانب لإعادة إنشاء نماذج ثلاثية الأبعاد في Cinema 4D.
• قام شون ليفلر بتطبيق نموذج مع تداخل على الصدأ .
• rid5x يخلق نسخة من WFC على OCaml .
• لقد نشرت نموذجًا بسيطًا للبلاط ثلاثي الأبعاد حتى يتمكن الأشخاص من إنشاء مجموعات ثلاثية الأبعاد خاصة بهم دون انتظار مستودع كامل لخوارزمية ثلاثية الأبعاد.
• قمت بإنشاء نموذج تفاعلي للنموذج المتداخل. يمكن تنزيل واجهة المستخدم الرسومية القابلة للتنفيذ من صفحات WFC على موقع itch.io.
• قام برايان باكلي بتجميع خط أنابيب من المستوى الأول للعبة Caves of Qud ، والتي تستخدم WFC في عدة تمريرات: 1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 7 ، 8 ، 9 ، 10 ، 11 ، 12 ، 13 ، 14 ، 15 ، 16 ، 17 ، 18 ، 19 ، 20 ، 21 .
• قام داني واين بتنفيذ نموذج البلاط ثلاثي الأبعاد .
• قام Arvi Teikari ببرمجة خوارزمية تخليق نسيج الإنتروبيا على لوا. استدار Headchant للعمل مع LÖVE.
• قام Isaac Curt بإنشاء منفذ على طراز Python مع تداخل.
• أنشأ Oscar Stalberg نسخة تفاعلية من نموذج التجانب الذي يتم تشغيله في المتصفح.
• قام مات ريكس بتطبيق نموذج البلاط ثلاثي الأبعاد ( 1 ، 2 ، 3 ، 4 ) وأنشأ نموذجًا ثلاثي الأبعاد للبلاط يكون فيه أحد الأبعاد هو الوقت ( 1 ، 2 ، 3 ، 4 ، 5 ).
• أنشأ نيك نينوف دليلًا مرئيًا لنظام التناظر في البلاط.
• قام Isaac Curt و Adam M. Smith بكتابة مقالة بحثية قاموا خلالها بصياغة WFC كمهمة ASP ، واستخدموا القيد العام لل clingo المعمم لإنشاء الصور النقطية ، وتجربة القيود العالمية ، وتتبع تاريخ WFC وتقديم وصف مفصل للخوارزمية.
• قام Sylvain Lefebvre بإنشاء تطبيق C ++ لتوليف النماذج ثلاثية الأبعاد ، ووصف عملية التفكير في إنشاء نموذج ، وأظهر مثالًا تضمن فيه قيود الحي ضمان توصيل الإخراج (يمكنك تجاوزه).
• لقد قمت بتعميم WFC ثلاثي الأبعاد بحيث يعمل مع مجموعة التناظر المكعب ويخلق مجموعة من المربعات التي تولد مشاهدًا على نمط Escher .
• هناك العديد من الطرق لتصور حالات الموجة التي يمكن ملاحظتها جزئيًا. في الكود ، يتم حساب قيم اللون للخيارات الممكنة للحصول على اللون النهائي. يُظهر Oscar Stalberg حالات يمكن ملاحظتها جزئيًا على شكل مستطيلات شفافة: كلما زادت الخيارات ، زاد المستطيل. في نظام voxel ، أتصور حالات الموجة بتصويت البكسل بكسل.
• نفذت ريمي ديفو نموذج التجانب في PICO-8 وكتبت مقالة عن توليد البيانات المتماسكة مع شرح WFC.
• بالنسبة للعبة Bad North ، يستخدم Oscar Stalberg منهجًا ارشاديًا يحاول تحديد هذه البلاطات بحيث تكون المنطقة المرصودة الناتجة في كل مرحلة ممكنة.
• نفذ وليام مانينغ نموذج تداخل في C # ؛ أولاً وقبل كل شيء ، سعى إلى جعل الشفرة قابلة للقراءة ، واستكمل برنامج WPF بواجهة رسومية.
• كتب جوزيف باركر برنامج WFC التعليمي لبرنامج Procjam 2017.
• صاغ أمان Tiwari قيد الاتصال كمهمة ASP عن clingo.
• قام MatveyK ببرمجة نموذج ثلاثي الأبعاد مع تداخل .
• يبحث Silvan Lefebvre و Lee Yu Wei و Connelly Barnes عن إمكانية إخفاء المعلومات داخل القوام. لقد قاموا بإنشاء أداة يمكنها تشفير الرسائل النصية على هيئة مربعات WFC وفك تشفيرها مرة أخرى. هذه التقنية تسمح باستخدام البلاط WFC كرموز QR.
• قام Mathieu Fer و Nathaniel Kuran بتحسين وقت تشغيل WFC بشكل كبير ، وذلك من أجل نموذج متداخل بترتيب من حيث الحجم. أنا دمج التحسينات الخاصة بهم في التعليمات البرمجية.
• قام Vasu Mahesh بنقل نموذج تجانب ثلاثي الأبعاد لـ TypeScript ، وقام بإنشاء مجموعة تجانب جديدة وتصور عملية التوليد في WebGL.
• قام Kim Huanghee بتجربة WFC ثلاثية الأبعاد وقام بإنشاء / تكييف العديد من مجموعات voxel: 1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 7 ، 8 .
• قدم أوسكار ستالبيرج عرضًا تقديميًا عن جيل المستوى في باد الشمالية في مؤتمر كل شيء الإجرائي 2018.
• كتبت عن كيفية إنشاء مسارات غير مشوهة (تقريبًا) بين نقطتين باستخدام خوارزميات WFC وغيرها.
• نشر Aiser Curt و Adam M. Smith مطبوعًا يصف النظام القائم على WFC ، والذي يتعلم من الأمثلة الإيجابية والسلبية ، وتحدثوا عنه في السياق العام للحوارات مع نماذج المولدات.
• يستخدم براندان أنتوني WFC لإنشاء زخارف الجدران في رودينا .
• قام تيم كونج بتطبيق نموذج متداخل على Haxe .
• قام بوريس ذا برايف بتطبيق طريقة الحفر على WFC لإنشاء هياكل متصلة. وقد نشر مكتبة تدعم الشبكات سداسية ، والقيود الإضافية ، والتراجع.
• صممت ماريان كلاينبرج لـ Procjam 2018 مولدًا للمدينة استنادًا إلى نموذج البلاط. وقد كتب مقالاً يصف فيه نهجه في تحديد الحي ، والعودة إلى الإنترنت ، وصيغ WFC عبر الإنترنت.
• قامت Sol Bekic ببرمجة نموذج البلاط القائم على GPU باستخدام PyOpenCL. بدلاً من تخزين قائمة انتظار من العقد التي يتم تنفيذ التوزيع منها ، يقوم هذا النموذج في وقت واحد بالتوزيع من كل عقدة شبكة.
• طبق Wouter van Oortmerssen نموذج التجانب في دالة C ++ واحدة بهيكل لتسريع الملاحظة ، على غرار قائمة انتظار الأولوية.
• طبق روبرت هونيغ نموذجًا يتداخل مع جوليا مع خيار توزيع القيود محليًا فقط.
• تطبيق إدوين جاكوبس WFC لنقل الأسلوب والتردد .

شكر وتقدير

بعض الأمثلة مأخوذة من ألعاب Ultima IV و Dungeon Crawl . الدوائر Tileset مأخوذة من ماريو Klingemann . تم اقتراح فكرة إنشاء دوائر متكاملة بواسطة Moonasaur ، وتم أخذ أسلوبها من لعبة Ruckingenur II بواسطة Zachtronics. تم أخذ مثال تداخل Cat من فيديو Nyan Cat ، تم إنشاء مثال Qud بواسطة Brian Buckley ، وأمثلة Magic Office + Spirals هي rid5x ، ومثالات Colored City + Link + Link 2 + Mazelike + Red Dot + Smile City هي Arvi Teikari. تم إنشاء Tileset Summer بواسطة Hermann Hillmann. يتم تقديم نماذج Voxel في MagicaVoxel .