تقسیم بازگشتی در درخت هشت‌تایی (Octree): چگونه نمایه‌سازی فضایی فراخوانی‌های ترسیم را کاهش داده و استریمینگ بی‌وقفه جهان‌باز را ممکن می‌کند

وقتی اپیک گیمز (Epic Games) سیستم World Partition موتور آنریل انجین ۵ (Unreal Engine 5) را در سال ۲۰۲۱ مستقر کرد، در واقع تیر خلاص را به صفحات بارگذاری در سراسر صنعت بازی‌سازی زد. این موتور، بارگذاری نقشه‌های مجزا را متوقف کرد و به استریم کردن مختصات روی آورد. ریسک این گذار بسیار بالا بود: یک جهان‌باز مدرن شامل میلیون‌ها شیء مجزاست و ارسال همزمان تمام آن‌ها به پردازنده گرافیکی (GPU) در کسری از ثانیه نرخ فریم را نابود می‌کند. پردازنده مرکزی (CPU) به یک روش بی‌رحمانه و پرسرعت نیاز داشت تا دقیقاً تشخیص دهد بازیکن چه چیزهایی را نمی‌تواند ببیند.[6]

راه‌حل این گلوگاه، نمایه‌سازی فضایی است و برجسته‌ترین فرم سه‌بعدی آن، درخت هشت‌تایی (Octree) نام دارد. مشخصات ویکی‌پدیا در سال ۲۰۰۴ اشاره می‌کند: «درخت‌های هشت‌تایی اغلب برای پارتیشن‌بندی یک فضای سه‌بعدی با تقسیم بازگشتی آن به هشت هشت‌گانه (Octant) استفاده می‌شوند.» این یک فیلتر ریاضی است که به موتور بازی اجازه می‌دهد حجم عظیمی از هندسه را تنها با یک محاسبه دور بریزد و بودجه رندرینگ سخت‌گیرانه ۱۶٫۶ میلی‌ثانیه‌ای را برای حفظ نرخ ۶۰ فریم بر ثانیه حفظ کند.[3]

مکانیک درخت هشت‌تایی بر پایه تقسیم بازگشتی استوار است. موتور بازی یک جعبه احاطه‌کننده (Bounding Box) عظیم را دور کل جهان بازی قرار می‌دهد. اگر این جعبه حاوی بیش از یک آستانه از پیش تعیین‌شده از اشیاء باشد—که اغلب به کمی ۱۰ تا ۵۰ شیء است—جعبه دقیقاً از وسط در امتداد محورهای X، Y و Z به دو نیم تقسیم می‌شود. این کار هشت مکعب کوچک‌تر ایجاد می‌کند. سپس موتور بازی هر یک از این هشت مکعب را ارزیابی می‌کند. اگر یک مکعب فرزند همچنان از محدودیت اشیاء فراتر رود، دوباره به هشت مکعب کوچک‌تر تقسیم می‌شود.[1]

این روند بازگشتی تا زمانی ادامه می‌یابد که هر شیء در جهان بازی به یک گره برگ (Leaf Node) اختصاص یابد—مکعبی آن‌قدر کوچک که تعداد اشیاء درون آن به زیر آستانه مجاز برسد. نتیجه، یک درخت سلسله‌مراتبی از فضاست. مناطق متراکم، مانند یک اتاق داخلی شلوغ، ممکن است ده یا دوازده بار تقسیم شوند و شبکه‌ای فشرده از جعبه‌های کوچک بسازند. مناطق خالی، مانند آسمان باز، ممکن است اصلاً تقسیم نشوند و به‌عنوان یک حجم عظیم و یکپارچه باقی بمانند.[4]

دستاوردهای عملکردی این ساختار، نمایی (Exponential) است. وقتی دوربین بازیکن حرکت می‌کند، موتور بازی فرآیند Frustum Culling را انجام می‌دهد—یعنی بررسی می‌کند کدام اشیاء با میدان دید دوربین تلاقی دارند. بدون درخت هشت‌تایی، پردازنده مرکزی مجبور بود تک‌تک اشیاء موجود در جهان بازی را در برابر مخروط دید دوربین آزمایش کند. در دنیایی با ۱۰۰,۰۰۰ شیء، این یعنی ۱۰۰,۰۰۰ تست تقاطع ریاضی در هر فریم.[2]

اما با درخت هشت‌تایی، موتور بازی دوربین را در برابر جعبه ریشه (Root Box) عظیم آزمایش می‌کند. سپس هشت جعبه فرزند را می‌سنجد. اگر دوربین رو به شمال باشد، چهار جعبه جنوبی فوراً کنار گذاشته می‌شوند. تمام اشیاء داخل آن جعبه‌های جنوبی بدون اینکه تک‌تک بررسی شوند، نادیده گرفته می‌شوند. رابرت نیستروم، مهندس نرم‌افزار، در کتاب الگوهای برنامه‌نویسی بازی می‌نویسد: «پارتیشن فضایی یک ساختار داده است که اشیاء را بر اساس موقعیتشان سازماندهی می‌کند»، و خاطرنشان می‌سازد که هدف، پرس‌وجوی سریع این است که کدام اشیاء در نزدیکی یک مکان خاص قرار دارند.[2]

درخت هشت‌تایی با دور انداختن یک‌باره شاخه‌های کامل درخت، پیچیدگی زمانی پرس‌وجوهای فضایی را از زمان خطی یا O(n) به زمان لگاریتمی یا O(log n) کاهش می‌دهد. پرس‌وجویی که به ۱۰۰,۰۰۰ عملیات نیاز داشت، به حدود ۱۷ عملیات تقلیل می‌یابد. این کارایی همان چیزی است که از غرق شدن پردازنده مرکزی زیر بار فراخوانی‌های ترسیم (Draw Calls)—دستوراتی که از CPU به GPU ارسال می‌شوند تا یک مش (Mesh) خاص را با متریالی خاص رندر کند—جلوگیری می‌کند.[4]

فراخوانی‌های ترسیم، گلوگاه اصلی در رندرینگ مدرن هستند. در حالی که یک پردازنده گرافیکی مدرن می‌تواند میلیاردها چندضلعی را پردازش کند، پردازنده مرکزی تنها می‌تواند چند هزار فراخوانی ترسیم در هر فریم صادر کند، پیش از آنکه پایپ‌لاین متوقف شود. موتور بازی با استفاده از درخت هشت‌تایی برای حذف تهاجمی اشیاء نامرئی، تضمین می‌کند که تنها هندسه‌ای که مستقیماً جلوی دوربین قرار دارد، یک فراخوانی ترسیم تولید کند.[1]

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

اشیاء پویا، مانند بازیکنان، وسایل نقلیه و اشیاء فیزیکی، ساختار را پیچیده می‌کنند. وقتی یک شیء از مرز یک هشت‌گانه به هشت‌گانه دیگر حرکت می‌کند، موتور باید آن را از گره قدیمی حذف کرده و در گره جدید درج کند. اگر یک بازی دارای هزاران پرتابه متحرک باشد، به‌روزرسانی درخت هشت‌تایی می‌تواند دقیقاً همان چرخه‌های پردازشی CPU را مصرف کند که این ساختار برای صرفه‌جویی در آن‌ها طراحی شده بود.[5]

برای کاهش این مشکل، معماران موتورهای بازی‌سازی اغلب از سیستم‌های هیبریدی استفاده می‌کنند. هندسه ایستا در یک درخت هشت‌تایی به‌شدت بهینه‌شده و فقط‌خواندنی (Read-only) قرار می‌گیرد، در حالی که اشیاء پویا در یک شبکه هش فضایی (Spatial Hash Grid) منعطف‌تر و با قابلیت به‌روزرسانی آسان‌تر، یا یک درخت هشت‌تایی ثانویه و کم‌عمق ردیابی می‌شوند. این دوگانگی تضمین می‌کند که جهان ایستا بدون کند کردن شبیه‌سازی فیزیک، به‌صورت یکپارچه استریم شود.[6]

درخت هشت‌تایی همچنین نحوه استریم دارایی‌ها از درایو حالت جامد (SSD) به حافظه سیستم را دیکته می‌کند. از آنجا که این درخت ذاتاً اشیاء را بر اساس نزدیکی گروه‌بندی می‌کند، موتور می‌تواند از موقعیت بازیکن در درخت هشت‌تایی استفاده کند تا پیش‌بینی کند کدام دارایی‌ها در مرحله بعد مورد نیاز خواهند بود. اگر بازیکن وارد یک گره والد خاص شود، موتور شروع به بارگذاری بافت‌های با وضوح بالا برای گره‌های فرزند در پس‌زمینه می‌کند و نیاز به صفحه بارگذاری را از بین می‌برد.[4]

در حالی که فناوری‌های جدیدتر بخش زیادی از بار حذف اشیاء (Culling) را با استفاده از سایه‌زن‌های محاسباتی (Compute Shaders) شتاب‌یافته سخت‌افزاری مستقیماً به پردازنده گرافیکی منتقل می‌کنند، نمایه‌سازی فضایی همچنان نقشه بنیادین جهان دیجیتال باقی می‌ماند. پردازنده مرکزی برای مدیریت برخورد فیزیک، انتشار صدا و ناوبری هوش مصنوعی همچنان به تقسیم بازگشتی متکی است. درخت هشت‌تایی تضمین می‌کند که مهم نیست شبیه‌سازی چقدر وسیع شود، سخت‌افزار تنها باید به فضایی که بلافاصله بازیکن را احاطه کرده است فکر کند.[6]