چگونه الگوریتم‌های A-Star و دایجسترا چرخه‌های پردازنده را فدای دقت مسیریابی در بازی‌سازی می‌کنند

یک بازیکن در یک مسابقه استراتژی همزمان و نفس‌گیر روی مینی‌مپ کلیک می‌کند. در یک چشم‌به‌هم‌زدن، جوخه‌ای متشکل از پنجاه واحد، مسیر پیچیده‌ای را از میان یک جنگل انبوه، دور یک رشته‌کوه و مستقیماً به داخل پایگاه دشمن محاسبه می‌کند. بازی فریز نمی‌شود و نرخ فریم افت نمی‌کند. این حرکت روان و آنی به یک بده‌بستان ریاضی متکی است که در کسری از میلی‌ثانیه اجرا می‌شود. در پشت صحنه، موتور بازی به‌سرعت تصمیم می‌گیرد که آیا چرخه‌های ارزشمند پردازنده را صرف یافتن بی‌نقص‌ترین مسیر ممکن کند، یا از میانبری استفاده کند که پیش از رندر شدن فریم بعدی، یک مسیر کاربردی را بیابد.

در استاندارد ۶۰ فریم بر ثانیه، یک موتور بازی دقیقاً ۱۶٫۶ میلی‌ثانیه فرصت دارد تا گرافیک را رندر کند، فیزیک را پردازش کند، ورودی‌های بازیکن را ثبت کند و رفتارهای هوش مصنوعی را محاسبه نماید. اگر الگوریتم‌های مسیریابی بخش زیادی از این پنجره زمانی محدود را مصرف کنند، شبیه‌سازی دچار لکنت می‌شود و تجربه‌ای آزاردهنده خلق می‌کند که یکپارچگی رقابت را از بین می‌برد. توسعه‌دهندگان باید دائماً بودجه محاسباتی را متعادل کنند و بین یافتن مسیر بی‌نقص ریاضی و یافتن یک مسیر «به‌اندازه کافی خوب» که سرعت لازم برای اجرای روان بازی را داشته باشد، یکی را انتخاب کنند. این تنش، معماری دنیاهای مجازی مدرن را تعریف می‌کند.

معیار تاریخی برای تضمین دقت مسیر، الگوریتم دایجسترا است که توسط دانشمند هلندی علوم کامپیوتر، ادسخر و. دایجسترا در سال ۱۹۵۶ ابداع و سه سال بعد منتشر شد. این الگوریتم با کاوش تمام مسیرهای ممکن از نقطه شروع به سمت بیرون و در همه جهات عمل می‌کند و شعاع جستجوی خود را به‌طور یکنواخت مانند آبی که یک هزارتوی پیچیده را فرا می‌گیرد، گسترش می‌دهد. این الگوریتم هزینه دقیق رسیدن به تک‌تک گره‌های در دسترس روی نقشه را محاسبه می‌کند تا در نهایت به مقصد برسد.[6]

آمیت پاتل در مرجع معتبر مسیریابی Red Blob Games خاطرنشان می‌کند: «الگوریتم دایجسترا برای یافتن کوتاه‌ترین مسیر به‌خوبی کار می‌کند، اما زمان را برای کاوش در جهاتی که امیدی به آن‌ها نیست هدر می‌دهد.» از آنجا که این الگوریتم ذاتاً نمی‌داند مقصد نسبت به نقطه شروع کجاست، گره‌هایی را که در جهت کاملاً مخالف حرکت می‌کنند، دقیقاً به همان اندازه گره‌هایی که به سمت هدف می‌روند، ارزیابی می‌کند. این الگوریتم کاملاً دقیق، اما کاملاً کور است.[2]

در یک بنچمارک تطبیقی در سال ۲۰۱۸ که در مجله بین‌المللی سیستم‌های اطلاعاتی و فناوری منتشر شد، محققان دایجسترا را در برابر الگوریتم‌های جایگزین در یک محیط بازی هزارتو آزمایش کردند. این جستجوی جامع همواره کوتاه‌ترین مسیر ممکن را تضمین می‌کرد، اما هزینه محاسباتی آن به‌شدت بالا می‌رفت. با افزایش اندازه شبکه و عمیق‌تر شدن پیچیدگی هزارتو، زمان مورد نیاز برای ارزیابی هزاران گره نامربوط به‌سرعت به یک نقطه‌ضعف برای برنامه‌های بلادرنگ تبدیل شد.[3]

برای حل این گلوگاه عملکردی خاص، دانشمندان موسسه تحقیقاتی استنفورد یعنی پیتر هارت، نیلز نیلسون و برترام رافائل، یک مبنای اکتشافی رسمی برای مسیرهای با حداقل هزینه را در یک مجله IEEE در سال ۱۹۶۸ منتشر کردند. آن‌ها الگوریتمی را معرفی کردند که در نهایت بر صنعت بازی‌های ویدیویی مسلط شد و آن را A* (با تلفظ اِی-استار) نامیدند. این الگوریتم طوری طراحی شده بود که دقت ریاضی روش‌های قبلی را حفظ کند، در حالی که زمان مورد نیاز برای رسیدن به راه‌حل را به‌شدت کاهش می‌داد.[4]

الگوریتم A* گسترش یکنواخت دایجسترا را با معرفی یک روش اکتشافی تغییر می‌دهد؛ یک حدس ریاضی حساب‌شده درباره فاصله باقی‌مانده از هر گره تا هدف نهایی. A* به‌جای اینکه مانند یک دایره کامل به‌طور مساوی به سمت بیرون سرازیر شود، کاوش گره‌های خاصی را در اولویت قرار می‌دهد که به نظر می‌رسد موجودیت را به مقصد نزدیک‌تر می‌کنند. این روش، هزینه شناخته‌شده مسیر طی‌شده تا آن لحظه را با هزینه تخمینی فاصله باقی‌مانده ترکیب می‌کند.[5]

این اولویت‌بندی، تعداد کل گره‌هایی را که موتور بازی باید پیش از یافتن یک مسیر معتبر ارزیابی کند، به‌شدت کاهش می‌دهد. در تحلیلی در سال ۲۰۲۳ که توسط Darcy & Roy Press منتشر شد و به بررسی A* در بازی‌های ویدیویی پرداخت، محققان نشان دادند که تنظیم این روش اکتشافی به توسعه‌دهندگان اجازه می‌دهد تا رفتار الگوریتم را به‌طور صریح کنترل کنند. با تنظیم ریاضیات، برنامه‌نویسان می‌توانند بسته به نیازهای فوری بازی، سیستم را از یک جستجوی کند و بی‌نقص به یک جستجوی برق‌آسا و تقریبی تغییر دهند.[1]

افزایش کارایی حاصل از این روش فوق‌العاده است. در زمین‌های دیجیتال باز، A* می‌تواند با ارزیابی کسر کوچکی از گره‌هایی که دایجسترا مجبور به بررسی آن‌هاست، یک مسیر را با موفقیت ترسیم کند. این رویکرد هدفمند دقیقاً همان چیزی است که به بازی‌های استراتژی مدرن و عناوین جهان‌باز گسترده اجازه می‌دهد تا صدها موجودیت فعال و متحرک را به‌طور همزمان و بدون تجاوز از آن بودجه حیاتی ۱۶٫۶ میلی‌ثانیه‌ای فریم مدیریت کنند.[2][7]

با این حال، این سرعت باورنکردنی با یک بده‌بستان سخت در دقت و حافظه سیستم همراه است. A* موتور بازی را ملزم می‌کند تا مقدار اکتشافی محاسبه‌شده برای هر گره بازی را که در نظر می‌گیرد ذخیره کند، که این امر بار حافظه را در مقایسه با الگوریتم‌های ساده‌تر افزایش می‌دهد. در محیط‌هایی که رم به‌شدت محدود است، ذخیره هزاران عدد اعشاری برای مسیریابی می‌تواند به گلوگاه عملکردی خاص خود تبدیل شود.[1][5]

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

برای مدیریت این محدودیت‌ها و به حداکثر رساندن عملکرد، موتورهای بازی‌سازی مدرن به‌ندرت A* را روی یک شبکه خام و پیکسل‌به‌پیکسل اجرا می‌کنند. در عوض، توسعه‌دهندگان از شبکه‌های ناوبری استفاده می‌کنند؛ نمایش‌های چندضلعی ساده و نامرئی از زمین‌های قابل عبور که روی هندسه قابل مشاهده قرار می‌گیرند. یک شبکه ناوبری هزاران مربع شبکه‌ای کوچک را در چند شکل بزرگ و متصل به هم دسته‌بندی می‌کند.[7]

با اجرای الگوریتم A* در یک شبکه ناوبری ساده‌شده به‌جای یک شبکه متراکم، سیستم تنها نیاز به ارزیابی چند چندضلعی بزرگ به‌جای هزاران نقطه منفرد دارد. این رویکرد ترکیبی - که جستجوی هدایت‌شده A* را با داده‌های فضایی بهینه‌شده ترکیب می‌کند - سرعت برق‌آسای مورد نیاز برای ورزش‌های الکترونیک رقابتی را ارائه می‌دهد، در حالی که توهم یک هوش محاسبه‌گر و بی‌نقص را حفظ می‌کند.[7]