دانلود مقاله کامل الگوریتم ای استار A Star و کاربرد آن در بازیهای رایانه ای

 

ای استار  و کاربرد آن در بازیهای رایانه ای

تعداد صفحات:

۷۳  (هفتاد و سه)

رشته:

کامپیوتر و  IT

نوع فایل:

Word

توضیحات:

قابل استفاده بعنوان پروژه پایانی و همچنین برای درس شیوه ارائه مطالب


دانلود مقاله کامل الگوریتم ای استار A Star و کاربرد آن در بازیهای رایانه ای

دانلود مقاله کامل الگوریتم A Star و کاربرد آن در بازیهای رایانه ای

.

فهرست مطالب

فصل اول- شناخت الگوریتم ) A-STAR)

۱-مقدمه

۱-۱

۱-۲ برخی از نکات مهم در هنگام پیاده سازی الگوریتم A-STAR

۱-۲-۱)) یافتن فاصله بین سلول ها

۱-۲-۲)) شی مورد نظر در نقطه ها

۱-۲-۳ ))تکنیکهای کاهش هزینه محاسباتی

۱-۲-۴ ))

۱-۲-۵)) راه حل های رفع مشکل چرخش ناگهانی

۱-۲-۶)) هزینه دهی (Costing)

۱-۲-۷ )) نقاط قابل حرکت و نقاط غیرقابل حرکت

۱-۲-۸ )) فرآیند محاسبه نزدیکترین مسیر

۱-۳ حرکت بین دو نقطه با

فصل دوم- در بازیها (بازی گربه ی مسیریاب)

۲-مقدمه

۲-۱ گربه‏ی مسیریاب

۲-۲ ساده کردن حوزه‏ی جستجو

۲-۳ لیست‏های باز و بسته

۲-۴

۲-۵ درباره‏ی G بیشتر بدانید

۲-۶ درباره‏ی H بیشتر بدانید

۲-۷ الگوریتم آ-ستاره

۲-۸ مسیر گربه

۲-۹ یک گربه‏ی معمولی

۲-۱۰ شبه کد حرکت بازی گربه

فصل سوم- همراه با ترجمه فارسی

۳- یک اجرای خوش بینانه از الگوریتم *A با استفاده از (STL)

۳-۱ ) مقدمه

۳-۲ مقدمه ای اجمالی برای الگوریتم

نتیجه گیری

منابع و ماخذ

.

چکیده :

در علوم کامپیوتر، الگوریتم A-STAR (A*) یک الگوریتم کامپیوتری است که به طور وسیع در پیمایش گراف و یافتن مسیر بین دو نقطه که گره نامیده می‌شوند، مورد استفاده قرار می‌گیرد. به علت عملکرد و دقت بالای این الگوریتم استفاده گسترده‌ای از آن می‌شود. پیتر ای هارت (Peter E. Hart)، نیلز نیلسون (Nils Nilsson) و برترام رافائل (Bertram Raphael) اولین کسانی بودند که آن را در سال ۱۹۶۸ میلادی شرح دادند. این الگوریتم درواقع تعمیمی از الگوریتم دیکسترا می‌باشد. *A با استفاده از آروین(heuristic) عملکرد بهتری نسبت به زمان به دست می‌آورد.

واژگان کلیدی :  الگوریتم های مسیریابی-پیمایش گراف-ای استار-A STAR-یافتن کوتاهترین مسیر

 

شناخت الگوریتم * (A-STAR)

  • مقدمه :

انواع روش های جستجو

در حالت کلی روش های جستجو را می توان به سه دسته زیر تقسیم کرد

  • ناآگاهانه
  • هیوریستیکی
  • متاهیوریستیکی

 

مسائلی وجود دارند که فضای جستجوی آنها به اندازه ای بزرگ می باشد که استفاده از روش های جستجوی ناآگاهانه و هیوریستیکی را برایمان غیرممکن می سازند. در چنین مواردی از  روش های متاهیوریستیکی یا  فرامکاشفه ای استفاده خواهیم کرد.

در ادامه این بخش ابتدا به بررسی انواع مسائل هوش مصنوعی خواهیم پرداخت، سپس روش های جستجوی ناآگاهانه را بررسی کرده و به دنبال آن با روش های جستجوی هیوریستیکی آشنا خواهیم شد.

مسائل مطرح شده در هوش مصنوعی را از چند دیدگاه مختلف می توان مورد بررسی قرار دارد :

  • هدف یافتن تنها یک جواب برای مسئله است یا همه جواب های ممکن برای مسئله باید جستجو شوند؟
  • پاسخ دهی الگوریتم جستجو برای حل مسئله بلادرنگ خواهد بود یا زمان بیشتری برای حل مساله می توان اختیار کرد
  • آیا در مسئله محدودیت هایی وجود دارد یا نه ؟

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

سیستم های پویا سیستم هایی هستند که در آنها به طور مداوم ورودی ها و حالت مسئله در حال تغییر است و هربار تغییر در یکی از پارامترها موجب خواهد شد که عمل جستجوی مجددی در فضای جستجو انجام پذیرد. در چنین مواردی ممکن است مدت زمان پاسخ دهی سیستم برای حل مساله بسیار کم باشد. همچنین ممکن است سیستم مدت زمان کافی برای حل مساله در اختیار داشته باشد که هریک از این موارد تاثیر بسزایی در طراحی الگوریتم جستجو خواهند داشت.

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

مسائلی که در عمل با آنها مواجه هستیم ترکیبی از موارد فوق را در خود دارند. به عنوان مثال در مسئله ی ۸ وزیر ، مسئله دارای محدودیت بوده ولی در مقابل هدف یافتن تنها یک جواب در مدت زمان معقول است و در واقع یافتن جواب در آن نیازی به بلادرنگ بودن ندارد.

۱-۱ معرفی الگوریتم A-STAR :

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

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

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

در یک کلام *A الگوریتمی قدرتمند برای یافتن نزدیکترین مسیر بین دو نقطه می باشد که می توان با انجام برخی تغییرات، آن را برای اهداف دیگری از جمله حل مسائل گراف ها نیز به کار برد.

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

*پس از اینکه ناحیه جستجو مشخص شد، باید این ناحیه را به قسمت های کوچکتری تبدیل کنید.

این نواحی کوچک که به عنوان سلول (cell) یا گره (node) شناخته می شوند، اساس کار این الگوریتم هستند. به طور معمول هرچه تعداد این قسمت های کوچک بیشتر باشد، دقت عملیات نیز افزایش خواهد یافت (که باعث کاهش سرعت پردازش نیز خواهد شد). برای درک بهتر روند کار این الگوریتم، مراحل کار در قالب چند شکل نشان داده شده اند. اگرچه ما در اینجا ناحیه جستجوی خود را به تعدادی مربع کوچک تقسیم کرده ایم (تصویر ۱) ولی در حالت کلی، این سلول ها می توانند هر شکلی داشته باشند (تعیین شکل و اندازه این سلول ها به شکل محیط و نحوه حرکت بستگی دارد، اما عموماً تقسیم ناحیه جستجو به مربع های کوچک، بهترین نتیجه را دارد). در این شکل مربع سبز مبدأ حرکت، خانه های آبی دیوار (یعنی مانع حرکت)، و مربع قرمز نیز مقصد می باشد.

*همان طور که گفته شد، این الگوریتم یک سری تست های تکراری را انجام می دهد تا در نهایت به هدف مورد نظر برسد (البته در صورت امکان، یعنی در صورت وجود یک مسیر). در تصویر دوم ۸ خانه اطراف خانه سبز، با فلش های مخصوصی نشان داده شده اند. ما در اولین گام، فاصله هر یک از این ۸ خانه تا مقصد (یعنی سلول قرمز) را بررسی می کنیم.

سپس از بین این ۸ خانه، نزدیکترین خانه را نسبت به مقصد انتخاب می کنیم. سپس موقعیت این خانه را ثبت می کنیم، زیرا در مرحله بعدی تست، باید از این خانه به عنوان مبدأ جدید حرکت استفاده کنیم. مجدداً این تست را برای خانه جدید انتخاب شده انجام می دهیم (یعنی هشت خانه اطراف آن را بررسی کرده و از بین آنها نزدیکترین سلول را به مقصد می یابیم). این تست تا زمانی ادامه می یابد که به مقصد برسیم.

البته دو نکته را نباید فراموش کنیم. مسئله اول اینکه در هنگام بررسی خانه های اطراف، نباید خانه های مانع را به حساب آوریم. این سلول ها می توانند دیوار، اشیاء داخل منزل، درخت، رودخانه و یا هر شیء دیگری باشند که شما در حین حرکت نباید درون آن وارد شوید. اما مسئله دوم هم اینکه نباید بیش از یک بار وارد هیچ سلولی شوید. یعنی در حالت کلی نباید هیچ خانه ای را بیش از یک بار در مسیر خود طی کنید. به این منظور می توانید کلیه خانه های مورد استفاده در مسیر را در یک آرایه ثبت کنید، سپس در هنگام انجام مراحل بعدی تست، آن خانه ها را مورد بررسی قرار ندهید.

در حقیقت این تئوری پشت پرده الگوریتم *A است که پیاده سازی آن به اشکال گوناگونی، امکان پذیر است. در تصویر ۳ شما می توانید فرآیند تست سلول های اطراف خانه سبز را مشاهده کنید.

ضمن اینکه در گوشه هر خانه، فاصله آن خانه تا سلول مقصد، مشخص شده است. شکل ۴ نیز کلیه تست های انجام گرفته برای حرکت از مبداء به مقصد را نشان می دهد. به این ترتیب شما می توانید هوشمندانه مسیر خود را در بین انبوهی از اشیاء و در محیط های ناشناخته نیز بیابید. البته کار در همین جا تمام نمی شود! کما اینکه پیاده سازی این الگوریتم بر حسب شرایط مختلف می تواند بسیار متفاوت باشد.

۱-۲ برخی از نکات مهم در هنگام پیاده سازی الگوریتم A-STAR :

۱-۲-۱)) یافتن فاصله بین سلول ها :

یافتن فاصله بین سلول ها در این الگوریتم اهمیت زیادی دارد، اما منظور از فاصله چیست؟ آیا می توان از فرمول فیثاغورث به این منظور استفاده کرد؟ یا باید تعداد مجموع خانه های عمودی و افقی موجود در مسیر را به عنوان فاصله محسوب نمود؟ این مسئله ای است که بر حسب نوع محیط و مسیر می تواند متفاوت باشد.

۱-۲-۲)) شی مورد نظر در نقطه ها

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

۱-۲-۳ ))تکنیکهای کاهش هزینه محاسباتی

این الگوریتم از نظر محاسباتی می تواند زمان بر باشد. پس درصورت امکان از تکنیک های دیگری نیز به صورت ترکیبی برای کاهش هزینه محاسباتی استفاده کنید (مثلاًَ می توانید برخی مسیرهای پیچیده و طولانی را با کدنویسی به صورت توکار در برنامه قرار دهید، به گونه ای که حرکت بر روی یک سری نقاط از پیش مشخص شده انجام گیرد و احتیاجی به انجام تست های الگوریتم *A نباشد).

۱-۲-۴ )) نقاط شکست

اگرچه این الگوریتم، کوتاهترین مسیر را به شما می دهد، اما این مسیر دارای نقاط شکست بسیاری می باشد. یعنی اگر بدون انجام بهینه سازی و برخی تغییرات محاسباتی، آن را بر روی کاراکترهای خود اعمال کنید، خواهید دید که در هنگام چرخش، حرکاتی بسیار ناگهانی خواهند داشت، علاوه بر این، برخی اوقات مسیرهای به دست آمده چندان بهینه نمی باشند. در نتیجه باید آنها را مورد بهینه سازی قرار دهید (فرآیندی که اغلب ازپیاده سازی اولیه الگوریتم، دشوارتر است).

۱-۲-۵)) راه حل های رفع مشکل چرخش ناگهانی

یکی از راه حل های رفع مشکل چرخش ناگهانی، ذخیره کلیه نقاط حرکتی و حذف نقاطی است که زاویه تندی می سازند. در نهایت شما می توانید مسیر اصلاح شده را مورد استفاده قرار دهید. به این منظور می توانید از لیست های پیوندی یا حتی آرایه های ساده استفاده کنید. بی شک پیاده سازی زیبای حرکت یک کاراکتر، فرآیندی دشوار می باشد که انواع محاسبات مثلثاتی، ماتریسی و برداری را در بر می گیرد.

۱-۲-۶)) هزینه دهی (Costing)

ما در این تست، هیچ تمایزی بین خانه های مختلف قائل نشدیم، یعنی احتمال انتخاب هر یک از خانه ها (البته نزدیکترین خانه ها به مقصد)، مساوی می باشد.

اما بیشتر اوقات شما باید بین خانه های مختلف، فرق قائل شوید. این تمایز قائل شدن بین خانه ها که در اصطلاح برنامه نویسی، به هزینه دهی (Costing) معروف است، یکی از پیچیده ترین بخش های این الگوریتم است. مثلاً می توانید هزینه های ورود به خانه های مورب و مستقیم را نامساوی در نظر بگیرید.

۱-۲-۷ )) نقاط قابل حرکت و نقاط غیرقابل حرکت

همچنین شما می توانید با تهیه یک نقشه از محیط مورد نظر خود از دید بالا، نقاط قابل حرکت و نقاط غیرقابل حرکت را به الگوریتم ارائه کنید. به این منظور می توانید از فرمت فایل RAW (که در فوتوشاپ قابل ساخت است) استفاده کنید. این فرمت هیچ داده ای به عنوان سرباره (header) ندارد و شما می توانید با تهیه یک فایل سیاه و سفید از محیط مورد نظر خود (یعنی رندر صحنه به صورت Plan با رنگ های سیاه و سفید.مثلاً رنگ های سیاه مشخص کننده موانع و نقاط غیرقابل ورود، و مناطق سفید مناطق قابل حرکت باشد. حتی می توانید هزینه ورود به نقاط مختلف نقشه را با رنگ های خاصی مشخص کنید)، به راحتی داده های محدوده جستجوی مورد نظر خود را برنامه بدهید.

۱-۲-۸ )) فرآیند محاسبه نزدیکترین مسیر

یکی از مهمترین بخش های این الگوریتم، فرآیند محاسبه نزدیکترین مسیر می باشد. به این منظور راهکارهای گوناگونی از جمله روش منهتن، روش نیوتن، روش فیثاغورث و نیز روش جستجوی عمقی (Heuristic) وجود دارد، ضمن اینکه در بسیاری از بازی ها، برنامه نویسان روش های اختصاصی را برای محیط های مورد نظر ایجاد کرده اند.

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

۱-۳ حرکت بین دو نقطه با الگوریتم مسیریابی *A:

یکی از مشکلات الگوریتم دیکسترا این بود که برای یافتن کوتاه ترین مسیر تمامی رئوس در تمامی جهات را بررسی کرده و پس از طی این روند طولانی به راس مقصد می رسید . برای حل این مشکل الگوریتم A* ارایه شد.

برای آشنایی با روند این الگوریتم به مثال زیر توجه کنید:

فرض کنید شخصی از نقطه ی A می خواهد به نقطه ی B برود و مانعی بین این دو نقطه قرار گرفته است. در شکل ۲ این وضعیت نشان داده شده است، که خانه ی سبز نقطه ی A ، خانه ی قرمز نقطه ی B و خانه های آبی نشان دهنده ی مانع می باشند.

.

دانلود مقاله کامل الگوریتم ای استار A Star و کاربرد آن در بازیهای رایانه ای

دانلود مقاله کامل الگوریتم ای استار A Star و کاربرد آن در بازیهای رایانه ای

.

فایل کامل این تحقیق ۷۳ صفحه بصورت ورد WORD می باشد.
در تمامی ساعات شبانه روز >> پرداخت آنلاین و دانلود آنلاین پروژه

 

توجه مهم :

*دوست عزیز در صورت نداشتن رمز پویا یا قطع بودن درگاه بانکی ، لطفا نام پروژه درخواستی خود را جهت هماهنگی برای دریافت شماره کارت واریزی و دریافت لینک دانلود، به واتساپ پشتیبانی سایت  ۰۹۳۹۲۷۶۱۶۳۰  ارسال کنید *(از ساعت ۸ الی ۲۳)

Related posts

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *