نویز پرلین و اتوماتای سلولی: الگوریتم‌های تولید رویه‌ای چگونه جهانِ بازی‌ها را خلق می‌کنند

بازیکن از یک کپسول فرود که به صورت رویه‌ای تولید شده، در یک بازی بقای مدرن بیرون می‌آید و به رشته‌کوهی پهناور چشم می‌دوزد که در دل یک سیستم غاری پیچ‌درپیچ و متراکم محو می‌شود. این انتقال یکپارچه از قله‌های سر به فلک کشیده به تونل‌های تنگ و تاریک، طوری به نظر می‌رسد که انگار کار یک طراح مرحله‌ی بسیار باحوصله است. اما در واقعیت، این شاهکار حاصل یک توافق ریاضیاتی بین دو الگوریتم است که در چهار دهه گذشته بی‌سروصدا جهان‌های مجازی را بنا کرده‌اند: نویز پرلین و اتوماتای سلولی.[6]

تولید رویه‌ای اغلب به اشتباه به عنوان یک «تصادف محض» در نظر گرفته می‌شود. اما تصادف محض، پرآشوب و غیرقابل‌بازی است. اگر یک توسعه‌دهنده به هر نقطه روی یک شبکه، یک مقدار ارتفاع کاملاً تصادفی اختصاص دهد، نتیجه‌اش می‌شود یک آشفتگی پر از نویز و میخ‌های تیز که هیچ شخصیت مجازی‌ای نمی‌تواند در آن قدم بگذارد. برای خلق محیط‌های ارگانیک و زنده، توسعه‌دهندگان به تصادفِ ساختاریافته تکیه می‌کنند.[1][4]

کن پرلین الگوریتم نویز هم‌نام خود را در سال ۱۹۸۲، زمانی که در گروه کاربردهای ریاضی روی فیلم دیزنی یعنی «ترون» کار می‌کرد، توسعه داد. او که از ظاهر بی‌روح و ماشین‌گونه‌ی تصاویر کامپیوتری اولیه به ستوه آمده بود، به دنبال یک تابع ریاضی می‌گشت که بتواند نقص‌های ارگانیک طبیعت را تقلید کند.[4]

نتیجه‌ی این تلاش، «نویز پرلین» بود؛ یک الگوریتم نویز گرادیان که در سال ۱۹۹۷ جایزه اسکار دستاورد فنی را برای او به ارمغان آورد. آکادمی در تقدیرنامه خود، این الگوریتم را به عنوان «تکنیکی که برای تولید بافت‌های طبیعی روی سطوح تولیدشده توسط کامپیوتر برای جلوه‌های بصری فیلم‌های سینمایی استفاده می‌شود» ستایش کرد.[4]

نویز پرلین به جای تولید مقادیر تصادفی در هر پیکسل، شبکه‌ای از بردارهای گرادیان تصادفی را در فواصل ثابت تولید می‌کند. سپس این الگوریتم حاصل‌ضرب نقطه‌ای بین این بردارهای گرادیان و فاصله تا نقطه‌ی در حال ارزیابی را محاسبه کرده و نتایج را درون‌یابی می‌کند. این کار یک منحنی پیوسته و هموار از مقادیر شبه‌تصادفی ایجاد می‌کند.[1][2]

از آنجا که خروجی پیوسته است، برای تولید نقشه‌های ارتفاعی بی‌نقص عمل می‌کند. مقدار منفی ۱.۰ ممکن است نشان‌دهنده کف اقیانوس باشد، در حالی که مثبت ۱.۰ یک قله‌ی برف‌گرفته را نشان می‌دهد. این انتقال‌های هموار تضمین می‌کنند که زمین به جای پرش‌های نامنظم از یک گودال عمیق به یک قله‌ی مرتفع در یک قدم، شیب طبیعی داشته باشد.[1]

برای افزودن چاشنی واقع‌گرایی، توسعه‌دهندگان از تکنیکی به نام حرکت براونی کسری استفاده می‌کنند که فرکانس‌های مختلفی از نویز پرلین را لایه‌بندی می‌کند. به این لایه‌ها «اکتاو» می‌گویند. اکتاو اول ساختار کلان مانند قاره‌ها و اقیانوس‌ها را تعریف می‌کند. اکتاو دوم که با فرکانس بالاتر و دامنه کمتر اعمال می‌شود، رشته‌کوه‌ها را اضافه می‌کند. اکتاوهای بعدی تپه‌ها، تخته‌سنگ‌ها و در نهایت بافت زبر خاک را شکل می‌دهند.[1][2]

اما در حالی که نویز پرلین در سطوح پیوسته می‌درخشد، در فضاهای محصور و باینری (صفر و یکی) به مشکل برمی‌خورد. اگر یک توسعه‌دهنده بخواهد یک شبکه غاری زیرزمینی پهناور تولید کند، نقشه‌های ارتفاعی پیوسته اغلب لوله‌های متقاطع غیرطبیعی یا مسیرهای کاملاً مسدود ایجاد می‌کنند.[3]

اینجاست که اتوماتای سلولی وارد میدان می‌شود. اتوماتای سلولی که در اصل در دهه ۱۹۴۰ توسط استانیسلاو اولام و جان فون نویمان در آزمایشگاه ملی لوس آلاموس ابداع شد، همان‌طور که محققان تعریف می‌کنند، «یک سیستم دینامیکی قطعی است که در زمان گسسته روی یک فضای گسسته، معمولاً یک شبکه یا توری منظم، تکامل می‌یابد.»[5]

در تولید رویه‌ای مراحل، توسعه‌دهندگان معمولاً از یک شبکه دوبعدی استفاده می‌کنند که در آن هر سلول یا عدد ۱ است (نشان‌دهنده یک دیوار جامد) یا عدد ۰ (نشان‌دهنده یک کف خالی). این شبکه در ابتدا با تصادف محض بذرپاشی می‌شود و اغلب نرخ پرشدگی آن روی ۴۵ تا ۵۰ درصد تنظیم می‌شود.[3]

سپس الگوریتم مجموعه‌ای از قوانین بقا و تولد را اعمال می‌کند و هر سلول را در برابر هشت همسایه بلافصل خود می‌سنجد. یک قانون رایج برای تولید غار، قانون ۴-۵ است: اگر یک سلول با پنج دیوار یا بیشتر احاطه شده باشد، تبدیل به دیوار می‌شود. اگر با کمتر از چهار دیوار احاطه شده باشد، به کف تبدیل می‌شود.[3]

وقتی این قانون به طور همزمان روی کل شبکه طی چند تکرار (معمولاً چهار تا پنج مرحله) اعمال می‌شود، آن نویز پرآشوب اولیه به شکلی ارگانیک منسجم می‌شود. دیوارهای کوچک و منزوی ناپدید می‌شوند و خوشه‌های بزرگ به هم می‌پیوندند تا صخره‌های جامد را تشکیل دهند.[3]

نتیجه‌ی کار، شبکه‌ای از غارهای ارگانیک و پیچ‌درپیچ است که به طرز شگفت‌انگیزی شبیه سنگ‌های آهکی فرسایش‌یافته با آب در طبیعت به نظر می‌رسند. از آنجا که این قوانین همسایه‌های محلی را ارزیابی می‌کنند، الگوریتم به طور طبیعی از ایجاد دیوارهای غیرممکنِ نازک یا راهروهای دندانه‌دار تک‌پیکسلی جلوگیری می‌کند و مطمئن می‌شود که فضا واقعاً برای بازیکنان قابل‌مسیریابی است.[3]

موتورهای بازی‌سازی مدرن اغلب این دو الگوریتم را برای ساخت جهان‌های جامع ترکیب می‌کنند. یک توسعه‌دهنده ممکن است از نویز پرلین دوبعدی برای تعیین زیست‌بوم کلی و ارتفاع سطح استفاده کند، در حالی که از یک اتوماتای سلولی برای حفر فضاهای زیرزمینی دقیقاً در زیر همان سطح بهره می‌برد.[2]

کارایی محاسباتی هر دو مدل به آن‌ها اجازه می‌دهد تا در لحظه (رِل‌تایم) اجرا شوند. نویز پرلین می‌تواند در کسری از ثانیه برای هر مختصات داده‌شده‌ای محاسبه شود؛ به این معنی که جهان بازی از نظر تئوری می‌تواند تا بی‌نهایت امتداد یابد، بدون اینکه نیازی باشد جغرافیای آن به طور دائم در حافظه ذخیره شود.[1][2]

اتوماتای سلولی نیز با وجود اینکه برای ارزیابی وضعیت همسایه‌ها به یک شبکه گسسته نیاز دارد، می‌تواند در قطعات (چانک‌های) محلی پردازش شود. وقتی بازیکن به لبه‌ی یک منطقه بارگذاری‌شده نزدیک می‌شود، موتور بازی درست قبل از ورود بازیکن، قطعه‌ی بعدی سیستم غاری را مقداردهی اولیه کرده و هموار می‌کند.[3]

میراث ماندگار این الگوریتم‌ها در سادگی ریاضیاتی آن‌ها نهفته است. با وجود جهش‌های عظیم در پردازش گرافیکی و یادگیری ماشین در چهل سال گذشته، معماری بنیادین جهان‌های رویه‌ای همچنان ریشه در همین قوانین ظریف دارد. دفعه‌ی بعد که یک افق مجازی تا بی‌نهایت در دوردست امتداد یافت، بدانید که این جادو نیست که چشم‌انداز را رندر می‌کند؛ بلکه فقط یک بردار گرادیان و یک قانون بقا است که در تاریکی کدهای بازی، بی‌نقص اجرا می‌شوند.[6]