يصف هذا المنشور الخوارزمية المستخدمة في
Generate Worlds ، وهي أداة تتيح للمستخدمين إنشاء واستكشاف عوالم إجرائية من خلال بناء مجموعات صغيرة من مربعات voxel. سأقدم وصفًا موجزًا للخوارزمية ، وفي المشاركات التالية سأتحدث عن مزاياها في السرعة والمرونة مقارنة بالطرق الأخرى. لمعرفة المزيد حول ماهية الجيل الإجرائي القائم على القيد وما هو المثير للاهتمام فيه ، أوصي بقراءة
منصبي السابق .
إذا كنت ترغب في اختبار نقاط قوتك في إنشاء عوالم إجرائية باستخدام هذا النظام ، يمكنك
شراء Generate Worlds. إذا كان السعر مرتفعًا جدًا بالنسبة لك ، فتابع القراءة: سيمنحك هذا المنشور معلومات حول كيفية تنفيذ خوارزمية Generate Worlds بشكل مستقل.
مجموعات البلاط
في Generate Worlds ، يتم تجميع كل عالم من
مجموعة من المربعات (tileet). في جوهرها ، البلاط هي مجرد نماذج فوكسل صغيرة. لنبدأ بمثال. تتكون الصورة أدناه من 9 بلاطات. كما ترون ، يتكون كل بلاطة من وحدات فوكسل تظهر كمكعبات ملونة.
إذا قمت بترتيب نماذج فوكسل بطريقة منطقية ، يمكنك إنشاء مشهد رعوي جميل ، كما في الرسوم المتحركة أدناه. بواسطة "المنطق" أعني أن البلاط يتناسب معًا إذا كانت ألوانه على طول حافة المباراة المشتركة.
تتمثل مهمة خوارزمية "إنشاء عالم" في إكمال مثل هذا التجميع سريعًا وتلقائيًا. قبل الشروع في الخوارزمية ، دعونا نلقي نظرة على بيان المشكلة.
نحن نربط البلاط فيما بينهم
ألقِ نظرة على المجموعة التي تحتوي على 4 مجموعات:
هذه البلاط تشبه البلاط ثلاثي الأبعاد المبين أعلاه.
تقوم خوارزمية Generate Worlds بإنشاء
مجموعات تجانب صالحة باستخدام قاعدة واحدة بسيطة:
إذا كان هناك بلاسيان يلمسان بعضهما البعض ، يجب أن تتطابق جميع الألوان على طول حافة اللمس . تضفي هذه القاعدة طابعًا رسميًا على النهج الذي يستخدمه المصمم الحي لإنشاء عالم ثلاثي الأبعاد من بلاطات voxel.
في مجموعة مسموح بها من المربعات الأربعة الموضحة أعلاه ، يجب أن تلمس الخلايا الضوئية على طول الحدود الخلايا الضوئية فقط ، ويجب أن تلمس الخلية المظلمة الخلايا المظلمة فقط. على سبيل المثال:
أمثلة على الاتصالات الصحيحة وغير الصحيحة.المثال على اليمين غير مقبول ، لأنه على طول حافة البلاط ، يمس مربع الضوء المربع المظلم. فيما يلي مجموعتان صالحتان تم إنشاؤهما لمجموعة البيانات هذه:
في الحالة العامة ، لا يعد إنشاء مجموعات تجانب صالحة مهمة تافهة. على سبيل المثال ، ضع في اعتبارك استراتيجية "الجشع" البسيطة التالية: نبدأ بشبكة فارغة. في كل تكرار ، نضع التجانب في مرحلة ما ، ونختار بلاطة مقبولة مع مراعاة التجانبات الموضوعة بالفعل. الرسم البياني أدناه يوضح مشاكل مثل هذه الاستراتيجية.
إذا وضعنا مربعات دون توقع كيف سيؤثر الموضع على الخيارات المستقبلية ، فإن الخوارزمية "الجشعة" سرعان ما تتوقف ؛ في المخطط أعلاه ، لا يمكن وضع بلاطة صالحة في المربع الأحمر. وهذه هي المشكلة الرئيسية: يمكن للبلاط المنشور السابق أن يقلل من عدد الخيارات الحالية إلى الصفر. نحن بحاجة إلى طريقة للحماية من وضع البلاط ، والتي يمكن أن تقودنا إلى طريق مسدود. تبدأ الخوارزمية المنفذة في Generate Worlds من خلال النظر في جميع المربعات قدر الإمكان وضعها في جميع نقاط الشبكة. إذا وضعنا مربعًا واحدًا في الشبكة ، فمن الواضح أن بعض الخيارات المستقبلية تصبح غير قابلة للوصول. بعد أن تتخلص الخوارزمية من هذه الخيارات ، يمكننا إعادة النظر في الخيارات المتبقية وإزالة التجانبات الأخرى التي لا تتوافق الآن مع العدد الأصغر للبلاطات المحتملة المتبقية في النقاط المجاورة.
النظر في المثال التالي. تبدأ الخوارزمية بشبكة 3 × 3 ، يوجد في الوسط بلاط واحد. يشير موقع هذا التجانب إلى أنه لا يُسمح بـ 9 بلاطات محتملة في نقاط الشبكة المجاورة ، لذلك يتجاهلها ولم يعد ينظر إليها. بعد حذف هذه المربعات ، يمكنه حذف المربعات غير المتوافقة مع جميع المربعات التي تعتبر مرشحة للموضع في نقاط الشبكة المجاورة. تحدد المربعات الحمراء في الرسم التخطيطي النقاط التي يتم عندها حذف المربعات ، لأنها لا تتوافق مع جميع الجيران التي لا تزال قيد الدراسة. إذا استمرت الخوارزمية في هذه العملية حتى يكون هناك مربعات يمكن حذفها ، فستعود إلى الحالة الموضحة في الركن الأيسر السفلي من الدائرة. كما ترون ، تم استبعاد العديد من البلاط من الاعتبار. إذا كانت استراتيجية وضع المربعات تتألف فقط من اختيار المربعات من هذه المجموعات الباقية ، فإن احتمال الدخول في طريق مسدود سيكون أقل بكثير من مقاربة "الجشع" الموصوفة أعلاه.
المشكلة في هذا النهج هي أنه في كل مرة يتم وضع البلاط ، فإنه يتطلب عملية تكرارية مكلفة. لكن لاحظ أنه في كل مرة أضع فيها بلاطة مع حرف T مقلوب ، يمكن إزالة تلك البلاطات الـ 19 التي قمت بإزالتها في المثال أعلاه من الاعتبار حول هذا الموضع. أدعو مجموعة التجانبات ، والتي تظل خيارات صالحة حول التجانب المستضاف ، وهو
حي صالح لهذه التجانب.
وضع تجانب سريع بفضل التخزين المؤقت للمعلومات
يتمثل المبدأ الأكثر أهمية في خوارزمية Generate Worlds في أنه يمكن إعادة استخدام المعلومات التي تم جمعها حول جيران التجانب المحتملين في كل مرة يتم فيها وضع هذا التجانب. على سبيل المثال ، في حالة حرف T المقلوب للمربعات الثمانية المحيطة بالشبكة ، يمكننا إزالة 19 مربعًا من الاعتبار فور وضع هذا البلاط من خلال النظر في الإصدار المخزن مؤقتًا من الحي المقبول لهذا التجانب.
على سبيل المثال ، في المثال أدناه ، تملأ الخوارزمية شبكة 5 × 5 بالبلاط باستخدام حي مسموح به مؤقتًا يتكون من 4 مربعات. بعد وضع أول بلاطة ، يقوم بإزالة 19 بلاطة مستحيلة في المثال أعلاه. بعد وضع كل تجانب ، تتم إزالة جميع الخيارات التي تغيبت في الجوار المقبول للبلاط المدرج من الاعتبار.
متابعةً بهذه الطريقة ، يمكننا ملء الشبكة بالكامل بتحديثات محلية سريعة فقط لمجموعة التجانبات ، والتي لا تزال خيارات صالحة لكل نقطة من النقاط.
يمكن أن تكون الأحياء المسموح بها بأي حجم تحتاج إليه ، حتى تتمكن من إزالة البلاط غير المتوافق البعيد من الاعتبار في كل مرة تضع فيها بلاطة. على الرغم من أن إنشاء حي مقبول بطيء نوعًا ما ، إلا أنه يجب القيام به مرة واحدة فقط ، وبعد ذلك يعتمد كل خط طولًا على حجم الحي لاستيعاب كل بلاطة.
توسيع النظام في 3D
تتسع خوارزمية توليد العوالم بشكل طبيعي لتشمل العوالم التي لها بعد ثالث. بدلاً من مطابقة التجانب ثنائي الأبعاد بالألوان مع 4 تجانب مجاور على طول الوجوه المشتركة ، أصبح لدينا الآن تجانب ثلاثي الأبعاد يجب أن يتطابق بلونه مع جيرانهم على طول 6 وجوه. النظر في البلاط 3D التالية:
تجميع هذه البلاط في 3D كما يلي:
في هذه الحالة ، فإن الأحياء المقبولة ليست شبكات ثنائية الأبعاد ، ولكن شبكات ثلاثية الأبعاد ، وتقوم الخوارزمية بتوليدها في حالة مماثلة ثنائية الأبعاد.
معرض النتائج
تظهر أدناه العوالم التي تم إنشاؤها بواسطة تطبيقات هذه الخوارزمية مع وصف موجز.
لقطة شاشة من " توليد عوالم" التي تظهر مساحة بها مخرج. الحواف على السقف تتزامن مع حدود البلاط.لقطة شاشة من أداة أخرى أقوم بإنشائها تستخدم أيضًا خوارزمية إنشاء عالم ؛ يتم عرض أنواع مختلفة من الغرف والممرات.عالم مشابه للعالم السابق ، ولكن الآن في منظر جميل متساوي القياسالعالم ، الذي استلهمته من الدائرة التاسعة لجحيم دانتي: الخطاة الذين جُمدوا في الجليد. المقدمة في MagicaVoxel.العالم ، الذي استلهمته من الجولة الثانية من جحيم دانتي: المناظر الطبيعية ، التي ترويها الأمطار الغزيرة ، التي تعبر الجسر. المقدمة في MagicaVoxel.عالم من المنصات العشبية مع الشلالات والأنهار. المقدمة في MagicaVoxel.منظر طبيعي لمدينة العصور الوسطى مع المباني والجدران. المقدمة في MagicaVoxel.