مسیر یابی مبتنی بر الگوریتم A* در بازی های رایانه ای مدرن

مسیریابی بازی در بازی های رایانه ای سال هاست که مورد توجه قرار گرفته است. مسیریابی احتمالا محبوب ترین و در عین حال خسته کننده ترین بازی هوش مصنوعی (AI) در صنعت بازی است. الگوریتم های جستجوی مختلفی از جمله الگوریتم دایجکسترا، الگوریتم جستجوی سطحی و الگوریتم جستجوی اول- عمق، برای حل مسائل کوتاهترین مسیر تا ظهور الگوریتمA* به عنوان یک راه حل بهینه قابل پیش بینی برای مسیر یابی ایجاد شده است. پس از اینکه این الگوریتم ایجاد شد، توانست نظر هزاران محقق مشتاق برای کار در این زمینه را با موفقیت جلب کند. لیست طولانی از الگوریتم ها و تکنیک های مبتنی بر A* تولید شده است. این پژوهش تعدادی از الگوریتم های محبوب مبتنی برA* و تکنیک ها ی آن ها را از دیدگاه های مختلف بررسی می کند. هدف، کشف رابطه بین الگوریتم های مختلف مبتنی بر A* است. در بخش اول، مروری بر مسیریابی ارائه شده است. سپس جزئیات الگوریتم A* به عنوان پایه ای برای ارائه تعدادی از تکنیک های بهینه سازی از زوایای مختلف مورد بررسی قرار گرفته است. سرانجام، تعدادی از نمونه های واقعی در مورد چگونگی تکنیک های مسیر یابی که در بازی های واقعی استفاده می شوند، ارائه و نتیجه ترسیم شده است.

Keywords:

مسیر یابی , A* , بهینه سازی A* , بازی های رایانه ای