في عام 2017، واثنين من العلماء، الكندي جون Aycock والبريطانية تارا Copplestone، نشرت على تحليل لعبة كلاسيكية مدفون ل أتاري 2600 لألعاب الفيديو . آليات هذه اللعبة ، التي تم إصدارها في عام 1982 ، بسيطة للغاية: يجب على عالم الآثار ، الذي يتحكم فيه اللاعب ، أن يشق طريقه عبر سراديب الموتى من أسفل إلى أعلى ، متهربًا من الزومبي.
كان لدى Atari 2600 فقط 128 بايت من ذاكرة الوصول العشوائي ؛ ومع ذلك ، كانت المتاهة التي تبدو بلا نهاية جديدة مع كل إطلاق ؛ ولدت في الذاكرة. كيف أدارها المبرمجون؟ إليكم تعليق ستيفن سيدلي ، المبرمج الذي ابتكر هذه اللعبة قبل 38 عامًا:
- . , , . , , , , , .
تسرد ويكيبيديا عشرات الخوارزميات المختلفة لتوليد المتاهات. تعتبر " خوارزمية Eller " التي تم إنشاؤها في عام 1982 من قبل Martin Eller من شركة Microsoft ، أكبر اهتمام لوحدات تحكم الألعاب . تسمح لك خوارزمية Eller بإنشاء متاهات متصلة بخطًا تلو الآخر بدون حلقات ، وتوليد متاهة ذات ارتفاع غير محدود ، يكفي تخزين آخر سطرين فقط في الذاكرة. يبدو أن هذا هو بالضبط ما يحتاجه Entombed! ولكن للأسف ، لا تتوافق خوارزمية Eller مع ميكانيكا اللعبة الخاصة بأداة التمرير الرأسية ، لأنه في المتاهة الناتجة يجب عليك بانتظام تجاوز العقبات من أعلى. لتوضيح ذلك ، قمت بتعديل خوارزمية Eller قليلاً حتى يتم إنشاء المتاهة في مصفوفة من "الجدران" و "الممرات" ، كما هو الحال في Entombed:
خوارزميات أكثر تعقيدا باستخدام العودية وما شابه لن تناسب 128 بايت من ذاكرة الوصول العشوائي. لذا ، فإن متطلبات الخوارزمية لـ Entombed هي:
- توليد متاهات ذات ارتفاع غير محدود سطرا بسطر ؛
- يجب أن تحتوي المتاهات التي تم إنشاؤها على أقل عدد ممكن من المقاطع غير المتصلة ؛ (لدى اللاعب قدرة محدودة على "اختراق الجدران" ، لذا فإن عدم الاتساق النادر ليس مشكلة)
- يجب أن تتكون المتاهات التي تم إنشاؤها بشكل رئيسي من تفرع وتوصيل الممرات الرأسية - بحيث لا يتطلب مرور المتاهة حركة صعودية ؛
- يجب استخدام الخطوط القليلة الأخيرة فقط لإنشاء خطوط جديدة من المتاهة. (نظرًا لأن Atari 2600 لا يحتوي على مخزن مؤقت للفيديو ، يجب تخزين جميع خطوط المتاهة المرئية على الشاشة في شكل ما في 128 بايت من الذاكرة الرئيسية).
من وكيف خلق هذه الخوارزمية؟
قرر عالمان يطلقان على أنفسهما "علماء الآثار في ألعاب الفيديو" بدء بحثهما مع Entombed - وهي لعبة عن عالم آثار في متاهة. أثناء بحثهم ، تعقبوا ستيفن سيدلي وسألوه عن الخوارزمية التي استخدمها لتوليد المتاهة. كما ذكرنا من قبل ، أخبرهم Sidley أنه حتى مؤلف الخوارزمية لا يمكنه تذكر ما هي خوارزميته ، و Sidley نفسه ، أكثر من ذلك. ثم حاول الباحثون العثور على "الحشاش" الذي أنشأ هذه الخوارزمية. تم العثور على النصف الثاني من القصة في مقابلة نشرت في عام 2008:
Entombed [Duncan Muirhead] [Paul Allen Newell]. - , , , . , . , VCS [Atari 2600], . , . , , . , Towering Inferno، باستخدام جزء من الخوارزمية لدينا ، والاستقالة. بعد أن غادرت ، استأجرت الشركة ستيفن سيدلي وسلمت له مولد المتاهة. كان عليه حذف جزء كبير من الكود الخاص بي لإفساح المجال لآليات اللعبة. [في Atari 2600 ، بالإضافة إلى القيود الصارمة على مقدار ذاكرة الوصول العشوائي وذاكرة القراءة فقط ، يُطلب أيضًا أن يستغرق إنشاء كل صف من وحدات البكسل ملاحظة المؤلف بالضبط 76 دورة ].
ذكر Sidley أن كود مولد المتاهة كتب في تجميع 6502 دون أي تعليقات. هذا في حد ذاته يبدو وكأنه إنجاز: كما لوحظ خيم، هناك "مجموعة الأوامر محدودة للغاية ومحتلة لدرجة أنه عند كتابة البرامج ، يطرح السؤال الرئيسي ،" كيف يمكنني كتابة أي شيء في هذه المعجزة؟ ومع ذلك ، حفر الباحثون في رمز اللعبة واكتشفوا أن المتاهة يتم إنشاؤها على النحو التالي: لكل خلية من الخلايا الثمانية للصف المولد ، يتم اعتبار خمس خلايا تم إنشاؤها بالفعل (ثلاث في الأعلى واثنتان على اليسار) ، ووفقًا لـ "الطاولة السحرية" ، يتم تحديد حالة الخلية الجديدة (ممر ، جدار ، أو اختيار عشوائي). تكون الخليتان الموجودتان في أقصى اليسار ممتلئين دائمًا ولا يتم تخزينهما في الذاكرة. النصف الأيمن من المتاهة هو مجرد صورة طبق الأصل لليسار.
جدول غامض في قلب خوارزمية غير محلولة
تعتمد خصائص المتاهة المتولدة على حالة مجموعة الخلايا الجديدة لكل خمس مجموعات تم إنشاؤها مسبقًا. جدول مخيط في Entombed ، حيرة العديد من الباحثين: "لم نلاحظها أي قوانين ، حتى عندما يكون لدينا عدة طرق لتقديمها في شكل خريطة Karnaugh ". قال سيدلي على نفس المنوال: "بالنسبة لي يبقى لغزا: لم أتمكن من كشفه ، واستخدمته كصندوق أسود". ومع ذلك ، فإن غياب الانتظام في الجدول هو نوع من المبالغة: على سبيل المثال ، على خريطة Karnot ، يمكنك أن ترى أنه عندما c = 1 (الجدار إلى أعلى يسار الخلية الحالية) X = 1 (الجدار في الخلية الحالية) لن يتم إنشاؤه .
بي بي سي في تقريرهاحول "علم الآثار الرقمية" لجأت إلى مبالغات أكثر دراماتيكية: "الطاولة بارعة حقًا: في كل مرة تبدأ فيها اللعبة ، يتم إنشاء متاهة جديدة ، يمكنك من خلالها الانتقال من البداية إلى النهاية. إذا كانت القيم في هذا الجدول مختلفة قليلاً ، فمن المرجح أن تكون المتاهة سالكة. هذا لا يمكن تفسيره ". تتم إعادة صياغة الرسالة على hackaday.com بثقة أكبر: "إن الطاولة الغامضة تخلق دائمًا متاهات يمكن تمريرها ، ولكن إذا قمت بتغيير أي أجزاء فيها ، فإن اللغز سيصبح غير قابل للذوبان." في الواقع ، لم تكن المتاهة متماسكة دائمًا ، كما يمكن رؤيته في فيديو اللعبة ؛ والتغييرات الصغيرة في الجدول ليس لها تأثير ملحوظ على المتاهات الناتجة: لقد صنعت نسخة جافا سكريبت، حيث يمكنك اللعب مع "الطاولة الغامضة" بنفسك - قم بتغييرها بشكل صحيح "أثناء التنقل" وشاهد كيف تتغير المتاهة نتيجة لذلك. ربما ، ضاع ضمان اتصال المتاهة ، الذي ذكره بول نيويل في مقابلته ، مع الجزء المحذوف من الرمز.
علم آثار ألعاب الفيديو
علق John Aycock على كيف أصبح Entombed هدفًا لبحثه: أعد مهمة هندسية عكسية لطلابه ، واختار لعبة غير معروفة نسبيًا ، لأنه بالنسبة للألعاب الشهيرة ، يمكن للطلاب العثور على رمز معرب بالفعل على الشبكة. إذا تم العثور على مثل هذا الاكتشاف الرائع في لعبة تم اختيارها عشوائيًا ، فهل هذا يعني أنه في أي لعبة تقريبًا في ذلك الوقت ستكون هناك حلول برمجة رائعة ، ما عليك سوى التعمق أكثر قليلاً؟ قارن ستيفن سيدلي التصميم لـ Atari 2600 ، مع مجموعة التعليمات الهزيلة ، و 128 بايت من ذاكرة الوصول العشوائي ، و 76 ساعة لكل سطر من وحدات البكسل ، إلى "تسلق Mount Everest بدون خزانات الأكسجين" : أجبرت قيود المنصة المبرمجين على اختراع خوارزميات عبقرية.
التعمق أكثر ليس مجرد استعارة. إن البحث في ألعاب الفيديو الكلاسيكية معقد بسبب هشاشة الوسائط التي تم تسجيلها عليها ومعاملة الألعاب القديمة على أنها قمامة غير مثيرة للاهتمام. في عام 1983 ، ألقى أتاري 47 طنًا من خراطيش أتاري 2600 في مكب نفايات - ما لا يقل عن اثنتي عشرة شاحنة ممتلئة! تم سحق هذه الخراطيش لمدة 30 عامًا حتى تم سحقها بواسطة أسطوانة أسفلت وسكبها بالخرسانة حتى عام 2014 ، حيث حصل "علماء الآثار الرقمية" على إذن للتنقيب واستعادة الخراطيش الباقية. لم تعمل أي من الخراطيش المحفورة ، ولكن تمت استعادة واحدة منها على الأقل عن طريق لحام المكونات.
إن سلوك Atari ، الذي سكب الخرسانة في الخراطيش لحمايتهم من "اللصوص" - هو نموذجي جدًا لمالكي حقوق الطبع والنشر الذين قد يرسلون عملهم إلى النسيان الأبدي بسهولة أكبر من المعاناة من "خسارة الأرباح" من حقيقة أن ملكيتهم الفكرية ستصل إلى شخص ما مجانًا. ولكن ربما لم يفت الأوان لحماية "الطبقة الثقافية الافتراضية" في القرن العشرين بالسماح بالنسخ المجاني للبرامج التي فقدت قيمتها التجارية لفترة طويلة؟
