مسیریابی در بازی

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

در این بازی ما یکسری خط لوله داریم می خواهیم از ابتدای یک لوله به انتهای آن برسیم کد ما باید خط لوله هایی که به ان میدهیم را ارزیابی کرده از طریق مسیر های مجاز از ابتدا به انتها برسد که با استفاده از الگوریتم های جستجو این کار صورت میگیرد.

۱. مقدمه

این پروژه در واقع یک بازی است و مسیر در آن از یک سری خط لوله تشکیل شده است که آن را به صورت یک فایل در اختیار داریم و نقشه ی لوله ها در آن قرار دارد.
این پروژه یک بازی از سایت pygame به نشانی http://pygame.org/project-pipe-1567-.html میباشد و برای اجرای آن باید pygame بر روی سیستم ما نصب باشد.
هدف ما در این بازی رسیدن از ابتدا به انتهای مسیر از طریق مسیر های مجاز است. کد ما باید این مسیر های مجاز را ارزیابی کرده و با الگوریتم های search
و heuristic با حالت بهینه از ابتدا به انتها برسد.

ایده ی این بازی و الگوریتم هایی که از آن ها برای مسیریابی در آن استفاده میکنیم چه کاربرد هایی دارد و در کجا ممکن است استفاده شود؟
یکی از بزرگترین چالش ها در طراحی هوش مصنوعی بازی های کامپیوتری حرکت agent است و استراتژی های مسیریابی به عنوان مهمترین بخش هر
AI moving system میباشند.
این پروژه و ایده ی آن کاربرد الگوریتم های search و heuristic را به خوبی به نمایش میگذارد و بیان میدارد که میتوان از این الگوریتم ها که به خوبی حرکت agent را توصیف میکنند در طراحی مناسب حرکت agent برای بازی های کامپیوتری و feild های دیگر مثل حرکت robot ها استفاده کرد از نمونه های آن میتوان به موارد زیر اشاره کرد:

  • ربات هایی که به سیاره ها فرستاده میشوند تا آن سیاره را بررسی کنند که این ربات ها از توانایی های دیگری در زمینه ی هوش مصنوعی نیز برخوردارند و
    میتوانند آن سیاره را به خوبی بررسی کنند مثل mars pathfinder که یک ربات آمریکایی است که در سال 1997 به مریخ فرستاده شد و در سطح مریخ
    به جست و جو و بررسی پرداخت.

  • ربات های بازیکن فوتبال که در زمین های مخصوص فوتبال بازی میکنند و باید مسیر یابی و تشخیص مکان توپ در هر لحظه را انجام دهد مثل
    NAO soccer player که یک ربات اسکاتلندی است.

۲. کارهای مرتبط

برای حل این مساله از 6 الگوریتم search و heuristic استفاده میکنیم :

  • Breadth-first search

  • Depth-first search

  • Uniform cost search

  • Iterative deeping search

  • A* search

  • Manhatan heuristic search

تعریف navigation mesh:
مجموعه ای از چند ضلعی های محدب که مسیر قابل عبور یک محیط 3D را به تصویر میکشد. الگوریتم هایی برای تولید navigation mesh برای هر map
داده شده پیاده سازی شده اند. navigation mesh های تولید شده با این الگوریتم ها از چند ضلعی های محدبی تشکیل شده اند که وقتی به هم متصل شوند
شکل map را مشابه یک طرح طبقه ای در می آورند. چند ضلعی ها در یک mesh باید محدب باشند که این باعث میشود agent بتواند در یک مسیر مستقیم
از یک point روی یک چند ضلعی به point دیگر در مرکز چندضلعی مجاور جابجا شود. هر کدام از این چند ضلعی های محدب میتوانند به عنوان یک node برای الگوریتم های مسیریابی مورد استفاده قرار گیرند.
navigation mesh ها برای محیط های static مناسب میباشند.

تعریف waypoint:
مجموعه ای از node ها با لینک هایی بینشان . وقتی یک agent میخواد از A به B بره ابتدا به نزدیک ترین waypoint از A سپس از یک مسیر پیش محاسبه شده استفاده میکند و به نزدیکترین waypoint از مکان B میرود. معمولا طراح این waypoint ها را به صورت دستی در map قرار میدهد که این کار باعث میشود
تعداد node ها به کمترین حالت برسد و برای map های static مناسب میباشند.

سیستم های مسیریابی یک starting point و یک destination دارند برای رسیدن به destination یک سری از point ها را پیدا میکنند و در کنار هم قرار میدهند تا یک مسیر به destination حاصل شود.
سیستم های مسیریاب از ساختمان های داده از قبیل صف و استک برای راهیابی و یافتن مسیر استفاده میکنند.
فضا و هندسه ی بازی در یک ساختاری به نام map ذخیره میشود. map ها معمولا تمام چندضلعی هایی که فضای بازی را تشکیل میدهند را در برمیگیرد.
در خیلی از موارد برای محدود کردن فضای جست و جو map را به قسمت هایی شکسته و ساده سازی میکنند , پس از آن مسیریاب از مسیر ساده سازی
شده استفاده میکند تا از starting point به destination برسد.
مسیریاب یک مسیر در virtual world برای خود تعیین میکند تا بتواند محدودیت هایی که برایش قرار داده شده را حل کند یک مثال خوب از این محدودیت ها میتواند یافتن کوتاه ترین مسیر برای انتقال یک agent از current position به target position باشد.
مسیریابی میتواند به دو بخش عمده تقسیم شود:

  • مسیریابی Directed:
    این نوع مسیریاب ها کورکورانه وارد محیط نمیشوند به عبارت دیگر همه ی آن ها متود هایی برای ارزیابی پیشرویشان نسبت به همه ی node های مجاور قبل از
    انتخاب یکی از آن ها دارند. استراتژی ها برای الگوریتم های مسریابی dircted عبارتند از:
    1- Uniform cost search- g:
    جست و جو را جوری تنظیم میکند که کوتاه ترین مسیر را نسبت به node بعدی انتخاب کند.
    2- Heuristic search- h:
    هزینه را از node بعدی تا goal را تخمین میزند.

  • مسیریابی Undirected:
    این نوع مسیریاب ها کورکورانه وارد محیط میشوند و برای یافتن مسیر تلاش میکنند. استراتژی ها برای الگوریتم های مسیریابی Undirected عبارتند از:
    1- Breadth-first search:
    محیط را به چشم یک گراف بزرگ از node های به هم پیوسته میبیند و همه ی node های متصل به node فعلی را گسترش میدهد و این فرایند را همینطور ادامه میدهد بنابراین اگر مسیری وجود داشته باشد آن را می یابد.
    2- Depth-first search:
    به بچه های هر node نگاه میکند قبل از این که به ادامه ی node ها نگاه کن و یک مسیر خطی به goal می یابد.

۳. آزمایش ها

آدرس کد پروژه روی git : https://github.com/pouria7575/AI_project.git

1-Breadth-first search

مثالی از یک بار اجرا کردن

2-Depth-first search

مثالی از یک بار اجرا کردن

3-Uniform-cost search

مثالی از یک بار اجرا کردن

4-Iterative Deepening search

مثالی از یک بار اجرا کردن

5-A* search

مثالی از یک بار اجرا کردن

6-Manhatan Heuristic search (g)

مثالی از یک بار اجرا کردن

پس از انجام آزمایش با الگوریتم های متفاوت به این نتیجه رسیدیم که الگوریتم A* کارا ترین الگوریتم میباشد.

۴. کارهای آینده

۵. مراجع

برخی از مراجع و پیوند های مفید استفاده شده:

محمد غضنفری

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

تایید شده

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

تایید شده

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

تایید شده

به طور کلی پروژه زبان ساده ای داشته و استفاده از جدول های زیاد فهم مطلب را اسان کرده است ولی بخش بهبود نتایج و همچنین کارهای آینده توضیحی داده نشده اند.

تایید شده

سلام
کار های مشابه و الگوریتم‌هارو بسیار خوب توضیح داده بودین. در قسمت نتایج بهتر بود که تمامی الگوریتم‌ها را کنار هم و در یک نمودار می‌گذاشتین که خواندن از آن راحت‌تر می‌شد. برای معیار «کارا ترین الگوریتم» هم ای‌کاش دقیق‌تر توضیح می‌اوردین که مثلا این کارایی از نظر زمانی است یا از نظر حافظه‌ای یا هر دو.